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

Assume $0<p<1$, so the ratio defining $Z_n$ is meaningful. Extend the random walk by $S_0=0$, the filtration by a trivial ${\mathcal{F}}_0$, and the process by $Z_0=1$. Write $r=q/p$. Each $Z_n=r^{S_n}$ is ${\mathcal{F}}_n$-measurable and integrable, since $|S_n|\le n$. The next increment is independent of ${\mathcal{F}}_n$, soTherefore $\boxed{(Z_n{)}_{n\ge 0}\text{ is a nonnegative martingale},\mathbb{E}{Z}_n=1}$. This is the exponential martingale of a biased simple random walk, with exponent $\log (q/p)$. At $p=q=1/2$, it is the constant process one. The endpoint cases $p=0$ or $p=1$ require separate definitions and are not covered by the printed ratio.

The Doob maximal inequality for a nonnegative submartingale states that, for a nonnegative submartingale $(M_j{)}_{0\le j\le N}$ and $u>0$,For completeness, partition the crossing event according to its first crossing time $j$. On that event $M_j\ge u$, while $\mathbb{E}[M_N\mid {\mathcal{F}}_j]\ge M_j$. Summing the corresponding expectations over $j$ proves $u\mathbb{P}(\max M_j\ge u)\le \mathbb{E}[M_N{1}_{\{\max M_j\ge u\}}]\le \mathbb{E}{M}_N$.

If $q>p$, the exponential $r^{S_j}$, with $r=q/p>1$, is increasing as a function of $S_j$. Apply the inequality to the martingale from part (a), with $u=r^k$:Letting $N\to \infty$ and using continuity of probability measures on increasing events givesThe same event is obtained if the supremum excludes time zero, since $k\ge 1$. If $p\ge q$, the right side is at least one and the bound is automatic; the nontrivial Doob maximal inequality argument is for $q>p$.

For $q>p$, let $M={\sup }_{n\ge 0}{S}_n$, including $S_0=0$. It is a nonnegative integer-valued random variable, possibly infinite before the following estimate. The tail-sum formula for expectation and part (i) giveThus $\boxed{\mathbb{E}\underset{n\ge 0}{\sup }{S}_n\le p/(q-p)}$, and the supremum is finite almost surely. The sum identity follows by writing $M={\sum }_{k\ge 1}{1}_{\{M\ge k\}}$ and applying monotone convergence theorem. If the printed supremum is read literally over $n\ge 1$, its positive part has exactly the same positive-level tails and its negative part is bounded by one. The same upper bound on its expected value remains valid.

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.