Concentration inequality explained

In probability theory, concentration inequalities provide mathematical bounds on the probability of a random variable deviating from some value (typically, its expected value).

The law of large numbers of classical probability theory states that sums of independent random variables, under mild conditions, concentrate around their expectation with a high probability. Such sums are the most basic examples of random variables concentrated around their mean.

Concentration inequalities can be sorted according to how much information about the random variable is needed in order to use them.

Markov's inequality

See main article: Markov's inequality. Let

X be a random variable that is non-negative (almost surely). Then, for every constant a > 0 ,\Pr(X \geq a) \leq (\operatorname{E)/((X)}{a}.)

Note the following extension to Markov's inequality: if

\Phi is a strictly increasing and non-negative function, then\Pr(X \geq a) = \Pr(\Phi (X) \geq \Phi (a)) \leq (\operatorname{E)/((\Phi(X))}{\Phi) (a)}.

Chebyshev's inequality

See main article: Chebyshev's inequality. Chebyshev's inequality requires the following information on a random variable

X :

• The expected value

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

Then, for every constant

a > 0 ,\Pr(|X - \operatorname{E}[X]| \geq a) \leq (\operatorname{Var)/([X]}{a) ^{2},}

or equivalently,

\Pr(|X - \operatorname{E}[X]| \geq a ⋅ \operatorname{Std}[X]) \leq (1)/(a ^{2}) ,

where

\operatorname{Std}[X] is the standard deviation of X .

Chebyshev's inequality can be seen as a special case of the generalized Markov's inequality applied to the random variable

|X - \operatorname{E}[X]| with \Phi(x) = x ^{2} .

Vysochanskij–Petunin inequality

See main article: Vysochanskij–Petunin inequality. Let X be a random variable with unimodal distribution, mean μ and finite, non-zero variance σ². Then, for any $\backslash lambda\; >\; \backslash sqrt\; =\; 1.63299\backslash ldots,$

Pr (\left|X - \mu\right|\geq λ \sigma)\leq (4)/(9λ ^{2}) .

(For a relatively elementary proof see e.g.^[1]).

One-sided Vysochanskij–Petunin inequality

For a unimodal random variable

X and r\geq 0 , the one-sided Vysochanskij-Petunin inequality^[2] holds as follows:Pr (X - E[X]\geq r)\leq \begin{cases} \dfrac{ 4 }{ 9 }\dfrac{\operatorname{Var}(X)}{r ^{2} + \operatorname{Var}(X)} & for r ^{2} \geq\dfrac{ 5 }{ 3 } \operatorname{Var}(X),\\[ 5 pt] \dfrac{ 4 }{ 3 }\dfrac{\operatorname{Var}(X)}{r ^{2} + \operatorname{Var}(X)} - \dfrac{ 1 }{ 3 } & otherwise. \end{cases}

Paley–Zygmund inequality

See main article: Paley–Zygmund inequality. In contrast to most commonly used concentration inequalities, the Paley-Zygmund inequality provides a lower bound on the deviation probability.

Cantelli's inequality

See main article: Cantelli's inequality.

Gauss's inequality

See main article: Gauss's inequality.

Chernoff bounds

See main article: Chernoff bound. The generic Chernoff bound^[3] requires the moment generating function of

X , defined as M ^{tX} _{X(t): = \operatorname{E}\left[e} \right]. It always exists, but may be infinite. From Markov's inequality, for every t> 0 :\Pr(X \geq a) \leq (\operatorname{E)/([e) ^{tX} ]}{e ^{ta} },

and for every

t< 0 :\Pr(X \leq a) \leq (\operatorname{E)/([e) ^{tX} ]}{e ^{ta} }.

There are various Chernoff bounds for different distributions and different values of the parameter

t . See ^[4] for a compilation of more concentration inequalities.

Mill's inequality

See main article: article and Mill's Inequality. Let

Z \sim N( 0 , 1 ) . Then$$\backslash operatorname\; (|Z|\; >\; t)\; \backslash le\; \backslash sqrt\; \backslash frac$$

Bounds on sums of independent bounded variables

