Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 101 / 3

A discrete-time martingale relative to a filtration $({\mathcal{F}}_n)$ is an adapted process $(M_n)$ with $\mathbb{E}|M_n|<\infty$ andIterating conditional expectation also gives $\mathbb{E}[M_m\mid {\mathcal{F}}_n]=M_n$ for $m\ge n$. It is bounded in $L^2$ when each $M_n$ is square integrable andThis is a uniform bound on the second moments, not a pathwise bound on all sample values.

The optional stopping theorem for bounded stopping times says that, if $\sigma \le \tau \le K$ for a deterministic finite $K$, thenHere ${\mathcal{F}}_{\sigma }$ is the stopping-time sigma-algebra. The second assertion follows by taking $\sigma =0$ and then expectations. An $L^2$ bound is not needed: integrability at the finitely many deterministic times suffices.

For a proof, both stopped values are integrable since $|M_{\tau }|,|M_{\sigma }|\le {\sum }_{j=0}^K|M_j|$. ExpandIf $A\in {\mathcal{F}}_{\sigma }$, then $A\cap \{\sigma \le k\}\in {\mathcal{F}}_k$ by the definition of the stopping-time sigma-algebra, and $\{\tau >k\}\in {\mathcal{F}}_k$ because $\tau$ is a stopping time. Thus the indicator of $A\cap \{\sigma \le k<\tau \}$ is ${\mathcal{F}}_k$-measurable. Multiplying the sum by $1_A$, taking expectations, and conditioning each summand on ${\mathcal{F}}_k$ gives zero, by the martingale increment property. Therefore $\mathbb{E}[1_A{M}_{\tau }]=\mathbb{E}[1_A{M}_{\sigma }]$ for every $A\in {\mathcal{F}}_{\sigma }$. Since $M_{\sigma }$ is ${\mathcal{F}}_{\sigma }$-measurable, this is exactly the claimed conditional expectation identity.

The global drift hypothesis as printed is impossible on a finite state space. Indeed, let $x_{\ast }$ minimize $f$. Every possible value of $f(X_{n+1})$ is at least $f(x_{\ast })$, socontradicting a decrease by $\delta >0$. Equivalently, its formal iteration would give ${\mathbb{E}}_{x}f(X_n)=f(x)-n\delta$, whereas $f$ is bounded on the finite state space. This is the constant nonzero drift is impossible on a finite Markov chain obstruction. Thus there is no genuine chain satisfying all the literal premises.

The meaningful intended version imposes the drift only on $S\setminus D$, and stops at $D$. In the natural filtration ${\mathcal{F}}_n=\sigma (X_0,\dots ,X_n)$, the Markov property then gives, on $\{T>n\}$,The correct stopped martingale isIt is adapted and integrable, since $f$ is bounded and $n\wedge T\le n$. Its increment equalswhose conditional expectation is zero. Taking expectations yieldsSince $T<\infty$ almost surely and $f(X_T)=0$, the bounded convergence theorem gives ${\mathbb{E}}_{x}f(X_{n\wedge T})\to 0$. The monotone convergence theorem gives ${\mathbb{E}}_x(n\wedge T)\uparrow {\mathbb{E}}_{x}T$, without presupposing its finiteness. Consequently the constant-drift hitting-time identity isFor $x\in D$, both sides are zero. Under the repaired hypothesis the unstopped $f(X_n)+n\delta$ need not be a martingale after hitting $D$; it is the displayed stopped martingale that proves the result.

The printed hitting-time formula is false for the stated transition probabilities. For example, take $N=2$ and $q=3/4$, put $p=1-q$, and write $m_i={\mathbb{E}}_{i}T$. A first step givesso $m_2=2/q=8/3$. The printed expression gives $3$, not $8/3$. This discrepancy is present in the original PDF, not just in its converted text. The quantifier mentioning every positive integer must also be restricted to positive starting states $1,\dots ,N$; states larger than $N$ are not in $S$.

Here is the exact solution for the chain as specified. Until $T$, only $\{1,\dots ,N\}$ is visited. From any such state, a sequence of downward steps reaches zero within $N$ steps with probability at least $q^N>0$; the forced step at $N$ only increases that probability. The Markov property therefore givesThus $T$ is finite almost surely and has finite expectation, without needing the supplied transience assumption. Set $m_0=0$. The first-step analysis givesPut $d=q-p=2q-1>0$, $r=p/q$, and $D_i=m_i-m_{i-1}$. The equations becomeBackward iteration, or substitution into this recursion, givesSumming from $1$ to $i$ gives the corrected hitting time of a downward-biased walk reflected at an upper barrier:and in particularThese values also supply the appropriate test function for part (b): $f(i)=m_i$, $f(0)=0$, and $Pf=f-1$ at every state before absorption. The finite-state stopped argument is applied on $\{0,\dots ,N\}$, with zero made absorbing.

For $N\ge 3$, the printed hint cannot produce constant drift by choosing its single constant $c$. With $f(i)=i$ for $i<N$ and $f(N)=N+c$, the expected downward drift is $d$ at ordinary interior states, $d-pc$ at $N-1$, and $1+c$ at $N$. Making the top drift $d$ requires $c=-2p$, but then the drift at $N-1$ is $d+2p^2$, not $d$. For $N=2$ there is no ordinary interior state; a different constant drift can be arranged, but still gives $2/q$ rather than the printed formula. This identifies precisely the missing correction at the neighboring state for the intended drift $d$; the geometric term in the correct test function repairs it throughout the interval.