Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Sampling in High Dimensional Spaces

Computer Science Dept, Ferdowsi University of Mashhad

Why a separate laboratory page?

The theory page argued that high-dimensional space does not look like the plane: the cube is all corners, the ball is a shell, and the nearest neighbour is as far as the farthest. Several of those statements are quantitative, and the only way to believe them is to compute: how much of a ball lies in its peel, what fraction of the cube survives rejection sampling, and where the points we generate actually land.

This page is that laboratory. It needs nothing beyond NumPy and matplotlib, and it uses the unit ball as the playground:

  1. the thin shell: the fraction of the volume of a ball that lies near its surface;

  2. rejection sampling: why “generate in the cube, keep what is inside the ball” stops working;

  3. uniform points on a hypersphere, by normalising Gaussian vectors;

  4. uniform points inside the ball, by inverse-transform sampling of the radius;

  5. the Gaussian annulus: the same shell phenomenon for Gaussian data.

V_2 = 3.1416 | V_3 = 4.1888

The Thin Shell Argument

Where is the volume located inside a hypersphere itself? Consider a thin shell of width ϵ\epsilon near the surface of a sphere of radius rr. The volume of this shell is:

Vol(Sd(r,ϵ))=Vol(Sd(r))−Vol(Sd(r−ϵ))\text{Vol}(S_d(r, \epsilon)) = \text{Vol}(S_d(r)) - \text{Vol}(S_d(r - \epsilon))

The ratio of the shell’s volume to the total volume is:

Vol(Sd(r,ϵ))Vol(Sd(r))=1−(1−ϵr)d\frac{\text{Vol}(S_d(r, \epsilon))}{\text{Vol}(S_d(r))} = 1 - \left( 1 - \frac{\epsilon}{r} \right)^d

As d→∞d \to \infty, the term (1−ϵr)d(1 - \frac{\epsilon}{r})^d tends to 0.

lim⁡d→∞Vol(Sd(r,ϵ))Vol(Sd(r))→1\lim_{d \to \infty} \frac{\text{Vol}(S_d(r, \epsilon))}{\text{Vol}(S_d(r))} \to 1

For example, for a circle in two dimensions, with r =1 and ϵ\epsilon = 0.01 the volume of the thin shell is 1−(0.99)2=0.0199≃2%1−(0.99)^2 = 0.0199 ≃ 2\%. As expected, in two-dimensions, the thin shell encloses only a small fraction of the volume of the original hypersphere. But for 100 dimensions thin shell volume becomes 1−(0.99)100≃1−0.37≃0.631−(0.99)^{100} ≃ 1 - 0.37 ≃ 0.63.

Conclusion: In high dimensions, almost 100% of the volume (and probability mass) of a hypersphere is concentrated in a thin shell near the surface (crust). The interior is essentially empty.


<Figure size 1000x600 with 1 Axes>

Generating Uniform Points on a Hypersphere

Generating points uniformly inside a hypersphere in high dimensions is tricky. Due to the volume properties discussed above, simple methods like “Rejection Sampling” (generate in cube, keep if in sphere) fail because the acceptance rate approaches zero (remember the Empty Center/Porcupine effect).

Rejection sampling: generate points uniformly in the cube [−1,1]d[-1,1]^d and keep those inside the unit ball. The acceptance probability is the volume ratio of the ball to the cube:

pd=Vol(Bd(1))2d=πd/22d Γ(d/2+1),p_d = \frac{\mathrm{Vol}(B_d(1))}{2^d} = \frac{\pi^{d/2}}{2^d\,\Gamma(d/2+1)},

so p2≈0.79p_2 \approx 0.79, p10≈0.0025p_{10} \approx 0.0025 and p20≈2.5×10−8p_{20} \approx 2.5\times10^{-8}. Rejection sampling stops being an option well before d=20d=20: it is correct, and useless. The next cell measures exactly this.

