Concentration inequality

A concentration inequality bounds the probability that a random variable differs substantially from a typical value such as its expected value or median.

Equip the symmetric group $S_n$ with its uniform probability measure and unnormalized Hamming distance. If $f$ has Lipschitz constant $K$, it obeys the displayed two-sided bound, and each one-sided tail has the same exponential without the factor two. Reveal a uniform permutation one image at a time. Two possible next images have completion sets paired by swapping those two values, changing exactly two coordinates. Thus the corresponding conditional means differ by at most $2K$. Each increment of the Doob exposure martingale has conditional range length at most $2K$. Applying the conditional Hoeffding lemma gives $\mathbb{E}{e}^{\lambda (f-\mathbb{E}f)}\le e^{n{\lambda }^2{K}^2/2}$; optimizing the exponential Markov bound proves the bound. A mere absolute-increment bound of $2K$ gives a weaker constant, so using the range length matters.

For an event $A$ in a product of finitely many probability spaces with its product measure, take the closed convex hull of the mismatch vectors $(1_{x_i\ne y_i}{)}_i$, $y\in A$. The distance of this hull from zero is $d_T(x,A)$. Equivalently it is the supremum, over nonnegative coordinate weights of squared sum at most one, of their minimum mismatch sum. Averaging mismatch patterns is the feature that distinguishes this quantity from ordinary Hamming distance.

On a finite product of standard probability spaces, for any measurable event $A$ of positive probability,Consequently $\mathbb{P}(A)\mathbb{P}(d_T(X,A)\ge s)\le e^{-s^2/4}$. Here $d_T$ is the Talagrand convex distance. The distance-event conclusion can be read with outer probability when necessary.

Let the largest last-coordinate section have probability $a$, and another section probability $ar$. Mix mismatch vectors from these two sections with weights $\lambda ,1-\lambda$. Their squared norm is at most $\lambda d_1^2+(1-\lambda )d_2^2+(1-\lambda {)}^2$. Hölder's inequality and induction bound that section's exponential integral by $a^{-1}{\inf }_{\lambda }{r}^{-\lambda }{e}^{(1-\lambda {)}^2/4}$. The scalar estimate for Talagrand product induction makes it at most $(2-r)/a$. Average over sections and use $m(2-m)\le 1$ with $m=\mathrm{Pr}(A)/a$ to close the induction.

For $a\in [0,1]$,where the endpoint $t=1$ is used directly if $a=0$. Put $L=-\log a$. For $L\le 1/2$, choose $t=2L$ and set $h(L)=\log (2-e^{-L})-L+L^2$. Then $h(0)=h^{\prime }(0)=0$ and $h^{\prime \prime }(L)=2-2e^L/(2e^L-1{)}^2\ge 0$, proving the bound. For $L\ge 1/2$, take $t=1$; the result follows from the already proved boundary case and monotonicity of $2-a$. This estimate closes the section-by-section induction for the exponential Talagrand convex distance moment.

For a nonnegative integrable random variable $Z$, the entropy functional isIt is the unnormalized relative entropy of the measure with density proportional to $Z$ relative to the original probability measure.

Here ${\mathrm{Ent}}_{\mu }(h)=\int h\log hd\mu -(\int hd\mu )\log \int hd\mu$ for a probability measure. The coefficient depends on the normalization of the energy. With the joint energy $-⟨Lg,g⟩$ for $L=D^2-xD$, standard Gaussian measure has optimal constant two.

// Target: analysis.bigb

Differentiate $\log \Vert u{\Vert }_q$ with $u=P_{t}f$ and a changing exponent. The derivative is $q^{\prime }\mathrm{Ent}(u^q)/(q^2\int u^q)-\mathcal{E}(u^{q-1},u)/\int u^q$. Apply the logarithmic Sobolev inequality to $u^{q/2}$ and the power inequality for symmetric Markov energies. Choosing $q^{\prime }=4(q-1)/c_{\mathrm{LS}}$ makes the upper bound zero.

// Target: probability-and-statistics.bigb

The Hoeffding inequality turns finite interval bounds and independence into exponentially small tail probabilities for a sum. It requires neither a normal distribution nor identical probability distributions. Let $X_1,\dots ,X_n$ be independent essentially bounded real random variables, with deterministic finite bounds $a_i\le X_i\le b_i$ almost surely. Define the centered sum and its squared-width budget byFor $V>0$ and $t>0$,The union bound therefore gives $\mathbb{P}(|S_n|\ge t)\le \min \{1,2e^{-2t^2/V}\}$. If $V=0$, every $X_i$ is constant almost surely, so $S_n=0$ and both positive-threshold tail probabilities vanish. The equal-width version is stated in the authored Stanford notes.^[ref]

