In probability theory, concentration inequalities provide bounds on how a random variable deviates from some 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. Then, for every constant, Note the following extension to Markov's inequality: if is a strictly increasing and non-negative function, then
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.
The generic Chernoff bound requires only the moment generating function of, defined as:, provided it exists. Based on 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.
Let be independent random variables such that, for all i: 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, 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. 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: 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 bounds the variance of a general function. Suppose that, are independent with and having the same distribution for all. Let Then
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 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.
