Monday 24 August 2026

Write $X_n$ for the bankroll after $n$ rounds, $X_0=a=20$, boundaries $0$ and $N=50$. The increments are i.i.d. mean-zero, so $X_n$ is a martingale, and $T$ (first exit from $\{1,\dots ,N-1\}$) is an a.s. finite stopping time with $𝔼[T]<\infty$, so optional stopping applies at $T$.

Part 1: hitting probability

Optional stopping on the martingale $X_n$:

$$a=𝔼[X_0]=𝔼[X_T]=0·(1-p)+N·p,p:=\mathbb{P}(A).$$

Hence $p=a/N=20/50=\frac{2}{5}$.

Part 2: unconditional duration

Use the compensated martingale $M_n=X_n^2-n$ (mean-zero unit-variance increments). Optional stopping:

$$a^2=𝔼[X_T^2]-𝔼[T].$$

Since $X_T\in \{0,N\}$, $𝔼[X_T^2]=N^{2}p=N^2·\frac{a}{N}=Na$. Therefore

$$𝔼[T]=Na-a^2=a(N-a)=20·30=600.$$

Part 3: duration conditioned on winning

The step a candidate misses: you cannot recurse directly on the conditional expectation $m_a={𝔼}_a[T\mid A]$, because conditioning on $A$ retilts the step probabilities away from $\frac{1}{2},\frac{1}{2}$ (the walk is no longer symmetric once you condition on its endpoint). The clean fix is to work with the unnormalized quantity

$$g_a:={𝔼}_a\left[T{\mathbf{1}}_A\right],$$

which obeys an ordinary first-step recursion under the true (symmetric) dynamics, and only divide by $p_a=a/N$ at the very end.

First-step analysis. From $a$, after one round we are at $a\pm 1$ and $T$ increases by $1$:

$$g_a=\frac{1}{2}{𝔼}_{a+1}[(1+T^{\prime }){\mathbf{1}}_A]+\frac{1}{2}{𝔼}_{a-1}[(1+T^{\prime }){\mathbf{1}}_A].$$

$$g_a=\frac{1}{2}(g_{a+1}+g_{a-1})+\frac{1}{2}(p_{a+1}+p_{a-1}).$$

Because $p_a=a/N$ is linear, $p_{a+1}+p_{a-1}=2p_a=2a/N$, so the source term is $a/N$ and the recursion becomes the discrete Poisson equation

$$g_{a+1}-2g_a+g_{a-1}=-\frac{2a}{N},$$

with boundary data $g_0=0$ and $g_N=0$ (at $N$, $A$ occurs but $T=0$; at $0$, ${\mathbf{1}}_A=0$).

A cubic kills the right side: since $(a+1{)}^3-2a^3+(a-1{)}^3=6a$, take particular solution $-a^3/(3N)$, then add the linear homogeneous solution $\alpha +\beta a$. Boundaries give $\alpha =0$, $\beta =N/3$:

$$g_a=\frac{a(N^2-a^2)}{3N}.$$

Divide by $p_a=a/N$:

$$𝔼[T\mid A]=\frac{g_a}{p_a}=\frac{N^2-a^2}{3}.$$

With $N=50,a=20$:

$$𝔼[T\mid A]=\frac{2500-400}{3}=\frac{2100}{3}=700.$$

Summary

Sanity check. By the reflection $a\mapsto N-a$, the duration conditioned on ruin is $(N^2-(N-a{)}^2)/3=(2Na-a^2)/3=1600/3$. Weighting by $p$ and $1-p$:

$$\frac{2}{5}·700+\frac{3}{5}·\frac{1600}{3}=280+320=600=𝔼[T].✓$$

Note. Conditional on winning, the expected number of rounds ($700$) exceeds the unconditional average ($600$): reaching the far boundary takes longer than a typical exit. The slicker route to Part 3 is Doob's $h$-transform — conditioning on $A$ turns the walk into a Markov chain with step probabilities $\mathbb{P}(a\to a+1)=\frac{a+1}{2a}$, $\mathbb{P}(a\to a-1)=\frac{a-1}{2a}$ (using $h_a=a/N$), and computing the expected time to hit $N$ in that chain reproduces $(N^2-a^2)/3$.

(a) The Sauer–Shelah/Massart bound