The quantity $V$ is a sum of squared interval widths, not the variance of $S_n$. Centering changes the endpoints to $a_i-\mathbb{E}{X}_i$ and $b_i-\mathbb{E}{X}_i$, leaving each width unchanged. For example, independent random variables in $[-2,1]$ and $[4,5]$ have $V=3^2+1^2=10$, whatever their expected values or probability distributions. A deviation at least three above their total expected value has probability at most $e^{-18/10}\approx 0.165299$. If all widths equal $b-a>0$, the sample mean ${\overline{X}}_n=n^{-1}{\sum }_i{X}_i$ satisfies

Independence is essential to this general guarantee. Take one Bernoulli random variable $B$ with success probability $1/2$ and set every $X_i=B$. Each lies in $[0,1]$, but for every $n$ the sample mean is either zero or one. Thus $\mathbb{P}(|{\overline{X}}_n-1/2|\ge 1/4)=1$, whereas incorrectly inserting these dependent observations into the formula would give $2e^{-n/8}$, less than one for $n\ge 6$. Some special dependent models have their own valid concentration inequalities; arbitrary statistical dependence cannot be ignored.

For the short proof, apply Markov's inequality to $e^{\lambda S_n}$ with $\lambda >0$, factor the expectation using independence, and apply the Hoeffding lemma to each factor:Minimizing this quadratic polynomial at $\lambda =4t/V$ gives the upper tail probability; applying it to $-S_n$ gives the lower one. This is the Chernoff bound method. The original 1963 article is Probability Inequalities for Sums of Bounded Random Variables by Wassily Hoeffding; its publisher record identifies the article, but its full text was unavailable during this source check. The argument above is a direct derivation rather than a claim to have inspected that article's proof.

Let $B_1,\dots ,B_n$ be independent and identically distributed Bernoulli random variables with success probability $p$, and let ${\hat{p}}_n=n^{-1}{\sum }_i{B}_i$ be their observed frequency, a sample mean. Since every interval width is one, $V=n$. Substituting $t=n\epsilon$ into the Hoeffding inequality givesFor tolerance $0<\epsilon <1$ and failure probability $0<\delta <1$, solving $2e^{-2n{\epsilon }^2}\le \delta$ yields the sufficient sample sizeHere $\log$ is the natural logarithm. For $\epsilon =0.05$ and $\delta =0.05$, $n=738$ guarantees an error smaller than $0.05$ with probability at least $0.95$, for every $p\in [0,1]$. The two-sided bound at this sample size is approximately $0.0499440$. A specified single direction instead needs $n\ge \lceil \log (1/\delta )/(2{\epsilon }^2)\rceil$, or $600$ for these choices. Halving the tolerance multiplies the unrounded sufficient sample size by four; reducing the failure probability tenfold adds $\log (10)/(2{\epsilon }^2)$ before rounding.

This is a conservative sufficient sample size, not a necessary minimum. For a specified $p$, the count $K={\sum }_i{B}_i$ has a binomial distribution, whose exact upper tail probability isFor $k>np$, the Hoeffding inequality bounds this by $\exp [-2(k-np{)}^2/n]$. An arbitrary frequency threshold uses $k=\lceil n(p+\epsilon )\rceil$; if $k>n$, the event is impossible. The discreteness of the count and its variance $np(1-p)$ can make the exact tail probability substantially smaller. At $n=100$, $p=1/2$, $k=60$, the exact upper tail probability is about $0.0284440$, while the bound is $e^{-2}\approx 0.135335$. At $p=1/10$, $k=20$, the same deviation $\epsilon =0.1$ gives the same bound but an exact upper tail probability about $0.00197856$.

For a fixed positive sample size $n$ of independent and identically distributed Bernoulli random variables, letThe Hoeffding inequality makes $C_n$ a conservative confidence interval for $p$: ${\mathbb{P}}_p(p\in C_n)\ge 1-\delta$ for every $p\in [0,1]$. Indeed, exclusion from the closed interval implies $|{\hat{p}}_n-p|>r_n$, an event contained in the deviation event bounded by $\delta$. Clipping to $[0,1]$ retains coverage because $p$ already lies there. For $n=738$, $\delta =0.05$, and an observed frequency $369/738=1/2$, $r_n\approx 0.0499924$, giving approximately $[0.450008,0.549992]$.

