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
- <math>|X_k - X_{k-1}| < c_k.<math>
Then for all positive integers N and all positive reals t,
- <math>P(X_N \geq X_0 + t) \leq \exp\left ({-t^2 \over 2 \sum_{k=1}^{N}c_k^2} \right). <math>
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.