Optional Stopping Theorem

A fair game stays fair at an honest stopping time — gambler's ruin in two lines.

The idea

Theorem (Optional Stopping Theorem).

Let $M_{n}$ be a martingale and let $T$ be a stopping time: a random time such that whether we have stopped by time $n$ depends only on what has happened up to time $n$, never on anything later. If the increments of $M$ are bounded and the game is certain to end with $\mathbb{E}[T]$ finite, then $\mathbb{E}[M_{T}] = \mathbb{E}[M_{0}].$

A martingale already freezes its mean at every fixed time; the theorem adds that the freeze survives a time chosen while the game is running. No rule for deciding when to walk away — quit while ahead, double the stake after each loss, wait for a streak — turns a fair game into a profitable one, because the decision cannot use information the game has not yet produced. Both hypotheses carry weight. The stopping-time condition rules out the clairvoyant who cashes out one round before every loss; the boundedness conditions rule out schemes that succeed only given unlimited time or unlimited credit, which is where the doubling strategy fails.

Read in the other direction, the theorem is a computing tool: choose a martingale, stop it, and the frozen mean gives one equation for a quantity that would otherwise require solving a recurrence.

Ways to work on it

• Walkthrough. The optional stopping theorem, its sufficient condition, and gambler's ruin as a first application.
• Proof. Prove the theorem for bounded stopping times by telescoping, and watch it fail without the hypotheses.
• Practice. Ruin probabilities and expected durations for fair walks, with even and uneven barriers.
• Hardest. Find the exit probabilities of gambler's ruin when the coin is biased.

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