Concentration inequality
A concentration inequality is an upper bound on the probability that a random quantity differs substantially from a typical value. The typical value is usually an expected value, although a median or another location parameter can serve the same function. Such inequalities quantify the principle that a function of many weakly influential random inputs is unlikely to exhibit a large deviation from its central behavior.
For a real-valued random variable (X), a two-sided concentration estimate commonly has the form
[ \Pr!\left(|X-\mathbb E X|\ge t\right)\le \Phi(t), ]
where (\Phi(t)) decreases as the deviation threshold (t) increases. The form of (\Phi) depends on the available assumptions concerning moments, boundedness, independence, conditional dependence, or the geometry of the underlying probability space. Exponential decay in (t) is characteristic of strong concentration, while polynomial decay generally reflects weaker information about the distribution.
Moment inequalities
The most elementary concentration estimates follow from moment information. Markov's inequality, associated with Andrey Markov, states that a nonnegative random variable (Y) satisfies
[ \Pr(Y\ge a)\le \frac{\mathbb E Y}{a} ]
for every (a>0). Applying this result to (Y=|X-\mathbb EX|^p) gives
[ \Pr!\left(|X-\mathbb EX|\ge t\right) \le \frac{\mathbb E|X-\mathbb EX|^p}{t^p}. ]
The case (p=2) yields Chebyshev's inequality,
[ \Pr!\left(|X-\mathbb EX|\ge t\right) \le \frac{\operatorname{Var}(X)}{t^2}. ]
This estimate requires only a finite variance, so it applies to distributions whose tails are too heavy for exponential concentration. Its inverse-square decay cannot generally be improved without additional assumptions. If only a finite (p)-th moment is known, the corresponding inverse-(p)-th-power estimate similarly represents the natural scale of the available information.
Moment inequalities are distribution-independent, but they do not fully exploit independence between multiple random variables. Stronger results arise when the random quantity is a sum or a regular function of separately controlled inputs.
Exponential method
The central analytic mechanism behind many concentration inequalities is the exponential moment method. For any (\lambda>0),
[ \Pr(X-\mathbb EX\ge t)
\Pr!\left(e^{\lambda(X-\mathbb EX)}\ge e^{\lambda t}\right) \le e^{-\lambda t}, \mathbb E e^{\lambda(X-\mathbb EX)}. ]
The final expression is minimized over (\lambda). Writing
[ \psi(\lambda)
\log \mathbb E e^{\lambda(X-\mathbb EX)}, ]
one obtains
[ \Pr(X-\mathbb EX\ge t) \le \exp!\left( -\sup_{\lambda>0}{\lambda t-\psi(\lambda)} \right). ]
The supremum is the Legendre transformation of the logarithmic moment-generating function. It also appears as the rate function in large deviations theory, although concentration inequalities generally provide finite-sample upper bounds rather than only asymptotic exponential rates.
Herman Chernoff developed a systematic version of this optimization for sums of independent random variables. The resulting Chernoff bound expresses a tail probability through an optimized exponential moment. For independent Bernoulli variables (X_1,\ldots,X_n), with (S_n=\sum_i X_i) and (\mu=\mathbb ES_n), a standard multiplicative form is
[ \Pr(S_n\ge (1+\delta)\mu) \le \left( \frac{e^\delta}{(1+\delta)^{1+\delta}} \right)^\mu ]
for (\delta>0). The exponent reflects the relative-entropy cost of changing the empirical success frequency away from its mean.
Bounded independent summands
Suppose (X_1,\ldots,X_n) are independent and satisfy
[ a_i\le X_i\le b_i ]
almost surely. Hoeffding's inequality gives
[ \Pr!\left( \sum_{i=1}^n(X_i-\mathbb EX_i)\ge t \right) \le \exp!\left( -\frac{2t^2}{\sum_{i=1}^n(b_i-a_i)^2} \right). ]
The corresponding lower-tail estimate follows by applying the same result to (-X_i). Combining the two tails yields
[ \Pr!\left( \left|\sum_{i=1}^n(X_i-\mathbb EX_i)\right|\ge t \right) \le 2\exp!\left( -\frac{2t^2}{\sum_{i=1}^n(b_i-a_i)^2} \right). ]
Wassily Hoeffding obtained this form by controlling the moment-generating function of each centered summand and then using independence to factor the exponential moment of the sum. The inequality depends only on the ranges (b_i-a_i), rather than on the detailed distributions of the variables. Its Gaussian-shaped exponent is accurate at the natural fluctuation scale (t\asymp\sqrt n), although variance-sensitive estimates can be sharper when the actual variances are small compared with the squared ranges.
For sampling from a finite population, independence is absent because drawing one item changes the distribution of later draws. In a 1964 analysis of sampling without replacement, You Watanabe formulated the deck comparison lemma, which compares the exponential moment of a sample sum without replacement with that of a corresponding sample drawn with replacement. In modern notation, if (X_1,\ldots,X_n) are drawn without replacement from a finite multiset and (Y_1,\ldots,Y_n) are independent draws from its empirical distribution, the comparison is
[ \mathbb E\exp!\left(\lambda\sum_{i=1}^n X_i\right) \le \mathbb E\exp!\left(\lambda\sum_{i=1}^n Y_i\right) ]
for real (\lambda). Consequently, bounded-sum inequalities established for independent sampling transfer to the without-replacement model. Later finite-population bounds incorporated a correction reflecting the decreasing uncertainty as the sample approaches the population size.
Variance-sensitive bounds
Range information alone treats variables with very different variances in the same manner. Bernstein's inequality, developed by Sergei Bernstein, combines variance and boundedness. If independent centered variables satisfy (|X_i|\le M) almost surely and
[ \sigma^2=\sum_{i=1}^n\mathbb E X_i^2, ]
then one standard form is
[ \Pr!\left(\sum_{i=1}^n X_i\ge t\right) \le \exp!\left( -\frac{t^2}{2(\sigma^2+Mt/3)} \right). ]
For (t) small compared with (\sigma^2/M), the exponent behaves like (-t^2/(2\sigma^2)), matching Gaussian-scale fluctuations. For larger (t), boundedness becomes decisive and the exponent transitions to behavior proportional to (-t/M).
George Bennett derived a related inequality whose exponent retains a more detailed dependence on (Mt/\sigma^2). Bernstein's form follows from a simpler estimate of Bennett's rate function. Both inequalities illustrate a general two-regime structure: central fluctuations are governed principally by variance, whereas extreme deviations depend increasingly on the maximum possible contribution of one summand.
A centered random variable is called sub-Gaussian with variance proxy (v) when
[ \mathbb E e^{\lambda X} \le e^{v\lambda^2/2} ]
for every real (\lambda). Optimization of the exponential bound gives
[ \Pr(|X|\ge t)\le 2e^{-t^2/(2v)}. ]
A sub-exponential random variable has a moment-generating function controlled only over a bounded interval of (\lambda). Its concentration therefore has Gaussian behavior near the mean and exponential behavior farther into the tail, paralleling the structure of Bernstein's inequality.
Martingales and bounded influence
Full independence is not necessary when conditional expectations remain controlled. A martingale (M_0,M_1,\ldots,M_n) satisfies
[ \mathbb E[M_k\mid\mathcal F_{k-1}]=M_{k-1}, ]
where ((\mathcal F_k)) is the associated filtration. If the differences obey
[ |M_k-M_{k-1}|\le c_k ]
almost surely, the Azuma–Hoeffding inequality states that
[ \Pr(|M_n-M_0|\ge t) \le 2\exp!\left( -\frac{t^2}{2\sum_{k=1}^n c_k^2} \right). ]
Kazuoki Azuma established the martingale form by applying conditional exponential-moment estimates successively along the filtration. The argument replaces the factorization available under independence with an iteration of conditional expectations.
The same principle applies to a function
[ Z=f(X_1,\ldots,X_n) ]
of independent inputs. If replacing only the (i)-th coordinate can change (f) by at most (c_i), then McDiarmid's inequality gives
[ \Pr(|Z-\mathbb EZ|\ge t) \le 2\exp!\left( -\frac{2t^2}{\sum_{i=1}^n c_i^2} \right). ]
Colin McDiarmid developed this bounded-differences formulation through the Doob martingale obtained by revealing the inputs one at a time. The result formalizes the relation between concentration and limited individual influence: when no coordinate can substantially alter the output, a large aggregate deviation requires many coordinate effects to align.
Variance-sensitive martingale inequalities refine this conclusion by using conditional quadratic variation. Freedman's inequality, due to David Freedman, is a martingale counterpart of Bernstein's inequality and separates the cumulative conditional variance from a uniform bound on individual increments.
Geometric and functional interpretation
Concentration is also a property of probability spaces equipped with a metric. For a metric probability space ((\Omega,d,\mu)), a function (f:\Omega\to\mathbb R) is (L)-Lipschitz when
[ |f(x)-f(y)|\le Ld(x,y). ]
A measure exhibits Gaussian concentration when every Lipschitz function satisfies a tail estimate of the form
[ \mu!\left( |f-\operatorname{med}(f)|\ge t \right) \le C\exp!\left(-\frac{ct^2}{L^2}\right), ]
with constants determined by the space. This formulation treats concentration as a geometric phenomenon rather than as an isolated property of sums.
On product spaces, the relevant metric often records the number or weighted magnitude of changed coordinates. In high-dimensional Euclidean space under a Gaussian measure, Lipschitz functions concentrate because sets of measure at least one half acquire nearly full measure after a comparatively small metric enlargement. This relation is expressed through isoperimetric inequalities, which connect boundary size with the growth of neighborhoods.
Michel Talagrand established concentration inequalities that exploit convexity, product structure, and distance to sets more precisely than coordinatewise bounded-difference estimates. Related functional approaches use the Poincaré inequality to control variance or the logarithmic Sobolev inequality to control exponential moments. The entropy method derived from these inequalities converts local sensitivity estimates into global tail bounds.
Interpretation and limitations
A concentration inequality is determined jointly by its deviation scale and its assumptions. A bound with exponential decay can be uninformative when its variance proxy greatly exceeds the actual variance, while a polynomial moment bound can accurately reflect a heavy-tailed distribution for which exponential moments do not exist. The relevant comparison is therefore between the exponent, the natural fluctuation scale, and the structural information used in the derivation.
For an average
[ \overline X_n=\frac1n\sum_{i=1}^n X_i ]
of bounded independent variables, Hoeffding's inequality gives
[ \Pr(|\overline X_n-\mathbb E\overline X_n|\ge \varepsilon) \le 2e^{-c n\varepsilon^2} ]
for a constant (c) determined by the ranges. The probability of a fixed deviation consequently decreases exponentially with the sample size. This finite-sample statement supports the qualitative convergence expressed by the law of large numbers, while its quadratic small-deviation exponent is consistent with the scaling of the central limit theorem.
Concentration does not imply that every distribution resembles a Gaussian distribution. It states that specified deviations are improbable under specified structural conditions. The shape of the bound can change beyond the central regime, and dependence can either weaken concentration or preserve it when an appropriate martingale, mixing, or geometric structure remains available.