What is a good method to find random points on the n-sphere when n is large?

Question

As part of a more complex algorithm, I need a fast method to find random points of the n-sphere, $S^n$, starting with a RNG (random number generator). A simple way to do this (in low dimensions at least) is to select a random point of the (n+1)-ball and normalize it. And to get a random point of the (n+1)-ball select a random point of the (n+1)-cube $[-1,1]^{n+1}$ (by selecting (n+1) points of $[0,1)$ with the RNG and scaling using $x \mapsto 2x-1$) and then use "rejection", i.e., just ignore a point if it is not in the (n+1)-ball. This works fine if n is reasonably small, however for large n the volume of the ball is such a tiny fraction of the volume of the cube that rejection is enormously inefficient. So what is a good alternative approach.

Answer 1

The usual approach is to generate $n+1$ i.i.d. mean zero Gaussian random variables $X_1, \dotsc, X_{n+1}$ to get a random point $X$ in $(n+1)$-space with rotationally invariant distribution and normalize.

Incidentally, if you ever actually need to generate a random point in an $n$-ball, the best way is probably to generate a random point in the $(n+1)$-sphere as above and drop the last two coordinates.

Answer 2

Here some algorithm that produce normal distributed random numbers :

1) Polar algorithm

2) Ziggurat algorithm

3) Box-Muller algorithm

By dividing the random vector of n+1 random numbers by the norm of the vector you get random numbers on the n-sphere.

Answer 3

I can't resist linking to this gem which describes a simple method for a generalisation of your problem.

Answer 4

Nice question! I ran into a similar problem a few years ago -- even for dimension $10$, the rejection method was annoyingly slow. One of the problems is that such questions straddle at least three huge fields (discrete mathematics, statistics and CS), so often one doesn't know where to start looking.

Here's what we finally used: a nice, explicit solution for how to generate uniformly random points on the $n$-sphere can be found in Section III of the unpublished paper:

Cumbus, Damien, Walker, Uniform sampling in the hypersphere via latent variables and the Gibbs sampler (1996).

You can find a copy of their work here. If you want to sample from some measurable subset of the $n$-sphere instead of the whole thing, try the (much less explicit) technical report

Shao, Badler, Spherical Sampling by Archimedes' Theorem (also 1996)

which can be found here. Good luck with your algorithm.

Answer 5

If you convert to an n-dimensional spherical coordinate system, then you would need n-1 angles and a radius (in [0,1]) to uniquely determine a point within (or on) the n-sphere. (If you want points strictly on the n-sphere, force the radius to be 1).

To get the angles, utilize a uniform distribution over [0,2*pi). The radius is another uniform variate over [0,1]. Then you get a uniform distribution over the n-sphere by conversion (from the wikipedia page for the n-sphere):

x_1 = r*cos(phi_1)

x_2 = r*sin(phi_1)*cos(phi_2)

. . .

x_{n-1} = r*sin(phi_1)*sin(phi_2)*...*sin(phi_{n-2})*cos(phi_{n-1})

x_n = r*sin(phi_1)*sin(phi_2)*...*sin(phi_{n-2})*sin(phi_{n-1})

The cost of this is n-1 uniform variates (and another if you want r in [0,1]) and the subsequent cosine and sine operations (most of which can be reused...)