Generation of uniform sampling points on and within N dimensional hyperspheres

Problem:

Rejection method is less effective the larger the dimension N is since we have:

(Volume of unit N-sphere)/ (Volume unit N-cube) =

This ratio decreases fast with increasing N. More and more points will be generated outside the hypersphere.

Specific Methods N=3

Specific Methods (Tashiro, Sibuya, Marsaglia and their variants)

General methods (isotropic)

Distribution of distances between points on and within a hypersphere

Paradoxa

References

Simple method for N = 3

Choose a random number s uniformly distributed in [-1, 1] and a random number uniformly distributed in . The x, y and z coordinates of the point are given by:

The principle underlying this algorithm is that for a sphere of radius R, the area of a zone of width h is always 2Rh, regardless of where the sphere is sliced. Therefore the Z-coordinates of random points on a sphere are distributed uniformly. Points obtained by using this algorithm are then uniformly distributed on the surface of the sphere.

Specific methods

Approaches used for specific number of dimensions N that are fast. Different algorithms using different transformations and coordinate representations.

Methods ala Sibuya, Tashiro, Marsaglia and its modifications

Map from Hyper-Rectangle to Hypersphere. Jacobian of Transformation should not depend on parameters for uniform distributions. Use of transformations to avoid calculation of sin and cos terms for efficient computation.

Methods: From N=4 to N=3, N=6 to N=5, N=8 to N=7…

N = 4

Hyperspherical coordinates

Rodriguez coordinates

• Generation of random points (Sibuya)

,

• Modified Marsaglia

Generate until

• Original Marsaglia

Generate until

Generate until

N = 3

Set , u₂ = 1-2T

• Sibuya Tashiro

• Marsaglia

Generate until

N = 6

• Sibuya

,

• Modified Marsaglia

, ,,

, , subject to constraints: ,,

• Modified Marsaglia

, ,

subject to constraints: ,

N = 5

Replace with

• Tashiro

,

• Modified Marsaglia

Set v1 = 0

,

N = 8

Hyperspherical coordinates

• Sibuya

General methods

The Isotropic method

Use hyperspherical coordinates

...

or shortly

for k = 1,...,N-1

The inverse transform is

k = 1,...,N-2

The Jacobian J of this transform is

Algorithm for the Isotropic method for producing random points on and if necessary inside a unit N-hypersphere

for i = 1,...,N {

Generate normal distributed number Generate N normal numbers

With mean 0 and sigma = 1 (USE for example BOX-MULLER)

}

Calculate

for i = 1,...,N {

Project onto surface

}

If (points also within the hypersphere) then { Vary the r distance

where a random uniformly distributed number

for i = 1,...,N {

}

}

The idea is that products of Gaussian distributions are also Gaussians. The z vectors are isotropically distributed. Then also the vectors x will be of norm 1 and also isotropically distributed. Therefore the points will be distributed uniform of the hypersphere. If we want to have also points inside the hypersphere we have to rescale these coordinates taking into consideration the dimension N.

References

W. P. Petersen, A. Bernasconi, Uniform sampling from an n-sphere, Swiss Center for Scientific Computing, ETH Zentrum, CH8092, Zürich, 10-July, 1997

G. Marsaglia, Ann. Math Stat 43, 645 (1972)

Luban, Marshall, and Lawrence P. Staunton, An efficient method for generating a uniform distribution of points within a hypersphere: Computer in Physics, 2(6), 55 (1988)

Last Update 28-12-2003