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}}}$ 

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

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:^{[clarification needed]}

${\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