<Figure size 600x600 with 1 Axes>
Dimension: 2, Total points generated: 2528, Ratio: 0.7911392405063291
Dimension: 3, Total points generated: 3886, Ratio: 0.514668039114771
Dimension: 4, Total points generated: 6639, Ratio: 0.3012501882813677
Dimension: 5, Total points generated: 12619, Ratio: 0.15849116411760045
Dimension: 6, Total points generated: 24356, Ratio: 0.08211528986697324
Dimension: 7, Total points generated: 54465, Ratio: 0.03672082989075553
Dimension: 8, Total points generated: 126709, Ratio: 0.015784198438942774
Dimension: 9, Total points generated: 307730, Ratio: 0.006499203847528678
Dimension: 10, Total points generated: 784299, Ratio: 0.0025500478771488936
<Figure size 800x600 with 1 Axes>

Generating points from a Gaussian distribution

We now switch from uniform points to Gaussian points, because the multivariate Gaussian is the distribution with no preferred direction: its level sets are spheres.

<Figure size 500x500 with 1 Axes>

Random vector uniformly distributed on the surface of a unit hypersphere

To generate a random vector y\mathbf{y} uniformly distributed on the surface of a unit hypersphere Sd(1)S_d(1):

  1. Generate xi∼N(0,1)x_i \sim \mathcal{N}(0, 1) for i=1…di=1 \dots d.

  2. Normalize: y=x∣∣x∣∣\mathbf{y} = \frac{\mathbf{x}}{||\mathbf{x}||}.

This works because the multivariate Gaussian is spherically symmetric.

<Figure size 600x600 with 1 Axes>

The joint probability density of the independent Gaussian components is spherically symmetric:

f(x)=∏i=1d12πe−xi2/2=1(2π)d/2e−12∑xi2=1(2π)d/2e−∣∣x∣∣22f(x) = \prod_{i=1}^d \frac{1}{\sqrt{2\pi}} e^{-x_i^2/2} = \frac{1}{(2\pi)^{d/2}} e^{-\frac{1}{2}\sum x_i^2} = \frac{1}{(2\pi)^{d/2}} e^{-\frac{||x||^2}{2}}

Since the density depends only on the length ∣∣x∣∣||x|| and not the direction, the direction vectors are uniformly distributed.

Conclusion: The density function f(x)f(\mathbf{x}) depends only on the length (magnitude) of the vector ∣∣x∣∣||\mathbf{x}||, and not on its coordinates (direction).

  • This property is called Spherical Symmetry or Isotropy.

  • It implies that the distribution is invariant under rotation. Therefore, all directions are equally probable, and the normalized vector y=x/∣∣x∣∣\mathbf{y} = \mathbf{x} / ||\mathbf{x}|| is uniformly distributed on the hypersphere.

Generating Points Inside the Ball

If we want points uniformly distributed inside the ball (not just on the surface), the first idea is to take a surface point and scale it by a uniform random number ρ∈[0,1]\rho \in [0,1]:

y=ρ x∥x∥,ρ∼U(0,1).\mathbf{y}=\rho\,\frac{\mathbf{x}}{\lVert\mathbf{x}\rVert}, \qquad \rho \sim \mathcal{U}(0,1).

It looks harmless, and it is wrong: it crowds the points near the centre, where the volume is almost nothing. The next cell shows the result, and the sections after it explain the repair.

<Figure size 600x600 with 1 Axes>

Why is the naive approach incorrect?
If we simply sample the radius ρ\rho uniformly from [0,1][0,1], the generated points will cluster near the center.
In dd dimensions, the volume of a thin shell at radius rr grows proportionally to rd−1r^{d-1}.
This means there is far more volume near the surface (r≈1r \approx 1) than near the center (r≈0r \approx 0).
To achieve a truly uniform distribution inside the ball, the probability of a point lying within radius rr must be proportional to the volume enclosed by that radius.

