Sampling the d-Ball

A simple way to sample a point uniformly in the unit $d$ -ball $\{x \in \mathbb{R}^d : \lVert x \rVert \le 1\}$ is to draw a point uniformly in the cube $[-1,1]^d$ and accept it only if its norm is at most $1$ . Find the acceptance probability as a function of $d$ and describe how it behaves for $d = 1, \dots, 50$ .

Reveal solutionHide solution

#The acceptance probability

A point drawn uniformly in the cube lands inside the ball with probability equal to the ratio of their volumes,

P_d = \frac{\operatorname{vol}(\text{ball})}{\operatorname{vol}(\text{cube})} = \frac{\pi^{d/2}/\Gamma(\tfrac{d}{2}+1)}{2^d}. \tag{1}

#It collapses with dimension

The ball's volume eventually shrinks while the cube's volume keeps doubling, so $P_d$ races to zero. A clean recursion is $P_d = \tfrac{\pi}{2d}\,P_{d-2}$ , starting from $P_0 = P_1 = 1$ .

The ball fills less and less of the cube as the dimension climbs, so the acceptance probability falls off a cliff. By fifty dimensions it is around ten to the minus 28, which is why naive rejection sampling is hopeless in high dimension.

#In code

import numpy as np
from scipy.special import gammaln

d = np.arange(1, 51)
log_p = (d / 2) * np.log(np.pi) - gammaln(d / 2 + 1) - d * np.log(2)
accept = np.exp(log_p)

#Read it off

By $d = 10$ the acceptance is already about $0.0025$ , and by $d = 20$ near $2.5 \cdot 10^{-8}$ . Past a handful of dimensions, rejection from the cube is hopeless, the curse of dimensionality in miniature, and one reaches instead for a direct method like normalizing a Gaussian vector.