azuma's inequality

In probability theory Azuma's inequality 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

|X_k - X_{k-1}| < c_k.

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

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

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

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.

Word Browser