For uniform volume density, the cumulative distribution function (CDF) must follow the volume growth rdr^d.
Thus, we require the random variable RR (the radius) to satisfy: P(R≤r)=rd.P(R \le r) = r^d. Using Inverse Transform Sampling with a∼U(0,1)a \sim U(0,1), we obtain: R=a1/d.R = a^{1/d}. A particular sample of RR will be denoted by ρ\rho.


1. Determining the Target CDF

Let RR denote the random variable representing the radius of a point.
The cumulative distribution function (CDF), F(r)F(r), gives the probability that a point lies within radius rr:

F(r)=P(R≤r).F(r) = P(R \le r).

For a uniform distribution inside the dd‑ball, this probability equals the ratio of the volume of the ball of radius rr to the total volume (radius 1):

F(r)=Vol(Sd(r))Vol(Sd(1))=KdrdKd⋅1d=rd.F(r) = \frac{\text{Vol}(S_d(r))}{\text{Vol}(S_d(1))} = \frac{K_d r^d}{K_d \cdot 1^d} = r^d.

So our target CDF is simply:

F(r)=rd.F(r) = r^d.

2. Inverse Transform Sampling

How do we generate random radii that follow F(r)=rdF(r) = r^d?
We use the Inverse Transform Sampling method:

  • If a∼U(0,1)a \sim \mathcal{U}(0,1) and FF is a continuous CDF, then X=F−1(a)X = F^{-1}(a) has distribution FF.

  • Intuitively: we draw a random probability aa from [0,1][0,1], and ask: “Which radius rr corresponds to this cumulative probability?”

  • Formally: If a∼U(0,1)a \sim U(0,1), then X=F−1(a)X = F^{-1}(a) has distribution FF:

P(X≤R)=P(F−1(a)≤R)=P(a≤F(R))=F(R).P(X \le R) = P(F^{-1}(a) \le R) = P(a \le F(R)) = F(R).

Therefore, if a∼U(0,1)a \sim \mathcal{U}(0,1), then:

R=F−1(a)=a1/d.R = F^{-1}(a) = a^{1/d}.

And when we actually generate a sample, we denote it by:

ρ=a1/d.\rho = a^{1/d}.

3. Example (for d=2d=2)

For a 2‑dimensional ball (a disk), we have:

ρ=a.\rho = \sqrt{a}.
a∼U(0,1)a \sim \mathcal{U}(0,1)ρ=a\rho = \sqrt{a}
0.000.000
0.100.316
0.250.500
0.500.707
0.750.866
1.001.000

This table shows how the transformation spreads points more evenly across the disk, avoiding clustering near the center.


4. Application to the Hypersphere

Applying this to our radius variable RR:

  1. Generate a uniform random number a∼U(0,1)a \sim \mathcal{U}(0,1).

  2. Compute the radius sample: ρ=a1/d\rho = a^{1/d}.

  3. Combine with a random direction to obtain a point inside the ball.


Algorithm for Uniform Points in a dd‑Ball

  1. Generate a random vector x∼N(0,Id)\mathbf{x} \sim \mathcal{N}(0, I_d).

  2. Normalize: y=x/∥x∥\mathbf{y} = \mathbf{x} / \|\mathbf{x}\| (this gives a random direction on the unit sphere).

  3. Generate a∼U(0,1)a \sim \mathcal{U}(0,1).

  4. Scale: z=(a1/d)y\mathbf{z} = (a^{1/d}) \mathbf{y} (this places the point uniformly inside the ball).

<Figure size 500x500 with 1 Axes>

Gaussian Distribution in High Dimensions

From Geometric Thin Shells to Statistical Thin Shells

In previous sections, we saw several geometric phenomena:

  • The Empty Center / Porcupine Effect in hypercubes (on the theory page)

  • The Thin Shell inside hyperspheres

  • How uniform sampling becomes concentrated near the surface rather than the center

We also generated uniform points on and inside a hypersphere and observed that the volume grows outward, causing most points to stay away from the center.

Now we show that Gaussian data behave in exactly the same way — even though the Gaussian distribution is centered at the origin.


