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 XX be a non-negative random variable with finite mean and a>0.a>0. Markov’s inequality states that the probability that XX is at least aa is at most the mean divided by a.a.

P(X≥a)≤E[X]a\mathbb{P}\left(X\geq a\right)\leq\frac{\mathbb{E}\left[X\right]}{a}

Markov’s inequality follows from a 1{X≥a}≤Xa\,\mathbf{1}_{\{X\geq a\}}\leq X by taking expectations. The inequalities below are derived from it by applying it to a transformation of X.X.

Let XX be a random variable with finite mean μ\mu and variance σ2,\sigma^2, and a>0.a>0. Chebyshev’s inequality states that the probability of a deviation of at least aa from the mean is at most the variance divided by a2.a^2.

P(∣X−μ∣≥a)≤σ2a2\mathbb{P}\left(\lvert X-\mu\rvert\geq a\right)\leq\frac{\sigma^2}{a^2}

Chebyshev’s inequality is Markov’s inequality applied to (X−μ)2.\left(X-\mu\right)^2. Taking a=kσa=k\sigma shows that the probability of a deviation of at least kk standard deviations is at most 1k2\frac{1}{k^2} for any distribution with finite variance. Applying Markov’s inequality to ∣X−μ∣k\lvert X-\mu\rvert^k gives the analogous bound E[∣X−μ∣k]ak\frac{\mathbb{E}\left[\lvert X-\mu\rvert^k\right]}{a^k} from any finite moment.

Let XX be a random variable whose mgf exists and a∈R.a\in\mathbb{R}. The Chernoff bound states that the tail probabilities of XX are bounded by the mgf, optimised over t.t.

P(X≥a)≤inf⁡t>0e−taMX(t),P(X≤a)≤inf⁡t<0e−taMX(t)\mathbb{P}\left(X\geq a\right)\leq\inf_{t>0}e^{-ta}M_X\left(t\right),\qquad\mathbb{P}\left(X\leq a\right)\leq\inf_{t<0}e^{-ta}M_X\left(t\right)

The Chernoff bound is Markov’s inequality applied to etXe^{tX} followed by optimising over t.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,a, whereas Chebyshev’s inequality decreases only as 1a2.\frac{1}{a^2}.

Let XX be a random variable with finite mean and φ:R→R\varphi:\mathbb{R}\rightarrow\mathbb{R} be a convex function such that E[φ(X)]\mathbb{E}\left[\varphi\left(X\right)\right] exists. Jensen’s inequality for random variables states that the value of φ\varphi at the mean is at most the mean of φ.\varphi.

φ(E[X])≤E[φ(X)]\varphi\left(\mathbb{E}\left[X\right]\right)\leq\mathbb{E}\left[\varphi\left(X\right)\right]

The inequality reverses for concave φ.\varphi. 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;\mathbb{R}^n;
  • E[X2]≥E[X]2,\mathbb{E}\left[X^2\right]\geq\mathbb{E}\left[X\right]^2, so that variances are non-negative;
  • E[1X]≥1E[X]\mathbb{E}\left[\frac{1}{X}\right]\geq\frac{1}{\mathbb{E}\left[X\right]} for positive X;X;
  • E[log⁡eX]≤log⁡eE[X]\mathbb{E}\left[\log_e X\right]\leq\log_e\mathbb{E}\left[X\right] for positive X.X.

Let XX and YY 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]\mathbb{E}\left[XY\right]^2\leq\mathbb{E}\left[X^2\right]\mathbb{E}\left[Y^2\right]

Equality holds if and only if Y=cXY=cX almost surely for some c∈R.c\in\mathbb{R}. The inequality is the Cauchy-Schwarz inequality of the inner product ⟨X,Y⟩=E[XY]\langle X,Y\rangle=\mathbb{E}\left[XY\right] on random variables with finite second moments. Applied to X−μXX-\mu_X and Y−μYY-\mu_Y it gives ∣cov[X,Y]∣≤σXσY,\lvert\mathrm{cov}\left[X,Y\right]\rvert\leq\sigma_X\sigma_Y, so that correlations lie in [−1,1].\left[-1,1\right].

Let XX and YY be random variables and p,q>1p,q>1 with 1p+1q=1.\frac{1}{p}+\frac{1}{q}=1. Hölder’s inequality states that the expectation of the absolute product is at most the product of the pp-th and qq-th root moments.

