Azuma's inequality
Encyclopedia
In probability theory
, the Azuma–Hoeffding inequality (named after Kazuoki Azuma
and Wassily Hoeffding
) gives a concentration result for the values of martingale
s that have bounded differences.
Suppose { Xk : k = 0, 1, 2, 3, ... } is a martingale
(or super-martingale
) and
almost surely
. Then for all positive integers N and all positive reals
t,
And symmetrically (when Xk is a sub-martingale):
If X is a martingale, using both inequalities above and applying the union bound allows one to obtain a two-sided bound:
Azuma's inequality applied to the Doob martingale
gives the method of bounded differences (MOBD) which is common in the analysis of randomized algorithm
s.
yields a martingale
with |Xk − Xk−1| ≤ 2, allowing us to apply Azuma's inequality. Specifically, we get
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.
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).
Probability theory
Probability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...
, the Azuma–Hoeffding inequality (named after Kazuoki Azuma
Kazuoki Azuma
is a Japanese mathematician. Azuma's inequality in probability theory is named after him.-External links:* at Miyagi University of Education...
and Wassily Hoeffding
Wassily Hoeffding
Wassily Hoeffding was an American statistician and probabilist...
) gives a concentration result for the values of martingale
Martingale (probability theory)
In probability theory, a martingale is a model of a fair game where no knowledge of past events can help to predict future winnings. In particular, a martingale is a sequence of random variables for which, at a particular time in the realized sequence, the expectation of the next value in the...
s that have bounded differences.
Suppose { Xk : k = 0, 1, 2, 3, ... } is a martingale
Martingale (probability theory)
In probability theory, a martingale is a model of a fair game where no knowledge of past events can help to predict future winnings. In particular, a martingale is a sequence of random variables for which, at a particular time in the realized sequence, the expectation of the next value in the...
(or super-martingale
Martingale (probability theory)
In probability theory, a martingale is a model of a fair game where no knowledge of past events can help to predict future winnings. In particular, a martingale is a sequence of random variables for which, at a particular time in the realized sequence, the expectation of the next value in the...
) and
almost surely
Almost surely
In probability theory, one says that an event happens almost surely if it happens with probability one. The concept is analogous to the concept of "almost everywhere" in measure theory...
. Then for all positive integers N and all positive reals
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
t,
And symmetrically (when Xk is a sub-martingale):
If X is a martingale, using both inequalities above and applying the union bound allows one to obtain a two-sided bound:
Azuma's inequality applied to the Doob martingale
Doob martingale
A Doob 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...
gives the method of bounded differences (MOBD) which is common in the analysis of randomized algorithm
Randomized algorithm
A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...
s.
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 likely to be -1 or 1 independent of the other values of Fi). Defining yields a martingaleMartingale (probability theory)
In probability theory, a martingale is a model of a fair game where no knowledge of past events can help to predict future winnings. In particular, a martingale is a sequence of random variables for which, at a particular time in the realized sequence, the expectation of the next value in the...
with |Xk − Xk−1| ≤ 2, allowing us to apply Azuma's inequality. Specifically, we get
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.
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).
See also
- McDiarmid's inequality
- Markov inequality
- Hoeffding's inequalityHoeffding's inequalityIn probability theory, Hoeffding's inequality provides an upper bound on the probability for the sum of random variables to deviate from its expected value. Hoeffding's inequality was proved by Wassily Hoeffding.LetX_1, \dots, X_n \!...
- Chebyshev's inequalityChebyshev's inequalityIn probability theory, Chebyshev’s inequality guarantees that in any data sample or probability distribution,"nearly all" values are close to the mean — the precise statement being that no more than 1/k2 of the distribution’s values can be more than k standard deviations away from the mean...
- Bernstein inequalities (probability theory)
- Bennett's inequalityBennett's inequalityIn probability theory, Bennett's inequality provides an upper bound on the probability that the sum of independent random variables deviates from its expected value by more than any specified amount...