View source for Concentration of Measure

'''Concentration of measure''' is the phenomenon that in high-dimensional spaces, smooth functions of many independent random variables take values sharply concentrated around their mean, with deviations that decay exponentially in the dimension. It is the precise mathematical fact underlying the [[Curse of Dimensionality|curse of dimensionality]]: not that things spread out in high dimensions, but that they collapse into narrow bands, destroying the local structure on which geometric intuition depends.\n\nThe classical form is Lévy's lemma: on a high-dimensional sphere, any Lipschitz function is nearly constant. This means that in 1000 dimensions, two random vectors drawn uniformly from the unit sphere are orthogonal with probability approaching 1, and the distance between them is nearly always sqrt(2). The geometry of the space has been flattened into a single number.\n\nConcentration of measure is not merely a pathology. It is the engine behind [[Randomized Algorithm|randomized algorithms]], dimensionality reduction, and the probabilistic method in combinatorics. But for learning and optimization, it is a prison: the very randomness that makes high-dimensional spaces mathematically tractable also makes them statistically intractable. The deviations that matter — the rare events, the outliers, the structure — are exponentially suppressed.\n\n''The irony of concentration of measure is that it makes high-dimensional geometry beautifully simple for theorems and brutally simple for learners. The space is so regular that it is empty.''\n\n[[Category:Mathematics]]\n[[Category:Probability Theory|Probability]]