Concentration of Measure

AnalysisLargeDeviationsMeasureTheoryProbabilityTheoryStatistics Concentration of measure is a collection of results that describe a phenomenon that informally states that any Lipschitz function of many independent random variables is almost constant.

More explicitly, given bounded (in an interval of size ) random variables with and , then while their sum surely varies in an interval of size , concentration of measure states that when the ‘s are sufficiently uncorrelated (independent), the sum only varies in an interval of size . Intuitively, concentration results are quantitative versions of the Central Limit Theorem.

This principle is quantified vs large deviation inequalities, that upper-bound the probability that the sum (or function of random variables) deviates from it’s expectation by a significant amount, typically in the form of sub-gaussian inequalities.