Coverage concerns repeated independent samples: the unknown $p$ is fixed and the confidence interval is random. This fixed-$n$ guarantee does not justify repeatedly checking the same bound and stopping as soon as it looks favorable. The Hoeffding sample size for Bernoulli frequencies chooses $n$ in advance; guarantees across repeated inspection times require separate control of the additional events, for example through a union bound with an allocated failure probability at each time.

The Hoeffding lemma controls the entire centered moment-generating function using only an interval width. For an essentially bounded real random variable $X$ with finite deterministic bounds $a\le X\le b$ almost surely, every real $\lambda$ satisfiesEquivalently, $\mathbb{E}{e}^{\lambda (X-\mathbb{E}X)}\le e^{{\lambda }^2(b-a{)}^2/8}$. This single-random variable statement needs no independence assumption; independence enters when applying it to the factors for a sum in the Hoeffding inequality. Both signs of $\lambda$ are allowed, and equality holds at $\lambda =0$ or when $a=b$.^[ref]

In the convention $\log \mathbb{E}{e}^{\lambda Y}\le {\lambda }^2{\sigma }^2/2$ for a centered sub-Gaussian random variable $Y$, the Hoeffding lemma supplies ${\sigma }^2=(b-a{)}^2/4$. This upper parameter need not equal the actual variance. For a Bernoulli random variable $B$ of success probability $p$,The actual variance is $p(1-p)$, whereas the supplied parameter is $1/4$ for every $p$. This explains part of the conservatism visible in Hoeffding sample size for Bernoulli frequencies.

A short proof exposes why the constant is $1/8$. Put $Y=X-\mathbb{E}X$ and define exponential tilting byThe tilted probability measure has the same interval of possible values, and differentiating the cumulant-generating function gives ${\psi }^{\prime \prime }(\lambda )={\mathrm{Var}}_{{\mathbb{P}}_{\lambda }}(Y)$. Boundedness justifies these derivatives for every finite $\lambda$. Under any such tilted law, Popoviciu's inequality on variances gives ${\psi }^{\prime \prime }(\lambda )\le (b-a{)}^2/4$: the variance is no larger than the expected value of the squared distance from the interval midpoint, itself at most $(b-a{)}^2/4$. Since $\psi (0)={\psi }^{\prime }(0)=0$, the integral form of Taylor's theorem yieldsThis expression handles either sign of $\lambda$ without changing the argument.

The constant $1/8$ cannot be reduced uniformly over all essentially bounded real random variables. Equal endpoint probabilities at $a$ and $b$ give $Y=\pm (b-a)/2$, a scaled Rademacher random variable, andThus the sharpness is already forced near zero by the variance; the bound need not be equality at nonzero parameters for a particular probability distribution.

If independent centered random variables satisfy $X_i\le b$ and ${\sum }_i\mathbb{E}{X}_i^2\le v$, then

For a binomial distribution with $p_n\to 0$ and $n{p}_n\to \infty$, the Bennett inequality at $C$ standard deviations tends to $2e^{-C^2/2}$, whereas the Hoeffding inequality tends to two. The raw Bennett inequality bound is eventually smaller for any fixed $C>0$; after clipping at one it is nontrivial in the limit only when $C>\sqrt{2\log 2}$.

The Bennett rate function has Taylor expansion $\varphi (u)=u^2/2-u^3/6+O(u^4)$ near zero. It is the optimized exponent in the Chernoff bound based on the moment-generating function estimate for the Bennett inequality.

A probability distribution $\mu$ has Poincaré constant $C_P$ when every sufficiently regular $f$ satisfies

For standard Gaussian measure $\gamma$, the sharp Poincaré constant is one:

If each probability measure ${\mu }_i$ has Poincaré constant $C_i$, then the product measure ${⨂}_i{\mu }_i$ has Poincaré constant at most ${\max }_i{C}_i$. This follows by iterating the law of total variance and applying Jensen inequality to derivatives of conditional expectations.

If $\mu$ has Poincaré constant $C$ and $\varphi$ is $L$-Lipschitz, then the pushforward measure ${\varphi }_{\ast }\mu$ has Poincaré constant at most $C{L}^2$. Apply the original inequality to $g\circ \varphi$ and use the chain rule.