See main article: Hoeffding's inequality, Azuma's inequality, McDiarmid's inequality, Bennett's inequality and Bernstein inequalities (probability theory). Let

X _{1,} X _{2,...,X} _{n} be independent random variables such that, for all i:a _{i\leq} X _{i\leq} b _{i} almost surely.c _{i} : = b _{i-a} _{i} \forall i: c _{i} \leq C Let S _{n} be their sum, E _{n} its expected value and V _{n} its variance:S _{n} : = \sum ^{n} _{i =1} X _{i} E _{n} : = \operatorname{E}[S _{n]} = \sum ^{n} _{i =1} \operatorname{E}[X _{i]} V _{n} : = \operatorname{Var}[S _{n]} = \sum ^{n} _{i =1} \operatorname{Var}[X _{i]}

It is often interesting to bound the difference between the sum and its expected value. Several inequalities can be used.

1. Hoeffding's inequality says that:

\Pr\left[|S _{n-E} _{n|>t\right]} \le 2 \exp \left( - (2 t ^{2})/(\sum ^{n} _{i =1} c ^{2} _{i}) \right) \le 2 \exp \left( - (2 t ^{2})/(n C ^{2}) \right)

2. The random variable

S _{n-E} _{n} is a special case of a martingale, and S _{0-E} _{0=0} . Hence, the general form of Azuma's inequality can also be used and it yields a similar bound:\Pr\left[|S _{n-E} _{n|>t\right]} < 2 \exp \left( - (2 t ^{2})/(\sum ^{n} _{i =1} c ^{2} _{i}) \right)< 2 \exp \left( - (2 t ^{2})/(n C ^{2}) \right) This is a generalization of Hoeffding's since it can handle other types of martingales, as well as supermartingales and submartingales. See Fan et al. (2015).^[5] Note that if the simpler form of Azuma's inequality is used, the exponent in the bound is worse by a factor of 4.

3. The sum function,

S _{n=f(X} _{1,...,X} _{n)} , is a special case of a function of n variables. This function changes in a bounded way: if variable i is changed, the value of f changes by at most b _{i-a} _{i<C} . Hence, McDiarmid's inequality can also be used and it yields a similar bound:\Pr\left[|S _{n-E} _{n|>t\right]} < 2 \exp \left( - (2 t ^{2})/(\sum ^{n} _{i =1} c ^{2} _{i}) \right)< 2 \exp \left( - (2 t ^{2})/(n C ^{2}) \right) This is a different generalization of Hoeffding's since it can handle other functions besides the sum function, as long as they change in a bounded way.

4. Bennett's inequality offers some improvement over Hoeffding's when the variances of the summands are small compared to their almost-sure bounds C. It says that:

\Pr\left[|S _{n-E} _{n|} > t \right] \leq 2 \exp\left[ - (V _{n})/(h\left( C ^{2}) (C t)/(V _{n}) \right)\right], where h(u) = ( 1+ u) log ( 1+ u) - u

5. The first of Bernstein's inequalities says that:

\Pr\left[|S _{n-E} _{n|>t\right]} < 2 \exp \left( - (t ^{2/2})/(V _{n} + C ⋅ t/ 3) \right) This is a generalization of Hoeffding's since it can handle random variables with not only almost-sure bound but both almost-sure bound and variance bound.

6. Chernoff bounds have a particularly simple form in the case of sum of independent variables, since

\operatorname{E}[e ^{t ⋅ S _{n}} ] = \prod ^{n} _{i =1} {\operatorname{E}[e ^{t ⋅ X _{i}} ]} .

For example,^[6] suppose the variables

X _{i} satisfy X _{i} \geq E(X _{i)-a} _{i-M} , for 1 \leq i \leq n . Then we have lower tail inequality:\Pr[S _{n} - E _{n} < -λ ]\leq \exp\left( - (λ ^{2})/(2 (V _{n + \sum} ^{n} ^{i =1} a ^{2+ M λ / 3 )} _{i}) \right)

If

