Opening the book…
This is to follow up on our discussion on the curse of dimensionality (see the section “Approximate Nearest Neighbor (ANN) Search”).
Distance Concentration in Higher Dimensions
High dimensional spaces have very special features that pose challenges to ML models (which is often referred to as the curse of dimensionality). One aspect of this “curse” is distance concentration: In high dimensional spaces, distances between all pairs of points tend to concentrate. For most points, the distance to the nearest point tends to be approximately the same as the distance to the farthest data point. In this note, we want to prove a result to illustrate such a phenomenon.
Consider random vectors, X, Y ∈ ℝp, with all their components being i.i.d. uniformly on the interval [0, 1]. We have
$$\begin{aligned} \mathbb{E} \left[ \left\lVert \mathbf{X} - \mathbf{Y} \right\rVert^2 \right] &= \frac{p}{6}, \\ \text{SD} \left[ \left\lVert \mathbf{X} - \mathbf{Y} \right\rVert^2 \right] & \approx 0.2 \sqrt{p} . \end{aligned}$$
(Here, SD denotes standard deviation).
Note: The first equation implies the mean squared distance between two random vectors grow linearly with p, while the second implies the spread (typical fluctuation) grows much slower (only as $\sqrt{p}$).
Together they imply
$$\label{02F=03} \frac{ \text{SD} \left[ \left\lVert \mathbf{X} - \mathbf{Y} \right\rVert^2 \right] }{ \mathbb{E} \text{SD} \left[ \left\lVert \mathbf{X} - \mathbf{Y} \right\rVert^2 \right] } \propto \frac{1}{\sqrt{p}} \rightarrow 0 \quad \text{(Distance Concentration)} .$$
This means, as the dimension grows, the relative variability (or “spread”) of the squared distances between random vectors shrinks rapidly. The distances, therefore, become increasingly concentrated around their mean, making nearly all pairwise distances look almost the same. This is the essence of the distance concentration phenomenon.
Proof of the first equation: Since ∥w∥2 = ∑iwi2, we have
$$\begin{aligned} \mathbb{E} \left[ \left\lVert \mathbf{X} - \mathbf{Y} \right\rVert^2 \right] &= \mathbb{E} \left[ \sum_{i=1}^p \left( X_i - Y_i \right)^2 \right] \\ &= \sum_{i=1}^p \mathbb{E} \left[ \left( X_i - Y_i \right)^2 \right] \\ &= p \, \mathbb{E} \left[ \, \left( X_1 - Y_1 \right)^2 \right] && \text{$\spadesuit $} \\ &= p \int_0^1 \int_0^1 (x-y)^2 \, p(x) p(y) \, dx dy && \text{(dropping the subscripts)} \\ &= p \int_0^1 \int_0^1 (x-y)^2 \, dx dy && \text{($p( \cdot)=1$)} \\ &= \frac{1}{6} .\end{aligned}$$
For ♠: We have used the fact that all 𝔼[(Xi−Yi)2] are equal.
Proof of the second equation:
$$\begin{aligned} \text{Var} \left[ \left\lVert \mathbf{X} - \mathbf{Y} \right\rVert^2 \right] &= \text{Var} \left[ \sum_{i=1}^p \left( X_i - Y_i \right)^2 \right] \\ &= \text{Var} \left[ \, \sum_{i=1}^p W_i \, \right] && \text{($W_i := ( X_i - Y_i )^2$)} \\ &= \sum_{i=1}^p \, \text{Var} \left[ W_i \right] + \sum_{i \neq j} \text{Cov} \left[ W_i , W_j \right] \\ &= \sum_{i=1}^p \, \text{Var} \left[ W_i \right] && \text{$\spadesuit \spadesuit$} \\ &= p \, \text{var} \left[ W_1 \right] \\ &= p \int_0^1 \int_0^1 \left( (x-y)^2 - \frac{1}{6} \right)^2 \, p(x) p(y) \, dx dy \\ &= p \int_0^1 \int_0^1 \left( (x-y)^2 - \frac{1}{6} \right)^2 \, dx dy && \text{(as $p( \cdot )=1$)} \\ &= \frac{7 }{180} p \approx (0.0388 \cdots) p.\end{aligned}$$
The square root of this gives the desired result. Note that, for ♠♠, we have used the fact that Cov[Wi,Wj] = 𝔼[(Wi−1/6)(Wj−1/6)] = 𝔼[(Wi−1/6)]𝔼[(Wj−1/6)] = 0.)
Further Exploration
-
The key papers are:
Beyer, K., Goldstein, J., Ramakrishnan, R., & Shaft, U. (1999). When is “nearest neighbor” meaningful? In Proceedings of Database Theory—ICDT’99 (pp. 217–235).
In the discussion above, we follow
Giraud, C. (2021). Introduction to high-dimensional statistics (2nd ed.). Chapman and Hall/CRC.
This page titled 2.5: Distance Concentration was last modified on Mon, 10 Aug 2026 12:25:12 GMT and is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Hei-Chi Chan.
The book could not be loaded just now.