Azuma's inequality ($\mathbb{P}(M_N-M_0\le -t)\le e^{-t^2/(2{\sum }_i{c}_i^2)}$)

If a martingale has increments with $|M_i-M_{i-1}|\le 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.

For deterministic bounds $|M_k-M_{k-1}|\le c_k$, the conditional mean-zero increment has exponential moment at most $e^{{\theta }^2{c}_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.