Mathematical inequality explaining concentration of random variables
In probability theory, concentration inequalities provide mathematical bounds on the probability of a random variable deviating from some value (typically, its expected value). The deviation or other function of the random variable can be thought of as a secondary random variable. The simplest example of the concentration of such a secondary random variable is the CDF of the first random variable which concentrates the probability to unity. If an analytic form of the CDF is available this provides a concentration equality that provides the exact probability of concentration. It is precisely when the CDF is difficult to calculate or even the exact form of the first random variable is unknown that the applicable concentration inequalities provide useful insight.
Another almost universal example of a secondary random variable is the law of large numbers of classical probability theory which 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.
Let formula_1 be a random variable that is non-negative (almost surely). Then, for every constant formula_2,
 formula_3
Note the following extension to Markov's inequality: if formula_4 is a strictly increasing and non-negative function, then
formula_5
Chebyshev's inequality.
Chebyshev's inequality requires the following information on a random variable formula_1:
Then, for every constant formula_2,
formula_10
or equivalently,
formula_11
where formula_12 is the standard deviation of formula_1.
Chebyshev's inequality can be seen as a special case of the generalized Markov's inequality applied to the random variable formula_14 with formula_15.
Vysochanskij–Petunin inequality.
Let "X" be a random variable with unimodal distribution, mean "μ" and finite, non-zero variance "σ"2. Then, for any formula_16
 formula_17
(For a relatively elementary proof see e.g.).
One-sided Vysochanskij–Petunin inequality.
For a unimodal random variable formula_1 and formula_19, the one-sided Vysochanskij-Petunin inequality holds as follows:
 formula_20
Paley–Zygmund inequality.
In contrast to most commonly used concentration inequalities, the Paley-Zygmund inequality provides a "lower" bound on the deviation probability.
Chernoff bounds.
The generic Chernoff bound requires the moment generating function of formula_1, defined as formula_22 It always exists, but may be infinite. From Markov's inequality, for every formula_23:
formula_24
and for every formula_25:
formula_26
There are various Chernoff bounds for different distributions and different values of the parameter formula_27. See for a compilation of more concentration inequalities.
Mill's inequality.
Let formula_28. Thenformula_29
Bounds on sums of independent bounded variables.
Let formula_30 be independent random variables such that, for all "i":
formula_31 almost surely.
formula_32
formula_33
Let formula_34 be their sum, formula_35 its expected value and formula_36 its variance:
formula_37
formula_38
formula_39
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:
formula_40
2. The random variable formula_41 is a special case of a martingale, and formula_42. Hence, the general form of Azuma's inequality can also be used and it yields a similar bound:
formula_43
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, formula_44, 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 formula_45. Hence, McDiarmid's inequality can also be used and it yields a similar bound:
formula_46
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:
formula_47 where formula_48
5. The first of Bernstein's inequalities says that:
formula_49
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 formula_50.
For example, suppose the variables formula_51 satisfy formula_52, for formula_53. Then we have lower tail inequality:
formula_54
If formula_51 satisfies formula_56, we have upper tail inequality:
formula_57
If formula_51 are i.i.d., formula_59 and formula_60 is the variance of formula_51, a typical version of Chernoff inequality is:
formula_62
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 formula_63, formula_64 are independent with formula_65 and formula_51 having the same distribution for all formula_67.
Let formula_68 Then
 formula_69
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 formula_70 
is multinomially distributed with parameters 
formula_71
and satisfies formula_72 
then 
formula_73
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 formula_74 be multinomially distributed with parameters formula_75 and formula_76 such that formula_77 for formula_78 Then for every formula_79 and formula_80 
there exist constants formula_81 such that for all formula_82 and formula_83 
satisfying formula_84 and formula_85 we have 
formula_86
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 formula_87, let formula_30 be real-valued independent and identically distributed random variables with cumulative distribution function "F"(·). Let formula_89 denote the associated empirical distribution function defined by
formula_90
So formula_91 is the probability that a "single" random variable formula_1 is smaller than formula_93, and formula_94 is the "average number" of random variables that are smaller than formula_93.
Then
formula_96
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 formula_87 times, the probability that any given number of heads appears will be less than formula_98. This idea can be greatly generalized. For example, a result of Rao and Yehudayoff implies that for any formula_99 there exists some formula_100 such that, for any formula_101, the following is true for at least formula_102 values of formula_103:
formula_104
where formula_105 is drawn uniformly from formula_106.
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.
 ;templatestyles src="Reflist/styles.css" / ;