Concentration Inequality

A concentration inequality is a bound on the probability that a random variable deviates from its expected value by more than a specified amount. These inequalities are the probabilistic machinery behind statistical learning theory, randomized algorithms, and the analysis of large systems where individual fluctuations must be controlled to ensure predictable aggregate behavior.

The most basic concentration inequality is Markov's inequality, but the field's power comes from sharper bounds: Chernoff bounds for sums of independent random variables, Hoeffding's inequality for bounded variables, and Bernstein's inequality for variables with bounded variance. These bounds share a common structure: they show that functions of many weakly dependent variables are sharply concentrated around their mean, provided the function does not depend too strongly on any single variable.

The deepest concentration inequalities arise from geometric and functional-analytic principles. The Poincaré inequality controls variance through local interaction energy. The log-Sobolev inequality controls entropy and yields sub-Gaussian tails. The transportation inequality connects concentration to optimal transport. These functional inequalities reveal that concentration is not merely a probabilistic phenomenon but a geometric one: it reflects the curvature and connectivity of the underlying space.

Concentration inequalities are often presented as technical tools for bounding tail probabilities. This misses their structural significance. A concentration inequality is the statement that a system is robust to microscopic perturbation — that the whole does not depend sensitively on the parts. In a world where every component is noisy, concentration is what makes prediction possible.