4.2. Martingales and a.s. convergence

•
probability   Durrett  

$\newcommand{\argmin}{\mathop{\mathrm{argmin}}\limits}$ $\newcommand{\argmax}{\mathop{\mathrm{argmax}}\limits}$

Remaining sections in chapter 4 is about martingales and convergence of it. Regarding martingales, our first topic will be convergence in almost sure sense. Next we will look into convergence in $L^p,$ with $p>1$ and $p=1$ separately. In the meantime the theory of optional stopping will be covered.


Martingales

Let $(\mathcal{F}_n)_{n=1}^\infty$ be a sequence of sub $\sigma$-fields of $\mathcal{F},$ $(X_n)$ be a sequence of random variables with $X_n \in \mathcal{F}_n,$ $E|X_n|<\infty$ for all $n.$ $(X_n, \mathcal{F}_n)$ is a martingale if $E(X_{n+1}|\mathcal{F}_n) = X_n$ a.s., a submartingale if $E(X_{n+1}|\mathcal{F}_n) \ge X_n$ a.s., or a supermartingale if $E(X_{n+1}|\mathcal{F}_n) \le X_n$ a.s.

We say $X_n$ is adapted to $\mathcal{F}_n$ if $X_n \in \mathcal{F}_n$ for all $n.$ For simplicity instead of denoting $\mathcal{F}_n$ together, we could just say $X_n$ is a (sub/super)martingale if the adapted $\sigma$-fields are clear. If $X_n$ is a martingale, $\int_A X_{n+1} dP = \int_A X_n dP$ for all $A \in \mathcal{F}n,$ so trivially $EX_{n+1} = EX_n$ for all $n.$ $X_n$ is a martingale if and only if $X_n$ is both a submartingale and a supermartingale. In addition, if $X_n$ is a submartingale, then $-X_n$ is a supermartingale.

The easiest but important examples are random walks and square martingales.

Suppose $\xi_1, \xi_2, \cdots$ are i.i.d. with mean 0 and variance $\sigma^2.$ Let $\mathcal{F}_n = \sigma(\xi_1,\cdots,\xi_n).$ Then
(i) $X_n := \xi_1 + \cdots \xi_n$ is a martingale.
(ii) $X_n := (\xi_1 + \cdots + \xi_n)^2 - n\sigma^2$ is a martingale.

Though we cannot guarantee that functions of martingales are also martingales, we can say for sure that a function of martingale is a submartingale if the function is convex.

For a martingale $X_n,$ if $\varphi$ is convex and $E|\varphi(X_n)|<\infty$ for all $n,$ then $\varphi(X_n)$ is a submartingale.

The proof is direct by conditional Jensen’s inequality. The obvious corollary is for submartingales.

For a submartingale $X_n,$ if $\varphi$ is convex, increasing and $E|\varphi(X_n)|<\infty$ for all $n,$ then $\varphi(X_n)$ is a submartingale.

The following two examples will be useful in the section comes later.

(i) If $X_n$ is a submartingale, then $(X_n-a)^+$ is a submartingale.
(ii) If $X_n$ is a supermartingale, then $X_n \wedge a$ is a supermartingale.


Martingale convergence theorems

For martingale convergence theorems, we need to define and prove predictable sequences, stopping times, upcrossing inequality and related properties.

Upcrossing inequality

Let $\mathcal{F}_n$ be a sequence of sub $\sigma$-fields of $\mathcal{F}.$ $\mathcal{F}_n$ is a filtration if $F_n \subset \mathcal{F}_{n+1}$ for all $n.$
For a filtration $(\mathcal{F}_n)_{n\ge0},$ a sequence of random variables $H_n$ is predictable if $H_{n+1} \in \mathcal{F}n$ for all $n \ge 0.$

Intuitively, consider $n$ as time index. The term “predictable” is from the fact that we knows every information about the behavior of $H_{n+1}$ in the time point $n.$

We get the result that the sum of submartingale increments weighted by a bounded predictable sequence is also a submartingale.

Let $X_n$ be a submartingale adapted to a filtration $(\mathcal{F}_n)_{n\ge0}.$ Let $H_n$ be a non-negative predictable sequence with $|H_n| \le M_n$ for some $M_n>0$ for all $n.$ Then $$(H\cdot X)_n := \sum_{m=1}^n H_m(X_m-X_{m-1})$$ is a submartingale.

