Concentration inequality

Concentration inequality

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.

Contents

Markov's inequality

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

\Pr(|X| \geq a) \leq \frac{\textrm{E}(|X|)}{a}.

Proof can be found here.

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

\Pr(X \geq a) = \Pr(\Phi (X) \geq \Phi (a)) \leq \frac{\textrm{E}(\Phi(X))}{\Phi (a)}.

Chebyshev's inequality

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

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

\Pr(|X-\textrm{E}(X)| \geq a) \leq \frac{\textrm{Var}(X)}{a^2},

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

 \operatorname{Var}(X) = \operatorname{E}[(X - \operatorname{E}(X) )^2].

Asymptotic behavior of binomial distribution

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

 f(k;n,p) = \Pr(K = k) = {n\choose k}p^k(1-p)^{n-k}.

Let S_n=\sum_{i=1}^n X_i and Xi's are i.i.d. Bernoulli random variables with parameter p. Sn follows the binomial distribution with parameter with parameter n and p. Central Limit Theorem suggests when n \to \infty, Sn is approximately normally distributed with mean np and variance np(1 − p), and


    \lim_{n\to\infty} \Pr[ a\sigma <S_n- np < b\sigma] = \int_a^b \frac{1}{\sqrt{2\pi}}e^{-x^2/2} dx

For p=\frac{\lambda}{n}, where λ is a constant, the limit distribution of binomial distribution B(n,p) is the Poisson distribution P(λ)

General Chernoff inequality

A Chernoff bound gives exponentially decreasing bounds on tail distributions of sums of independent random variables. [1] Let Xi denote independent but not necessarily identical random variables, satisfying X_i \geq E(X_i)-a_i-M, for 1 \leq i \leq n.

X = \sum_{i=1}^n X_i

we have lower tail inequality:


\Pr[X \leq E(X)-\lambda]\leq e^{-\frac{\lambda^2}{2(Var(X)+\sum_{i=1}^n a_i^2+M\lambda/3)}}

If Xi satisfies X_i \leq E(X_i)+a_i+M, we have upper tail inequality:


\Pr[X \geq E(X)+\lambda]\leq e^{-\frac{\lambda^2}{2(Var(X)+\sum_{i=1}^n a_i^2+M\lambda/3)}}

If Xi are i.i.d., |X_i| \leq 1 and σ2 is the variance of Xi. A typical version of Chernoff Inequality is:


\Pr[|X| \geq k\sigma]\leq 2e^{-k^2/4}

Hoeffding's inequality

Hoeffding's inequality can be stated as follows:

If :X_1, \dots, X_n \! are independent. Assume that the Xi are almost surely bounded; that is, assume for 1 \leq i \leq n that

\Pr(X_i \in [a_i, b_i]) = 1. \!

Then, for the empirical mean of these variables

\overline{X} = \frac{X_1 + \cdots + X_n}{n}

we have the inequalities (Hoeffding 1963, Theorem 2 [2]):

\Pr(\overline{X} - \mathrm{E}[\overline{X}] \geq t) \leq \exp \left( - \frac{2t^2n^2}{\sum_{i=1}^n (b_i - a_i)^2} \right),\!
\Pr(|\overline{X} - \mathrm{E}[\overline{X}]| \geq t) \leq 2\exp \left( - \frac{2t^2n^2}{\sum_{i=1}^n (b_i - a_i)^2} \right),\!

Bennett's inequality

Bennett's inequality was proved by George Bennett of the University of New South Wales in 1962.[3]

Let X1, … Xn be independent random variables, and assume (for simplicity but without loss of generality) they all have zero expected value. Further assume |Xi| ≤ a almost surely for all i, and let

 \sigma^2 = \frac1n \sum_{i=1}^n \operatorname{Var}(X_i).

Then for any t ≥ 0,

\Pr\left( \sum_{i=1}^n X_i > t \right) \leq
\exp\left( - \frac{n\sigma^2}{a^2} h\left(\frac{at}{n\sigma^2} \right)\right),

