Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 201 / 1

Work on a filtered probability space $(\Omega ,\mathcal{F},({\mathcal{F}}_n{)}_{n\ge 0},\mathbb{P})$. A submartingale is a real-valued stochastic process satisfying the following three conditions: $Y_n$ is ${\mathcal{F}}_n$-measurable, $\mathbb{E}|Y_n|<\infty$, andThus it is adapted, has integrable random variables at every time, and its conditional expected next value is at least its current value. Repeated conditioning gives $\mathbb{E}[Y_m\mid {\mathcal{F}}_n]\ge Y_n$ for every $m\ge n$. The inequality concerns conditional expectation; individual sample paths need not increase. If no filtration is specified, the definition can be applied to the natural filtration generated by the process.

The almost sure submartingale convergence theorem says that if a submartingale $(Y_n)$ satisfiesthen there is an integrable random variable $Y_{\infty }$ such thatIndeed the positive-part bound also bounds the negative parts, since $\mathbb{E}{Y}_n\ge \mathbb{E}{Y}_0$; the theorem gives a finite limit. In particular, the martingale convergence theorem applies to any martingale with ${\sup }_n\mathbb{E}|M_n|<\infty$.

For a nonnegative martingale, $\mathbb{E}{M}_n=\mathbb{E}{M}_0$ supplies this bound automatically. Its limit obeys $\mathbb{E}{M}_{\infty }\le \mathbb{E}{M}_0$ by the Fatou lemma. Almost sure convergence alone need not preserve the expectation or give convergence in L1. Uniform integrability is the additional condition that supplies convergence in L1 and the identity $M_n=\mathbb{E}[M_{\infty }\mid {\mathcal{F}}_n]$.

Take independent and identically distributed random variables ${\xi }_k$ with the Bernoulli distribution of parameter $1/2$, and their natural filtration. SetThe event at $n=0$ is the whole sample space. Independence givesso this is a nonnegative martingale; it is integrable with $\mathbb{E}{M}_n=1$. The first zero among the ${\xi }_k$ is almost surely finite, since the probability of having only ones through time $n$ is $2^{-n}\to 0$. After that first zero, every $M_n$ is zero. Hence the almost sure limit is zero:This fair-coin doubling martingale also exhibits failure of uniform integrability: convergence in L1 would force the expectations to converge to zero.

Let $({\mathcal{F}}_n)$ be the natural filtration of the random walk on a graph. For a bounded harmonic function on a graph, the transition rule and the Markov property giveThus $h(X_n)$ is a bounded martingale. The martingale convergence theorem gives a finite almost sure limit $L$.

On the probability-one recurrence event, every vertex $v$ is visited along a sequence $n_k\to \infty$. Along that sequence $h(X_{n_k})=h(v)$, while convergence of the whole sequence forces $h(v)=L$. Therefore every pair of vertices has the same value. This is the bounded harmonic function theorem on a recurrent graph:Recurrence makes each vertex value a subsequential limit of the same convergent martingale. A connected locally finite graph is countable, since it is the union of its finite distance balls, so these almost sure assertions can also be combined by a countable intersection. The one-vertex case is immediate.

Write $D_k=M_k-M_{k-1}$ for the martingale difference sequence. Bounded increments mean that one deterministic $C<\infty$ satisfies $|D_k|\le C$ for every $k$, almost surely. Then $\mathbb{E}{D}_k=0$ and, for $j<k$,The increments are uncorrelated random variables, uniformly bounded in $L^2$. Applying the supplied strong law for uniformly L2-bounded uncorrelated random variables gives $n^{-1}{\sum }_{k=1}^n{D}_k\to 0$ almost surely. Also $M_0/n\to 0$, because $M_0$ is finite almost surely. Therefore a martingale with bounded increments has zero linear growth:This is the strong law for martingales with bounded increments.

For the submartingale, let $\Delta Y_k=Y_k-Y_{k-1}$ and define its predictable drift and compensator byThis is the Doob decomposition in discrete time. The process $N_n$ is a martingale. Since $|\Delta Y_k|\le C$, we have $0\le a_k\le C$, so $|N_k-N_{k-1}|\le 2C$. The result just proved gives $N_n/n\to 0$ almost surely, and $A_n\ge 0$. Consequently the strong law for submartingales with bounded increments isThe compensator may grow, so the conclusion is a lower bound rather than a claim of convergence to zero.