For the uniform distribution on $[0,1]$,The constant $1/{\pi }^2$ is sharp and is the mean-zero Poincare-Wirtinger inequality on the interval.

For standard Gaussian measure $\gamma$,

For standard one-dimensional Gaussian measure, $\int e^{sx}d\gamma =e^{s^2/2}$. Thus ${\mathrm{Ent}}_{\gamma }(e^{sx})=(s^2/2)e^{s^2/2}$, while $\int |(e^{sx/2}{)}^{\prime }{|}^{2}d\gamma =(s^2/4)e^{s^2/2}$. Every nonzero $s$ therefore attains ratio two, proving optimality of the Gaussian constant.

For bounded smooth positive $h$ bounded away from zero, differentiation and Gaussian integration by parts give the displayed identity. The Ornstein-Uhlenbeck gradient commutation identity and weighted Cauchy-Schwarz inequality bound its right side by $e^{-2t}\int |h^{\prime }{|}^2/hd\gamma$. Integrating and setting $h=f^2$ proves the Gaussian logarithmic Sobolev inequality. Positive clipped approximation extends it to functions of finite Gaussian Dirichlet energy.

For independent random variables supported on $[0,1]$ and a differentiable convex function $f$,

For every $\lambda >0$, Markov inequality applied to $e^{\lambda X}$ givesOptimizing over $\lambda$ gives the Chernoff bound in terms of the moment-generating function of $X$.

For a $d\times p$ matrix of independent standard normal entries and $0<t<1$, diagonal entries of $A^{T}A/d-I$ have two-sided tails bounded by $2e^{-d{t}^2/8}$, while off-diagonal entries have tails bounded by $2e^{-d{t}^2/4}$. A union bound over $p$ diagonal entries and $p(p-1)/2$ distinct off-diagonal entries controls their common entrywise maximum norm.

A function $f(x_1,\dots ,x_n)$ has bounded differences with constants $c_i$ when changing only $x_i$ changes its value by at most $c_i$.

If $X_1,\dots ,X_n$ are independent random variables and $f$ has bounded differences constants $c_i$, thenand the same bound holds for the lower tail.

For a nonempty $A\subseteq \{0,1{\}}^n$ of relative size at least $\epsilon \in (0,1]$, its Hamming distance function $F(x)=d(x,A)$ has the bounded differences property with all constants one. If $\mu =\mathbb{E}F$, the concentration bound at $F=0$ gives $\epsilon \le 2e^{-2{\mu }^2/n}$, so $\mu \le t/2$ for $t=\sqrt{2n\log (2/\epsilon )}$. Then $\mathrm{Pr}(F>t)\le 2e^{-2(t-\mu {)}^2/n}\le \epsilon$, proving that the radius-$t$ neighbourhood contains at least $(1-\epsilon )2^n$ cube points.

If a function of independent coordinates has one-sided squared-difference proxy at most $v$, Talagrand's one-sided inequality gives a Gaussian lower-tail bound $\mathbb{P}(Z-\mathbb{E}Z\le -t)\le e^{-t^2/(2v)}$. Applied to the negative of a concave function, it gives the corresponding upper-tail bound.

An integer-valued function $f$ is $g$-certifiable when every input $x$ with $f(x)=k$ has a set of at most $g(k)$ coordinates whose values alone guarantee that $f\ge k$.

The entropy method combines a coordinatewise certificate with tensorization of entropy to bound the moment-generating function of a certifiable random quantity and hence its tails.

A nonnegative function $f$ of independent coordinates is self-bounding when there are coordinate-deleted versions $f_i$ such that $0\le f-f_i\le 1$ andThese inequalities make the natural variance proxy no larger than the function itself.

A nonnegative function $f$ is weakly self-bounding when coordinate-deleted functions $f_i$ satisfy $f_i\le f$ andThe squared coordinate sensitivity is then controlled by the observed value of the function itself.

For a weakly self-bounding function $Z=f(X_1,\dots ,X_n)$ of independent random variables, the coordinatewise variance inequality giveswhere $Z_i=f_i(X^{(i)})$.

The entropy method givesfor $\lambda \ge 0$. Consequently the Chernoff bound yields $\mathbb{P}(Z-\mathbb{E}Z\le -t)\le \exp [-t^2/(2\mathbb{E}Z)]$.

For a nonnegative function $Z$ of independent random variables, entropy is at most the sum of its conditional coordinate entropies. This tensorization is a basic step of the entropy method.