where h(u) = (1 + u)log(1 + u) – u.[4]

Bernstein's inequality

Bernstein inequalities give bounds on the probability that the sum of random variables deviates from its mean. In the simplest case, let X1, ..., Xn be independent Bernoulli random variables taking values +1 and −1 with probability 1/2, then for every positive ε,

 \mathbf{P} \left\{\left|\;\frac{1}{n}\sum_{i=1}^n X_i\;\right| > \varepsilon \right\} \leq 2\exp \left\{ - \frac{n\varepsilon^2}{ 2 (1 + \varepsilon/3) } \right\}.

Efron–Stein nequality

The Efron–Stein inequality (or influence inequality, or MG bound on variance) bounds the variance of a general function.

Suppose that X_1 \dots X_n, X_1^' \dots X_n^' are independent with X_i^' and Xi having the same distribution for all i.

Let X = (X_1,\dots , X_n), X^{(i)} = (X_1, \dots , X_{i-1}, X_i^',X_{i+1}, \dots , X_n). Then


\mathrm{Var}(f(X)) \leq \frac{1}{2} \sum_{i=1}{n} E[(f(X)-f(X^{(i)}))^2].

References

  1. ^ Chung, Fan. "Old and New Concentration Inequalities". Old and New Concentration Inequalities. http://www.math.ucsd.edu/~fan/complex/ch2.pdf. Retrieved 2010. 
  2. ^ Wassily Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58 (301): 13–30, March 1963. (JSTOR)
  3. ^ Bennett, G. (1962). "Probability Inequalities for the Sum of Independent Random Variables". Journal of the American Statistical Association 57 (297): 33–45. doi:10.2307/2282438.  edit
  4. ^ Devroye, Luc; Lugosi, Gábor (2001). Combinatorial methods in density estimation. Springer. p. 11. ISBN 9780387951171. http://books.google.com/books?id=jvT-sUt1HZYC&pg=PA11. 

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Concentration of measure — In mathematics, concentration of measure (about a median) is a principle that is applied in measure theory, probability and combinatorics, and has consequences for other fields such as Banach space theory. Informally, it states that A random… …   Wikipedia

  • Concentration of wealth — often refers to: Wealth condensation Related: Distribution of wealth Income disparity Economic inequality Income inequality metrics International inequality This disambiguation page lists articles associated with …   Wikipedia

  • Wealth concentration — Wealth Concentration, also known as wealth condensation, is a process by which, in certain conditions, newly created wealth tends to become concentrated in the possession of already wealthy individuals or entities, a form of preferential… …   Wikipedia

  • Income inequality metrics — The concept of inequality is distinct from that of poverty[1] and fairness. Income inequality metrics or income distribution metrics are used by social scientists to measure the distribution of income, and economic inequality among the… …   Wikipedia

  • Market concentration — In economics, market concentration is a function of the number of firms and their respective shares of the total production (alternatively, total capacity or total reserves) in a market. Alternative terms are Industry concentration and Seller… …   Wikipedia

  • Social inequality — refers to a lack of social equality, where individuals in a society do not have equal social status. Areas of potential social inequality include voting rights, freedom of speech and assembly, the extent of property rights and access to education …   Wikipedia

  • Gaussian isoperimetric inequality — The Gaussian isoperimetric inequality, proved by Boris Tsirelson and Vladimir Sudakov and independently by Christer Borell, states that among all sets of given Gaussian measure in the n dimensional Euclidean space, half spaces have the minimal… …   Wikipedia

  • 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 …   Wikipedia

  • Ventilation-perfusion inequality — (also known as Ventilation Perfusion Mismatch) is when certain groups of alveoli experience a decrease in ventilation which causes a higher concentration of carbon dioxide (CO2) and a lower concentration of oxygen (O2). The inequality refers to… …   Wikipedia

  • Michel Talagrand — Born February 1952 (age 59) Nationality …   Wikipedia

Share the article and excerpts

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