Azuma's inequality

In probability theory Azuma's inequality gives a concentration result for the values of martingales that have bounded differences.

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

[itex]|X_k - X_{k-1}| < c_k.[itex]

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

[itex]P(X_N \geq X_0 + t) \leq \exp\left ({-t^2 \over 2 \sum_{k=1}^{N}c_k^2} \right). [itex]

Azuma's inequality applied to the Doob martingale gives the method of bounded differences (MOBD) which is common in the analysis of random 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.
• 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.

• Art and Cultures
• Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
• Space and Astronomy