Concentration inequality

Let ${\displaystyle X}$ be a random variable that is non-negative (almost surely). Then, for every constant ${\displaystyle a>0}$,

${\displaystyle \Pr(X\geq a)\leq {\frac {\operatorname {E} (X)}{a}}.}$

Note the following extension to Markov's inequality: if ${\displaystyle \Phi }$ is a strictly increasing and non-negative function, then

${\displaystyle \Pr(X\geq a)=\Pr(\Phi (X)\geq \Phi (a))\leq {\frac {\operatorname {E} (\Phi (X))}{\Phi (a)}}.}$

Chebyshev's inequality requires the following information on a random variable ${\displaystyle X}$:

• The expected value ${\displaystyle \operatorname {E} [X]}$ is finite.
• The variance ${\displaystyle \operatorname {Var} [X]=\operatorname {E} [(X-\operatorname {E} [X])^{2}]}$ is finite.

Then, for every constant ${\displaystyle a>0}$,

${\displaystyle \Pr(|X-\operatorname {E} [X]|\geq a)\leq {\frac {\operatorname {Var} [X]}{a^{2}}},}$

or equivalently,

${\displaystyle \Pr(|X-\operatorname {E} [X]|\geq a\cdot \operatorname {Std} [X])\leq {\frac {1}{a^{2}}},}$

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

Chebyshev's inequality can be seen as a special case of the generalized Markov's inequality applied to the random variable ${\displaystyle |X-\operatorname {E} [X]|}$ with ${\displaystyle \Phi (x)=x^{2}}$.

Let X be a random variable with unimodal distribution, mean μ and finite, non-zero variance σ². Then, for any ${\textstyle \lambda >{\sqrt {\frac {8}{3}}}=1.63299\ldots ,}$

${\displaystyle {\text{Pr}}(\left|X-\mu \right|\geq \lambda \sigma )\leq {\frac {4}{9\lambda ^{2}}}.}$

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

For a unimodal random variable ${\displaystyle X}$ and ${\displaystyle r\geq 0}$, the one-sided Vysochanskij-Petunin inequality[2] holds as follows:

${\displaystyle {\text{Pr}}(X-E[X]\geq r)\leq {\begin{cases}{\dfrac {4}{9}}{\dfrac {\operatorname {Var} (X)}{r^{2}+\operatorname {Var} (X)}}&{\text{for }}r^{2}\geq {\dfrac {5}{3}}\operatorname {Var} (X),\\[5pt]{\dfrac {4}{3}}{\dfrac {\operatorname {Var} (X)}{r^{2}+\operatorname {Var} (X)}}-{\dfrac {1}{3}}&{\text{otherwise.}}\end{cases}}}$

The generic Chernoff bound[3]^: 63–65 requires the moment generating function of ${\displaystyle X}$, defined as ${\displaystyle M_{X}(t):=\operatorname {E} \!\left[e^{tX}\right].}$ It always exists, but may be infinite. From Markov's inequality, for every ${\displaystyle t>0}$:

${\displaystyle \Pr(X\geq a)\leq {\frac {\operatorname {E} [e^{tX}]}{e^{ta}}},}$

and for every ${\displaystyle t<0}$:

${\displaystyle \Pr(X\leq a)\leq {\frac {\operatorname {E} [e^{tX}]}{e^{ta}}}.}$

There are various Chernoff bounds for different distributions and different values of the parameter ${\displaystyle t}$. See [4]^: 5–7 for a compilation of more concentration inequalities.

Let ${\displaystyle X_{1},X_{2},\dots ,X_{n}}$ be independent random variables such that, for all i:

${\displaystyle a_{i}\leq X_{i}\leq b_{i}}$ almost surely.

${\displaystyle c_{i}:=b_{i}-a_{i}}$

${\displaystyle \forall i:c_{i}\leq C}$

Let ${\displaystyle S_{n}}$ be their sum, ${\displaystyle E_{n}}$ its expected value and ${\displaystyle V_{n}}$ its variance:

${\displaystyle S_{n}:=\sum _{i=1}^{n}X_{i}}$

${\displaystyle E_{n}:=\operatorname {E} [S_{n}]=\sum _{i=1}^{n}\operatorname {E} [X_{i}]}$

