Azuma's inequality Guide, Meaning , Facts, Information and Description

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

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

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.

This is an Article on Azuma's inequality. Page Contains Information, Facts Details or Explanation Guide About Azuma's inequality

	Web www.E-paranoids.com