Why Gaussian Points Do Not Cluster Near the Mean (Unlike 1D)

Let x=(x1,…,xd)∼N(0,Id) x = (x_1,\dots,x_d) \sim \mathcal{N}(0, I_d) .

In one dimension, many sampled points lie “close to zero,” and the distance ∣x∣|x| is usually small. However, this intuition completely breaks down as soon as we move to dimension 2 or higher.

The key difference is geometry:

  • In 1D, “the center” is just a point, and the line has no notion of volume growth.

  • In higher dimensions, volume explodes with radius:

    • Area ∝r2\propto r^2

    • Volume ∝r3\propto r^3

    • In general: hypersphere volume ∝rd\propto r^{d}

Thus, although the Gaussian density is highest at the origin, the available volume near the origin is vanishingly small.

The center has the highest density but almost zero volume ⇒\Rightarrow almost no sampled points appear there.

This exactly mirrors the thin-shell phenomenon you observed for uniform sampling.


Distance of a Gaussian Vector from the Origin

A central identity explains the behavior:

∣x∣2=∑i=1dxi2∼χd2|x|^2 = \sum_{i=1}^d x_i^2 \sim \chi^2_d

Thus (See Chi-squared distribution):

E[∣x∣2]=d⇒E[∣x∣]≈d.\mathbb{E}[|x|^2] = d \qquad\Rightarrow\qquad \mathbb{E}[|x|] \approx \sqrt{d}.
  • In 1D: ∣x∣≈0.8|x| \approx 0.8 (close to the center)

  • In 2D: ∣x∣≈2≈1.41|x| \approx \sqrt{2} \approx 1.41

  • In 10D: ∣x∣≈10≈3.16|x| \approx \sqrt{10} \approx 3.16

  • In 200D: ∣x∣≈200≈14.1|x| \approx \sqrt{200} \approx 14.1

And importantly:

Increasing dimension pushes all Gaussian samples outward, not just a few outliers. Almost the entire distribution lies in a thin spherical shell around radius d\sqrt{d}.

This is the statistical analogue of the geometric thin-shell effect.


Numerical Simulation: Gaussian Thin Shell

<>:26: SyntaxWarning: invalid escape sequence '\s'
<>:28: SyntaxWarning: invalid escape sequence '\s'
<>:26: SyntaxWarning: invalid escape sequence '\s'
<>:28: SyntaxWarning: invalid escape sequence '\s'
/tmp/ipykernel_2698829/2529169885.py:26: SyntaxWarning: invalid escape sequence '\s'
  ax[1].set_title(f"{d}-D Gaussian: Mass at Tail ($\sqrt{{d}}$)")
/tmp/ipykernel_2698829/2529169885.py:28: SyntaxWarning: invalid escape sequence '\s'
  ax[1].axvline(np.sqrt(d), color='red', linestyle='--', label='$\sqrt{d} \\approx 14.1$')
<Figure size 1200x500 with 2 Axes>

These two plots illustrate the fundamental shift from “mass at center” (low dimension) to “mass in a thin shell” (high dimension).


The Gaussian Annulus Phenomenon

A formal version states:

With overwhelming probability, a Gaussian sample lies inside d±O(1) \sqrt{d} \pm O(1) — a thin annulus whose thickness does not grow with dd.

As dd increases:

  • Radius grows like d\sqrt{d}

  • Shell thickness remains constant

  • Relative shell thickness →\rightarrow 0

So the Gaussian distribution becomes extremely concentrated on a thin spherical layer.

This mirrors exactly what we saw earlier for:

  • Uniform points inside a hypersphere

  • Rejection sampling

  • Volume concentration

  • Empty Center effect

This is why Gaussian distributions are used so heavily in theory: they reflect the intrinsic geometry of high-dimensional space.


Connection to Previous Sections

Here is how the Gaussian phenomenon links back to the concepts earlier in the notebook:

Relation to “Empty Center / Porcupine Effect”

