A gambler bets on a fair coin. The first stake is \(1\) ; after every loss the stake is doubled; at the first win the gambler stops. If the first win comes at toss \(T\) , the losses so far amount to \(1+2+\dots+2^{T-2}=2^{T-1}-1\) and the winning stake is \(2^{T-1}\) , so the net gain is exactly \(1\) . The first win comes sooner or later with probability one. The gambler therefore ends with a gain of \(1\) , with certainty, in a game each of whose rounds is fair.

At every fixed time, though, nothing has been gained on average: after \(n\) tosses the gambler is ahead by \(1\) with probability \(1-2^{-n}\) and behind by \(2^n-1\) with probability \(2^{-n}\) , and the expectation of the fortune is \(0\) . The expected fortune at each time \(n\) is \(0\) , the fortune converges almost surely to \(1\) , and the expectation of the limit is not the limit of the expectations. After Chapter 5 the diagnosis can be guessed: the fortunes are not uniformly integrable.

This chapter is about processes that are fair in the sense that the gambler’s fortune is fair: the conditional expectation of the next value, given everything observed so far, is the present value. Such processes are called martingales. Three questions organize the chapter. What can and cannot be achieved by betting on a martingale and by stopping it at a cleverly chosen time? Why must a martingale that does not blow up converge? And for which martingales does the limit retain all the information, so that nothing is lost as it is for the doubling gambler? Stochastic Processes uses martingales as a modelling device for fair games (math.stochastic-processes.martingale-fair-game); here the theorems behind that use are proved.

7.1 Fairness relative to a filtration

The sigma-algebra \(\mathcal F_n\) is the information available at time \(n\) ; adaptedness says that the value \(X_n\) is known by then.

By the tower property the one-step condition propagates: for a martingale, \(\mathbb E[X_m\mid\mathcal F_n]=X_n\) whenever \(m\ge n\) , and in particular \(\mathbb E X_n=\mathbb E X_0\) for all \(n\) . A submartingale increases on average and a supermartingale decreases; the names are backwards from the gambler’s point of view, for whom a supermartingale is an unfavourable game. If \(X\) is a martingale and \(\varphi\) is convex with \(\varphi(X_n)\) integrable, the conditional Jensen inequality gives \(\mathbb E[\varphi(X_{n+1})\mid\mathcal F_n]\ge\varphi(X_n)\) , so \(\varphi(X_n)\) is a submartingale; thus \(\lvert X_n\rvert\) and, for square-integrable martingales, \(X_n^2\) are submartingales.

Four constructions produce most of the martingales in this book.

Sums. If \(\xi_1,\xi_2,\dots\) are independent and integrable with mean \(0\) , then \(S_n=\xi_1+\dots+\xi_n\) is a martingale for the natural filtration of the \(\xi_k\) , since \(\mathbb E[S_n+\xi_{n+1}\mid\mathcal F_n]=S_n+\mathbb E\xi_{n+1}\) by Theorem 6.4.

Products. If \(Y_1,Y_2,\dots\) are independent, nonnegative, with mean \(1\) , then \(M_n=Y_1\cdots Y_n\) is a martingale, since \(\mathbb E[M_nY_{n+1}\mid\mathcal F_n]=M_n\,\mathbb E Y_{n+1}\) .

Successive estimates. If \(X\) is integrable and \((\mathcal F_n)\) is any filtration, then \(X_n=\mathbb E[X\mid\mathcal F_n]\) is a martingale by the tower property. A martingale of this form is called closed.

Compensated functions of a walk. Example 6.5 showed that \(S_n^2-n\) is a martingale when the steps are \(\pm 1\) with equal probability.

7.2 Betting strategies and stopping times

A gambler who may vary the stakes plays a transformed game. The stake on round \(k\) must be chosen before round \(k\) is played.

If \(X_k-X_{k-1}\) is the gain per unit stake on round \(k\) , then \((H\cdot X)_n\) is the total gain after \(n\) rounds of a gambler who stakes \(H_k\) on round \(k\) .

The simplest strategy is to bet one unit until some moment and then stop. The moment may depend on what has happened, but not on what is yet to happen.

