Azuma's inequality

From Wikipedia, the free encyclopedia

You have new messages (last change).
It has been suggested that this article or section be merged into Hoeffding's inequality. (Discuss)


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

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

| Xk − Xk − 1 | < ck.

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

P(|X_N - X_0| \geq t) \leq 2\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 randomized algorithms.

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

[edit] 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.
Retrieved from "http://en.wikipedia.org../../../a/z/u/Azuma%27s_inequality.html"