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:
the thin shell: the fraction of the volume of a ball that lies near its surface;
rejection sampling: why “generate in the cube, keep what is inside the ball” stops working;
uniform points on a hypersphere, by normalising Gaussian vectors;
uniform points inside the ball, by inverse-transform sampling of the radius;
the Gaussian annulus: the same shell phenomenon for Gaussian data.
import math
import matplotlib.pyplot as plt
import numpy as np
def hypersphere_volume(d, R):
"""Volume of the solid ball of radius R in d dimensions."""
return (math.pi ** (d / 2)) * (R ** d) / math.gamma(d / 2 + 1)
np.random.seed(0) # reproducible figures
print("V_2 =", round(hypersphere_volume(2, 1), 4),
"| V_3 =", round(hypersphere_volume(3, 1), 4))
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 near the surface of a sphere of radius . The volume of this shell is:

The ratio of the shell’s volume to the total volume is:
As , the term tends to 0.
For example, for a circle in two dimensions, with r =1 and = 0.01 the volume of the thin shell is . 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 .
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.
def shell_volume(d, R, e):
"""Volume of the layer R - e < |x| <= R."""
return hypersphere_volume(d, R) - hypersphere_volume(d, R - e)
dims = list(range(1, 30))
ratio = [shell_volume(d, 1, 0.2) / hypersphere_volume(d, 1) for d in dims]
plt.figure(figsize=(10, 6))
plt.plot(dims, ratio, marker='o', linestyle='-', color='b',
label=r'shell volume / ball volume ($\epsilon = 0.2$)')
plt.xlabel('dimension d')
plt.ylabel('fraction of the volume inside the shell')
plt.title('A thin shell holds almost all the volume of a high-dimensional ball')
plt.ylim(0, 1.02)
plt.legend()
plt.grid(True)
plt.show()
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 and keep those inside the unit ball. The acceptance probability is the volume ratio of the ball to the cube:
so , and . Rejection sampling stops being an option well before : it is correct, and useless. The next cell measures exactly this.
import numpy as np
import matplotlib.pyplot as plt
np.random.seed(0) # reproducible figures
# Function to generate num_points points uniformly inside a d-dimensional unit sphere
def generate_points_in_unit_sphere(num_points, d):
points_inside = []
total_generated_points = 0 # To track the total number of points generated
batch_size = num_points # Initial batch size for generating points
while len(points_inside) < num_points:
# Generate batch_size points uniformly in the d-dimensional hypercube
points = np.random.uniform(-1, 1, (batch_size, d))
# Calculate the Euclidean distance of each point from the origin
distances = np.sum(points**2, axis=1)
# Select points that lie inside the unit sphere
inside_sphere = points[distances <= 1]
# Append the points inside the sphere to the list
points_inside.extend(inside_sphere)
# Count total generated points
total_generated_points += len(points)
# Adjust batch size if we're close to the desired number of points
remaining_points = num_points - len(points_inside)
if remaining_points < batch_size:
batch_size = remaining_points
# Convert the list to a numpy array for efficient storage and manipulation
points_inside = np.array(points_inside[:num_points])
# acceptance ratio: accepted / generated
ratio = num_points / total_generated_points
# Return the points inside the sphere and the ratio
return points_inside, total_generated_points, ratio
# Visualize 2D case
def visualize_2D(points):
plt.figure(figsize=(6, 6))
plt.scatter(points[:, 0], points[:, 1], s=1)
plt.title('2,000 Points Uniformly Distributed in a 2D Unit Circle')
plt.gca().set_aspect('equal')
plt.show()
# Generate and visualize points in various dimensions
num_points = 2000
dimensions = list(range(2, 11)) # d from 2 to 10
ratios = [] # To store the ratios for different dimensions
for d in dimensions:
points_inside, total_generated_points, ratio = generate_points_in_unit_sphere(num_points, d)
ratios.append(ratio)
if d == 2:
# For 2D case, visualize the points
visualize_2D(points_inside)
print(f"Dimension: {d}, Total points generated: {total_generated_points}, Ratio: {ratio}")
# Plot the ratios for dimensions from 2 to 10
plt.figure(figsize=(8, 6))
plt.plot(dimensions, ratios, marker='o')
plt.title('Acceptance ratio of rejection sampling, d = 2 to 10')
plt.xlabel('Dimensions')
plt.ylabel('accepted / generated')
plt.grid(True)
plt.show()

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

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.
n_points = 500
d = 2
x = np.random.randn(n_points, d)
plt.figure(figsize=(5, 5))
plt.scatter(x[:, 0], x[:, 1], s=4)
plt.title(f'{n_points} points from a {d}-D standard Gaussian')
plt.gca().set_aspect('equal')
plt.show()
Random vector uniformly distributed on the surface of a unit hypersphere¶
To generate a random vector uniformly distributed on the surface of a unit hypersphere :
Generate for .
Normalize: .
This works because the multivariate Gaussian is spherically symmetric.
norm_x = np.linalg.norm(x, axis=1)
y = x / norm_x[:, np.newaxis]
plt.figure(figsize=(6, 6))
plt.scatter(x[:, 0], x[:, 1], s=1, label='Gaussian points')
plt.scatter(y[:, 0], y[:, 1], s=8, label='after normalisation (unit circle)')
plt.title('Normalising a Gaussian sample puts it on the unit circle')
plt.legend()
plt.gca().set_aspect('equal')
plt.show()
The joint probability density of the independent Gaussian components is spherically symmetric:
Since the density depends only on the length and not the direction, the direction vectors are uniformly distributed.
Conclusion: The density function depends only on the length (magnitude) of the vector , 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 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 :
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.
rho = np.random.rand(len(x))
y_naive = rho[:, np.newaxis] * x / norm_x[:, np.newaxis]
plt.figure(figsize=(6, 6))
plt.scatter(x[:, 0], x[:, 1], s=1)
plt.scatter(y_naive[:, 0], y_naive[:, 1], s=8, color='tab:orange')
plt.title(r'Scaling a surface point by a uniform $\rho$ crowds the centre')
plt.gca().set_aspect('equal')
plt.show()
Why is the naive approach incorrect?
If we simply sample the radius uniformly from , the generated points will cluster near the center.
In dimensions, the volume of a thin shell at radius grows proportionally to .
This means there is far more volume near the surface () than near the center ().
To achieve a truly uniform distribution inside the ball, the probability of a point lying within radius must be proportional to the volume enclosed by that radius.
For uniform volume density, the cumulative distribution function (CDF) must follow the volume growth .
Thus, we require the random variable (the radius) to satisfy: Using Inverse Transform Sampling with , we obtain: A particular sample of will be denoted by .
1. Determining the Target CDF¶
Let denote the random variable representing the radius of a point.
The cumulative distribution function (CDF), , gives the probability that a point lies within radius :
For a uniform distribution inside the ‑ball, this probability equals the ratio of the volume of the ball of radius to the total volume (radius 1):
So our target CDF is simply:
2. Inverse Transform Sampling¶
How do we generate random radii that follow ?
We use the Inverse Transform Sampling method:
If and is a continuous CDF, then has distribution .
Intuitively: we draw a random probability from , and ask: “Which radius corresponds to this cumulative probability?”
Formally: If , then has distribution :
Therefore, if , then:
And when we actually generate a sample, we denote it by:
3. Example (for )¶
For a 2‑dimensional ball (a disk), we have:
| 0.00 | 0.000 |
| 0.10 | 0.316 |
| 0.25 | 0.500 |
| 0.50 | 0.707 |
| 0.75 | 0.866 |
| 1.00 | 1.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 :
Generate a uniform random number .
Compute the radius sample: .
Combine with a random direction to obtain a point inside the ball.
Algorithm for Uniform Points in a ‑Ball¶
Generate a random vector .
Normalize: (this gives a random direction on the unit sphere).
Generate .
Scale: (this places the point uniformly inside the ball).
# Uniform points inside a 2-D ball
n_points = 500
d = 2
# 1. Direction: normalise a Gaussian vector (uniform on the sphere)
x = np.random.randn(n_points, d)
norm_x = np.linalg.norm(x, axis=1)
y_surface = x / norm_x[:, np.newaxis]
# 2. Radius: rho = a**(1/d), so that P(R <= r) = r**d
a = np.random.rand(n_points)
rho = a ** (1 / d)
y_inside = rho[:, np.newaxis] * y_surface
plt.figure(figsize=(5, 5))
plt.scatter(x[:, 0], x[:, 1], s=1, label='Gaussian points')
plt.scatter(y_inside[:, 0], y_inside[:, 1], s=8, label='uniform in the ball')
plt.gca().set_aspect('equal')
plt.legend()
plt.title(f'Uniform points inside the {d}-D unit ball')
plt.show()
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 .
In one dimension, many sampled points lie “close to zero,” and the distance 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
Volume
In general: hypersphere volume
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 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:
Thus (See Chi-squared distribution):
In 1D: (close to the center)
In 2D:
In 10D:
In 200D:
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 .
This is the statistical analogue of the geometric thin-shell effect.
Numerical Simulation: Gaussian Thin Shell¶
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
# Simulation: 1D vs High-D Gaussian
d = 200
n_samples = 5000
# 1D Gaussian
x_1d = np.random.randn(n_samples)
# High-D Gaussian
x_high = np.random.randn(n_samples, d)
norm_x_high = np.linalg.norm(x_high, axis=1)
fig, ax = plt.subplots(1, 2, figsize=(12, 5))
# Plot 1: 1D behavior
sns.histplot(x_1d, kde=True, ax=ax[0], color='blue')
ax[0].set_title("1D Gaussian: Mass at Mean")
ax[0].set_xlabel("Value")
ax[0].axvline(0, color='red', linestyle='--', label='Mean (0)')
# Plot 2: High-D behavior
sns.histplot(norm_x_high, kde=True, ax=ax[1], color='green')
ax[1].set_title(f"{d}-D Gaussian: Mass at Tail ($\sqrt{{d}}$)")
ax[1].set_xlabel("Distance from Origin (Norm)")
ax[1].axvline(np.sqrt(d), color='red', linestyle='--', label='$\sqrt{d} \\approx 14.1$')
ax[1].axvline(0, color='black', linestyle='-', label='Mean (0)')
ax[0].legend()
ax[1].legend()
plt.tight_layout()
plt.show()<>: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$')

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 — a thin annulus whose thickness does not grow with .
As increases:
Radius grows like
Shell thickness remains constant
Relative shell thickness 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 Gaussian mass avoids the center, exactly like uniform points.
Relation to “Thin Shell Argument”
Uniform hypersphere volume concentrates at radius : Gaussian probability mass concentrates at radius . The geometry is identical; only the radius scale differs.
Relation to “Generating Points Inside the Ball”
You observed that uniform points require special sampling () 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 , 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 is of the whole ball, so for a peel holds of the volume: the centre is empty.
Rejection sampling accepts a cube point with probability , which is at : 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 , hence with ; scaling by a uniform without the root crowds the centre.
A Gaussian sample in dimensions sits in a shell of radius whose thickness does not grow with — the geometric fact behind the Johnson–Lindenstrauss lemma.
Exercises¶
For and , what fraction of the volume of the unit ball lies in the shell ? Check the number with
shell_volume.Measure the acceptance ratio of rejection sampling for and compare it with . At which does it fall below ?
Generate 104 points with for and and plot the histogram of . Where is the mode, and what does the theory predict?
Keep the Gaussian radius but replace the direction by a random vector (signs of Gaussian coordinates). Are the points still uniform on the sphere? Explain what you see.
Simulate Gaussian samples for and measure the standard deviation of . The identity gives variance for , i.e. about for . 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).
- 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