Equivalently \(\{\tau=n\}\in\mathcal F_n\) for every \(n\) . The first time an adapted sequence enters a Borel set \(B\) , \(\tau=\inf\{n:X_n\in B\}\) with \(\inf\emptyset=\infty\) , is a stopping time, because \(\{\tau\le n\}=\bigcup_{k\le n}\{X_k\in B\}\) . The last time the sequence visits \(B\) is in general not one: to know that a visit is the last, one must see the future.

So stopping cannot change the expectation at any fixed time. The whole question is what happens when the fixed time is removed.

7.3 Optional stopping

For the doubling gambler none of the four conditions holds: \(T\) is unbounded, the stopped fortunes are unbounded and not uniformly integrable, and although \(\mathbb E T=2\) is finite, the increments \(2^{k-1}\xi_k\) are unbounded. Each hypothesis guards against a different way for expectation to escape.

Example 7.3: Leaving an interval

Let \(S_n\) be the symmetric walk with steps \(\pm1\) , let \(a\) and \(b\) be positive integers, and let \(\tau=\inf\{n:S_n=-a\ \text{or}\ S_n=b\}\) .

The exit time is integrable. Any run of \(a+b\) consecutive up-steps carries the walk out of the interval \((-a,b)\) from wherever it is. Cutting time into blocks of length \(a+b\) , the blocks are independent and each consists of up-steps with probability \(2^{-(a+b)}\) , so \(\mathbb P(\tau>k(a+b))\le(1-2^{-(a+b)})^k\) . The tail of \(\tau\) is geometrically small; hence \(\tau<\infty\) almost surely and \(\mathbb E\tau<\infty\) .

The exit side. Up to time \(\tau\) the walk stays in \([-a,b]\) , so condition (b) of Theorem 7.7 holds for the martingale \(S_n\) , and \(\mathbb E S_\tau=0\) . With \(\pi=\mathbb P(S_\tau=b)\) this reads \(b\pi-a(1-\pi)=0\) , so

\[ \mathbb P(S_\tau=b)=\frac{a}{a+b},\qquad \mathbb P(S_\tau=-a)=\frac{b}{a+b}. \]

The expected exit time. For the martingale \(S_n^2-n\) , Theorem 7.6 gives \(\mathbb E S_{\tau\wedge n}^2=\mathbb E[\tau\wedge n]\) for every \(n\) . Let \(n\to\infty\) : the left side converges to \(\mathbb E S_\tau^2\) by bounded convergence, and the right side to \(\mathbb E\tau\) by monotone convergence. Hence

\[ \mathbb E\tau=\mathbb E S_\tau^2=b^2\cdot\frac{a}{a+b}+a^2\cdot\frac{b}{a+b}=ab . \]

For \(a=2\) and \(b=3\) : the walk exits at \(3\) with probability \(\tfrac25\) , and the expected exit time is \(6\) . For the barriers \(-6\) and \(10\) of Figure 7.1, the walk exits at the top with probability \(\tfrac38\) and takes \(60\) steps on average.

A stopping time for which optional stopping fails. Let \(T=\inf\{n:S_n=1\}\) . Since \(\{S_\tau=b\}\) with \(b=1\) is contained in \(\{T<\infty\}\) , we get \(\mathbb P(T<\infty)\ge a/(a+1)\) for every \(a\) , so \(T<\infty\) almost surely. Then \(S_T=1\) and \(\mathbb E S_T=1\ne 0=\mathbb E S_0\) . Consequently no condition of Theorem 7.7 can hold; since the increments are bounded, condition (c) shows that \(\mathbb E T=\infty\) . A fair walk reaches \(1\) with certainty, and the expected waiting time is infinite.

7.4 Two inequalities

The convergence theorem rests on an estimate for how often a martingale can cross an interval. A related estimate, for how large it can become, is proved first because the method is the same: decompose according to the first time something happens.

The first inequality of the corollary, applied to sums of independent mean-zero variables, is Kolmogorov’s inequality. It has the same right-hand side as Chebyshev’s inequality for the final value \(X_n\) alone, and bounds the maximum over the whole stretch \(k\le n\) . That is the kind of improvement Lemma 4.2 said almost sure convergence requires.

