Friday 14 August 2026

1. Backward induction

Work backwards from the last roll, which is the only place where the answer is obvious.

With one roll available you must take it, so

$$V_1=𝔼[D]=3.5.$$

With two available, you see a value $d$ and then choose between $d$ and a fresh $V_1=3.5$, so you stop exactly when $d\ge 4$:

$$V_2=𝔼[max(D,3.5)]=\frac{3.5+3.5+3.5+4+5+6}{6}=\frac{25.5}{6}=4.25.$$

With three available you compare $d$ against $V_2=4.25$, so you stop exactly when $d\ge 5$:

$$V_3=𝔼[max(D,4.25)]=\frac{4.25·4+5+6}{6}=\frac{28}{6}=\frac{14}{3}.$$

Answer. On the first roll keep only 5 or 6; on the second keep 4, 5 or 6; take whatever the third gives. The expected payoff is $14/3\approx 4.667$.

The thing to notice is that the threshold depends only on how many rolls remain, never on what you have already seen — the rolls are independent, so a forfeited value carries no information.

2. The recursion and its limit

$$V_{k+1}=𝔼[max(D,V_k)]=\frac{1}{6}\sum _{d=1}^{6}max(d,V_k)$$

The map $v\mapsto 𝔼[max(D,v)]$ is nondecreasing and satisfies $𝔼[max(D,v)]>v$ for every $v<6$, so $V_k$ increases strictly, and it is bounded above by 6. Its limit $v^{\star }$ is a fixed point with $v^{\star }\le 6$, and the only fixed point of $v=𝔼[max(D,v)]$ in $[1,6]$ is $v=6$: for $v<6$ the roll $d=6$ contributes $6>v$ with probability $1/6$ while every other term is at least $v$, making the right side strictly larger. Hence

$${lim}_{k\to \infty }{V}_k=6.$$

Concretely $V_4=4.94$, $V_5\approx 5.12$: the approach is slow, because gaining more requires waiting for a 6, and the probability of not having seen one decays like $(5/6{)}^k$.

1. The bound

Write $u=\frac{1}{n}{\sum }_i{\sigma }_i{x}_i$. The supremum over a Euclidean ball is a dual norm and is attained, by Cauchy-Schwarz with equality at $w=Bu/\Vert u\Vert$:

$${sup}_{\Vert w{\Vert }_2\le B}⟨w,u⟩=B\Vert u{\Vert }_2.$$

That step is an equality, which is worth noticing — no slack is introduced by the class geometry. Hence

$${\hat{\Re }}_n(\mathscr{H})=\frac{B}{n}{𝔼}_{\sigma }\backslash |\sum _{i=1}^n{\sigma }_i{x}_i{\backslash |}_2.$$

Now the two inequalities. First Jensen, since $\sqrt{·}$ is concave:

$$𝔼\backslash |\sum _i{\sigma }_i{x}_i{\backslash |}_2\le \sqrt{𝔼\backslash |{\sum }_i{\sigma }_i{x}_i{\backslash |}_2^2}.$$

The second moment collapses because the signs are independent and mean zero, so $𝔼[{\sigma }_i{\sigma }_j]={\delta }_{ij}$:

$$𝔼\backslash |\sum _i{\sigma }_i{x}_i{\backslash |}_2^2=\sum _{i,j}𝔼[{\sigma }_i{\sigma }_j]⟨x_i,x_j⟩=\sum _i\Vert x_i{\Vert }_2^2\le n{X}^2.$$

That last step is the second inequality, and it is the only place the radius bound is used. Combining,

$${\hat{\Re }}_n(\mathscr{H})\le \frac{B}{n}\sqrt{n{X}^2}=\frac{BX}{\sqrt{n}}.$$

2. The guarantee

Composing with an $L$-Lipschitz loss costs a factor $L$ by Talagrand's contraction lemma, and the standard symmetrization bound for losses in $[0,1]$ gives, with probability at least $1-\delta$, simultaneously for all $h\in \mathscr{H}$,

$$R(h)\le \hat{R}(h)+2L{\hat{\Re }}_n(\mathscr{H})+3\sqrt{\frac{\log (2/\delta )}{2n}}\le \hat{R}(h)+\frac{2LBX}{\sqrt{n}}+3\sqrt{\frac{\log (2/\delta )}{2n}}.$$

The constants depend on which version of the bound you quote — some texts state it with the population rather than empirical complexity, and then the deviation term shrinks — but the shape, $O(LBX/\sqrt{n})$ plus an $O(\sqrt{\log (1/\delta )/n})$ confidence term, is common to all of them.

3. What replaced the dimension

The product $BX$ has. The class is not indexed by how many coordinates $x$ has but by a scale: how long the weight vector is allowed to be and how large the inputs can be. This is the technical content behind margin-based explanations of why heavily overparameterized linear models can still generalize — control the norm and $d$ never enters.

The argument breaks at the very first step under an ${\ell }_1$ constraint. There the dual norm is ${\ell }_{\infty }$,

$${sup}_{\Vert w{\Vert }_1\le B}⟨w,u⟩=B\Vert u{\Vert }_{\infty },$$

and $𝔼\Vert u{\Vert }_{\infty }$ is not a second moment of a single vector, so the identity $𝔼\Vert {\sum }_i{\sigma }_i{x}_i{\Vert }^2={\sum }_i\Vert x_i{\Vert }^2$ no longer applies — a maximum over $d$ coordinates is not controlled by its own variance. The right tool is a maximal inequality for sub-Gaussian variables (Massart's lemma), which yields a bound of order $B{X}_{\infty }\sqrt{2\log (2d)/n}$ where $X_{\infty }$ bounds $\Vert x_i{\Vert }_{\infty }$. The dimension returns, but only logarithmically, which is exactly the tradeoff that makes ${\ell }_1$ attractive in the high-dimensional regime.