One of the nicer illustrations of the counterintuitive nature of high-dimensional space is that an orange in this space is mostly peel. In an oranges-to-apples comparison, let’s try this with an apple instead, which is roughly spherical with a diameter of 70mm and a peel thickness of 0.2mm.

The vanishing act

The volume of a $d$-dimensional sphere of radius $r$ is

$$V_d(r) = C_d r^d$$

where $C_d$ is the volume of the $d$-dimensional unit ball. We don’t have to worry about this though, as we are only interested in the fraction of the peel to the apple, where $C_d$ cancels out:

$$\frac{V_d(r) - V_d(r-\epsilon)}{V_d(r)}$$

Show intermediate steps$$\begin{aligned} &= \frac{C_d r^d - C_d(r-\epsilon)^d}{C_d r^d} \\ &= \frac{C_d r^d}{C_d r^d} - \frac{C_d(r-\epsilon)^d}{C_d r^d} \\ &= 1 - \frac{(r-\epsilon)^d}{r^d} \\ &= 1 - \left(\frac{r-\epsilon}{r}\right)^d \end{aligned}$$

$$= 1 - \left(1 - \frac{\epsilon}{r}\right)^d$$

In the case of 3D, with radius $r = 35\text{mm}$ and peel thickness $\epsilon = 0.2\text{mm}$, the peel makes up roughly $1 - \left(\frac{34.8}{35}\right)^3 \approx 1.7\%$ of the apple.

Assuming that the apple expands into the higher-dimensional space in the same way it does for 3D, the proportion of the peel to the total apple explodes with dimensionality.

Data in 10'000 dimensions or more are common, for example in biological research, and in this space the apple is

$$1 - \left(\frac{34.8}{35}\right)^{10000} \approx 100 \%$$

peel, a turn off for even the greatest apple aficionado.

1. In many real-life high-dimensional distributions, probability mass concentrates in a shell, leaving little mass near the center

Every atom an island

Even though it now lives in 10'000 dimensions, we assume our “apple” still consists of (point-like) “atoms”. How far are those from each other? Answering this requires some use of random vectors:

The squared (to simplify calculations) distance between two atoms $\mathbf{x} = (x_1, \dots, x_d)$ and $\mathbf{y} = (y_1, \dots, y_d)$ is

$$\|\mathbf{x} - \mathbf{y}\|^2 = \|\mathbf{x}\|^2 - 2\,\mathbf{x}\cdot\mathbf{y} + \|\mathbf{y}\|^2$$

Since both atoms sit on the shell, $\|\mathbf{x}\|^2 = \|\mathbf{y}\|^2 = r^2$, so

$$\|\mathbf{x} - \mathbf{y}\|^2 = 2r^2 - 2\,\mathbf{x}\cdot\mathbf{y}$$

For a random point on the shell, each coordinate is equally likely to be positive or negative, so

$$\mathbb{E}[x_i] = 0$$

and for two independent random atoms,

$$\mathbb{E}[x_i y_i] = \mathbb{E}[x_i]\,\mathbb{E}[y_i] = 0$$

and therefore

$$\mathbb{E}[\mathbf{x}\cdot\mathbf{y}] = 0$$

This gives

$$\mathbb{E}[\|\mathbf{x} - \mathbf{y}\|^2] = 2r^2$$

Since the variability vanishes in high dimensions, the distance is typically close to:

$$\sqrt{2r^2} = \sqrt{2}\,r$$

Not just on average, but for virtually every pair of atoms, the distance is essentially $\sqrt{2}\,r$.

2. In high-dimensional space, Euclidean distance loses its meaning: all points are roughly equally far from each other

An apple made of nothing

An apple of that size has roughly $2 \times 10^{25}$ atoms, but in 10'000 dimensions, almost every pair is roughly $\sqrt{2} \times 35\text{mm} \approx 49\text{mm}$ from each other. For comparison, the interstellar medium averages around $1\,\text{cm}$ between atoms.

In summary, we ended up with a low-density gas made out of apple-peel atoms. Bon appetit.

3. In high-dimensional space, even an astronomical number of points leaves this space virtually empty