E[∣XY∣]≤E[∣X∣p]1pE[∣Y∣q]1q\mathbb{E}\left[\lvert XY\rvert\right]\leq\mathbb{E}\left[\lvert X\rvert^p\right]^{\frac{1}{p}}\mathbb{E}\left[\lvert Y\rvert^q\right]^{\frac{1}{q}}

Hölder’s inequality generalises the Cauchy–Schwarz inequality, which is the case p=q=2.p=q=2.

Let XX be a random variable and 0<r<s.0<r<s. Lyapunov’s inequality states that the rr-th root of the rr-th absolute moment is at most the ss-th root of the ss-th absolute moment.

E[∣X∣r]1r≤E[∣X∣s]1s\mathbb{E}\left[\lvert X\rvert^r\right]^{\frac{1}{r}}\leq\mathbb{E}\left[\lvert X\rvert^s\right]^{\frac{1}{s}}

Lyapunov’s inequality follows from Jensen’s inequality applied to the convex function x↦xsr,x\mapsto x^{\frac{s}{r}}, and shows that the existence of the ss-th moment implies the existence of all lower moments.

Let XX be a random variable with mean μ\mu and v>0.v>0. The random variable XX is sub-Gaussian with variance proxy vv if and only if its centred mgf is bounded by that of a N(0,v)\mathrm{N}\left(0,v\right) random variable.

E[et(X−μ)]≤exp⁡(vt22)  ∀ t∈R\mathbb{E}\left[e^{t\left(X-\mu\right)}\right]\leq\exp\left(\frac{vt^2}{2}\right)\,\,\forall\,t\in\mathbb{R}

Sub-Gaussian random variables have the following properties:

  • the Chernoff bound gives P(X−μ≥a)≤exp⁡(−a22v)\mathbb{P}\left(X-\mu\geq a\right)\leq\exp\left(-\frac{a^2}{2v}\right) for every a>0,a>0, so the tails decay at least as fast as those of a normal distribution with variance v;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 XX be a random variable with mean μ\mu and a≤X≤ba\leq X\leq b almost surely. Hoeffding’s lemma states that XX is sub-Gaussian with variance proxy (b−a)24.\frac{\left(b-a\right)^2}{4}.

E[et(X−μ)]≤exp⁡(t2(b−a)28)  ∀ t∈R\mathbb{E}\left[e^{t\left(X-\mu\right)}\right]\leq\exp\left(\frac{t^2\left(b-a\right)^2}{8}\right)\,\,\forall\,t\in\mathbb{R}

Let X1,…,XnX_1,\ldots,X_n be independent random variables with ai≤Xi≤bia_i\leq X_i\leq b_i almost surely, Sn=∑i=1nXiS_n=\sum_{i=1}^n X_i and s>0.s>0. Hoeffding’s inequality states that the deviation of the sum from its mean has tails bounded as follows.

P(Sn−E[Sn]≥s)≤exp⁡(−2s2∑i=1n(bi−ai)2)\mathbb{P}\left(S_n-\mathbb{E}\left[S_n\right]\geq s\right)\leq\exp\left(-\frac{2s^2}{\sum_{i=1}^n\left(b_i-a_i\right)^2}\right) P(∣Sn−E[Sn]∣≥s)≤2exp⁡(−2s2∑i=1n(bi−ai)2)\mathbb{P}\left(\left\lvert S_n-\mathbb{E}\left[S_n\right]\right\rvert\geq s\right)\leq 2\exp\left(-\frac{2s^2}{\sum_{i=1}^n\left(b_i-a_i\right)^2}\right)

Hoeffding’s inequality follows from the Chernoff bound and Hoeffding’s lemma. For the average X‾n=1nSn\overline{X}_n=\frac{1}{n}S_n of iid random variables in [0,1]\left[0,1\right] with mean μ\mu it gives

