en>Chris the speller: /* Flamed plasma processing */replaced: cost effective → cost-effective using AWB

2013-09-26T16:17:41Z

Flamed plasma processing: replaced: cost effective → cost-effective using AWB

New page

In [[mathematics]], '''concentration inequalities''' provide probability bounds on how a [[random variable]] deviates from some value (e.g. its [[Expectation (epistemic)|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

: <math>\Pr(|X| \geq a) \leq \frac{\textrm{E}(|X|)}{a}.</math>

Proof can be found [[Markov's inequality|here]].

We can extend Markov's inequality to a strictly increasing and non-negative function <math>\Phi</math>. We have

:<math>\Pr(X \geq a) = \Pr(\Phi (X) \geq \Phi (a)) \leq \frac{\textrm{E}(\Phi(X))}{\Phi (a)}.</math>

==Chebyshev's inequality==

[[Chebyshev's inequality]] is a special case of generalized Markov's inequality when <math>\Phi = x^2</math>

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

:<math>\Pr(|X-\textrm{E}(X)| \geq a) \leq \frac{\textrm{Var}(X)}{a^2},</math>

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

:<math> \operatorname{Var}(X) = \operatorname{E}[(X - \operatorname{E}(X) )^2]. </math>

==Asymptotic behavior of binomial distribution==

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

:<math> f(k;n,p) = \Pr(K = k) = {n\choose k}p^k(1-p)^{n-k}.</math>

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

: <math>
\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
</math>

For <math>p=\frac{\lambda}{n}</math>, where <math>\lambda</math> is a constant, the limit distribution of binomial distribution <math>B(n,p)</math> is the [[Poisson distribution]] <math>P(\lambda)</math>

==General Chernoff inequality==

A [[Chernoff bound]] gives exponentially decreasing bounds on tail distributions of sums of independent random variables.<ref name=ChungChernoff>{{cite web|last=Chung|first=Fan|title=Old and New Concentration Inequalities|url=http://www.math.ucsd.edu/~fan/complex/ch2.pdf|work=Old and New Concentration Inequalities|accessdate=2010}}</ref> Let <math>X_i</math> denote independent but not necessarily identical random variables, satisfying <math>X_i \geq E(X_i)-a_i-M</math>, for <math>1 \leq i \leq n</math>.

: <math>X = \sum_{i=1}^n X_i</math>

we have lower tail inequality:

: <math>
\Pr[X \leq E(X)-\lambda]\leq e^{-\frac{\lambda^2}{2(Var(X)+\sum_{i=1}^n a_i^2+M\lambda/3)}}
</math>
If <math>X_i</math> satisfies <math>X_i \leq E(X_i)+a_i+M</math>, we have upper tail inequality:

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

If <math>X_i</math> are ''i.i.d.'', <math>|X_i| \leq 1</math> and <math>\sigma^2</math> is the variance of <math>X_i</math>. A typical version of Chernoff Inequality is:
: <math>
\Pr[|X| \geq k\sigma]\leq 2e^{-k^2/4n}
</math> for <math>
0 \leq k\leq 2\sigma
</math>

==Hoeffding's inequality==

[[Hoeffding's inequality]] can be stated as follows:

If :<math>X_1, \dots, X_n \!</math> are independent. Assume that the <math>X_i</math> are [[almost sure]]ly bounded; that is, assume for <math>1 \leq i \leq n</math> that
:<math>\Pr(X_i \in [a_i, b_i]) = 1. \!</math>

Then, for the empirical mean of these variables

:<math>\overline{X} = \frac{X_1 + \cdots + X_n}{n} </math>

we have the inequalities (Hoeffding 1963, Theorem 2 <ref>Wassily Hoeffding, Probability inequalities for sums of bounded random variables, ''Journal of the American Statistical Association'' '''58''' (301): 13–30, March 1963. ([http://links.jstor.org/sici?sici=0162-1459%28196303%2958%3A301%3C13%3APIFSOB%3E2.0.CO%3B2-D JSTOR])
</ref>):

:<math>\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),\!</math>
:<math>\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),\!</math>

==Bennett's inequality==

[[Bennett's inequality]] was proved by George Bennett of the [[University of New South Wales]] in 1962.<ref name=bennett>{{cite jstor|2282438}}</ref>

Let
{{math|''X''1, … ''X''''n''}}
be [[independent random variables]], and assume (for simplicity but [[without loss of generality]]) they all have zero expected value. Further assume {{math|{{!}}''X''''i''{{!}} ≤ ''a''}} [[almost surely]] for all {{math|''i''}}, and let
:<math> \sigma^2 = \frac1n \sum_{i=1}^n \operatorname{Var}(X_i).</math>
Then for any {{math|''t'' ≥ 0}},

:<math>\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),</math>

where {{math|''h''(''u'') {{=}} (1 + ''u'')log(1 + ''u'') – ''u''}},<ref name=devroye>{{cite book|title=Combinatorial methods in density estimation| first1=Luc |last1=Devroye| authorlink1=Luc Devroye| first2=Gábor |last2=Lugosi| publisher=[[Springer (publisher)|Springer]]| year=2001| isbn=978-0-387-95117-1| page=11| url=http://books.google.com/books?id=jvT-sUt1HZYC&pg=PA11}}</ref> see also Fan et al. (2012) <ref name=fan>{{cite journal |title=Hoeffding's inequality for supermartingales| first1=X. |last1=Fan| first2=I. |last2=Grama | publisher=Stochastic Process. Appl. 122| year=2012| pages=3545–3559| url=http://www.sciencedirect.com/science/article/pii/S0304414912001378}}</ref> for martingale version of Bennett's inequality and its improvement.

==Bernstein's inequality==
[[Bernstein inequalities (probability theory)|Bernstein inequalities]] give bounds on the probability that the sum of random variables deviates from its mean. In the simplest case, let ''X''1, ..., ''X''''n'' be independent Bernoulli random variables taking values +1 and −1 with probability 1/2, then for every positive <math>\varepsilon</math>,

:<math> \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\}.</math>

==Efron–Stein inequality==

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

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

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

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

==References==

{{reflist}}

[[Category:Inequality]]

Polymeric surface - Revision history

en>Chris the speller: /* Flamed plasma processing */replaced: cost effective → cost-effective using AWB