Proof of the Upcrossing Inequality

The upcrossing inequality is the key technical tool in proving Doob's martingale convergence theorem. It bounds the expected number of times a submartingale crosses upward through an interval.

Statement

Proof

Step 1: Define the stopped process $Y_k = (X_k - a)^+$ (shift so the interval is $[0, b-a]$).

Step 2: Track upcrossings using a betting strategy. Let $\beta_0, \beta_1, \ldots$ be the starts of upcrossings (below $0$) and $\alpha_1, \alpha_2, \ldots$ the completions (above $b-a$). The total gain from upcrossings is at least $(b-a) U_n(a,b)$.

Step 3: By the submartingale property and the optional stopping theorem for the martingale transform (betting $1$ during upcrossings, $0$ otherwise):

$(b-a) U_n(a,b) \leq \mathbb{E}[Y_n] = \mathbb{E}[(X_n - a)^+].$

Rearranging gives the result.

Consequence

If $\mathbb{E}[(X_n - a)^+] \leq C$ for all $n$, then $\mathbb{E}[U_\infty(a, b)] \leq C/(b-a) < \infty$, so $U_\infty(a, b) < \infty$ a.s. This means the process crosses $[a,b]$ finitely many times, implying convergence.