Azuma–Hoeffding 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 { X_k : k = 0, 1, 2, 3, ... } is a martingale (or super-martingale) and

almost surely. Then for all positive integers N and all positive reals t,

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

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

Azuma's inequality applied to the Doob martingale gives McDiarmid's inequality which is common in the analysis of randomized algorithms.

Let F_i be a sequence of independent and identically distributed random coin flips (i.e., let F_i be equally likely to be −1 or 1 independent of the other values of F_i). Defining ${\displaystyle X_{i}=\sum _{j=1}^{i}F_{j}}$ yields a martingale with |X_k − X_k−1| ≤ 1, allowing us to apply Azuma's inequality. Specifically, we get

...
Wikipedia