= Azuma-Hoeffding inequality
{c}
{title2=$\mathbb P(M_N-M_0\leq-t)\leq e^{-t^2/(2\sum_i c_i^2)}$}
{wiki=Azuma's_inequality}
= Azuma's inequality
{c}
{synonym}
= Azuma inequality
{c}
{synonym}
If a <martingale> has increments with $|M_i-M_{i-1}|\leq c_i$ almost surely for deterministic $c_i$, then each one-sided deviation of magnitude $t>0$ from $M_0$ has <probability> at most $\exp(-t^2/(2\sum_i c_i^2))$. If all $c_i$ vanish, the <martingale> is constant. The inequality gives concentration from bounded increments without requiring independent increments.
Back to article page
