Concentration of measure
Concentration of measure is the phenomenon in which a function defined on a high-dimensional probability space is nearly constant on most of that space, provided that the function changes slowly with respect to the underlying metric. The effect arises from the combined geometry and probability of many-dimensional systems rather than from pointwise regularity alone. It underlies quantitative results in asymptotic geometric analysis, probability theory, and the study of random structures.
The standard framework is a metric probability space ((X,d,\mu)), where (d) measures separation and (\mu) is a probability measure. A real-valued function (f) is (L)-Lipschitz when
[ |f(x)-f(y)|\leq Ld(x,y) ]
for every (x,y\in X). Concentration occurs when the deviation probability
[ \mu\left(\left{x:\lvert f(x)-m_f\rvert\geq t\right}\right) ]
decreases rapidly as (t) grows, where (m_f) is a median of (f). In many central examples, the decay is Gaussian in form and is bounded by an expression proportional to (\exp(-ct^2/L^2)), with the scale constant (c) determined by the geometry of the space.
Geometric formulation
For a measurable set (A\subseteq X), its (r)-neighborhood is
[ A_r={x\in X:d(x,A)<r}. ]
The concentration function of ((X,d,\mu)) is defined by
[ \alpha_X(r)= \sup_{\mu(A)\geq 1/2} \left(1-\mu(A_r)\right). ]
A small value of (\alpha_X(r)) means that every set carrying at least half of the probability has an (r)-neighborhood carrying almost all of it. This set-theoretic statement is equivalent, up to elementary changes in constants, to deviation inequalities for Lipschitz functions. If (f) is (1)-Lipschitz and (m_f) is a median, then
[ \mu{f\geq m_f+r}\leq \alpha_X(r), \qquad \mu{f\leq m_f-r}\leq \alpha_X(r). ]
The equivalence follows because the sublevel set ({f\leq m_f}) has measure at least (1/2), while Lipschitz continuity forces points at distance less than (r) from that set to satisfy (f<m_f+r).
This formulation connects concentration with isoperimetric inequalities. An isoperimetric theorem identifies sets whose neighborhoods grow least rapidly. Bounds for those extremal sets then produce bounds that apply to every Lipschitz observable on the same space.
The spherical model
The unit sphere (S^{n-1}), equipped with normalized surface measure and geodesic distance, is a basic model of the phenomenon. Paul Lévy established the relevant spherical isoperimetric inequality by showing that spherical caps minimize neighborhood measure among sets of prescribed measure. As a consequence, a (1)-Lipschitz function on (S^{n-1}) satisfies a bound of the form
[ \Pr\left(\lvert f-m_f\rvert\geq t\right) \leq 2\exp(-c n t^2), ]
where (c>0) is an absolute constant.
The factor (n) reflects the dimension of the sphere. As (n) increases, deviations of fixed size become exponentially less probable. A coordinate function illustrates the scale: for a uniformly distributed point (X\in S^{n-1}), each coordinate has mean zero and variance (1/n). Most points therefore lie close to the equatorial region associated with any fixed direction, even though no individual equator occupies positive surface measure.
Vitali Milman incorporated this concentration principle into the modern theory of high-dimensional normed spaces. In particular, concentration supplies the probabilistic component of proofs of Dvoretzky's theorem, where a norm restricted to a suitable low-dimensional section is approximately Euclidean.
Product spaces and bounded differences
A second major source of concentration is independence. Let
[ X=(X_1,\ldots,X_n) ]
have independent coordinates, and suppose that replacing coordinate (i) while leaving the remaining coordinates unchanged alters (f(X)) by at most (c_i). Colin McDiarmid’s bounded-differences inequality gives
[ \Pr\left(f(X)-\mathbb E f(X)\geq t\right) \leq \exp\left( -\frac{2t^2}{\sum_{i=1}^{n}c_i^2} \right). ]
The corresponding lower-tail estimate follows by applying the same result to (-f). The inequality expresses a structural principle: when no coordinate has substantial individual influence, large collective deviations require many coordinate changes to align in the same direction.
This setting includes the discrete cube ({0,1}^n) with product measure and Hamming distance. Its concentration behavior is governed by discrete isoperimetry, with subcubes and threshold families providing extremal or near-extremal configurations under related formulations. The resulting estimates are closely connected with Azuma's inequality, since exposing independent coordinates sequentially produces a martingale with bounded increments.
Sampling without replacement
Independence is sufficient but not necessary for concentration. Uniform sampling from a finite population produces dependent indicator variables because the sample size remains fixed. The natural state space is the slice
[ \Omega_{n,k}= \left{ x\in{0,1}^n: \sum_{i=1}^{n}x_i=k \right}, ]
equipped with the uniform measure. Its elementary moves exchange one selected coordinate with one unselected coordinate.
In 1978, You Watanabe derived a bounded-differences estimate for this exchange geometry. If (f:\Omega_{n,k}\to\mathbb R) changes by at most (L) under a single exchange, then her estimate has the form
[ \Pr\left(\lvert f-m_f\rvert\geq t\right) \leq 2\exp\left( -\frac{t^2} {C L^2\min{k,n-k}} \right), ]
where (C) is a universal constant. The dependence on (\min{k,n-k}) reflects the symmetry between a sample and its complement. This result established concentration directly on the fixed-weight slice rather than by comparison with an independent Bernoulli sample.
The slice is also the state space of the Bernoulli–Laplace model. Its concentration inequalities can be recovered from functional inequalities for the associated exchange chain. The absence of independence changes the proof mechanism but preserves the characteristic sub-Gaussian behavior for observables with bounded exchange sensitivity.
Gaussian concentration
For the standard Gaussian measure (\gamma_n) on (\mathbb R^n), every (L)-Lipschitz function satisfies
[ \gamma_n \left( \lvert f-\operatorname{med}(f)\rvert\geq t \right) \leq 2\exp\left(-\frac{t^2}{2L^2}\right). ]
The estimate is dimension-free because the Euclidean metric already incorporates the natural fluctuation scale of the Gaussian distribution. The extremal sets in the Gaussian isoperimetric problem are half-spaces, whose enlargements are governed by the one-dimensional Gaussian distribution function.
Gaussian concentration is closely related to the logarithmic Sobolev inequality. For sufficiently regular (f), the Gaussian logarithmic Sobolev inequality controls the entropy of (e^f) through the squared gradient of (f). Applying the exponential-moment method yields
[ \mathbb E \exp\left( \lambda(f-\mathbb E f) \right) \leq \exp\left(\frac{\lambda^2L^2}{2}\right), ]
which implies the standard tail estimate by the Chernoff bound.
Functional and transport formulations
Concentration inequalities admit several equivalent or closely related formulations. A Poincaré inequality controls variance through an energy form and typically yields exponential-scale concentration after additional regularity assumptions. A logarithmic Sobolev inequality controls entropy and generally produces Gaussian-scale concentration.
Michel Talagrand developed transportation-cost and convex-distance inequalities that strengthened the analysis of product measures. In a representative transport formulation, the relative entropy of a probability measure (\nu) with respect to (\mu) controls a Wasserstein distance:
[ W_2(\nu,\mu)^2 \leq 2C,D(\nu\Vert\mu). ]
Such an inequality implies Gaussian concentration for Lipschitz functions. The connection follows by tilting (\mu) with an exponential density involving the observable and comparing the displacement cost with the resulting relative entropy.
These formulations identify concentration as a consequence of stability in the underlying measure. Geometric expansion controls neighborhoods, functional inequalities control fluctuations through derivatives or discrete gradients, and transport inequalities control the cost of shifting probability mass. Their constants encode the effective fluctuation scale of the space.
Interpretation and limitations
Concentration does not state that all functions on a high-dimensional space are nearly constant. Regularity relative to the metric is essential, since an arbitrary measurable function can separate the space into regions with widely different values. The phenomenon also depends on the compatibility of the measure and metric. Rescaling the metric changes every Lipschitz constant and therefore changes the apparent concentration scale.
The relevant center can be a median or an expectation. Median-based estimates follow directly from neighborhood expansion, while expectation-based estimates usually follow after integrating the tail bound. Under sub-Gaussian concentration, the difference between a median and the expectation is bounded by a constant multiple of the natural fluctuation scale.
Dimension alone does not cause concentration. The decisive property is that the family of metric probability spaces has concentration functions that decay increasingly rapidly. A sequence with this behavior is called a Lévy family. High-dimensional spheres and normalized product spaces provide standard instances, while spaces containing widely separated components of substantial measure do not exhibit comparable concentration.