Azuma's inequality

Remarks

Proof idea: let $D_k = X_k - X_{k-1}$. Since $E[D_k \mid \mathcal{F}_{k-1}] = 0$ and $D_k \in [-c_k, c_k]$, Hoeffding's lemma applied to the conditional expectation gives $E[e^{\lambda D_k} \mid \mathcal{F}_{k-1}] \le e^{\lambda^2 c_k^2 / 2}$. By induction $E[e^{\lambda (X_n - X_0)}] \le e^{\lambda^2 \sum_k c_k^2 / 2}$, and Markov's inequality with $\lambda = t / \sum_k c_k^2$ gives the bound. For independent centred $D_k$ the result is a form of Hoeffding's inequality, and it is also called the Azuma–Hoeffding inequality. Example: for a simple random walk $X_n = D_1 + \dots + D_n$ with independent fair $\pm 1$ steps, $P(X_n \ge t) \le e^{-t^2 / (2n)}$.

Going deeper

For a student

Azuma's inequality is applied to Doob martingales $X_k = E[f \mid \mathcal{F}_k]$ of a function $f$ of independent variables, revealed one at a time. This gives concentration of quantities such as the chromatic number of a random graph, and it leads to McDiarmid's inequality.