Volume around the center is negligible in high dimensions →\rightarrow Gaussian mass avoids the center, exactly like uniform points.


Relation to “Thin Shell Argument”

Uniform hypersphere volume concentrates at radius rr: Gaussian probability mass concentrates at radius d\sqrt{d}. The geometry is identical; only the radius scale differs.


Relation to “Generating Points Inside the Ball”

You observed that uniform points require special sampling (ρ=a1/d\rho = a^{1/d}) because naive sampling bunches points near the center.

Gaussian sampling naturally avoids the center due to the same volume effects.


Relation to “Random Vectors are Nearly Orthogonal”

Since nearly all Gaussian points lie at distance d\sqrt{d}, their normalized directions behave almost like points uniformly distributed on the sphere.

Thus Gaussian vectors are almost orthogonal — the basis for random projection and Johnson–Lindenstrauss.


Why This Matters (Preparing for JL)

Gaussian thin-shell concentration ensures:

  • Pairwise distances are stable

  • Dot products are small

  • Random projections preserve geometry

These facts are exactly what the Johnson–Lindenstrauss Lemma formalizes.

This section therefore serves as the bridge from geometric properties of high-dimensional space to the theoretical foundation of dimensionality reduction.

Summary

  • The volume of a ball of radius 1−ϵ1-\epsilon is (1−ϵ)d(1-\epsilon)^d of the whole ball, so for d=100d=100 a 1%1\% peel holds 63%63\% of the volume: the centre is empty.

  • Rejection sampling accepts a cube point with probability pd=πd/2/(2dΓ(d/2+1))p_d=\pi^{d/2}/(2^d\Gamma(d/2+1)), which is 2.5×10−82.5\times10^{-8} at d=20d=20: correct, and useless.

  • Normalising a Gaussian vector gives a uniform direction on the sphere, because the Gaussian density depends only on the length of the vector.

  • For a uniform point inside the ball the radius must satisfy P(R≤r)=rd\mathbb{P}(R\le r)=r^d, hence ρ=a1/d\rho=a^{1/d} with a∼U(0,1)a\sim\mathcal{U}(0,1); scaling by a uniform ρ\rho without the root crowds the centre.

  • A Gaussian sample in dd dimensions sits in a shell of radius d\sqrt{d} whose thickness does not grow with dd — the geometric fact behind the Johnson–Lindenstrauss lemma.

Exercises

  1. For d=10d=10 and ϵ=0.01\epsilon=0.01, what fraction of the volume of the unit ball lies in the shell 0.99<r≤10.99<r\le1? Check the number with shell_volume.

  2. Measure the acceptance ratio of rejection sampling for d=2,…,12d=2,\ldots,12 and compare it with pdp_d. At which dd does it fall below 1%1\%?

  3. Generate 104 points with ρ=a1/d\rho=a^{1/d} for d=2d=2 and d=5d=5 and plot the histogram of ∥x∥\lVert x\rVert. Where is the mode, and what does the theory predict?

  4. Keep the Gaussian radius but replace the direction by a random ±1\pm1 vector (signs of Gaussian coordinates). Are the points still uniform on the sphere? Explain what you see.

  5. Simulate Gaussian samples for d=10,100,1000d=10,100,1000 and measure the standard deviation of ∥x∥\lVert x\rVert. The χ2\chi^2 identity gives variance 2d2d for ∥x∥2\lVert x\rVert^2, i.e. about 1/21/\sqrt{2} for ∥x∥\lVert x\rVert. Check it.

Sources

  • A. Blum, J. Hopcroft, R. Kannan, Foundations of Data Science, the sections on sampling in high dimension and the thin shell.

  • Zaki & Meira (2020), Ch. 6 (figures reused on the theory page).

References
  1. Zaki, M. J., & Meira, W. (2020). Data Mining and Machine Learning: Fundamental Concepts and Algorithms (2nd ed.). Cambridge University Press. https://www.cambridge.org/9781108497367