McDiarmid's inequality

Remarks

Proof idea: let $Z_k = E[Y \mid X_1, \dots, X_k]$, the Doob martingale of $Y$. By independence and the bounded differences property, given $X_1, \dots, X_{k-1}$ the increment $Z_k - Z_{k-1}$ lies in an interval of length $c_k$. Hoeffding's lemma then bounds its conditional moment-generating function by $e^{\lambda^2 c_k^2 / 8}$, and the argument of Azuma's inequality finishes the proof. Example: throw $m$ balls independently into $N$ bins and let $Y$ be the number of empty bins. Moving one ball changes $Y$ by at most $1$, so $P(\abs{Y - E[Y]} \ge t) \le 2 e^{-2t^2 / m}$. With $f(x) = x_1 + \dots + x_n$ and $X_i \in [a_i, b_i]$, one gets Hoeffding's inequality. Independence is needed: if $X_1 = \dots = X_n$ is a fair $0/1$ coin and $f$ is the sum, then $c_i = 1$ but $Y \in \set{0, n}$, so $P(Y - E[Y] \ge n/2) = \frac{1}{2}$, far above $e^{-n/2}$.

Going deeper

For a student

This is the method of bounded differences. It is often the quickest way to prove concentration in random graphs, randomized algorithms and learning theory, for instance for generalization bounds through Rademacher complexity. It only gives concentration around the mean; estimating the mean itself needs other arguments. Sharper results for convex Lipschitz functions follow from Talagrand's concentration inequality.