Azuma's inequality

From Wikipedia, the free encyclopedia

In probability theory, the Azuma-Hoeffding inequality (named after Kazuoki Azuma and Wassily Hoeffding) 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,

almost surely. Then for all positive integers N and all positive reals t,

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

Applying Azuma's inequality to the martingale -X and applying the union bound allows one to obtain a two-sided bound:

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.

[edit] Simple example of Azuma's inequality for coin flips

Let Fi be a sequence of independent and identically distributed random coin flips (i.e., let Fi be equally like to be +1 or −1 independent of the other values of Fi). Defining X_i = \sum_{j=1}^i F_j yields a martingale with |X_{k}-X_{k-1}|\leq 1, allowing us to apply Azuma's inequality. Specifically, we get

\Pr[X_N > X_0 + t] \leq \exp\left(\frac{-t^2}{2 N}\right).

For example, if we set t proportional to N, then this tells us that although the maximum possible value of XN scales linearly with N, the probability that the sum scales linearly with N decreases exponentially fast with N.

[edit] Remark

A similar inequality was proved under weaker assumptions by Sergei Bernstein in 1937. Hoeffding's result was derived in the special case of sums of independent random variables rather than martingales.

[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)
  • S.N. Bernstein, "On certain modifications of Chebyshev's inequality", Doklady Akad. Nauk SSSR, 17, n. 6, (1937), 275-277 (vol. 4, item 22 in the collected works)
  • 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.
  • W. Hoeffding, "Probability inequalities for sums of bounded random variables", J. Amer. Statist. Assoc. 58, 13-30, 1963 MR0144363
  • A. P. Godbole and P. Hitczenko, "Beyond the method of bounded differences", DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 41, 43-58, 1998 MR1630408