X _{i} satisfies X _{i} \leq E(X _{i)+a} _{i+M} , we have upper tail inequality:\Pr[S _{n} - E _{n} > λ ]\leq \exp\left( - (λ ^{2})/(2 (V _{n} + \sum ^{n} _{i =1} a ^{2+ M λ / 3 )} _{i}) \right)

If

X _{i} are i.i.d., |X _{i|} \leq 1 and \sigma ^{2} is the variance of X _{i} , a typical version of Chernoff inequality is:\Pr[|S _{n|} \geq k\sigma]\leq 2 e ^{- k ^{2/4n}} for 0 \leq k\leq 2 \sigma.

7. Similar bounds can be found in: Rademacher distribution#Bounds on sums

Efron–Stein inequality

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

Suppose that

X _{1} ... X _{n} , X _{1'} ... X _{n'} are independent with X _{i'} and X _{i} having the same distribution for all i .

Let

X = (X _{1,...} , X _{n),} X ^{(i)} = (X _{1,} ... , X _{i-1} , X _{i',X} _{i+1} , ... , X _{n).} ThenVar (f(X)) \leq (1)/(2) \sum ^{n} _{i =1} E[(f(X) - f(X ^{(i)} )) ^{2].}

A proof may be found in e.g.,.^[7]

Bretagnolle–Huber–Carol inequality

Bretagnolle–Huber–Carol Inequality bounds the difference between a vector of multinomially distributed random variables and a vector of expected values.^{[8] [9]} A simple proof appears in ^[10] (Appendix Section).

If a random vector

(Z _{1,} Z _{2,} Z _{3,} \ldots , Z _{n)} is multinomially distributed with parameters (p _{1,} p _{2,} \ldots , p _{n)} and satisfies Z _{1} + Z _{2} + ... + Z _{n} = M, then \Pr\left( \sum ^{n} _{i =1} |Z _{i} - M p _{i|} \geq 2 M \varepsilon \right) \leq 2 ^{n} e ^{-2 M\varepsilon ^{2}} .

This inequality is used to bound the total variation distance.

Mason and van Zwet inequality

The Mason and van Zwet inequality^[11] for multinomial random vectors concerns a slight modification of the classical chi-square statistic.

Let the random vector

(N _{1,} \ldots ,N _{k)} be multinomially distributed with parameters n and (p _{1,\ldots} , p _{k)} such that p _{i} > 0 for i < k. Then for every C > 0 and \delta > 0 there exist constants a, b, c > 0 , such that for all n \geq 1 and λ ,p _{1,} \ldots , p _{k-1} satisfying λ > Cn min \{p _{i} | 1 \leq i \leq k -1 \} and \sum ^{k -1} _{i =1} p _{i} \leq 1 - \delta, we have \Pr\left( \sum ^{k -1} _{i =1} ((N _{i - np} ^{2} ^{i)})/(np _{i}) > λ \right) \leq a e ^{bk-cλ} .

Dvoretzky–Kiefer–Wolfowitz inequality

See main article: Dvoretzky–Kiefer–Wolfowitz inequality.

The Dvoretzky–Kiefer–Wolfowitz inequality bounds the difference between the real and the empirical cumulative distribution function.

Given a natural number

n , let X _{1,} X _{2,...,X} _{n} be real-valued independent and identically distributed random variables with cumulative distribution function F(·). Let F _{n} denote the associated empirical distribution function defined byF _{n(x)} = (1 n)/(\sum) ^{n} ^{i =1} 1 _{\{X _{i\leq} x\} },\qquad x\in\mathbb.So F(x) is the probability that a single random variable X is smaller than x , and F _{n(x)} is the average number of random variables that are smaller than x .

Then

\Pr\left(\sup _{x\inR} l (F _{n(x)} - F(x) r ) > \varepsilon \right) \le e ^{-2 n\varepsilon ^{2}} forevery \varepsilon \geq \sqrt{\tfrac 1 { 2 n} ln2 }.

Anti-concentration inequalities

Anti-concentration inequalities, on the other hand, provide an upper bound on how much a random variable can concentrate, either on a specific value or range of values. A concrete example is that if you flip a fair coin

n times, the probability that any given number of heads appears will be less than (1)/(\sqrt{n) }. This idea can be greatly generalized. For example, a result of Rao and Yehudayoff^[12] implies that for any \beta, \delta > 0 there exists some C > 0 such that, for any k , the following is true for at least 2 ^{n(1} values of x \in \{\pm 1 \} ^{n} :\Pr\left(\langle x, Y\rangle = k\right) \le (C)/(\sqrt{n) },where Y is drawn uniformly from \{\pm 1 \} ^{n} .

Such inequalities are of importance in several fields, including communication complexity (e.g., in proofs of the gap Hamming problem^[13]) and graph theory.^[14]

An interesting anti-concentration inequality for weighted sums of independent Rademacher random variables can be obtained using the Paley–Zygmund and the Khintchine inequalities.^[15]

External links

• Karthik Sridharan, "A Gentle Introduction to Concentration Inequalities"  —Cornell University

Notes and References

1. https://www.jstor.org/stable/pdf/2684253.pdf Pukelsheim, F., 1994. The Three Sigma Rule. The American Statistician, 48(2), pp. 88–91
2. Mercadier . Mathieu . Strobel . Frank . 2021-11-16 . A one-sided Vysochanskii-Petunin inequality with financial applications . European Journal of Operational Research . en . 295 . 1 . 374–377 . 10.1016/j.ejor.2021.02.041 . 0377-2217.
3. Book: Probability and Computing: Randomized Algorithms and Probabilistic Analysis . Cambridge University Press . Mitzenmacher, Michael . Upfal, Eli . 2005 . 0-521-83540-2.
4. News: One Hundred Statistics and Probability Inequalities . Slagle, N.P. . 2012. 2102.07234 .
5. Exponential inequalities for martingales with applications. X. . Fan. I. . Grama . Q. . Liu . Electronic Journal of Probability . Electron. J. Probab. 20. 2015. 20 . 1–22. 10.1214/EJP.v20-3496. 1311.6273.
6. Web site: Chung. Fan. Fan Chung . Linyuan . Lu . Old and new concentration inequalities. Complex Graphs and Networks . . 2010 . August 14, 2018.
7. Boucheron . Stphane . Lugosi . Gbor . Bousquet . Olivier . Concentration inequalities . Advanced Lectures on Machine Learning: ML Summer Schools 2003, Canberra, Australia, February 2–14, 2003, Tbingen, Germany, August 4–16, 2003, Revised Lectures . 2004 . 208–240 . Springer.
8. Book: Bretagnolle, Jean . Lois empiriques et distance de Prokhorov . Huber-Carol, Catherine . 1978 . 978-3-540-08761-8 . Lecture Notes in Mathematics . 649 . 332–341 . 10.1007/BFb0064609.
9. Book: van der Vaart, A.W.. Wellner, J.A.. Weak convergence and empirical processes: With applications to statistics. Springer Science & Business Media. 1996.
10. Yuto Ushioda. Masato Tanaka. Tomomi Matsui. Monte Carlo Methods for the Shapley–Shubik Power Index. Games . 13 . 3 . 44 . 2022. 10.3390/g13030044 . free . 2101.02841 .
11. Mason, David M.. Willem R. Van Zwet . A Refinement of the KMT Inequality for the Uniform Empirical Process . The Annals of Probability . 15 . 3 . 1987 . 871–884 . 10.1214/aop/1176992070 . free .
12. News: Anti-concentration in most directions . Electronic Colloquium on Computational Complexity . Rao, Anup . Yehudayoff, Amir . 2018.
13. News: The Communication Complexity of Gap Hamming Distance . . Sherstov, Alexander A. . 2012.
14. Anticoncentration for subgraph statistics . Journal of the London Mathematical Society . 99 . 3 . 757–777 . Matthew Kwan . Benny Sudakov . Tuan Tran . 2018. 10.1112/jlms.12192 . 2018arXiv180705202K . 1807.05202 . 54065186 .
15. 0909.2586v1. Veraar. Mark. On Khintchine inequalities with a weight. math.PR. 2009.