Learn Concentration of Measure Phenomena | Geometry of High Dimensions

The concentration of measure is a striking phenomenon in high-dimensional probability and statistics. It asserts that for many random variables and functions defined on high-dimensional spaces, the values are tightly clustered around their mean or median, with deviations becoming exponentially unlikely as the dimension increases. This property is especially powerful for Lipschitz functions — functions whose output does not change too rapidly with small changes in input.

Formally, a function $f$ defined on a metric space $(X, d)$ is called Lipschitz with constant $L$ if for all $x, y$ in $X$ , the following holds:

|f(x) - f(y)| \leq L \cdot d(x, y)

This regularity enables the application of measure concentration inequalities, which provide probabilistic bounds on how much a random variable (often a function of many independent variables) can deviate from its expected value. Two foundational inequalities in this context are Hoeffding's inequality and the Gaussian concentration inequality.

Hoeffding's inequality applies to bounded independent random variables. Suppose $X_1, ..., X_n$ are independent, with each $X_i$ taking values in $[a_i, b_i]$ . For the sum $S_n = X_1 + ... + X_n$ , Hoeffding's inequality states:

P(|S_n - E[S_n]| \geq t) \leq 2 \cdot \exp\left(-\frac{2t^2}{\sum (b_i - a_i)^2}\right)

This shows that the probability of large deviations drops off exponentially in the number of variables.

For functions of Gaussian random vectors, the Gaussian concentration inequality says that if $f: \mathbb{R}^n \to \mathbb{R}$ is Lipschitz with constant $L$ , and $X$ is a standard Gaussian vector in $\mathbb{R}^n$ , then for any $t > 0$ :

P(|f(X) - E[f(X)]| \geq t) \leq 2 \cdot \exp\left(-\frac{t^2}{2L^2}\right)

This formalizes the idea that Lipschitz functions of high-dimensional random vectors are highly concentrated around their mean.

The power of concentration of measure is most evident in high dimensions. As the number of variables increases, the likelihood of observing a value far from the mean becomes vanishingly small. This underpins much of modern high-dimensional statistics, where classical intuition often fails.

One of the most important implications of concentration is its role in the stability of random projections and the behavior of high-dimensional random vectors. In high-dimensional spaces, random projections — such as those used in the Johnson-Lindenstrauss lemma — almost always preserve distances between points up to a small distortion. This is because the lengths and inner products of high-dimensional random vectors are tightly concentrated around their expected values. As a result, you can project data onto a lower-dimensional space with high probability of maintaining its geometric structure.

This regularity is counterintuitive. In low dimensions, random fluctuations can cause significant deviations. But in high dimensions, the law of large numbers and measure concentration ensure that random vectors behave in a highly predictable manner. For example, the length of a standard Gaussian vector in $R^n$ is tightly concentrated around $\sqrt{n}$ , and the angles between two independent random vectors are nearly orthogonal with high probability.


              123456789101112131415161718
            
import numpy as np
import matplotlib.pyplot as plt

# Draw 10,000 samples of n-dimensional standard Gaussian vectors
n = 1000
num_samples = 10000
X = np.random.randn(num_samples, n)

# Compute the norms of each vector
norms = np.linalg.norm(X, axis=1)

plt.hist(norms, bins=50, density=True, alpha=0.7, color='royalblue')
plt.axvline(np.sqrt(n), color='red', linestyle='dashed', linewidth=2, label='$$sqrt(n)$$')
plt.title('Distribution of Norms of Standard Gaussian Vectors (n=1000)')
plt.xlabel('Norm')
plt.ylabel('Density')
plt.legend()
plt.show()

In this example, almost all the norms cluster tightly around $\sqrt{1000} ≈ 31.62$ , with very few outliers. This illustrates the concentration of measure: in high dimensions, random vectors exhibit remarkable regularity, and their properties become almost deterministic.

These phenomena are at the heart of why high-dimensional statistics can be both challenging and powerful. The concentration of measure provides the theoretical foundation for understanding and exploiting the stability and predictability of random structures in high dimensions.

Everything was clear?

Thanks for your feedback!

Section 3. Chapter 1

Ask AI

Ask anything or try one of the suggested questions to begin our chat

Swipe to show menu