Martingale Convergence

Bound a fair game's whole path, and watch it settle down with probability 1.

The idea

Martingale convergence and Doob's maximal inequality describe a fair game's whole path rather than one snapshot of it. A submartingale is a process that, given the history, never expects to fall: $\mathbb{E}[X_{n+1} \mid \text{history}] \ge X_{n}$.

Theorem (Doob's maximal inequality).

Let $X_{n}$ be a non-negative submartingale. Then for every $a > 0$, $\mathbb{P}\left(\max_{k \le n} X_{k} \ge a\right) \le \frac{\mathbb{E}[X_{n}]}{a}.$

The left side asks whether the path ever reaches $a$ in the first $n$ steps, yet the right side is the same bound Markov's inequality gives for the single value $X_{n}$.

Theorem (Martingale Convergence Theorem).

Let $M_{n}$ be a martingale that is bounded in mean: one fixed constant $C$ satisfies $\mathbb{E}[|M_{n}|] \le C$ for every $n$. Then with probability $1$ the sequence $M_{0}, M_{1}, M_{2}, \dots$ settles down to a finite value.

The second theorem is the more striking: fairness alone forbids perpetual wandering. A fair game whose size stays under control on average may finish anywhere, but it cannot swing back and forth without limit.

Ways to work on it

• Walkthrough. Doob's maximal and L^2 inequalities, then the convergence theorem and why non-negativity suffices.
• Proof. Doob's maximal inequality from the first-crossing time — and a fortune that attains it exactly.
• Practice. Maximal bounds, the L^2 bound for a walk's high-water mark, and convergence diagnoses.
• Hardest. Test the convergence theorem on a doubling betting strategy.

Not sure where to start? Take the ten-question placement test.