${\displaystyle V_{n}:=\operatorname {Var} [S_{n}]=\sum _{i=1}^{n}\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:

${\displaystyle \Pr \left[|S_{n}-E_{n}|>t\right]\leq 2\exp \left(-{\frac {2t^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right)\leq 2\exp \left(-{\frac {2t^{2}}{nC^{2}}}\right)}$

2. The random variable ${\displaystyle S_{n}-E_{n}}$ is a special case of a martingale, and ${\displaystyle S_{0}-E_{0}=0}$. Hence, the general form of Azuma's inequality can also be used and it yields a similar bound:

${\displaystyle \Pr \left[|S_{n}-E_{n}|>t\right]<2\exp \left(-{\frac {2t^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right)<2\exp \left(-{\frac {2t^{2}}{nC^{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, ${\displaystyle S_{n}=f(X_{1},\dots ,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 ${\displaystyle b_{i}-a_{i}<C}$. Hence, McDiarmid's inequality can also be used and it yields a similar bound:

${\displaystyle \Pr \left[|S_{n}-E_{n}|>t\right]<2\exp \left(-{\frac {2t^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right)<2\exp \left(-{\frac {2t^{2}}{nC^{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:

${\displaystyle \Pr \left[|S_{n}-E_{n}|>t\right]\leq 2\exp \left[-{\frac {V_{n}}{C^{2}}}h\left({\frac {Ct}{V_{n}}}\right)\right],}$ where ${\displaystyle h(u)=(1+u)\log(1+u)-u}$

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

${\displaystyle \Pr \left[|S_{n}-E_{n}|>t\right]<2\exp \left(-{\frac {t^{2}/2}{V_{n}+C\cdot 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 ${\displaystyle \operatorname {E} [e^{t\cdot S_{n}}]=\prod _{i=1}^{n}{\operatorname {E} [e^{t\cdot X_{i}}]}}$.

For example,[6] suppose the variables ${\displaystyle X_{i}}$ satisfy ${\displaystyle X_{i}\geq E(X_{i})-a_{i}-M}$, for ${\displaystyle 1\leq i\leq n}$. Then we have lower tail inequality:

${\displaystyle \Pr[S_{n}-E_{n}<-\lambda ]\leq \exp \left(-{\frac {\lambda ^{2}}{2(V_{n}+\sum _{i=1}^{n}a_{i}^{2}+M\lambda /3)}}\right)}$

If ${\displaystyle X_{i}}$ satisfies ${\displaystyle X_{i}\leq E(X_{i})+a_{i}+M}$, we have upper tail inequality:

${\displaystyle \Pr[S_{n}-E_{n}>\lambda ]\leq \exp \left(-{\frac {\lambda ^{2}}{2(V_{n}+\sum _{i=1}^{n}a_{i}^{2}+M\lambda /3)}}\right)}$

If ${\displaystyle X_{i}}$ are i.i.d., ${\displaystyle |X_{i}|\leq 1}$ and ${\displaystyle \sigma ^{2}}$ is the variance of ${\displaystyle X_{i}}$, a typical version of Chernoff inequality is:

${\displaystyle \Pr[|S_{n}|\geq k\sigma ]\leq 2e^{-k^{2}/4n}{\text{ for }}0\leq k\leq 2\sigma .}$

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

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

Suppose that ${\displaystyle X_{1}\dots X_{n}}$, ${\displaystyle X_{1}'\dots X_{n}'}$ are independent with ${\displaystyle X_{i}'}$ and ${\displaystyle X_{i}}$ having the same distribution for all ${\displaystyle i}$.

Let ${\displaystyle X=(X_{1},\dots ,X_{n}),X^{(i)}=(X_{1},\dots ,X_{i-1},X_{i}',X_{i+1},\dots ,X_{n}).}$ Then

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

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

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 ${\displaystyle (Z_{1},Z_{2},Z_{3},\ldots ,Z_{n})}$ is multinomially distributed with parameters ${\displaystyle (p_{1},p_{2},\ldots ,p_{n})}$ and satisfies ${\displaystyle Z_{1}+Z_{2}+\dots +Z_{n}=M,}$ then

${\displaystyle \Pr \left(\sum _{i=1}^{n}|Z_{i}-Mp_{i}|\geq 2M\varepsilon \right)\leq 2^{n}e^{-2M\varepsilon ^{2}}.}$

This inequality is used to bound the total variation distance.

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 ${\displaystyle (N_{1},\ldots ,N_{k})}$ be multinomially distributed with parameters ${\displaystyle n}$ and ${\displaystyle (p_{1},\ldots ,p_{k})}$ such that ${\displaystyle p_{i}>0}$ for ${\displaystyle i<k.}$ Then for every ${\displaystyle C>0}$ and ${\displaystyle \delta >0}$ there exist constants ${\displaystyle a,b,c>0,}$ such that for all ${\displaystyle n\geq 1}$ and ${\displaystyle \lambda ,p_{1},\ldots ,p_{k-1}}$ satisfying ${\displaystyle \lambda >Cn\min\{p_{i}|1\leq i\leq k-1\}}$ and ${\displaystyle \sum _{i=1}^{k-1}p_{i}\leq 1-\delta ,}$ we have

${\displaystyle \Pr \left(\sum _{i=1}^{k-1}{\frac {(N_{i}-np_{i})^{2}}{np_{i}}}>\lambda \right)\leq ae^{bk-c\lambda }.}$

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

Given a natural number ${\displaystyle n}$, let ${\displaystyle X_{1},X_{2},\dots ,X_{n}}$ be real-valued independent and identically distributed random variables with cumulative distribution function F(·). Let ${\displaystyle F_{n}}$ denote the associated empirical distribution function defined by

${\displaystyle F_{n}(x)={\frac {1}{n}}\sum _{i=1}^{n}\mathbf {1} _{\{X_{i}\leq x\}},\qquad x\in \mathbb {R} .}$

So ${\displaystyle F(x)}$ is the probability that a single random variable ${\displaystyle X}$ is smaller than ${\displaystyle x}$, and ${\displaystyle F_{n}(x)}$ is the average number of random variables that are smaller than ${\displaystyle x}$.

Then

${\displaystyle \Pr \left(\sup _{x\in \mathbb {R} }{\bigl (}F_{n}(x)-F(x){\bigr )}>\varepsilon \right)\leq e^{-2n\varepsilon ^{2}}{\text{ for every }}\varepsilon \geq {\sqrt {{\tfrac {1}{2n}}\ln 2}}.}$

Anti-concentration inequalities, on the other hand, provide an upper bound on how much a random variable can concentrate around a quantity.

For example, Rao and Yehudayoff[12] show that there exists some ${\displaystyle C>0}$ such that, for most directions of the hypercube ${\displaystyle x\in \{\pm 1\}^{n}}$, the following is true:

${\displaystyle \Pr \left(\langle x,Y\rangle =k\right)\leq {\frac {C}{\sqrt {n}}},}$

where ${\displaystyle Y}$ is drawn uniformly from a subset ${\displaystyle B\subseteq \{\pm 1\}^{n}}$ of large enough size.

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]

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