Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 33 / 1

Use the natural filtration ${\mathcal{F}}_n=\sigma (X_1,\dots ,X_n)$ of the simple symmetric random walk. The event $\{T_1\le n\}={\bigcup }_{k=0}^n\{S_k=1\}$ belongs to ${\mathcal{F}}_n$, so $T_1$ is a stopping time.

For a positive integer $m$, set ${\tau }_m=T_1\wedge T_{-m}$. This exit time from the finite interval is integrable: in each block of $m+1$ steps there is a probability at least $2^{-(m+1)}$ of all steps being positive, which forces exit if it has not already occurred. Consequently the survival probabilities have a geometric upper bound.

We use the bounded-time optional stopping theorem: if $M$ is a martingale and $\sigma$ a bounded stopping time, then $\mathbb{E}{M}_{\sigma }=\mathbb{E}{M}_0$. Apply it at ${\tau }_m\wedge n$ to $S_n$ and to the square-minus-time martingale of a simple symmetric random walk $S_n^2-n$. The stopped positions lie in $[-m,1]$, so dominated convergence and monotone convergence giveWriting $p_m=\mathbb{P}(T_1<T_{-m})$, the first equation becomes $p_m-m(1-p_m)=0$, hence $p_m=m/(m+1)$. The second gives $\mathbb{E}{\tau }_m=p_m+m^2(1-p_m)=m$. Since ${\tau }_m\le T_1$, its expectation satisfies $\mathbb{E}{T}_1\ge m$ for every $m$. ThereforeNevertheless $\mathbb{P}(T_1<\infty )\ge p_m\to 1$. Thus the infinite mean first passage of a simple symmetric random walk occurs despite almost sure finiteness; using unrestricted optional stopping directly at $T_1$ would be unjustified.

Define the stopped martingaleIt is nonnegative: before the first visit to $1$, the nearest-neighbour random walk is at most $0$, and afterwards the stopped position is $1$. Each $M_n$ is integrable, with $|M_n|\le n+1$. MoreoverThe indicator is ${\mathcal{F}}_n$-measurable and the increment has conditional mean zero, so $M_n$ is a martingale with $\mathbb{E}{M}_n=M_0=1$.

Part (a) shows $T_1<\infty$ almost surely, so every such path eventually has $M_n=0$. Thus $M_n\to 0$ almost surely. But $\mathbb{E}|M_n-0|=1$ for every $n$, so there is no convergence in L1. Any possible L1 convergence limit would agree with the almost sure limit. This is a nonnegative martingale with almost sure convergence but no convergence in L1, and hence it is not uniformly integrable.

Because each increment is $\pm 1$, the event at time $k$ defining $T$ is exactly $\{X_{k-1}=X_k=1\}$. Therefore, for $n\ge 2$,and for $n<2$ this event is empty. Thus $T$ is a stopping time for the natural filtration.

On the other hand, $\{U\le 0\}=\{T=2\}=\{X_1=X_2=1\}$. This event has probability $1/4$, whereas the initial sigma-algebra ${\mathcal{F}}_0$ is trivial, even after completion up to null sets. It therefore cannot belong to ${\mathcal{F}}_0$. Hence $U=T-2$ is not a stopping time. Subtracting a deterministic delay from a stopping time can require information from the future.

The time $T$ is the waiting time for two consecutive successes in independent fair trials. First note its integrability: if any one of the disjoint pairs $(X_1,X_2),\dots ,(X_{2k-1},X_{2k})$ is $++$, then $T\le 2k$. Thus $\mathbb{P}(T>2k)\le (3/4{)}^k$.

Let $e_0$ be the expected additional waiting time with no trailing positive step, and let $e_1$ be the expected additional time when the preceding step was positive. Conditioning on the next independent increment givesA negative step returns either state to state $0$; a positive step moves state $0$ to state $1$ and completes the pattern from state $1$. Substitution yields $e_0=2+e_1=3+e_0/2$, so $e_0=6$. The original process starts in state $0$, and thereforeOverlapping pairs are dependent, so regarding each successive pair as a fresh trial of success probability $1/4$ would give the wrong expectation.