Concentration inequality
In probability theory, concentration inequalities provide bounds on how a random variable deviates from some value (typically, its expected value). The law of large numbers of classical probability theory states 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 show that such behavior is shared by other functions of independent random variables. Concentration inequalities can be sorted according to how much information about the random variable is needed in order to use them. Markov's inequality

Let  be a random variable that is non-negative (almost surely). Then, for every constant , 

 

Note the following extension to Markov's inequality: if  is a strictly increasing and non-negative function, then

Chebyshev's inequality 

Chebyshev's inequality requires the following information on a random variable :

 The expected value  is finite. The variance  is finite. Then, for every constant , 

or equivalently, 

where  is the standard deviation of . Chebyshev's inequality can be seen as a special case of the generalized Markov's inequality applied to the random variable  with . Vysochanskij–Petunin inequality 
Let X be a random variable with unimodal distribution, mean μ and finite, non-zero variance σ2. Then, for any 

 

(For a relatively elementary proof see e.g. ). One-sided Vysochanskij–Petunin inequality 

For a unimodal random variable  and , the one-sided Vysochanskij-Petunin inequality holds as follows:

Paley–Zygmund inequality

Cantelli's inequality

Gauss's inequality

Chernoff bounds

The generic Chernoff bound requires the moment generating function of , defined as  It always exists, but may be infinite. From Markov's inequality, for every :

and for every :

There are various Chernoff bounds for different distributions and different values of the parameter . See  for a compilation of more concentration inequalities. Bounds on sums of independent bounded variables 

Let  be independent random variables such that, for all i:
 almost surely. Let  be their sum,  its expected value and  its variance:

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:

2. The random variable  is a special case of a martingale, and . Hence, the general form of Azuma's inequality can also be used and it yields a similar bound:

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). 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, , 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 . Hence, McDiarmid's inequality can also be used and it yields a similar bound:

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:
 where 

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

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 . For example, suppose the variables  satisfy , for . Then we have lower tail inequality:

If  satisfies , we have upper tail inequality:

If  are i.i.d.,  and  is the variance of , a typical version of Chernoff inequality is:

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 ,  are independent with  and  having the same distribution for all . Let  Then

 

A proof may be found in e.g., . 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. A simple proof appears in (Appendix Section). If a random vector  
is multinomially distributed with parameters 

and satisfies  
then 

This inequality  is used to bound the   total variation distance. Mason and van Zwet inequality 

The Mason and van Zwet inequality for multinomial random vectors concerns a slight modification of the classical chi-square statistic. Let the random vector  be multinomially distributed with parameters  and  such that  for  Then for every  and  
there exist constants  such that for all   and  
satisfying  and  we have

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 , let  be real-valued independent and identically distributed random variables with cumulative distribution function F(·). Let  denote the associated empirical distribution function defined by

So  is the probability that a single random variable  is smaller than , and  is the average number of random variables that are smaller than . Then

Anti-concentration inequalities
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 show that there exists some  such that, for most directions of the hypercube , the following is true:

where  is drawn uniformly from a subset  of large enough size. Such inequalities are of importance in several fields, including communication complexity (e.g., in proofs of the gap Hamming problem) and graph theory. An interesting anti-concentration inequality for weighted sums of independent Rademacher random variables can be obtained using the Paley–Zygmund and the Khintchine inequalities. References

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

Probabilistic inequalities