For the second estimate fix real numbers \(a<b\) and count the upcrossings of \([a,b]\) by the sequence: the number of times it passes from a value at most \(a\) to a later value at least \(b\) . Formally, let \(\sigma_1=\inf\{k\ge 0:X_k\le a\}\) , \(\tau_1=\inf\{k>\sigma_1:X_k\ge b\}\) , and inductively \(\sigma_{j+1}=\inf\{k>\tau_j:X_k\le a\}\) , \(\tau_{j+1}=\inf\{k>\sigma_{j+1}:X_k\ge b\}\) . These are stopping times, and \(U_n[a,b]=\max\{j:\tau_j\le n\}\) is the number of upcrossings completed by time \(n\) .

The proof is a betting argument: the strategy “buy low, sell high” would make money on every oscillation, and in an unfavourable or fair game no strategy makes money on average. So there cannot be many oscillations.

7.5 The convergence theorem

The theorem is the probabilistic counterpart of the fact that a bounded monotone sequence of real numbers converges: a supermartingale decreases on average, boundedness in \(L^1\) replaces boundedness, and the conclusion is convergence of the paths. It asserts almost sure convergence and nothing about convergence of expectations. The inequality \(\mathbb E X_\infty\le\mathbb E X_0\) in the corollary can be strict even for a martingale. The doubling gambler supplies one instance after a change of sign: with \(X_{T\wedge n}\) the stopped fortune of Example 7.2, the variables \(1-X_{T\wedge n}\) form a nonnegative martingale, equal to \(2^n\) with probability \(2^{-n}\) and to \(0\) otherwise, with mean \(1\) and almost sure limit \(0\) . The next example is another.

7.6 Uniformly integrable martingales

The difference between Examples 7.4 and 7.5 is uniform integrability, and the next theorem says that this is the whole story.

Lévy’s theorem is the statement that learning converges to the truth, as far as the truth is observable: successive estimates of \(X\) converge to the best estimate based on all the information that will ever arrive, and to \(X\) itself when \(X\) is \(\mathcal F_\infty\) -measurable. It answers the question left open in Example 6.2: for every integrable \(X\) on \([0,1)\) the dyadic averages \(\mathbb E[X\mid\mathcal G_n]\) converge to \(X\) almost everywhere and in \(L^1\) , because the dyadic intervals generate the Borel sigma-algebra. This is the Lebesgue differentiation theorem of Measure Theory along dyadic intervals (math.measure-theory.lebesgue-differentiation-theorem), obtained here by a probabilistic argument.

It also gives a second proof of Kolmogorov’s zero-one law. Let \(A\) be a tail event of an independent sequence \(\xi_1,\xi_2,\dots\) and \(\mathcal F_n=\sigma(\xi_1,\dots,\xi_n)\) . Since \(A\) is independent of \(\mathcal F_n\) , \(\mathbb P(A\mid\mathcal F_n)=\mathbb P(A)\) for every \(n\) . Since \(A\in\mathcal F_\infty\) , Theorem 7.14 gives \(\mathbb P(A\mid\mathcal F_n)\to\mathbf 1_A\) almost surely. So \(\mathbf 1_A=\mathbb P(A)\) almost surely, and an indicator that equals a constant is \(0\) or \(1\) .

Martingales bounded in \(L^2\) are the most convenient uniformly integrable ones, because their increments are orthogonal.

Exercises

1. Let \(S_n\) be the symmetric walk with steps \(\pm1\) . Prove that \(S_n^3-3nS_n\) is a martingale for the natural filtration, by computing the conditional expectation of its next value at a node where \(S_n=s\) .

   Solution

   Let \(X_n=S_n^3-3nS_n\) . It is \(\mathcal F_n\) -measurable and bounded for each \(n\) , hence integrable. By Proposition 6.7 the conditional expectation of \(X_{n+1}\) given \(\mathcal F_n\) is \(H(S_n)\) , where \(H(s)\) is the average of the two possible next values from a node with \(S_n=s\) :

   \[ H(s)=\tfrac12\bigl[(s+1)^3+(s-1)^3\bigr]-3(n+1)\cdot\tfrac12\bigl[(s+1)+(s-1)\bigr]. \]

   Expanding, \((s+1)^3+(s-1)^3=2s^3+6s\) , so the first term is \(s^3+3s\) ; the second is \(3(n+1)s=3ns+3s\) . Hence

   \[ H(s)=s^3+3s-3ns-3s=s^3-3ns , \]

   which is the value of \(X_n\) at the node. So \(\mathbb E[X_{n+1}\mid\mathcal F_n]=X_n\) . The correction term \(-3nS_n\) is exactly what cancels the drift \(3S_n\) that the cube picks up from \(\mathbb E\xi^2=1\) ; the same bookkeeping, one power lower, produced \(S_n^2-n\) in Example 6.5.

