Martingales: Maximal and Upcrossing Inequalities

A martingale has no predictable change in its conditional mean. Individual paths can nevertheless fluctuate widely. The two estimates developed here control different aspects of that fluctuation: a maximal inequality bounds the probability of a large excursion, while an upcrossing inequality bounds repeated passages between two levels. The latter will give almost-sure convergence.

Definition 1 (Martingale). Let \(X_1,X_2,\dots\) be a sequence of random variables on a probability space \((\Omega, \mathscr F, \mathop{\mathrm{\mathbf{P}\!\,}})\). Let \(\mathscr F_1, \mathscr F_2, \dots\) be a sequence of \(\sigma\)-fields in \(\mathscr F\). Then, the (double) sequence \(\{(X_n, \mathscr F_n)\}_{n \in \mathbb N}\) is called a martingale if the following conditions are satisfied for all \(n \in \mathbb N\):

(\(\{\mathscr F_n\}\) form a filtration) \(\mathscr F_n \subset \mathscr F_{n+1}\);
(\(\{X_n\}\) is adapted to the filtration) \(X_n\) is \(\mathscr F_n\)-measurable;
\(\mathbb{E}|X_n| < \infty\); and
\(\mathbb{E}[X_{n+1} \mid \mathscr F_n] = X_n\) with probability one.

The filtration is part of the definition: a sequence is called a martingale if it is a martingale relative to some sequence of \(\sigma\)-fields. Therefore, the sequence of \(\sigma\)-fields \(\mathscr H_n = \sigma(X_1,\dots,X_n)\) also works for a process already known to be a martingale. The tower property gives the required conditional expectation when we pass to this smaller filtration. This is referred to as the smallest \(\sigma\)-fields with respect to which \(X_n\) are a martingale.

Remark 2. Note that \(\mathbb{E}[X_{n+1} \mid \mathscr F_n] = X_n\) with probability one gives rise to the following relation for all \(n\):

\[\int_A X_{n+1} \dif \mathop{\mathrm{\mathbf{P}\!\,}}= \int_A X_n \dif \mathop{\mathrm{\mathbf{P}\!\,}}\quad \text{for all } A \in \mathscr F_n ~.\]

This requirement follows because \(X_n\) is \(\mathscr F_n\)-measurable. Since \(\mathscr F_n\) is a nested sequence of \(\sigma\)-fields, it follows that \(\int_A X_n \dif \mathop{\mathrm{\mathbf{P}\!\,}}= \int_A X_{n+1} \dif \mathop{\mathrm{\mathbf{P}\!\,}}= \dots = \int_A X_{n+k} \dif \mathop{\mathrm{\mathbf{P}\!\,}}\) for any \(k \geq 1\), with probability one. So, \(X_n\) is a version of \(\mathbb{E}[X_{n+k} \mid \mathscr F_n]\) for any \(k \geq 1\), with probability one.

Remark 3. It is equivalent to give the defining conditions of a martingale using differences; to do so, let \(\Delta_n = X_n - X_{n-1}\), with \(\Delta_1 = X_1\). Then, by linearity, the condition \(\mathbb{E}[X_{n+1} \mid \mathscr F_n] = X_n\) is equivalent to \(\mathbb{E}[\Delta_{n+1} \mid \mathscr F_n] = 0\), by linearity. Therefore, the sets \(X_1, \dots, X_n\) and \(\Delta_1, \dots, \Delta_n\) generate the same \(\sigma\)-field.

Example 4. Let \(\Omega = (0,1]\), \(\mathscr F\) be the collection of Borel sets of \(\Omega\), and \(\mathop{\mathrm{\mathbf{P}\!\,}}\) be the Lebesgue measure over \(\mathscr F\). Then, let \(\mathscr F_n\) be the (finite!) \(\sigma\)-field generated by the partition of \(\Omega\) into dyadic intervals, \((k2^{-n}, (k+1)2^{-n}]\) for \(k \in [0,2^n)\). Let \(\nu\) be any finite positive Borel measure on \((0,1]\). Its restriction to each finite sigma-field has the following Radon–Nikodym derivative with respect to Lebesgue measure:

\[X_n(\omega) = \frac{\nu((k2^{-n}, (k+1)2^{-n}])}{2^{-n}} \quad \text{for } \omega \in (k2^{-n}, (k+1)2^{-n}] ~.\]

Clearly, \(X_n\) is a martingale with respect to \(\mathscr F_n\). Note that \(A \in \mathscr F_n\) implies \(A \in \mathscr F_{n+1}\), and \(\int_A X_{n+1} \dif \mathop{\mathrm{\mathbf{P}\!\,}}= \nu(A)\) for any \(A \in \mathscr F_n\).

