Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 34 / 4

Put $S_0=0$ and take ${\mathcal{F}}_0$ to be the trivial sigma-algebra. Each $S_n$ is measurable with respect to the natural filtration ${\mathcal{F}}_n=\sigma (X_1,\dots ,X_n)$, andIndependence of $X_{n+1}$ from ${\mathcal{F}}_n$ makes its conditional expectation equal to its expected value, which is zero. HenceThe measurability, integrability and conditional expectation conditions are all verified, so $\boxed{(S_n)\text{ is a martingale for }({\mathcal{F}}_n).}$

Here $X_1\le 1$, so for every $\tau >0$,The Jensen inequality for the strictly convex exponential function givesIn fact the inequality is strict: $\mathbb{P}(X_1=1)>0$ and $\mathbb{E}{X}_1=0$ exclude a constant random variable. In particular, $\boxed{1\le M(\tau )<\infty }$ as required.

For $Z_n=e^{\tau S_n}/M(\tau {)}^n$, independence and identical distribution giveThus $Z_n$ is positive, integrable with mean one, and adapted to the natural filtration. Conditioning on the next increment givesConsequently $\boxed{(Z_n)\text{ is a martingale}.}$ This is the exponential martingale of a random walk.

The hitting time $T$ is a stopping time for the natural filtration, because $\{T\le n\}={\bigcup }_{k\le n}\{S_k=b\}$. The integer-valued increments are at most one. A path started at zero therefore cannot reach or exceed $b$ without first visiting $b$, soDefine $Y_n=b-S_{n\wedge T}$. It is nonnegative and integrable: $|S_{n\wedge T}|\le {\sum }_{j\le n}|X_j|$. Moreover,The indicator function is ${\mathcal{F}}_n$-measurable, and $X_{n+1}$ is independent of ${\mathcal{F}}_n$ with zero expected value. Taking conditional expectation therefore proves directly that $(Y_n)$ is a nonnegative martingale.

The general result used here is that a nonnegative discrete-time martingale has a finite almost-sure limit; this is the martingale convergence theorem, since $\mathbb{E}{Y}_n=\mathbb{E}{Y}_0=b$ bounds its L1 norm. On $\{T=\infty \}$ it follows that $S_n=b-Y_n$ converges finitely. A convergent sequence of integers is eventually constant, so $X_n=S_n-S_{n-1}$ would eventually be zero on this event.

However, the independent events $\{X_n=1\}$ all have the same strictly positive probability. The second Borel-Cantelli lemma says that they occur infinitely often almost surely. This contradicts eventual constancy on any positive-probability subset of $\{T=\infty \}$. ThusNotice that no lower bound on the negative increments was needed.

The stopped martingale $Z_{n\wedge T}$ is a martingale. For completeness, the bounded-time stopping rule follows directly fromwhose conditional expectation given ${\mathcal{F}}_n$ is zero. Integrability at each fixed $n$ follows by expressing the stopped value as a finite sum of the integrable $Z_j$ restricted to disjoint events. Therefore $\mathbb{E}{Z}_{n\wedge T}=\mathbb{E}{Z}_0=1$.

The crucial bound is deterministic. Since $S_{n\wedge T}\le b$ and $M(\tau )\ge 1$,A bounded family is uniformly integrable: for $K>e^{\tau b}$ all its quantities $\mathbb{E}[|Z_{n\wedge T}|1_{\{|Z_{n\wedge T}|>K\}}]$ vanish. Part (c) gives $T<\infty$ almost surely, and then $S_T=b$. HenceThe general result for passing to expectations is the dominated convergence theorem: almost-sure convergence under one integrable bound implies convergence in L1 and convergence of expectations. Applying it with the bound $e^{\tau b}$ givesThis is the exponential first-passage transform for an upward skip-free random walk; it avoids an unjustified use of optional stopping at an unbounded stopping time.

For the simple symmetric random walk, the moment-generating function isFor a given $\alpha >0$, choose the unique $\tau >0$ satisfying $\cosh \tau =e^{\alpha }$. The transform in part (d) becomes $\mathbb{E}{e}^{-\alpha T}=e^{-b\tau }$. To express this in terms of $\alpha$, put $r=e^{-\tau }\in (0,1)$. The equation $(r+r^{-1})/2=e^{\alpha }$ gives $r^2-2e^{\alpha }r+1=0$. Its smaller root is the one in $(0,1)$, soThe second expression follows by rationalizing the first root. As $\alpha \downarrow 0$ the transform tends to one, consistent with the almost-sure finiteness proved in part (c).