P(∣X‾n−μ∣≥ε)≤2e−2nε2,\mathbb{P}\left(\left\lvert\overline{X}_n-\mu\right\rvert\geq\varepsilon\right)\leq 2e^{-2n\varepsilon^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,…,XnX_1,\ldots,X_n be independent random variables with ∣Xi−E[Xi]∣≤M\lvert X_i-\mathbb{E}\left[X_i\right]\rvert\leq M almost surely, σ2=∑i=1nvar[Xi],\sigma^2=\sum_{i=1}^n\mathrm{var}\left[X_i\right], Sn=∑i=1nXiS_n=\sum_{i=1}^n X_i and s>0.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⁡(−s22(σ2+Ms3))\mathbb{P}\left(S_n-\mathbb{E}\left[S_n\right]\geq s\right)\leq\exp\left(-\frac{s^2}{2\left(\sigma^2+\frac{Ms}{3}\right)}\right)

For ss small relative to σ2M\frac{\sigma^2}{M} the bound behaves like the Gaussian tail exp⁡(−s22σ2)\exp\left(-\frac{s^2}{2\sigma^2}\right) and for large ss like the exponential tail exp⁡(−3s2M).\exp\left(-\frac{3s}{2M}\right).

Let f:Rn→Rf:\mathbb{R}^n\rightarrow\mathbb{R} be a function and c1,…,cn≥0.c_1,\ldots,c_n\geq 0. The function ff has the bounded differences property with constants c1,…,cnc_1,\ldots,c_n if and only if changing its ii-th argument alone changes its value by at most ci.c_i.

sup⁡x1,…,xn, xi′∣f(x1,…,xi,…,xn)−f(x1,…,xi′,…,xn)∣≤ci  ∀ i\sup_{x_1,\ldots,x_n,\,x_i'}\left\lvert f\left(x_1,\ldots,x_i,\ldots,x_n\right)-f\left(x_1,\ldots,x_i',\ldots,x_n\right)\right\rvert\leq c_i\,\,\forall\,i

Let X1,…,XnX_1,\ldots,X_n be independent random variables, ff have the bounded differences property with constants c1,…,cnc_1,\ldots,c_n and s>0.s>0. McDiarmid’s inequality or the bounded differences inequality states that the deviation of f(X1,…,Xn)f\left(X_1,\ldots,X_n\right) from its mean has a Gaussian tail.

P(f(X1,…,Xn)−E[f(X1,…,Xn)]≥s)≤exp⁡(−2s2∑i=1nci2)\mathbb{P}\left(f\left(X_1,\ldots,X_n\right)-\mathbb{E}\left[f\left(X_1,\ldots,X_n\right)\right]\geq s\right)\leq\exp\left(-\frac{2s^2}{\sum_{i=1}^n c_i^2}\right)

Hoeffding’s inequality is the special case f(x‾)=∑i=1nxif\left(\underline{x}\right)=\sum_{i=1}^n x_i with ci=bi−ai.c_i=b_i-a_i. 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,…,XnX_1,\ldots,X_n be independent random variables, X1′,…,Xn′X_1',\ldots,X_n' be independent copies of them, X‾(i)\underline{X}^{(i)} be X‾\underline{X} with its ii-th component replaced by Xi′X_i' and f:Rn→Rf:\mathbb{R}^n\rightarrow\mathbb{R} be a function. The Efron–Stein inequality states that the variance of f(X‾)f\left(\underline{X}\right) is bounded by the expected effect of resampling one component at a time.

var[f(X‾)]≤12∑i=1nE[(f(X‾)−f(X‾(i)))2]\mathrm{var}\left[f\left(\underline{X}\right)\right]\leq\frac{1}{2}\sum_{i=1}^n\mathbb{E}\left[\left(f\left(\underline{X}\right)-f\left(\underline{X}^{(i)}\right)\right)^2\right]

For a sum the inequality is an equality, and for a function with the bounded differences property it gives var[f(X‾)]≤14∑i=1nci2.\mathrm{var}\left[f\left(\underline{X}\right)\right]\leq\frac{1}{4}\sum_{i=1}^n c_i^2.

Let Z‾∼Nn(0‾,In)\underline{Z}\sim\mathrm{N}_n\left(\underline{0},I_n\right) and f:Rn→Rf:\mathbb{R}^n\rightarrow\mathbb{R} be Lipschitz continuous with constant LL with respect to Euclidean distance. Gaussian concentration states that f(Z‾)f\left(\underline{Z}\right) is sub-Gaussian with variance proxy L2.L^2.

P(f(Z‾)−E[f(Z‾)]≥s)≤exp⁡(−s22L2)  ∀ s>0\mathbb{P}\left(f\left(\underline{Z}\right)-\mathbb{E}\left[f\left(\underline{Z}\right)\right]\geq s\right)\leq\exp\left(-\frac{s^2}{2L^2}\right)\,\,\forall\,s>0

The bound does not depend on the dimension n.n. For example, the Euclidean length ∥Z‾∥\lVert\underline{Z}\rVert of a standard normal random vector concentrates within a constant distance of n\sqrt{n} in every dimension.