Azuma's inequality

In probability theory, the Azuma–Hoeffding inequality (named after Kazuoki Azuma and Wassily Hoeffding) gives a concentration result for the values of martingales that have bounded differences.

Suppose ${\displaystyle \{X_{k}:k=0,1,2,3,\dots \}}$ is a martingale (or super-martingale) and

${\displaystyle |X_{k}-X_{k-1}|\leq c_{k},\,}$

almost surely. Then for all positive integers N and all positive reals ${\displaystyle \epsilon }$,

${\displaystyle {\text{P}}(X_{N}-X_{0}\geq \epsilon )\leq \exp \left({-\epsilon ^{2} \over 2\sum _{k=1}^{N}c_{k}^{2}}\right).}$

And symmetrically (when X_k is a sub-martingale):

${\displaystyle {\text{P}}(X_{N}-X_{0}\leq -\epsilon )\leq \exp \left({-\epsilon ^{2} \over 2\sum _{k=1}^{N}c_{k}^{2}}\right).}$

If X is a martingale, using both inequalities above and applying the union bound allows one to obtain a two-sided bound:

${\displaystyle {\text{P}}(|X_{N}-X_{0}|\geq \epsilon )\leq 2\exp \left({-\epsilon ^{2} \over 2\sum _{k=1}^{N}c_{k}^{2}}\right).}$