Doob's Upcrossing Inequality and Martingale Convergence

Why Count Crossings?

A sequence can fail to converge only if it keeps moving between separated levels, or escapes to infinity. Counting how often it travels from below one level to above another turns this pathwise observation into an expectation bound. For martingales, that bound yields a useful convergence test for samples taken at discrete times.

Work on a filtered probability space $(\Omega,\mathcal{F},(\mathcal{F}_t)_{t\ge0},\mathbb{P})$. A discrete-time sequence $(X_k)_{k=0}^N$ is adapted if $X_k$ is $\mathcal{F}_k$-measurable. It is an integrable submartingale if each $X_k$ is integrable and $\mathbb{E}[X_{k+1}\mid\mathcal{F}_k]\ge X_k$ almost surely for $k<N$. A martingale satisfies equality instead. The arguments below use only this discrete-time conditional-expectation property; no stochastic integral is involved.

Definition: Fix real numbers $a<b$. An upcrossing of $[a,b]$ is completed when the sequence, after being at or below $a$, subsequently reaches or exceeds $b$. Begin looking for an entry at time $0$; after a completed crossing, begin looking for the next entry at the next time the sequence is at or below $a$. Write $U_N(a,b)$ for the number of completed upcrossings by time $N$. Equality counts at both thresholds: entry uses $X_k\le a$, and exit uses $X_k\ge b$.

Thus an unfinished entry at the terminal time is not counted. This convention matters in both the proof and the examples.

Doob’s Upcrossing Inequality

Theorem: If $(X_k)_{k=0}^N$ is an integrable submartingale and $a<b$, then $$ (b-a)\,\mathbb{E}[U_N(a,b)] \le \mathbb{E}[(X_N-a)^+]+\mathbb{E}[(X_0-a)^-], $$ where $x^+=\max(x,0)$ and $x^-=\max(-x,0)$.

Proof. At each step from $k-1$ to $k$, hold one unit of the sequence if an entry at or below $a$ has occurred and has not yet been followed by an exit at or above $b$. Let $H_k$ be $1$ when holding and $0$ otherwise. The decision uses only observations through time $k-1$, so $H_k$ is $\mathcal{F}_{k-1}$-measurable. Set $G=\sum_{k=1}^N H_k(X_k-X_{k-1})$, the cumulative gain of this rule. On each completed crossing, the gain from entry to exit is at least $b-a$. If there is an unfinished entry at time $N$, at a time $r$ with $X_r\le a$, its remaining gain is $X_N-X_r\ge X_N-a$. Consequently, path by path, $G\ge (b-a)U_N(a,b)+I(X_N-a)$, where $I$ is $1$ if an entry is unfinished and $0$ otherwise. Since $-I(X_N-a)\le (X_N-a)^-$, this gives $(b-a)U_N(a,b)\le G+(X_N-a)^-$.

For any predictable coefficients $C_k$ taking values in $[0,1]$, the submartingale property gives $\mathbb{E}[C_k(X_k-X_{k-1})]=\mathbb{E}[C_k\mathbb{E}[X_k-X_{k-1}\mid\mathcal{F}_{k-1}]]\ge0$. Apply this first to $H_k$, and then to $1-H_k$. The complementary gain $G^c=\sum_{k=1}^N(1-H_k)(X_k-X_{k-1})$ therefore has nonnegative expectation, so $\mathbb{E}[G]\le\mathbb{E}[G+G^c]=\mathbb{E}[X_N-X_0]$. Taking expectations in the pathwise inequality yields $(b-a)\mathbb{E}[U_N(a,b)]\le\mathbb{E}[X_N-X_0]+\mathbb{E}[(X_N-a)^-]$. The identity $x+(x-a)^-=(x-a)^++a$ changes the right-hand side to $\mathbb{E}[(X_N-a)^+]+a-\mathbb{E}[X_0]$. Finally, $a-\mathbb{E}[X_0]=\mathbb{E}[(X_0-a)^-]-\mathbb{E}[(X_0-a)^+]\le\mathbb{E}[(X_0-a)^-]$. This proves the claimed bound. If $N=0$, the crossing count is zero and the right-hand side is nonnegative, so the result also holds in that case. $\square$

Worked Crossings for a Fair Random Walk

Worked Example: Two Steps and the Threshold Rule

Let $\xi_1,\xi_2$ be independent, each taking values $1$ and $-1$ with probability $1/2$. Set $X_0=0$, $X_1=\xi_1$, and $X_2=\xi_1+\xi_2$, with the filtration generated by the observed increments. This is a martingale: each increment has conditional mean zero. Find $\mathbb{E}[U_2(0,1)]$, then compare it with the inequality.

