Azuma-Hoeffding

Hoeffding for martingales — concentration without independence.

The idea

Theorem (Azuma-Hoeffding inequality).

Let $M_{0}, M_{1}, \ldots, M_{n}$ be a martingale, so that each term is the conditional mean of the next, $\mathbb{E}[M_{k} \mid M_{0}, \ldots, M_{k-1}] = M_{k-1}$, and suppose it has bounded differences $|M_{k} - M_{k-1}| \leq c_{k}$ almost surely. Then for every $t > 0$, $\mathbb{P}(|M_{n} - M_{0}| \geq t) \leq 2\exp\!\left(-\frac{t^{2}}{2\sum_{k=1}^{n} c_{k}^{2}}\right).$

Hoeffding's inequality gives a bound of this shape for sums of independent bounded terms. Many quantities are not such sums: a gambler's fortune, a graph parameter revealed one vertex at a time, an algorithm's running total — each depends at every step on everything that came before. The martingale condition replaces independence with a weaker demand. The increments may depend on the past in any way at all, provided that, whatever has already happened, the next increment has conditional mean zero and size at most $c_{k}$. The figure shows the condition itself: from the current fortune $M_{n}$ the possible futures fan out, but their conditional average never leaves the level line through $M_{n}$.

The increments enter the bound only through $\sum_{k} c_{k}^{2}$, so a long walk of small steps concentrates far more tightly than a short walk of large steps covering the same distance.

Ways to work on it

• Walkthrough. Bound a ± 1 random walk's deviation, then meet the Doob martingale.
• Practice. Apply Azuma's inequality to bound a random walk's deviation.
• Hardest. Show that a random graph's chromatic number concentrates around its mean.

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