High-Dimensional Probability and Statistics

In hundreds of dimensions randomness stops spreading out and starts piling up. Averages, distances and directions all concentrate, so high-dimensional data behaves nothing like the 2D pictures suggest.

A 1000-dimensional standard Gaussian cloud sits in a thin shell of radius near 31.6, not near the origin, so distances concentrate

Why Does This Exist?

Classical statistics was built with one long sequence in mind: fix the dimension, let the sample size grow. Machine learning flipped it. A single example can have 1,000 features, 50,000 pixels or 12,288 embedding coordinates, while the number of examples stays modest. When dimension $d$ rivals or exceeds sample size $n$ , the old pictures break. Distances between random points stop varying, volumes hide in corners, and a maximum over many coordinates grows even when each coordinate is well behaved.

This page is the map for that regime. It names the three surprises you will meet everywhere downstream: norms concentrate, maxima grow like $\sqrt{\log d}$ , and averages concentrate exponentially fast. Later pages prove each one: concentration of measure, sub-Gaussian tails and random matrices. This page covers what changes and why you should care, not the proofs.

Prerequisite in one paragraph. You need means, variances and a tail bound. If $X$ has mean $\mu$ (its average value) and variance $\sigma^2$ (its typical squared spread), then Markov and Chebyshev inequalities already cap how often $X$ strays far. High-dimensional theory is what happens when you apply that idea $d$ times at once. The full treatment of the one-dimensional case is in expectation, variance and covariance.

Think of It Like This

A stadium crowd doing the wave

You watch one fan and their motion looks random. You watch 30,000 fans and the wave is razor sharp. Nobody coordinated it precisely; the sharpness comes from averaging over so many people that the wobbles cancel.

High dimensions do the same thing to a single random vector. One coordinate is unpredictable. All 1,000 coordinates together produce an almost deterministic length, an almost deterministic distance to the next point, an almost deterministic maximum. Randomness does not disappear. It concentrates.

Where the analogy stops: fans can see each other, coordinates usually cannot. Dependence between coordinates weakens every bound on this page, which is why later pages keep saying independent with such insistence.

How It Actually Works

Write a random vector $X = (X_1, \ldots, X_d)$ where each coordinate $X_i$ is independent with mean $0$ (average zero) and variance $1$ (unit spread). Three facts follow, and each has its own page later.

First, the squared length $\lVert X \rVert^2 = X_1^2 + \cdots + X_d^2$ is a sum of $d$ independent terms, each with mean $1$ . Its average is $d$ , so the length $\lVert X \rVert$ sits near $\sqrt{d}$ . For $d = 1000$ that is $\sqrt{1000} \approx 31.6$ , far from the origin. A standard Gaussian cloud in 1,000 dimensions is a thin shell of radius about 31.6, not a ball around zero. That is why nearest-neighbour distances in high dimensions all look the same.

Second, the maximum of $d$ standard Gaussians grows like $\sqrt{2 \log d}$ . With $d = 1000$ , $\log$ here is the natural log, $\ln 1000 \approx 6.91$ , so $\sqrt{2 \times 6.91} = \sqrt{13.82} \approx 3.72$ . Even though each coordinate averages zero, you should expect some coordinate to reach $3.7$ . Selection creates size: the more knobs you check, the larger the largest looks.

Third, averages concentrate exponentially. If $\bar{X}$ is the mean of $n$ independent standard normals, the tail bound says $P(|\bar{X}| \ge t) \le 2\exp(-nt^2/2)$ , where $P$ means chance and $\exp$ is the exponential function.

Worked example

Take $n = 1000$ samples and tolerance $t = 0.14$ . Then $t^2 = 0.0196$ and $nt^2/2 = 1000 \times 0.0196 / 2 = 9.8$ . So $\exp(-9.8) \approx 0.0000554$ and the bound gives $P(|\bar{X}| \ge 0.14) \le 2 \times 0.0000554 \approx 0.00011$ . In words: the average of 1,000 standard normals lands within $0.14$ of zero with chance above $0.9999$ . Chebyshev with variance alone would only promise chance about $0.95$ for a wider band. The exponential bound is what makes high-dimensional estimation possible at all, and it is the template every later tail bound copies.

Compare with the central limit theorem, which describes the shape of the fluctuations. Concentration describes their size, and in high dimensions size is what bites first.

Watch Out For

Reading a 2D scatter plot as high-dimensional evidence

Two projected dimensions of a 1,000-dimensional Gaussian look like a friendly blob around the origin. The real cloud sits 31.6 units out in a shell you cannot see in the projection. Decisions based on the 2D picture, like a distance threshold tuned by eye, fail on the real distances because every pairwise distance concentrated near $\sqrt{2d} \approx 44.7$ while your plot suggested single digits.

Fix: never trust a low-dimensional plot for distances or densities. Check the histogram of actual norms and pairwise distances in full dimension before setting any threshold.

Mixing up d and n in the bound

The tail bound above has $n$ (samples) in the exponent, not $d$ (dimension). Swapping them turns a strong guarantee into nonsense: with $d = 50{,}000$ features and $n = 200$ samples, the average over samples concentrates at rate $n = 200$ , while the maximum over features grows at rate $\sqrt{\log d} \approx 3.7$ . One shrinks with data, the other grows with dimension.

Fix: label every bound with what grows and what shrinks. Ask: does this quantity average over samples or maximise over dimensions.

The Quick Version

High-dimensional means $d$ rivals or exceeds $n$ , and then classical low-dimensional intuition misleads.
A standard Gaussian vector in $d$ dimensions has length near $\sqrt{d}$ , so for $d = 1000$ the cloud is a shell of radius about 31.6.
The maximum of $d$ standard Gaussians is about $\sqrt{2 \log d}$ , which is 3.72 at $d = 1000$ .
Averages concentrate exponentially: 1,000 samples pin the mean within 0.14 with chance above 0.9999.
Every later page in this band proves one of these three facts under weaker or stronger assumptions.