2. Let \(X\) be a martingale that is also predictable, that is, \(X_n\) is \(\mathcal F_{n-1}\) -measurable for all \(n\ge 1\) . Show that \(X_n=X_0\) almost surely for all \(n\) .

   Answer

   For \(n\ge 1\) , \(X_n\) is \(\mathcal F_{n-1}\) -measurable, so \(X_n=\mathbb E[X_n\mid\mathcal F_{n-1}]=X_{n-1}\) almost surely, by Theorem 6.4(d) and the martingale property. Induct on \(n\) .

3. Prove that if \(X\) is a martingale and \(\varphi\) is convex with \(\varphi(X_n)\) integrable then \(\varphi(X_n)\) is a submartingale, and that for a submartingale \(X\) the same conclusion holds provided \(\varphi\) is also nondecreasing. Give a submartingale \(X\) for which \(X^2\) is not a submartingale.

   Hint

   Use the conditional Jensen inequality; for a submartingale one additionally needs \(\varphi(\mathbb E[X_{n+1}\mid\mathcal F_n])\ge\varphi(X_n)\) , which is where monotonicity enters. Counterexample: the deterministic sequence \(X_n=-1/n\) increases, so it is a submartingale, while \(X_n^2=1/n^2\) decreases.

4. Let \(\sigma\) and \(\tau\) be stopping times. Show that \(\sigma\wedge\tau\) , \(\sigma\vee\tau\) , and \(\sigma+\tau\) are stopping times, and explain why \(\tau-1\) need not be one even when \(\tau\ge 1\) .

   Answer

   \(\{\sigma\wedge\tau\le n\}=\{\sigma\le n\}\cup\{\tau\le n\}\) , \(\{\sigma\vee\tau\le n\}=\{\sigma\le n\}\cap\{\tau\le n\}\) , and \(\{\sigma+\tau=n\}=\bigcup_{k\le n}\{\sigma=k\}\cap\{\tau=n-k\}\) , all in \(\mathcal F_n\) . But \(\{\tau-1\le n\}=\{\tau\le n+1\}\) belongs to \(\mathcal F_{n+1}\) and in general not to \(\mathcal F_n\) : stopping one step before the first head of a coin requires knowing the next toss.

5. Prove the Doob decomposition: every adapted integrable sequence \(X\) can be written uniquely as \(X_n=X_0+M_n+A_n\) with \(M\) a martingale, \(A\) predictable, and \(M_0=A_0=0\) . Find the decomposition of \(S_n^2\) for the symmetric walk.

   Solution

   Existence. Define \(A_0=0\) and

   \[ A_n=\sum_{k=1}^{n}\mathbb E[X_k-X_{k-1}\mid\mathcal F_{k-1}],\qquad M_n=X_n-X_0-A_n . \]

   Each summand of \(A_n\) is \(\mathcal F_{k-1}\) -measurable with \(k-1\le n-1\) , so \(A_n\) is \(\mathcal F_{n-1}\) -measurable: \(A\) is predictable. \(M\) is adapted and integrable, and

   \[ \mathbb E[M_{n+1}-M_n\mid\mathcal F_n]=\mathbb E[X_{n+1}-X_n\mid\mathcal F_n]-(A_{n+1}-A_n)=0, \]

   because \(A_{n+1}-A_n=\mathbb E[X_{n+1}-X_n\mid\mathcal F_n]\) by construction. So \(M\) is a martingale with \(M_0=0\) .

   Uniqueness. If \(X_n=X_0+M_n+A_n=X_0+M_n'+A_n'\) are two such decompositions, then \(M_n-M_n'=A_n'-A_n\) is a martingale that is predictable and vanishes at \(n=0\) . By Exercise 2 it is identically \(0\) .

   The walk. For \(X_n=S_n^2\) , Example 6.5 gives \(\mathbb E[S_k^2-S_{k-1}^2\mid\mathcal F_{k-1}]=1\) , so \(A_n=n\) and \(M_n=S_n^2-n\) . The predictable part records the accumulated conditional drift; \(X\) is a submartingale exactly when \(A\) is nondecreasing.

