Doob's maximal inequality
/ Doob rhymes with 'tube' /
Knowing that a process has a small typical value at a fixed time is one thing; controlling how high it ever climbs over a whole stretch of time is much harder and far more useful. If a fair game's fortune wobbles around zero, what is the chance it ever spiked above some big level lambda at any point during the first n rounds? Doob's maximal inequality answers this: for a martingale (or non-negative submartingale), the probability of the entire running maximum exceeding a level is controlled by the value at the final time alone. The peak of the whole path is governed by the endpoint.
Write M_n^* = max over k from 0 to n of |M_k|, the largest absolute value the process reaches up to time n. For a martingale M (so |M_n| is a non-negative submartingale), the inequality states lambda * P(M_n^* >= lambda) <= E[|M_n|] for every lambda > 0. Read it as a souped-up Markov inequality: ordinary Markov bounds the chance that the value at the FINAL time is large, while Doob bounds the chance that the value at SOME time up to n is large — yet pays the same price, E[|M_n|]/lambda. The reason it works is a stopping-time argument: let T be the first time |M_k| crosses lambda; on the event the max is exceeded, M_T is at least lambda, and the submartingale property pins E[|M_n|] from below by lambda * P(max exceeded). There is also a powerful L^p version: for p > 1, E[(M_n^*)^p] <= (p/(p-1))^p * E[|M_n|^p], bounding the expected size of the peak by the expected size of the endpoint.
This inequality is a cornerstone. The L^p form is the engine that makes martingales converge in L^p and underlies the upcrossing-free route to the convergence theorem; it is also the discrete ancestor of the bounds controlling the maximum of Brownian motion. The honest caveat: the inequality needs M to be a martingale or |M| a non-negative submartingale, and the L^p version genuinely requires p > 1 — at p = 1 the constant p/(p-1) blows up, and the clean bound fails, which is exactly the technical reason L^1-bounded martingales converge almost surely but need not converge in L^1.
For a fair +/-1 walk S_n, Doob's inequality says P(max over k <= n of |S_k| >= lambda) <= E[|S_n|]/lambda. Since E[|S_n|] is about sqrt(2n/pi), the chance the walk's peak ever exceeds lambda in n steps is bounded by roughly sqrt(2n/pi)/lambda — a single endpoint quantity controlling the whole trajectory's highest excursion.
The whole path's maximum is controlled by the endpoint: a stronger statement than ordinary Markov, at the same price.
The L^p maximal inequality holds only for p > 1; the constant p/(p-1) diverges at p = 1. This is exactly why L^1-bounded martingales converge almost surely yet may not converge in L^1.