Restrict each $h$ to the sample: let $A=\{(h(x_1),\dots ,h(x_n)):h\in \mathcal{H}\}\subseteq \{0,1{\}}^n$. The supremum defining ${\widehat{R}}_n$ depends on $h$ only through its restriction, so $${\widehat{R}}_n(\mathscr{H})={𝔼}_{\sigma }{sup}_{a\in A}\frac{1}{n}\sum _{i=1}^n{\sigma }_i{a}_i.$$ Every $a\in A$ has entries in $\{0,1\}$, so $\Vert a{\Vert }_2\le \sqrt{n}$; take $R=\sqrt{n}$ in Massart's lemma. By Sauer–Shelah, $|A|={\Pi }_{\mathcal{H}}(n)\le (en/d{)}^d$, hence $\log |A|\le d\log (en/d)$. Massart gives $${\widehat{R}}_n(\mathscr{H})\le \frac{\sqrt{n}\sqrt{2\log |A|}}{n}=\sqrt{\frac{2\log |A|}{n}}\le \sqrt{\frac{2d\log (en/d)}{n}}.$$ Since $\log (en/d)=1+\log (n/d)$, this carries an extra factor $\sqrt{1+\log (n/d)}$ over the target rate — the logarithm we now remove.

(b) Chaining removes the logarithm

The loss in (a) comes from bounding the whole class at the single scale $ϵ=1$ (a global cardinality bound). Dudley's integral instead pays for the class at every resolution, and the metric entropy of a VC class grows only like $d\log (1/ϵ)$, whose square root is integrable near $0$.

Converting Haussler to $L_2$. For $\{0,1\}$-valued $h,h^{\prime }$ one has $(h(x_i)-h^{\prime }(x_i){)}^2=|h(x_i)-h^{\prime }(x_i)|$, so $$\Vert h-h^{\prime }{\Vert }_{L_2(P_n)}^2=\Vert h-h^{\prime }{\Vert }_{L_1(P_n)}.$$ Thus an $L_1(P_n)$-cover at radius $\tau ={ϵ}^2$ is an $L_2(P_n)$-cover at radius $ϵ$. Applying Haussler with $Q=P_n$ and $\tau ={ϵ}^2$, $$N(ϵ,\mathscr{H},L_2(P_n))\le e(d+1)(\frac{2e}{{ϵ}^2}{)}^d,0<ϵ\le 1.$$ Taking logs, $$\log N(ϵ)\le 1+\log (d+1)+d\log (2e)+2d\log (1/ϵ)\le d(C_1+2\log (1/ϵ)),$$ where $C_1:=\frac{1+\log (d+1)}{d}+\log (2e)$ is bounded by the absolute constant $1+\log 2+\log (2e)$ for all $d\ge 1$ (using $\log (d+1)\le d\log 2$).

The integral. For $ϵ>1$ the diameter of $\mathcal{H}$ in $L_2(P_n)$ is at most $1$, so $N(ϵ)=1$ and the integrand vanishes. Hence the Dudley integral runs only over $(0,1]$: $${\int }_0^1\sqrt{\log N(ϵ)}dϵ\le \sqrt{d}{\int }_0^1\sqrt{C_1+2\log (1/ϵ)}dϵ.$$ Using $\sqrt{a+b}\le \sqrt{a}+\sqrt{b}$ and the exact value ${\int }_0^1\sqrt{\log (1/ϵ)}dϵ={\int }_0^{\infty }\sqrt{u}{e}^{-u}du=\Gamma (3/2)=\frac{\sqrt{\pi }}{2}$, $${\int }_0^1\sqrt{C_1+2\log (1/ϵ)}dϵ\le \sqrt{C_1}+\sqrt{2}·\frac{\sqrt{\pi }}{2}=:C_2,$$ a finite absolute constant. This convergence at $ϵ\to 0$ is exactly the step (a) could not exploit. Therefore $${\widehat{R}}_n(\mathscr{H})\le \frac{12}{\sqrt{n}}{C}_2\sqrt{d}=C\sqrt{\frac{d}{n}},C=12C_2.$$

(c) Matching lower bound