6. Prove Wald’s identity: if \(\xi_1,\xi_2,\dots\) are i.i.d. and integrable with mean \(\mu\) , and \(\tau\) is a stopping time for their natural filtration with \(\mathbb E\tau<\infty\) , then \(\mathbb E S_\tau=\mu\,\mathbb E\tau\) .

   Solution

   Write \(S_\tau=\sum_{k\ge 1}\xi_k\mathbf 1_{\{\tau\ge k\}}\) . The event \(\{\tau\ge k\}=\{\tau\le k-1\}^{c}\) belongs to \(\mathcal F_{k-1}=\sigma(\xi_1,\dots,\xi_{k-1})\) , which is independent of \(\xi_k\) . Hence, by Theorem 2.6,

   \[ \mathbb E\bigl[\lvert\xi_k\rvert\mathbf 1_{\{\tau\ge k\}}\bigr]=\mathbb E\lvert\xi_1\rvert\,\mathbb P(\tau\ge k),\qquad \mathbb E\bigl[\xi_k\mathbf 1_{\{\tau\ge k\}}\bigr]=\mu\,\mathbb P(\tau\ge k). \]

   Summing the first identity over \(k\) and using \(\sum_{k\ge 1}\mathbb P(\tau\ge k)=\mathbb E\tau\) (Exercise 1.9) gives \(\mathbb E\sum_k\lvert\xi_k\rvert\mathbf 1_{\{\tau\ge k\}}=\mathbb E\lvert\xi_1\rvert\,\mathbb E\tau<\infty\) . So the series defining \(S_\tau\) converges absolutely almost surely, \(S_\tau\) is integrable, and the Dominated Convergence Theorem, with the integrable dominating variable \(\sum_k\lvert\xi_k\rvert\mathbf 1_{\{\tau\ge k\}}\) , allows the expectation to be taken term by term:

   \[ \mathbb E S_\tau=\sum_{k\ge 1}\mu\,\mathbb P(\tau\ge k)=\mu\,\mathbb E\tau . \]

   Theorem 7.7(c) would give the same result for bounded steps; the argument here needs only integrable steps, because independence lets each term be computed exactly. The hypothesis \(\mathbb E\tau<\infty\) cannot be dropped: for the symmetric walk and \(T\) the hitting time of \(1\) , \(\mathbb E S_T=1\) and \(\mu=0\) .

7. For the biased walk of Example 7.1 with \(p=\tfrac23\) , let \(\tau\) be the first exit time from \((-2,3)\) . Use the martingales \(2^{-S_n}\) and \(S_n-\tfrac n3\) to find \(\mathbb P(S_\tau=3)\) and \(\mathbb E\tau\) .

   Solution

   The block argument of Example 7.3 applies unchanged: a run of five consecutive up-steps forces an exit, so \(\tau<\infty\) almost surely and \(\mathbb E\tau<\infty\) .

   Exit side. Up to time \(\tau\) the walk lies in \([-2,3]\) , so \(M_{\tau\wedge n}=2^{-S_{\tau\wedge n}}\in[\tfrac18,4]\) is bounded, and Theorem 7.7(b) gives \(\mathbb E\,2^{-S_\tau}=1\) . With \(\pi=\mathbb P(S_\tau=3)\) ,

   \[ \pi\cdot 2^{-3}+(1-\pi)\cdot 2^{2}=1\quad\Longrightarrow\quad 3=\pi\bigl(4-\tfrac18\bigr)\quad\Longrightarrow\quad\pi=\frac{24}{31}. \]

   Expected exit time. For the martingale \(S_n-\tfrac n3\) , Theorem 7.6 gives \(\mathbb E S_{\tau\wedge n}=\tfrac13\mathbb E[\tau\wedge n]\) . Let \(n\to\infty\) , using bounded convergence on the left and monotone convergence on the right: \(\mathbb E S_\tau=\tfrac13\mathbb E\tau\) . Now \(\mathbb E S_\tau=3\cdot\tfrac{24}{31}-2\cdot\tfrac{7}{31}=\tfrac{58}{31}\) , so

   \[ \mathbb E\tau=\frac{174}{31}\approx 5.61 . \]

   Compare the symmetric walk on the same interval, which exits at the top with probability \(\tfrac25\) and takes \(6\) steps on average: the bias nearly doubles the chance of exiting at the top and shortens the wait only slightly.