(i) $E|(H\cdot X)_n| \le \sum_{m=1}^n M_nE(|X_m|+|X_{m-1}|) < \infty$ for all $n.$
(ii) Clearly, $(H\cdot X)_n \in \mathcal{F}_n$ for all $n.$
(iii) $$\begin{aligned} E((H\cdot X)_{n+1} | \mathcal{F}_n) &= (H\cdot X)_n + E(H_{n+1}(X_{n+1}-X_n)|\mathcal{F}_n) \\ &= (H\cdot X)_n + H_{n+1}\cancel{\{E(X_{n+1}|\mathcal{F}_n)-X_n\}}. \end{aligned}$$

We already get a glimpse of stopping times while studying coupon collector’s problem and renewal theory. They were random variables that specify the time that an event occurs. Here, we define it formally.

Let $N$ be a random variable taking values $0,1,\cdots,\infty.$ $N$ is a stopping time if $\{N=n\}\in\mathcal{F}_n$ for all $n=0,1,\cdots,\infty.$

It is highly useful to define a predictable sequence as an indicator function related to stopping times. With such sequence, we can easily derive the following theorem.

Let $N$ be a stopping time, $X_n$ be a submartingale. Then $X_{n\wedge N}$ is a submartingale.

Let $H_m = \mathbf{1}_{m\le N}$ then it is a non-negative bounded predictable sequence since $\{m\le N\} = \{N \le m-1\}^c \in \mathcal{F}_{m-1}.$ By theorem 4.2.8 $X_{n\wedge N}-X_0$ is a submartingale, so $X_{n\wedge N}$ is also a submartingale.

As an example and a lemma for our main theorem - martingale convergence - I will state and prove the upcrossing inequality.

Let $(X_n, \mathcal{F}_n)_{n\ge0}$ be a submartingale. For $a<b,$ define $$N_{2k-1} := \inf\{m>N_{2k-2}:~ X_m \le a\},\\ N_{2k} := \inf\{m>N_{2k-1}:~ X_m \ge b\}, \\ N_0 := -1, \\ U_n = \sup\{k:~ N_{2k} \le n\}.$$ For a submartingale $(X_n)_{n\ge0},$ $$(b-a)EU_n \le E(X_n-a)^+ - E(X_0-a)^+.$$
expand proof

First we show that $N_m$'s are stopping times. For given $n,$ $$\{N_1=n\} = \{X_0>a, \cdots, X_{n-1}>a,X_n\le a\} \in \mathcal{F}_n. \\ \{N_1=n\} = \bigcup_{\ell=1}^{n-1}\{N_1=\ell, X_{\ell+1}<b,\cdots, X_{n-1}<b,X_n\ge b\} \in \mathcal{F}_n. \\ \cdots$$ Thus $N_m$'s are stopping times. Next, we define $Y_n = a + (X_n-a)^+$ so that $Y_{N_{2k}} \ge b$ and $Y_{N_{2k-1}} = a$ for all $k.$ Since $x\mapsto a + (x-a)^+$ is increasing and convex, $Y_n$ is also a submartingale.
$$\begin{aligned} (b-a)EU_n &\le \sum_{k=1}^{U_n}(Y_{N_{2k}}-Y_{N_{2k-1}}) \\ &= \sum_{k=1}^{U_n} \sum_{i\in J_k}(Y_i-Y_{i-1}),\\ &\;\;\;\;\text{where } J_k=\{N_{2k-1}+1,\cdots,N_{2k}\} \\ &= \sum_{m\in J} (Y_m - Y_{m-1}),\\ &\;\;\;\;\text{where } J=\cup_{k=1}^{U_n} J_k \\ &\le \sum_{m=1}^n \mathbf{1}_{m\in J}(Y_m - Y_{m-1}). \end{aligned}$$ Let $H_m = \mathbf{1}_{m\in J},$ then since $$\{m\in J\} = \{N_{2k-1} < m \le N_{2k} \text{ for some } k\}$$ $H_m$ is a bounded, non-negative predictable sequence. Thus $$(b-a)U_n \le (H\cdot Y)_n$$ and the right hand side is a submartingale. Let $K_m = 1-H_m$ then similarly $(K\cdot Y)_n$ is a submartingale and $E(K\cdot Y)_n \ge 0.$ Hence $$\begin{aligned} E(Y_n-Y_0) &= E(H\cdot Y)_n + E(K\cdot Y)_n \\ &\ge E(H\cdot Y)_n \ge (b-a)EU_n. \end{aligned}$$

