A concentration inequality is an inequality that bounds the probability that a random variable deviates from its mean, or another reference value, using limited information about its distribution such as its moments, its range or the independence of its components. A concentration inequality is valid for every distribution that satisfies its assumptions.
Let X be a non-negative random variable with finite mean and a>0.Markov’s inequality states that the probability that X is at least a is at most the mean divided by a.
P(X≥a)≤aE[X]
Markov’s inequality follows from a1{X≥a}≤X by taking expectations. The inequalities below are derived from it by applying it to a transformation of X.
Let X be a random variable with finite mean μ and variance σ2, and a>0.Chebyshev’s inequality states that the probability of a deviation of at least a from the mean is at most the variance divided by a2.
P(∣X−μ∣≥a)≤a2σ2
Chebyshev’s inequality is Markov’s inequality applied to (X−μ)2. Taking a=kσ shows that the probability of a deviation of at least k standard deviations is at most k21 for any distribution with finite variance. Applying Markov’s inequality to ∣X−μ∣k gives the analogous bound akE[∣X−μ∣k] from any finite moment.
Let X be a random variable whose mgf exists and a∈R. The Chernoff bound states that the tail probabilities of X are bounded by the mgf, optimised over t.
P(X≥a)≤t>0infe−taMX(t),P(X≤a)≤t<0infe−taMX(t)
The Chernoff bound is Markov’s inequality applied to etX followed by optimising over t. Because the mgf of a sum of independent random variables is the product of their mgfs, the Chernoff bound gives tail probabilities for sums that decrease exponentially in a, whereas Chebyshev’s inequality decreases only as a21.
Let X be a random variable with finite mean and φ:R→R be a convex function such that E[φ(X)] exists. Jensen’s inequality for random variables states that the value of φ at the mean is at most the mean of φ.
φ(E[X])≤E[φ(X)]
The inequality reverses for concave φ. Jensen’s inequality for random variables has the following properties:
it is the extension of Jensen’s inequality for convex combinations from finite weighted averages to expectations;
the same statement holds for a random vector and a convex function on Rn;
E[X2]≥E[X]2, so that variances are non-negative;
E[X1]≥E[X]1 for positive X;
E[logeX]≤logeE[X] for positive X.
Let X and Y be random variables with finite second moments. The Cauchy–Schwarz inequality for random variables states that the squared expectation of the product is at most the product of the second moments.
E[XY]2≤E[X2]E[Y2]
Equality holds if and only if Y=cX almost surely for some c∈R. The inequality is the Cauchy-Schwarz inequality of the inner product ⟨X,Y⟩=E[XY] on random variables with finite second moments. Applied to X−μX and Y−μY it gives ∣cov[X,Y]∣≤σXσY, so that correlations lie in [−1,1].
Let X and Y be random variables and p,q>1 with p1+q1=1.Hölder’s inequality states that the expectation of the absolute product is at most the product of the p-th and q-th root moments.
E[∣XY∣]≤E[∣X∣p]p1E[∣Y∣q]q1
Hölder’s inequality generalises the Cauchy–Schwarz inequality, which is the case p=q=2.
Let X be a random variable and 0<r<s.Lyapunov’s inequality states that the r-th root of the r-th absolute moment is at most the s-th root of the s-th absolute moment.
E[∣X∣r]r1≤E[∣X∣s]s1
Lyapunov’s inequality follows from Jensen’s inequality applied to the convex function x↦xrs, and shows that the existence of the s-th moment implies the existence of all lower moments.
Let X be a random variable with mean μ and v>0. The random variable X is sub-Gaussian with variance proxyv if and only if its centred mgf is bounded by that of a N(0,v) random variable.
E[et(X−μ)]≤exp(2vt2)∀t∈R
Sub-Gaussian random variables have the following properties:
the Chernoff bound gives P(X−μ≥a)≤exp(−2va2) for every a>0, so the tails decay at least as fast as those of a normal distribution with variance v;
a normal random variable is sub-Gaussian with variance proxy equal to its variance;
the sum of independent sub-Gaussian random variables is sub-Gaussian with variance proxy equal to the sum of their variance proxies.
Let X be a random variable with mean μ and a≤X≤b almost surely. Hoeffding’s lemma states that X is sub-Gaussian with variance proxy 4(b−a)2.
E[et(X−μ)]≤exp(8t2(b−a)2)∀t∈R
Let X1,…,Xn be independent random variables with ai≤Xi≤bi almost surely, Sn=∑i=1nXi and s>0.Hoeffding’s inequality states that the deviation of the sum from its mean has tails bounded as follows.
Hoeffding’s inequality follows from the Chernoff bound and Hoeffding’s lemma. For the average Xn=n1Sn of iid random variables in [0,1] with mean μ it gives
P(Xn−μ≥ε)≤2e−2nε2,
so the average concentrates around the mean at a rate that does not depend on the distribution beyond its range. Hoeffding’s inequality uses only the range of each variable and so is loose when the variances are much smaller than the squared ranges.
Let X1,…,Xn be independent random variables with ∣Xi−E[Xi]∣≤M almost surely, σ2=∑i=1nvar[Xi],Sn=∑i=1nXi and s>0.Bernstein’s inequality states that the deviation of the sum from its mean has a tail bounded in terms of the total variance and the range.
P(Sn−E[Sn]≥s)≤exp(−2(σ2+3Ms)s2)
For s small relative to Mσ2 the bound behaves like the Gaussian tail exp(−2σ2s2) and for large s like the exponential tail exp(−2M3s).
Let f:Rn→R be a function and c1,…,cn≥0. The function f has the bounded differences property with constants c1,…,cn if and only if changing its i-th argument alone changes its value by at most ci.
Let X1,…,Xn be independent random variables, f have the bounded differences property with constants c1,…,cn and s>0.McDiarmid’s inequality or the bounded differences inequality states that the deviation of f(X1,…,Xn) from its mean has a Gaussian tail.
Hoeffding’s inequality is the special case f(x)=∑i=1nxi with ci=bi−ai. McDiarmid’s inequality bounds, for example, the deviation of an empirical error rate or of the largest deviation between an empirical and a true cdf from its mean.
Let X1,…,Xn be independent random variables, X1′,…,Xn′ be independent copies of them, X(i) be X with its i-th component replaced by Xi′ and f:Rn→R be a function. The Efron–Stein inequality states that the variance of f(X) is bounded by the expected effect of resampling one component at a time.
var[f(X)]≤21i=1∑nE[(f(X)−f(X(i)))2]
For a sum the inequality is an equality, and for a function with the bounded differences property it gives var[f(X)]≤41∑i=1nci2.
Let Z∼Nn(0,In) and f:Rn→R be Lipschitz continuous with constant L with respect to Euclidean distance. Gaussian concentration states that f(Z) is sub-Gaussian with variance proxy L2.
P(f(Z)−E[f(Z)]≥s)≤exp(−2L2s2)∀s>0
The bound does not depend on the dimension n. For example, the Euclidean length ∥Z∥ of a standard normal random vector concentrates within a constant distance of n in every dimension.