If $Z=f(X_1,\dots ,X_n)$ for independent coordinates and $Z_i^{\prime }$ replaces $X_i$ by an independent copy, then

For independent coordinates $X_1,\dots ,X_n$ and square-integrable $f$,For Bernoulli coordinates, each conditional variance is an explicit squared coordinate difference.

A modified logarithmic Sobolev inequality bounds the entropy of $e^{\lambda Z}$ by a one-sided coordinate-difference energy. For independent coordinates and arbitrary coordinate-deleted functions $f_i$, tensorization givesIf that energy is at most $v$, one common normalization is

The Herbst argument integrates a logarithmic Sobolev bound on $\lambda H^{\prime }(\lambda )-H(\lambda )$ to control the centered cumulant-generating function $H$, then applies a Chernoff bound to obtain concentration.

A transport-entropy inequality controls an optimal expected transportation cost between probability distributions by their Kullback-Leibler divergence.

If each coordinate law satisfies the same convex transport-entropy inequality, then the product law satisfies the sum-cost version. Sequentially couple conditional coordinates, apply Jensen inequality, and use the chain rule for relative entropy.

A centered random variable $X$ is sub-Poisson in the right tail with variance parameter ${\sigma }^2$ whenfor every $\lambda \ge 0$.

A centered random variable $X$ is sub-Gamma in the right tail with variance parameter $v$ and scale parameter $c$ whenfor $0\le \lambda <c^{-1}$.

For independent centered variables $X_i\le b$ and $v={\sum }_i\mathbb{E}{X}_i^2$,

Suppose independent centered sub-exponential random variables satisfy $\log \mathbb{E}{e}^{\lambda X_i}\le v_i{\lambda }^2/(2(1-b|\lambda |))$ for $|\lambda |<1/b$, and put $v={\sum }_i{v}_i$. Independence adds the log moment-generating functions. The Chernoff bound with $\lambda =t/(v+bt)$ gives the displayed two-sided tail. If each variable has common scale $K$, one may take $v_i\le C{K}^2$ and $b\le CK$, giving $\mathbb{P}(|n^{-1}{\sum }_i{X}_i|>t)\le 2e^{-cn\min \{t^2/K^2,t/K\}}$. This form of Bernstein's inequality allows unbounded variables with factorial moment control, including the centered square of a sub-Gaussian random variable.

For independent centered variables and $p\ge 2$, the $p$th moment of their sum is bounded, up to a constant depending only on $p$, by the sum of their $p$th moments plus the $p/2$ power of their total variance.

Talagrand's concentration inequality gives strong concentration in product spaces using convex distance. If $A$ has positive product probability, its convex-distance enlargement has Gaussian tails. A Talagrand concentration inequality for certifiable functions follows by bounding this distance using bounded differences and small certificates.

This is an application of Talagrand's concentration inequality to certifiable functions. Talagrand's product-space inequality gives sub-Gaussian-type concentration for a bounded-differences, certifiable function, with a variance scale controlled by the certificate size.

Suppose an integer-valued certifiable function is $L$-Lipschitz under one-coordinate changes and a value at least $b$ has a certificate of at most $rb$ coordinates. Any input with value at most $a<b$ must differ on at least $(b-a)/L$ certificate positions. Equal weights on those positions bound its Talagrand convex distance from the low-value event. Applying Talagrand's convex distance inequality gives the displayed product bound. For $0\le Z\le D$, median tails integrate to $|\mathbb{E}Z-\mathrm{med}Z|=O(L\sqrt{rD})$, and deviations of order $D$ have exponentially small probability.

For the longest increasing subsequence length $L$ on a product space of independent coordinates, a witness of length $\ell$ uses only $\ell$ coordinates. Any point with subsequence length at most $a$ must differ on at least $\ell -a$ witness positions. Weights $1/\sqrt{\ell }$ on those positions show $d_T(x,\{L\le a\})\ge (\ell -a)/\sqrt{\ell }$. Thus for $0\le a<b$,At a median $m$, this gives upper tail $2e^{-t^2/[4(m+t)]}$ and lower tail $2e^{-t^2/(4m)}$. Integrating the tails places the mean within $O(\sqrt{m}+1)$ of the median, so the natural concentration scale near the mean is $\sqrt{\mathbb{E}L}$. A random permutation is represented by the ranks of independent continuous variables; arbitrary dependent sequences need not obey this conclusion.