Azuma's inequality

Azuma's inequality

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 { "X""k" : "k" = 0, 1, 2, 3, ... } is a martingale and

:|X_k - X_{k-1}| < c_k,

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

:P(X_N - X_0 geq t) leq expleft ({-t^2 over 2 sum_{k=1}^{N}c_k^2} ight).

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 2expleft ({-t^2 over 2 sum_{k=1}^{N}c_k^2} ight).

Azuma's inequality applied to the Doob martingale gives the method of bounded differences (MOBD) which is common in the analysis of randomized algorithms.

imple example of Azuma's inequality for coin flips

Let F_i be a sequence of independent and identically distributed random coin flips (i.e., let F_i be equally like to be +1 or −1 independent of the other values of F_i). 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 expleft(frac{-t^2}{2 N} ight).

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

Remark

A similar inequality was proved under weaker assumptions by Sergei Bernstein in 1937.

Hoeffding proved this result for independent variables rather than martingale differences, and also observed that slight modifications of his argument establish the result for martingale differences (see page 18 of his 1963 paper).

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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Azuma — is a name of several places and people:The historical name for Eastern Japan, now called Tohoku. In Gunma prefecture: * Former Azuma Village in Agatsuma District * Former Azuma Village in Sawa District * Former Azuma Village in Seta DistrictIn… …   Wikipedia

  • Inequality — In mathematics, an inequality is a statement about the relative size or order of two objects, or about whether they are the same or not (See also: equality) *The notation a < b means that a is less than b . *The notation a > b means that a is… …   Wikipedia

  • Inequality (mathematics) — Not to be confused with Inequation. Less than and Greater than redirect here. For the use of the < and > signs as punctuation, see Bracket. More than redirects here. For the UK insurance brand, see RSA Insurance Group. The feasible regions… …   Wikipedia

  • Hoeffding's inequality — Hoeffding s inequality, named after Wassily Hoeffding, is a result in probability theory that gives an upper bound on the probability for the sum of random variables to deviate from its expected value.Let :X 1, dots, X n ! be independent random… …   Wikipedia

  • Kazuoki Azuma — (Japanese: 吾妻 一興 Azuma Kazuoki ) is a Japanese mathematician. Azuma s inequality in probability theory is named after him.External links* [http://www.miyakyo u.ac.jp/syomu/sub/math.html#azuma Faculty biography] at Miyagi University of… …   Wikipedia

  • Inégalité d'Azuma — L’inégalité d Azuma, parfois appelée inégalité d Azuma Hoeffding, est une inégalité de concentration concernant les martingales dont les accroissements sont bornés. C est une généralisation de l inégalité de Hoeffding, une inégalité de… …   Wikipédia en Français

  • Doob martingale — A Doob martingale (also known as a Levy martingale) is a mathematical construction of a stochastic process which approximates a given random variable and has the martingale property with respect to the given filtration. It may be thought of as… …   Wikipedia

  • List of inequalities — This page lists Wikipedia articles about named mathematical inequalities. Inequalities in pure mathematics =Analysis= * Askey–Gasper inequality * Bernoulli s inequality * Bernstein s inequality (mathematical analysis) * Bessel s inequality *… …   Wikipedia

  • List of probability topics — This is a list of probability topics, by Wikipedia page. It overlaps with the (alphabetical) list of statistical topics. There are also the list of probabilists and list of statisticians.General aspects*Probability *Randomness, Pseudorandomness,… …   Wikipedia

  • Bernstein inequalities (probability theory) — In probability theory, the Bernstein inequalities are a family of inequalities proved by Sergei Bernstein in the 1920 s and 1930 s. In these inequalities, X 1, X 2, X 3, dots, X n are random variables with zero expected value: mathbf{E} X i = 0.… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”