= Two-sided Azuma-Hoeffding inequality
{title2=$\mathbb P(|M_n-M_0|\ge x)\le2e^{-x^2/(2\sum_{k=1}^nc_k^2)}$}
For deterministic bounds $|M_k-M_{k-1}|\le c_k$, the conditional mean-zero increment has exponential moment at most $e^{\theta^2c_k^2/2}$. Iteration, the <Markov inequality> and optimization at $\theta=x/\sum c_k^2$ give each one-sided tail, and the <union bound> gives the displayed inequality. The factor two in the exponent denominator cannot be omitted: a single symmetric increment of size one has absolute deviation one with probability one.
Back to article page
