Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 28 / 1 / c

The increments have expected value $p-q<0$. The strong law of large numbers for independent and identically distributed random variables with finite absolute mean givesHence $S_n\to -\infty$. Since $q/p>1$,Its expected value nevertheless stays equal to one. Thus this martingale is not uniformly integrable, and it does not converge to zero in $L^1$. This distinction will be avoided in part (ii) by stopping at an upper level, which makes the stopped process bounded.

Let $r=q/p>1$ and $H_k$ be the first hitting time of level $k$. Nearest-neighbour steps imply $S_{H_k}=k$ whenever $H_k<\infty$: the walk cannot overshoot its first upward crossing. On this event the stopped martingale eventually has the constant value $r^k$. On $\{H_k=\infty \}$, it is $Z_n$ and tends to zero by part (i). ThereforeFor every $n$, $0\le Z_{n\wedge H_k}\le r^k$. Before the hit the walk is below $k$, and at the hit it equals $k$. The optional stopping theorem for the bounded stopping time $n\wedge H_k$ gives $\mathbb{E}{Z}_{n\wedge H_k}=\mathbb{E}{Z}_0=1$. The dominated convergence theorem now yields $1=r^k\mathbb{P}(H_k<\infty )$. ConsequentlyThe uniform bound on the stopped variables justifies the limit; applying optional stopping directly at the possibly infinite $H_k$ without this argument would not be valid.

Put $\rho =p/q\in (0,1)$ and $M={\sup }_{n\ge 0}{S}_n$. For $k\ge 1$, $\{M\ge k\}=\{H_k<\infty \}$, so part (ii) gives $\mathbb{P}(M\ge k)={\rho }^k$. Since $\mathbb{P}(M\ge 0)=1$, taking differences givesThis is the geometric distribution of parameter $1-p/q$ on the failures-before-first-success convention, with support $\{0,1,\dots \}$. Its expected value is $\rho /(1-\rho )=p/(q-p)$, so the bound in part (b)(ii) is attained. This proves the maximum of a downward-biased random walk formula.

The time-zero convention is necessary here. If $M_1={\sup }_{n\ge 1}{S}_n$, then the first step can be $-1$ and the walk may never return to zero. Using the same hitting probability calculation after that step gives $\mathbb{P}(M_1=-1)=q(1-\rho )=q-p>0$. Also $\mathbb{P}(M_1\ge 0)=p+q\rho =2p$, while its tails at positive $k$ remain ${\rho }^k$. Its masses are thereforeThus the printed geometric conclusion is correct for the standard maximum that includes $S_0=0$, and false for a supremum restricted to the positive times.