We call $U_n$ the number of upcrossings. An important fact directly follows from the theorem is $EU_n \le \frac{1}{b-a}(EX_n^+ + |a|).$ This will be the key to prove the martingale convergence.

Martingale convergence theorems

We get our first convergence theorem for dependent sequence.

For a submartingale $X_n,$ if $\sup_n X_n^+<\infty,$ then there exists $X \in L^1$ such that $X_n \to X$ a.s.
expand proof

Given $a<b,$ let $U_n[a,b]$ be the number of upcrossings of $X_1,\cdots,X_n$ over $[a,b].$ By the upcrossing inequality, $EU_n[a,b] \le \frac{EX_n^++|a|}{b-a}.$ Let $U[a,b] = \lim_n U_n[a,b]$ then $$EU[a,b] = \lim_n EU_n[a,b] \le \sup_n \frac{EX_n^++|a|}{b-a} < \infty.$$ Thus by Markov's inequality, $0\le U[a,b]\le \infty$ a.s.
Now suppose $\liminf_n X_n < \limsup_n X_n.$ Then for some $a<b,$ $X_n<a$ and $X_n>b$ infinitely often. Thus $$\begin{aligned} P(\liminf_n X_n < \limsup_n X_n) &= P(\liminf_n X_n < a < b< \limsup_n X_n \text{ for some } a,b\in\mathbb{Q}) \\ &\le \sum_{a,b\in\mathbb{Q}}P(\liminf_n X_n <a<b< \limsup_n X_n) \\ &= \sum_{a,b\in\mathbb{Q}}P(U[a,b]=\infty) = 0 \end{aligned}$$ so there exists $X$ such that $X_n \to X$ a.s. We now need to show that such $X$ is integrable. By Fatou's lemma, $$\begin{aligned} EX^+ &\le \liminf_nEX_n^+ \le \sup_n EX_n^+ < \infty.\\ EX^- &\le \liminf_nEX_n^- = \liminf_nE(X_n^+-X_n) \\ &\le \sup_nEX_n^+ - EX_0 < \infty. \end{aligned}$$

As corollaries, we get supermartingale convergence and closability of negative submartingales.

Let $X_n\ge0$ be a supermartingale. There exists $X\in L^1$ such that $X_n\to X$ a.s. and $EX_n \le EX_0.$
If $X_n, n=1,2,\cdots$ is a negative submartingale, then $X_n, n=1,2,\cdots,\infty$ is also a negative submartingale.

The next example shows that even if a martingale converges almost surely, we cannot guarantee $L^p$ convergence to the same limit. The following sections will be about the condition that a martingale converges a.s. and in $L^p$.

Let $\xi_1,\cdots$ be i.i.d. with $P(\xi_1=1)=P(\xi_1=-1)=\frac{1}{2}.$ Let $S_n = \xi_1 + \cdots + \xi_n,$ $S_0=1$ and $\mathcal{F}_n = \sigma(\xi_1,\cdots,\xi_n),$ $\mathcal{F}_0 = \{\phi,\Omega\}$ then $S_n$ is a martingale. Let $N = \inf\{n\ge1:~ S_n=0\}$ be a stopping time, then $X_n := S_{n\wedge N} \ge 0$ is also a martingale. $X_n \to 0$ a.s. but $X_n \to 1$ in $L^1.$

By supermartingale convergence, $X_n \to X$ for some $X\in L^1.$ Note that on $(N=\infty),$ $X_n = S_n.$ By the law of iterated logarithm, $P(\liminf_n S_n = -\infty, \limsup_n S_n = \infty)=1.$ It follows that $$\begin{aligned} P(N=\infty) &= P(N=\infty, \liminf_n S_n = -\infty, \limsup_n S_n = \infty) \\ &= P(N=\infty, \liminf_n X_n = -\infty, \limsup_n X_n = \infty) \\ &\le P(\liminf_n X_n = -\infty, \limsup_nX_n = \infty) = 0. \end{aligned} $$ and $N<\infty$ a.s. Hence $X=\lim_nS_{n\wedge N} = S_N = 0$ a.s.
However, $E|X_n| = ES_{n\wedge N} = ES_0 = 1$ for all $n$ since $X_n$ is a martingale.


Acknowledgement

This post series is based on the textbook Probability: Theory and Examples, 5th edition (Durrett, 2019) and the lecture at Seoul National University, Republic of Korea (instructor: Prof. Sangyeol Lee).