Concentration of measure

Concentration of measure is the phenomenon, pervasive in high-dimensional geometry and probability, that a function of many independent random variables is overwhelmingly likely to take values close to its mean. The canonical example is the concentration inequality: if a function depends smoothly on many independent inputs, then the probability of large deviation from the mean decays exponentially with the number of inputs. This is not merely a technical lemma; it is a structural property of high-dimensional spaces that explains why macroscopic systems behave deterministically despite microscopic randomness.

The connection to hardness amplification is direct. Concentration of measure is the probabilistic engine that makes the Direct Product Theorem work: when many independent weakly hard instances are composed, the probability that a solver succeeds on the ensemble is not merely small but exponentially small. The same geometric principle that makes a random vector in a high-dimensional sphere lie near the equator also makes a solver fail on the direct product.