Example 5. Let \(X\) be an integrable random variable defined on \((\Omega, \mathscr F, \mathop{\mathrm{\mathbf{P}\!\,}})\). Let \(\mathscr F_n\) be nondecreasing \(\sigma\)-fields in \(\mathscr F\). If we let \(X_n = \mathbb{E}[X \mid \mathscr F_n]\), the tower property of conditional expectations gives \(\mathbb{E}[X_{n+1} \mid \mathscr F_n] = X_n\). Therefore, \(X_n\), as defined, is a martingale relative to \(\mathscr F_n\).

Example 6 (Branching process). Let \(\{N_{n,k}:n,k\geq1\}\) be i.i.d. nonnegative integer-valued random variables with \(0<m=\mathbb{E} N_{1,1}<\infty\). Set \(Z_0=1\) and \(Z_n=\sum_{k=1}^{Z_{n-1}}N_{n,k}\), interpreting an empty sum as zero. With \(\mathscr F_n=\sigma(N_{j,k}:1\leq j\leq n,\ k\geq1)\), independence of the next row gives \(\mathbb{E}[Z_{n+1}\mid\mathscr F_n]=mZ_n\). Induction gives \(\mathbb{E} Z_n=m^n\), so \(X_n=Z_n/m^n\) is an integrable martingale. It is also a martingale for the smaller natural filtration \(\sigma(Z_0,\ldots,Z_n)\), by the tower property.

The conditional mean in the branching example can be checked without treating the random upper summation limit as deterministic. Nonnegativity permits conditional monotone convergence:

\[\mathbb E(Z_{n+1}\mid\mathscr F_n) =\sum_{k\geq1}\mathbf1_{\{Z_n\geq k\}}\mathbb E(N_{n+1,k}\mid\mathscr F_n) =m\sum_{k\geq1}\mathbf1_{\{Z_n\geq k\}}=mZ_n.\]

The entire next row is independent of \(\mathscr F_n\). Starting with \(Z_0=1\), induction gives \(\mathbb EZ_n=m^n<\infty\), so the normalized variables satisfy all parts of the martingale definition.

Definition 7 (Submartingale). Let \(X_1,X_2,\dots\) be a sequence of random variables on a probability space \((\Omega, \mathscr F, \mathop{\mathrm{\mathbf{P}\!\,}})\). Let \(\mathscr F_1, \mathscr F_2, \dots\) be a sequence of \(\sigma\)-fields in \(\mathscr F\). Then, the (double) sequence \(\{(X_n, \mathscr F_n)\}_{n \in \mathbb N}\) is called a submartingale if the following conditions are satisfied for all \(n \in \mathbb N\):

(\(\{\mathscr F_n\}\) form a filtration) \(\mathscr F_n \subset \mathscr F_{n+1}\);
(\(\{X_n\}\) is adapted to the filtration) \(X_n\) is \(\mathscr F_n\)-measurable;
\(\mathbb{E}|X_n| < \infty\); and
\(\mathbb{E}[X_{n+1} \mid \mathscr F_n] \geq X_n\) with probability one.

By way of nomenclature, a sequence is called a supermartingale if \(\mathbb{E}[X_{n+1} \mid \mathscr F_n] \leq X_n\) with probability one.

Proposition 8.

Let \(X_1,X_2,\dots\) be a martingale relative to \(\mathscr F_1, \mathscr F_2, \dots\). If \(\varphi\) is a convex function, and \(\varphi(X_n)\) are integrable, then \(\varphi(X_1),\varphi(X_2),\dots\) form a submartingale relative to \(\mathscr F_1, \mathscr F_2, \dots\).
Let \(X_1,X_2,\dots\) be a submartingale relative to \(\mathscr F_1, \mathscr F_2, \dots\). If \(\varphi\) is a nondecreasing, convex function, and \(\varphi(X_n)\) are integrable, then \(\varphi(X_1),\varphi(X_2),\dots\) form a submartingale relative to \(\mathscr F_1, \mathscr F_2, \dots\).

Proof. Conditional Jensen gives

\[\mathbb E(\varphi(X_{n+1})\mid\mathscr F_n) \geq\varphi\bigl(\mathbb E(X_{n+1}\mid\mathscr F_n)\bigr).\]