The four equally likely paths, their values, and their completed crossings are: $ (0,1,2)$: one; $ (0,1,0)$: one; $ (0,-1,0)$: zero; and $ (0,-1,-2)$: zero. In the first two paths, time $0$ is an entry because $X_0=0\le0$, and time $1$ is an exit because $X_1=1\ge1$. Neither path completes a second crossing. Thus $\mathbb{E}[U_2(0,1)]=(1+1+0+0)/4=1/2$.

For the bound, $b-a=1$, and $X_0=0$ gives $(X_0-a)^-=0$. The terminal values are $2,0,0,-2$, each with probability $1/4$, so $\mathbb{E}[(X_2-0)^+]=(2+0+0+0)/4=1/2$. The inequality reads $1/2\le1/2$, with equality. This also checks the crossing count against the terminal-value calculation.

The submartingale condition is essential to the expectation argument in the proof. The pathwise crossing count can be defined for any sequence, but the stated expectation bound does not follow merely from having a finite sequence of random variables.

Almost-Sure Convergence from an L1 Bound

Theorem: Let $(X_n)_{n\ge0}$ be an integrable submartingale. If $\sup_{n\ge0}\mathbb{E}[|X_n|]<\infty$, then $X_n$ converges almost surely to a finite real-valued random variable.

Proof. Fix real $a<b$. The finite-time upcrossing inequality applies to $(X_k)_{k=0}^N$. Since $(X_N-a)^+\le |X_N|+|a|$ and $(X_0-a)^-\le |X_0|+|a|$, its right-hand side is bounded uniformly in $N$. The counts $U_N(a,b)$ increase with $N$; by monotone convergence, $\mathbb{E}[\lim_{N\to\infty}U_N(a,b)]$ is bounded by the same finite constant divided by $b-a$. Therefore the total number of upcrossings is finite almost surely. There are countably many rational pairs $a<b$, so with probability one every rational interval has only finitely many upcrossings.

For any real sequence whose lower limit is strictly less than its upper limit, including the possibility that either is infinite, there are rational $a<b$ strictly between those two limits. The sequence then visits values at or below $a$ and later values at or above $b$, repeatedly, and hence makes infinitely many upcrossings of $[a,b]$. Thus, on the probability-one event just obtained, the lower and upper limits of $X_n$ agree in the extended real line: the sequence has an extended-real limit.

It remains to rule out an infinite limit. Fatou’s lemma gives $\mathbb{E}[\liminf_{n\to\infty}|X_n|]\le\liminf_{n\to\infty}\mathbb{E}[|X_n|]<\infty$. A limit of $+\infty$ or $-\infty$ for $X_n$ would make this lower limit infinite on that event. A nonnegative random variable with finite expectation is finite almost surely, so neither infinite limit can occur with positive probability. The limit is therefore finite almost surely. $\square$

Corollary: If $(M_n)$ is an integrable martingale with $\sup_n\mathbb{E}[|M_n|]<\infty$, then $M_n$ converges almost surely to a finite limit. In particular, if $M_t$ is a cadlag martingale and $t_0\le t_1\le\cdots$ are deterministic times, the sampled sequence $M_{t_n}$ converges almost surely whenever $\sup_n\mathbb{E}[|M_{t_n}|]<\infty$.

Indeed, the sampled variables are adapted to $\mathcal{F}_{t_n}$ and satisfy the martingale conditional-expectation property, so the theorem applies. Cadlag means right-continuous paths with left limits; it ensures the process has well-defined path values, but the discrete convergence assertion itself uses the sampled martingale and its L1 bound. If the sampling times increase to a finite endpoint from below, the sample limit is a left limit, not necessarily the value at the endpoint.

Worked Example: A Conditional-Expectation Martingale

Worked Example: Bounded Terminal Data

Suppose $Y$ is integrable and $|Y|\le 3$ almost surely, and let $M_n=\mathbb{E}[Y\mid\mathcal{F}_n]$. Conditional Jensen’s inequality gives $|M_n|\le\mathbb{E}[|Y|\mid\mathcal{F}_n]$ almost surely. Taking expectations, $\mathbb{E}[|M_n|]\le\mathbb{E}[\mathbb{E}[|Y|\mid\mathcal{F}_n]]=\mathbb{E}[|Y|]\le3$. Also, the tower property gives $\mathbb{E}[M_{n+1}\mid\mathcal{F}_n]=M_n$, so $(M_n)$ is a martingale. The corollary therefore proves that $M_n$ has a finite almost-sure limit.

Here the bound is uniform in $n$: every sample has expected absolute value at most $3$. If, in addition, $\mathcal{F}_n$ increases to a sigma-field $\mathcal{F}_\infty$ containing $Y$, the limit is $Y$ in L1. One can see the L1 conclusion from the uniform-integrability argument below, since $|M_n|\le3$ makes the family uniformly integrable and the conditional expectations converge almost surely.

