Jump to content

Concentration inequality

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Duananzhao (talk | contribs) at 00:35, 9 June 2011. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In mathematics, concentration inequalities provide probability bounds on how a random variable deviates from some value (e.g. its expectation). The laws of large numbers of classical probability theory state that sums of independent random variables are, under very mild conditions, close to their expectation with a large probability. Such sums are the most basic examples of random variables concentrated around their mean. Recent results shows that such behavior is shared by other functions of independent random variables.

Markov's inequality

If X is any random variable and a > 0, then

Proof can be found here.

We can extend Markov's inequality to a strictly increasing and non-negative function . We have

Chebyshev's inequality

Chebyshev's inequality is a special case of generalized Markov's inequality when

If X is any random variable and a > 0, then

Where Var(X) is the variance of X, defined as:

Asymptotic Behavior of Binomial Distribution

If a random variable X follows the binomial distribution with parameter and . The probability of getting exact successes in trials is given by the probability mass function

Let and 's are i.i.d. Bernoulli random variables with parameter . follows the binomial distribution with parameter with parameter and . Central Limit Theorem suggests when , is approximately normally distributed with mean and variance , and