8. For the symmetric walk let \(T=\inf\{n:S_n=1\}\) . Prove that \(\mathbb P(T<\infty)=1\) and \(\mathbb E T=\infty\) , and for each of the four conditions of Theorem 7.7 say why it fails for \(T\) .

   Solution

   Finiteness. For a positive integer \(a\) let \(\tau_a\) be the exit time from \((-a,1)\) . By Example 7.3, \(\mathbb P(S_{\tau_a}=1)=a/(a+1)\) , and on that event \(T\le\tau_a<\infty\) . So \(\mathbb P(T<\infty)\ge a/(a+1)\) for every \(a\) , and letting \(a\to\infty\) gives \(\mathbb P(T<\infty)=1\) .

   Infinite mean. Since \(T<\infty\) almost surely, \(S_T=1\) and \(\mathbb E S_T=1\ne 0=\mathbb E S_0\) . The increments of the walk are bounded by \(1\) , so if \(\mathbb E T\) were finite, Theorem 7.7(c) would give \(\mathbb E S_T=0\) . Hence \(\mathbb E T=\infty\) .

   The four conditions. (a) \(T\) is not bounded: for each \(N\) the first \(N\) steps are all down with probability \(2^{-N}>0\) , and then \(T>N\) . (b) The stopped walk is not bounded: on that same event \(S_{T\wedge N}=-N\) . (c) The increments are bounded but \(\mathbb E T=\infty\) . (d) The stopped walk is not uniformly integrable, for otherwise the conclusion \(\mathbb E S_T=0\) would hold; concretely, \(\mathbb E S_{T\wedge n}=0\) and \(S_{T\wedge n}\to 1\) almost surely, so by Theorem 5.6 uniform integrability is impossible. The walk does reach \(1\) , but on the way it makes excursions to the negative side that are large enough, with enough probability, to balance the certain final gain at every finite time.

9. A student argues that the symmetric walk \(S_n\) is a martingale and therefore converges almost surely by the martingale convergence theorem. Identify the hypothesis that fails and say what the walk actually does.

   Answer

   The hypothesis \(\sup_n\mathbb E\lvert S_n\rvert<\infty\) fails. By Hölder’s inequality \(\mathbb E S_n^2\le(\mathbb E\lvert S_n\rvert)^{2/3}(\mathbb E S_n^4)^{1/3}\) , and \(\mathbb E S_n^2=n\) , \(\mathbb E S_n^4=3n^2-2n\le 3n^2\) , so \(\mathbb E\lvert S_n\rvert\ge\sqrt{n/3}\to\infty\) . The walk does not converge, since \(\lvert S_{n+1}-S_n\rvert=1\) always. In fact it visits every integer: by Example 7.3, for positive integers \(a\) and \(b\) the walk reaches \(b\) before \(-a\) with probability \(a/(a+b)\) , so it reaches \(b\) at some time with probability at least \(a/(a+b)\) for every \(a\) , hence with probability \(1\) ; no restart at a hitting time is needed. The same holds for \(-b\) by symmetry, and intersecting over \(b\) gives \(\limsup_nS_n=\infty\) and \(\liminf_nS_n=-\infty\) almost surely.

10. For the symmetric walk compute exactly \(\mathbb P(\max_{k\le 16}\lvert S_k\rvert\ge 8)\) and compare it with the bound of Corollary 7.9.

    Answer

    Counting paths that stay strictly inside \((-8,8)\) for \(16\) steps gives \(\mathbb P(\max_{k\le 16}\lvert S_k\rvert\ge 8)=\tfrac{1607}{16384}\approx 0.098\) . Corollary 7.9 gives the bound \(\mathbb E S_{16}^2/8^2=16/64=0.25\) .

11. For the numerical sequence \(0,2,-1,3,1,-2,4\) count the upcrossings of \([0,2]\) , list the values of the strategy \(H\) of Theorem 7.10, and verify the inequality \(Y_n\ge(b-a)U_n-(X_n-a)^{-}\) for \(n=6\) .

    Answer

    With \(a=0\) , \(b=2\) : \(\sigma_1=0\) , \(\tau_1=1\) , \(\sigma_2=2\) , \(\tau_2=3\) , \(\sigma_3=5\) , \(\tau_3=6\) , so \(U_6=3\) . The strategy is \(H_1,\dots,H_6=1,0,1,0,0,1\) , and \(Y_6=(2-0)+(3-(-1))+(4-(-2))=12\) . The inequality reads \(12\ge 2\cdot 3-(4-0)^{-}=6\) .