Let $z_1,\dots ,z_d\in \mathcal{X}$ be distinct and set $\mathcal{H}=\{h:h{|}_{\{z_1,\dots ,z_d\}}\text{ arbitrary},h\equiv 0\text{ elsewhere}\}$, i.e. all $2^d$ patterns on the $z_j$. This class shatters $\{z_1,\dots ,z_d\}$ and shatters no set of size $d+1$, so its VC dimension is exactly $d$.

Choice of sample — the key move. Do not take $n=d$ (which gives a constant) and do not pad with a fixed point (which gives $d/n$). Instead spread the shattered points evenly: with $m=n/d$, let each $z_j$ appear exactly $m$ times among $x_1,\dots ,x_n$.

For a sign vector $\sigma$, group the indices by their point and write $T_j={\sum }_{i:x_i=z_j}{\sigma }_i$, a sum of $m$ independent Rademacher signs. Since $h(z_j)\in \{0,1\}$ can be chosen independently for each $j$, $${sup}_{h\in \mathcal{H}}\sum _{i=1}^n{\sigma }_{i}h(x_i)=\sum _{j=1}^d{sup}_{h(z_j)\in \{0,1\}}h(z_j)T_j=\sum _{j=1}^d(T_j{)}_{+}.$$ By symmetry of $T_j$, $𝔼(T_j{)}_{+}=\frac{1}{2}𝔼|T_j|$. Lower-bound $𝔼|T_j|$ by interpolation: $\Vert T{\Vert }_2\le \Vert T{\Vert }_1^{1/3}\Vert T{\Vert }_4^{2/3}$ (Hölder with exponents matching $\frac{1}{2}=\frac{1}{3}·1+\frac{2}{3}·\frac{1}{4}$), so $$𝔼|T_j|=\Vert T_j{\Vert }_1\ge \frac{\Vert T_j{\Vert }_2^3}{\Vert T_j{\Vert }_4^2}=\frac{m^{3/2}}{\sqrt{𝔼T_j^4}}.$$ For a Rademacher sum, $𝔼T_j^2=m$ and $𝔼T_j^4=3m^2-2m\le 3m^2$, hence $𝔼|T_j|\ge m^{3/2}/(\sqrt{3}m)=\sqrt{m/3}$. Therefore $${𝔼}_{\sigma }{sup}_h\sum _{i=1}^n{\sigma }_{i}h(x_i)=\sum _{j=1}^d\frac{1}{2}𝔼|T_j|\ge \frac{d}{2}\sqrt{\frac{m}{3}}.$$ Dividing by $n=md$ and using $m=n/d$, $${\widehat{R}}_n(\mathcal{H})\ge \frac{1}{n}·\frac{d}{2}\sqrt{\frac{m}{3}}=\frac{1}{2\sqrt{3}}·\frac{d\sqrt{m}}{md}=\frac{1}{2\sqrt{3}}·\frac{1}{\sqrt{m}}=\frac{1}{2\sqrt{3}}\sqrt{\frac{d}{n}}.$$

Conclusion

For every VC class of dimension $d$ and every sample of size $n\ge d$, $$c\sqrt{\frac{d}{n}}\le {sup}_{\mathcal{H},x_{1:n}}{\widehat{R}}_n(\mathcal{H})\le C\sqrt{\frac{d}{n}},c=\frac{1}{2\sqrt{3}},C=12(\sqrt{1+\log 2+\log (2e)}+\frac{\sqrt{2\pi }}{2}).$$ So ${\widehat{R}}_n(\mathcal{H})=\Theta (\sqrt{d/n})$, dimension-free in the ambient space and free of the extra logarithm.

Closing note. The tempting wrong conclusion is that the $\sqrt{\log (n/d)}$ factor in part (a) is intrinsic — it is an artifact of controlling the class at one scale. Chaining trades one global bound for a geometric sum of local ones, and ${\int }_0\sqrt{\log (1/ϵ)}dϵ<\infty$ is what makes the trade profitable. On the lower-bound side, the classic trap is to evaluate at $n=d$ (giving the constant $\frac{1}{2}$) or to pad with an inert point (giving $d/2n$, which is smaller than $\sqrt{d/n}$); replicating each shattered point $n/d$ times, so that each coordinate group contributes $𝔼(T_j{)}_{+}~\sqrt{m}$, is what produces the correct $\sqrt{dn}$ scaling.