2.5: Distance Concentration

Ancillary Materials for The Shallow and the Deep by M. Biehl · LibreTexts

0%

Contents

    Text

    Size
    100%
    Theme
    Typeface
    Line length
    Spacing

    Read aloud

    How

    Speed: 1×
    Light up
    Highlight

    Symbols: Mulberry Symbols, © 2018–2026 Steve Lee, CC BY-SA 4.0 (licence, the set), the site's own copies.

    From LibreTexts, under CC BY-NC-SA 4.0, as the source states it; its equations are written in TeX, which the PDF shows typeset. This page at LibreTexts.

    2.5: Distance Concentration

    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

    1. 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.