12. Let \(X\) be a nonnegative supermartingale and \(\tau=\inf\{n:X_n=0\}\) . Prove that almost surely \(X_n=0\) for all \(n\ge\tau\) .

    Hint

    For \(n\ge m\) the event \(\{\tau=m\}\) is in \(\mathcal F_m\) , so \(0\le\mathbb E[X_n;\tau=m]\le\mathbb E[X_m;\tau=m]=0\) . Hence \(X_n=0\) almost surely on \(\{\tau=m\}\) ; take the union over \(m\le n\) .

13. Let \(Y_1,Y_2,\dots\) be i.i.d. with density \(f\) , and let \(g\) be another probability density with \(g=0\) wherever \(f=0\) . Prove that \(L_n=\prod_{k\le n}g(Y_k)/f(Y_k)\) is a martingale, and that \(L_n\to 0\) almost surely unless \(f=g\) almost everywhere.

    Solution

    Martingale. The factors \(g(Y_k)/f(Y_k)\) are independent and nonnegative; they are well defined because \(f(Y_k)>0\) almost surely. Each has mean

    \[ \mathbb E\,\frac{g(Y_1)}{f(Y_1)}=\int_{\{f>0\}}\frac{g}{f}\,f\,dx=\int_{\{f>0\}}g\,dx=1, \]

    the last step because \(g\) vanishes where \(f\) does. So \(L_n\) is a product martingale, nonnegative, and by Corollary 7.12 it converges almost surely to some \(L_\infty\) .

    The limit. Let \(\rho=\mathbb E\sqrt{g(Y_1)/f(Y_1)}=\int\sqrt{fg}\,dx\) . By the Cauchy–Schwarz inequality \(\rho\le(\int f)^{1/2}(\int g)^{1/2}=1\) , with equality only if \(\sqrt g\) is a constant multiple of \(\sqrt f\) almost everywhere, which for two probability densities means \(f=g\) almost everywhere. Suppose \(f\ne g\) , so \(\rho<1\) . By independence \(\mathbb E\sqrt{L_n}=\rho^n\to 0\) . Thus \(\sqrt{L_n}\to 0\) in \(L^1\) , hence in probability, and so \(L_n\to 0\) in probability. But \(L_n\to L_\infty\) almost surely, hence in probability, and limits in probability are unique. Therefore \(L_\infty=0\) almost surely.

    In statistical terms \(L_n\) is the likelihood ratio of the wrong density to the true one, and it tends to \(0\) : the data eventually reveal which density generated them. As in Example 7.4, \(\mathbb E L_n=1\) for all \(n\) and the martingale is not uniformly integrable.

14. In Pólya’s urn started with \(r\) red and \(b\) blue balls, show that the red fraction is a martingale and find the mean of its limit.

    Hint

    The computation of Example 7.5 goes through with \(n+2\) replaced by \(n+r+b\) . The fraction is bounded, so it converges in \(L^1\) and the mean of the limit is the initial fraction \(r/(r+b)\) .

15. Let \(X\) be a uniformly integrable martingale with limit \(X_\infty\) , and let \(\tau\) be any stopping time, with \(X_\tau=X_\infty\) on \(\{\tau=\infty\}\) . Prove that \(\mathbb E X_\tau=\mathbb E X_0\) .

    Hint

    For each \(n\) , \(\mathbb E X_0=\mathbb E X_{\tau\wedge n}=\mathbb E[X_\tau;\tau\le n]+\mathbb E[X_n;\tau>n]\) , and \(\mathbb E[X_n;\tau>n]=\mathbb E[X_\infty;\tau>n]\) because \(\{\tau>n\}\in\mathcal F_n\) and \(X_n=\mathbb E[X_\infty\mid\mathcal F_n]\) . Show \(\mathbb E[\lvert X_\tau\rvert;\tau<\infty]\le\mathbb E\lvert X_\infty\rvert\) using \(\lvert X_k\rvert\le\mathbb E[\lvert X_\infty\rvert\mid\mathcal F_k]\) on \(\{\tau=k\}\) , then let \(n\to\infty\) by dominated convergence.