Almost-Sure Convergence Need Not Be L1 Convergence

Uniform boundedness of $\mathbb{E}[|M_n|]$ proves almost-sure convergence, but does not by itself prove convergence in L1. A stronger hypothesis is uniform integrability: a family $(Z_n)$ is uniformly integrable if $\lim_{K\to\infty}\sup_n\mathbb{E}[|Z_n|\mathbf{1}_{\{|Z_n|>K\}}]=0$. For a uniformly integrable sequence that converges almost surely to $Z$, convergence also holds in L1. Here is the relevant implication. Define $T_K(x)=\max(-K,\min(x,K))$. For fixed $K$, bounded convergence gives $\mathbb{E}[|T_K(Z_n)-T_K(Z)|]\to0$. The truncation errors for $Z_n$ are bounded by the uniform tail expectations. Fatou’s lemma applied to $|Z_n|\mathbf{1}_{\{|Z_n|>K\}}$ gives the same tail bound for $\mathbb{E}[|Z|\mathbf{1}_{\{|Z|>K\}}]$. The triangle inequality, followed first by $n\to\infty$ and then $K\to\infty$, yields $\mathbb{E}[|Z_n-Z|]\to0$.

Worked Example: A Martingale That Loses Its Mean at the Limit

Let $\xi_1,\xi_2,\ldots$ be independent fair coin tosses, and let $\mathcal{F}_n$ record the first $n$ tosses. Define $M_0=1$ and, for $n\ge1$, $M_n=2^n\mathbf{1}_{\{\xi_1=\cdots=\xi_n=\mathrm{H}\}}$. If the first $n$ tosses are all heads, the conditional probability of one more head is $1/2$, so $\mathbb{E}[M_{n+1}\mid\mathcal{F}_n]=2^{n+1}(1/2)=2^n=M_n$. If any of the first $n$ tosses is a tail, both $M_n$ and $M_{n+1}$ are zero. Thus $(M_n)$ is a martingale. Also, $\mathbb{E}[|M_n|]=2^n 2^{-n}=1$ for every $n$, so it satisfies the L1 bound and converges almost surely.

The probability that the first $n$ tosses are all heads is $2^{-n}$, which tends to zero. The event that every toss is heads is contained in this event for every $n$, and therefore has probability zero. Almost surely there is a first tail, after which $M_n=0$; hence the almost-sure limit is $0$. But $\mathbb{E}[|M_n-0|]=1$ for every $n$, so convergence is not in L1. For any $K$, choose $n$ with $2^n>K$; then $\mathbb{E}[|M_n|\mathbf{1}_{\{|M_n|>K\}}]=2^n2^{-n}=1$. The family is not uniformly integrable, explaining why the L1 conclusion does not apply.

Common Pitfall: Check the Entry Before Counting

Suppose $X_0=0$, and from time $1$ onward $X_n=\xi$, where $\xi$ is $1$ or $-1$ with equal probability. Take $a=-\tfrac12$ and $b=\tfrac12$. A tempting but incorrect count says there is one upcrossing when $\xi=1$. In fact, $X_0=0>a$, so the sequence has not entered at or below $a$; the path stays at $1$ and makes no completed upcrossing. When $\xi=-1$, it enters at time $1$ but never reaches or exceeds $b$. Thus $U_N(a,b)=0$ on both outcomes for every $N\ge1$, and $\mathbb{E}[U_N(a,b)]=0$, not $1/2$.

The inequality still holds: $b-a=1$, the initial negative part is $(X_0-a)^-=0$, and the terminal positive part has expectation $\mathbb{E}[(X_N-a)^+]=\tfrac12(1+\tfrac12)+\tfrac12(0)=\tfrac34$. So the bound is $0\le\tfrac34$. If instead $a=0$ and $b=\tfrac12$, time $0$ is a valid entry. The path with $\xi=1$ completes one upcrossing and the path with $\xi=-1$ completes none; the expected count is then $1/2$. Checking the entry rule before counting avoids confusing a visit above the lower threshold with an actual entry.

Check Your Understanding

For each question, state any assumptions you use and apply the entry and exit conventions explicitly.

For the two-step fair random walk in the worked example, compute $\mathbb{E}[(X_2-a)^+]$ and $\mathbb{E}[(X_0-a)^-]$ when $a=-1$, then state the resulting bound for $U_2(-1,0)$.
Why does the proof use both $H_k$ and $1-H_k$, rather than only the nonnegative expected gain from $H_k$?
Explain how infinitely many upcrossings of one rational interval rule out convergence of a real sequence.
For the coin-toss martingale, verify directly that $\mathbb{E}[M_n]=1$ while its almost-sure limit has expectation $0$.
What additional property of a martingale sample sequence allows almost-sure convergence to be strengthened to L1 convergence?