For a martingale the conditional mean inside \(\varphi\) equals \(X_n\), proving the first assertion. For a submartingale it is at least \(X_n\); the additional monotonicity assumption then gives the same lower bound \(\varphi(X_n)\). Convex real functions are continuous, hence Borel, so adaptedness is preserved; integrability is assumed in both statements. Without monotonicity, the second implication can fail: take \(X_n=n\) and \(\varphi(x)=-x\). ◻

To control a path, we often stop it the first time it enters a specified set. The stopping rule must use only information available at that time. Let \(\tau\) be a random variable taking values in the positive integers together with infinity. We say \(\tau\) is a stopping time with respect to \(\{\mathscr F_n\}\) if \(\{\omega : \tau(\omega) = k\} \in \mathscr F_k\) for every finite \(k\). Equivalently, we can rewrite the condition as \(\{\omega : \tau(\omega) \leq k\} \in \mathscr F_k\) for every finite \(k\).

Proposition 9 (Optional Sampling). Let \(X_1,\dots,X_n\) be a submartingale with respect to \(\mathscr F_1, \dots, \mathscr F_n\). Let \(\tau_1,\tau_2\) be stopping times satisfying \(1 \leq \tau_1 \leq \tau_2 \leq n\). Then, \(X_{\tau_1}, X_{\tau_2}\) is a submartingale with respect to \(\mathscr F_{\tau_1}, \mathscr F_{\tau_2}\).

Proof. For a bounded stopping time \(\tau\), define

\[\mathscr F_\tau=\{A\in\mathscr F:A\cap\{\tau=k\}\in\mathscr F_k\text{ for every }k\}.\]

The finite sum \(X_\tau=\sum_{k=1}^nX_k\mathbf1_{\{\tau=k\}}\) is integrable and \(\mathscr F_\tau\)-measurable. If \(\tau_1\leq\tau_2\), then \(\mathscr F_{\tau_1}\subseteq\mathscr F_{\tau_2}\): intersect \(A\in\mathscr F_{\tau_1}\) with \(\{\tau_2=k\}\), and split it over \(\{\tau_1=j\}\), \(j\leq k\).

For \(A\in\mathscr F_{\tau_1}\), the pathwise telescoping identity is

\[(X_{\tau_2}-X_{\tau_1})\mathbf1_A =\sum_{k=1}^{n-1}(X_{k+1}-X_k)\mathbf1_{A\cap\{\tau_1\leq k<\tau_2\}}.\]

Each event in the sum belongs to \(\mathscr F_k\), because \(A\cap\{\tau_1\leq k\}\) is a finite union of \(\mathscr F_k\)-events and \(\{\tau_2>k\}\in\mathscr F_k\). Conditioning each summand on \(\mathscr F_k\) shows its expectation is nonnegative. Thus

\[\mathbb E(X_{\tau_2}\mathbf1_A)\geq\mathbb E(X_{\tau_1}\mathbf1_A)\qquad(A\in\mathscr F_{\tau_1}).\]

The defining property of conditional expectation yields \(\mathbb E(X_{\tau_2}\mid\mathscr F_{\tau_1})\geq X_{\tau_1}\) almost surely. The bounded stopping times ensure every sum and expectation used here is finite; no unbounded optional-sampling assertion is being used. ◻

Theorem 10 (Kolmogorov). Let \(\{(X_i,\mathscr F_i)\}_{1 \leq i \leq n}\) be a submartingale. Then, for any \(\varepsilon > 0\),

\[\mathop{\mathrm{\mathbf{P}\!\,}}\left( \max_{1 \leq k \leq n} X_k \geq \varepsilon \right) \leq \frac{\mathbb{E} |X_n|}{\varepsilon} ~.\]

Proof. Separate paths according to the first time they reach the threshold. The first-crossing events are disjoint, so their contributions can be added. Define the event

\[\begin{aligned} E = \left\{ \max_{1 \leq i \leq n} X_i \geq \varepsilon \right\} = \bigcup_{1 \leq i \leq n} \left\{ X_i \geq \varepsilon ~,~ \max_{1 \leq j < i} X_j < \varepsilon \right\} ~, \end{aligned}\]

where, going forward, we write \(E_i =\left\{ X_i \geq \varepsilon ~,~ \max_{1 \leq j < i} X_j < \varepsilon \right\}\). Note that \(E_i\) is disjoint and \(\mathscr F_i\)-measurable. It then follows that