16. Let \(Z_n\) be the size of the \(n\) -th generation of a branching process in which individuals have independent numbers of offspring with mean \(m\in(0,\infty)\) , and \(Z_0=1\) . Show that \(Z_n/m^n\) is a martingale that converges almost surely, and deduce that \(Z_n\to 0\) almost surely when \(m<1\) .

    Hint

    Given \(\mathcal F_n\) , \(Z_{n+1}\) is a sum of \(Z_n\) independent offspring counts, so \(\mathbb E[Z_{n+1}\mid\mathcal F_n]=mZ_n\) by Proposition 6.7. Corollary 7.12 gives convergence of \(W_n=Z_n/m^n\) to a finite limit; if \(m<1\) then \(Z_n=m^nW_n\to 0\) , and an integer-valued sequence tending to \(0\) is eventually \(0\) .

17. Let \(X\) be a martingale with \(\mathbb E X_n^2<\infty\) for all \(n\) . Prove that its increments are pairwise orthogonal, deduce the formula of Theorem 7.15, and verify it by enumeration for the random harmonic series with \(n=4\) .

    Solution

    Let \(D_k=X_k-X_{k-1}\) for \(k\ge 1\) ; each \(D_k\) is square-integrable. Fix \(j<k\) . The variable \(D_j\) is \(\mathcal F_{k-1}\) -measurable, and \(D_jD_k\) is integrable by the Cauchy–Schwarz inequality, so taking out what is known gives

    \[ \mathbb E[D_jD_k]=\mathbb E\bigl[D_j\,\mathbb E[D_k\mid\mathcal F_{k-1}]\bigr]=0, \]

    since \(\mathbb E[D_k\mid\mathcal F_{k-1}]=0\) for a martingale. The same computation with \(X_0\) in place of \(D_j\) gives \(\mathbb E[X_0D_k]=0\) . Writing \(X_n=X_0+D_1+\dots+D_n\) and expanding the square, all cross terms have expectation zero, so

    \[ \mathbb E X_n^2=\mathbb E X_0^2+\sum_{k=1}^{n}\mathbb E D_k^2 . \]

    For the random harmonic series, \(X_0=0\) and \(D_k=\varepsilon_k/k\) with \(\mathbb E D_k^2=1/k^2\) , so \(\mathbb E X_4^2=1+\tfrac14+\tfrac19+\tfrac1{16}=\tfrac{205}{144}\) . Enumerating the sixteen sign patterns and averaging \((\varepsilon_1+\varepsilon_2/2+\varepsilon_3/3+\varepsilon_4/4)^2\) gives the same value: the squares contribute \(\tfrac{205}{144}\) in every pattern, and each cross term \(\varepsilon_j\varepsilon_k/(jk)\) is \(+1/(jk)\) in eight patterns and \(-1/(jk)\) in the other eight. Orthogonality here is independence, but the general argument needed only the martingale property.

18. For the product martingale \(M_n\) of Example 7.4 prove directly that \(\lim_n\mathbb E[M_n;M_n>K]=1\) for every \(K>0\) , and conclude from Definition 5.1 that \((M_n)\) is not uniformly integrable.

    Solution

    Fix \(K>0\) . Since \(\mathbb E M_n=1\) ,

    \[ \mathbb E[M_n;M_n>K]=1-\mathbb E[M_n;M_n\le K]. \]

    The variables \(M_n\mathbf 1_{\{M_n\le K\}}\) are bounded by \(K\) and tend to \(0\) almost surely, because \(M_n\to 0\) almost surely by Example 7.4. The Dominated Convergence Theorem, with the constant \(K\) as dominating function, gives \(\mathbb E[M_n;M_n\le K]\to 0\) . Hence \(\mathbb E[M_n;M_n>K]\to 1\) as \(n\to\infty\) .

    Consequently \(\sup_n\mathbb E[M_n;M_n>K]=1\) for every \(K\) : it is at most \(\mathbb E M_n=1\) and at least the limit. The supremum does not tend to \(0\) as \(K\to\infty\) , so by Definition 5.1 the family \((M_n)\) is not uniformly integrable. In the limit all of the expectation sits beyond every fixed level, which is the same escape of mass as in the spike \(n\mathbf 1_{(0,1/n)}\) , produced here by a martingale.