the Azuma-Hoeffding inequality
/ ah-ZOO-mah HUF-ding /
Hoeffding's inequality assumes the contributions you are summing are independent. But many real processes build up step by step, where each step can depend on the past — a running gambling balance, a quantity revealed one piece of data at a time, an algorithm's state updating. If the running total is a 'fair game' (a martingale) whose individual steps are bounded, can we still prove it stays concentrated? The Azuma-Hoeffding inequality says yes.
Setup: let M_0, M_1, ..., M_n be a martingale, meaning each step is fair in the sense that, given the past, the expected next value equals the current value (E[M_k given the history up to k-1] = M_{k-1}). Suppose each increment is bounded: |M_k - M_{k-1}| <= c_k. Then P(M_n - M_0 >= t) <= exp( -t^2 / (2 sum of c_k^2) ), with the same bound for the lower tail. It looks exactly like Hoeffding, with the squared step-sizes c_k^2 playing the role of the squared ranges — but it no longer requires independence, only the martingale (fair-game) and bounded-step conditions.
This is the workhorse for concentration in dependent, sequential settings. The standard recipe: take any quantity that depends on many inputs, reveal the inputs one at a time, and let M_k be the expected final value given the first k inputs (a 'Doob martingale'); if revealing one input cannot change the conditional expectation by more than c_k, Azuma delivers a concentration bound. McDiarmid's bounded-differences inequality is precisely this idea packaged for functions of independent inputs. The honest caveat: you must verify the martingale property and a genuine bound on every step, which can be the hard part.
Shuffle a deck and reveal cards one by one; let M_k be the expected final number of red-before-black adjacencies given the first k cards seen. Each revealed card shifts this expectation by at most a small c. Azuma then shows the final count is sharply concentrated around its mean, even though the cards are highly dependent (no replacement).
Concentration without independence: a fair game with bounded steps stays near where it started.
Azuma needs a true martingale (E[next given past] = current) and a hard bound on every increment. Drop the martingale property or let one step be unbounded and the bound collapses.