\[\begin{aligned} \varepsilon \mathop{\mathrm{\mathbf{P}\!\,}}\left( \max_{1 \leq k \leq n} X_k \geq \varepsilon \right) &\leq \sum_{1 \leq i \leq n} \mathbb{E} [X_i \mathbb 1 \{E_i\}] \leq \sum_{1 \leq i \leq n} \mathbb{E} [\mathbb{E}[X_n \mid \mathscr F_i] \mathbb 1 \{E_i\}] \\ &= \sum_{1 \leq i \leq n} \mathbb{E} [\mathbb{E}[X_n \mathbb 1 \{E_i\} \mid \mathscr F_i]] \\ &= \sum_{1 \leq i \leq n} \mathbb{E} [X_n \mathbb 1\{E_i\}] = \mathbb{E} [X_n \mathbb 1 \{E\}] \leq \mathbb{E}|X_n| ~, \end{aligned}\]

which proves the bound. ◻

Theorem 11 (Doob; Martingale Convergence). Let \(X_1, X_2, \dots\) be a submartingale. Suppose \(K = \sup_{n \in \mathbb N} \mathbb{E} |X_n| < \infty\). Then, \(X_n \xrightarrow{\rm a.s.} X\), where \(X\) is a random variable such that \(\mathbb{E}|X| \leq K\).

The proof of Doob’s martingale convergence theorem controls repeated crossings between two levels. Fix real numbers \(a<b\). Define successive entrance times by

\[\tau_1=\inf\{j\geq1:X_j\leq a\},\qquad \tau_{2r}=\inf\{j>\tau_{2r-1}:X_j\geq b\},\qquad \tau_{2r+1}=\inf\{j>\tau_{2r}:X_j\leq a\}.\]

The infimum of an empty set is infinity, and every later entrance time is then infinity. These are stopping times: each decision at time \(j\) depends only on the observations through \(j\). The number of completed upcrossings by time \(n\) is \(\mathscr U_n=\sum_{r\geq1}\mathbb1_{\{\tau_{2r}\leq n\}}\). It increases with \(n\). The interval \([a,b]\) consists of values of the process, not observation times.

For an equivalent predictable description, put \(U_1=0\) and, for \(k\geq2\), let \(U_k\) indicate whether the increment from \(k-1\) to \(k\) is taken during an unfinished crossing:

\[U_k=\begin{cases} 0,&U_{k-1}=0,\ X_{k-1}>a,\quad\text{or }U_{k-1}=1,\ X_{k-1}\geq b,\\ 1,&U_{k-1}=0,\ X_{k-1}\leq a,\quad\text{or }U_{k-1}=1,\ X_{k-1}<b. \end{cases}\]

Lemma 12 (Upcrossing Inequality). The number of upcrossings of a submartingale \(\{X_n, \mathscr F_n\}_{n \in \mathbb N}\), denoted \(\mathscr U_n\) as above, satisfies

\[\mathbb{E} \mathscr U_n \leq \frac{\mathbb{E} |X_n| + |a|}{b-a} ~.\]

Proof. Let \(Y_k=(X_k-a)^+\) and \(c=b-a\). Convexity and monotonicity show that \(Y\) is a nonnegative submartingale; this is the second part of Proposition 8. The same entrance times describe crossings of \(Y\) from zero to at least \(c\). The gain

\[G_n=\sum_{k=2}^n U_k(Y_k-Y_{k-1})\]

is at least \(c\mathscr U_n\) on every path. Each completed holding interval begins at zero and ends at a value at least \(c\); any unfinished interval also has nonnegative gain. Moreover, \(U_k\) is \(\mathscr F_{k-1}\)-measurable, so the submartingale property gives

\[\mathbb{E}\sum_{k=2}^n(1-U_k)(Y_k-Y_{k-1})\geq0. \qquad \mathbb{E} G_n\leq\mathbb{E}(Y_n-Y_1)\leq\mathbb{E} Y_n.\]

Consequently \((b-a)\mathbb{E}\mathscr U_n\leq\mathbb{E}(X_n-a)^+\leq\mathbb{E}|X_n|+|a|\), which proves the bound. ◻

Proof of Theorem 11. For each rational pair \(a<b\), monotone convergence and the upcrossing bound give \(\mathbb{E}\mathscr U_\infty(a,b)\leq(K+|a|)/(b-a)<\infty\). Thus there are only finitely many such upcrossings almost surely. Take the intersection of these probability-one events over the countably many rational pairs. On that event the lower and upper limits of \(X_n\) agree; otherwise two rational numbers strictly between them would be crossed infinitely often. Hence the limit exists in the extended real line. Fatou’s lemma gives \(\mathbb{E}\liminf_n|X_n|\leq K\), so the limit is finite almost surely and has expected absolute value at most \(K\). ◻