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

Suppose { X_k : k = 0, 1, 2, 3, ... } is a martingale and

Then for all positive integers N and all positive reals t,

$P(X\_N\; \backslash geq\; X\_0\; +\; t)\; \backslash leq\; \backslash exp\backslash left\; (\{-t^2\; \backslash over\; 2\; \backslash sum\_\{k=1\}^\{N\}c\_k^2\}\; \backslash right).$

Azuma's inequality applied to the Doob martingale gives the method of bounded differences (MOBD) which is common in the analysis of randomized algorithms.

A simple example of Azuma's inequality for coin flips illustrates why this result is interesting.

References

• N. Alon & J. Spencer, The Probabilistic Method. Wiley, New York 1992.
• K. Azuma, "Weighted Sums of Certain Dependent Random Variables". Tôhoku Math. Journ. 19, 357-367 (1967)
• C. McDiarmid, On the method of bounded differences. In Surveys in Combinatorics, London Math. Soc. Lectures Notes 141, Cambridge Univ. Press, Cambridge 1989, 148-188.

Probability theory | Inequalities