Azuma's inequality
In probability theory Azuma's inequality gives a concentration result for the values of martingales that have bounded differences. Formally, it says that:
if is a martingale, and if
.
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, Cambrige Univ. Press, Cambridge 1989, 148-188.
