the Azuma martingale method
/ ah-ZOO-mah /
The Azuma martingale method is the engine room beneath McDiarmid and most function-concentration results: a way to prove concentration for quantities that are revealed one piece of information at a time. The idea is to stop thinking of a complicated random variable directly, and instead track how its conditional expectation evolves as you condition on more and more of the underlying randomness. Each newly-revealed piece nudges that conditional expectation by a martingale increment, and if those increments are bounded, the total wander is sharply controlled.
Azuma-Hoeffding's inequality: if (M_0, M_1, ..., M_n) is a martingale (E[M_k | F_{k-1}] = M_{k-1}) whose increments are bounded, |M_k - M_{k-1}| <= c_k almost surely, then P(M_n - M_0 >= t) <= exp(-t^2 / (2 sum_k c_k^2)), with a two-sided factor 2. The proof is the conditional version of the Hoeffding argument: each increment is a bounded, conditionally-mean-zero variable, so its conditional MGF satisfies E[exp(lambda(M_k - M_{k-1})) | F_{k-1}] <= exp(lambda^2 c_k^2 / 2) (a conditional sub-Gaussian bound), and these multiply through the tower property to bound the MGF of M_n - M_0 by exp(lambda^2 sum c_k^2 / 2). Then Chernoff. To concentrate a function f(X_1,...,X_n), one builds the Doob martingale M_k = E[f | X_1, ..., X_k], which interpolates from M_0 = E[f] to M_n = f as the inputs are revealed one by one; bounded differences of f translate directly into bounded martingale increments, recovering McDiarmid.
The power of the method is that it never needs the X_i to be independent in the sum-of-variables sense — it only needs the FILTRATION (the increasing sequence of sigma-algebras) and bounded increments, so it concentrates path functionals of Markov chains, online algorithms, and exploration processes on random graphs (vertex- and edge-exposure martingales). The honest caveat is the same as McDiarmid's: Azuma uses only the worst-case increment bounds c_k, so it is blind to small conditional variance. The sharper Freedman inequality is the martingale analogue of Bernstein — it replaces sum c_k^2 by the predictable quadratic variation sum E[(M_k - M_{k-1})^2 | F_{k-1}], recovering the variance-aware rate for martingales and is what one uses when the increments are usually small but occasionally large.
Reveal the n^2 potential edges of an Erdos-Renyi graph G(n, p) one at a time and let f be the chromatic number. Adding or removing one edge changes the chromatic number by at most 1, so the edge-exposure Doob martingale has increments c_k = 1, and Azuma gives P(|chi - E[chi]| >= t) <= 2 exp(-t^2 / (2 binom(n,2))), so chi concentrates within O(n) of its mean — even though E[chi] itself is hard to compute.
Doob martingales concentrate quantities you cannot even compute the mean of.
Azuma bounds increments in the worst case (c_k), so it ignores conditional variance — use Freedman's inequality (the martingale Bernstein) when increments are usually small. The martingale must have bounded increments almost surely; a bound in probability is not enough.