# How to generate uniformly random points on n-spheres and in n-balls

For many Monte Carlo methods, such as those in graphical computing, it is critical to uniformly sample from $d$-dimensional spheres and balls. This post describes over twenty different methods to uniformly random sample from the (surface of) a $d$-dimensional sphere or the (interior of) a $d$-dimensional ball.

First published: 10th March, 2019 Last updated:    16 April, 2020

# Introduction.

This post gives a comprehensive list of the twenty most frequent and useful methods to uniformly sample from a the surface of a  $d$-sphere, and the interior of the $d$-ball.

Many of them are simple and intuitive; others utilize well-known math methods in sophisticated ways; whilst others can only be described as truly remarkable in their structure. The choice of which one suits your needs will most likely be a balance between code complexity and time efficiency. However, other aspects such as variance reduction may also be of considerable importance.

It is of course, always possible to use the most generalised versions of these formulae as outlined in methods 19-22 for all $d$, but I specifically list some of the specialised methods for smaller $d$ because they may be more efficient, relevant to your application,  and/or amenable to understanding than their  more general expressions. Furthermore, many of the methods applicable to the lower dimensions do not have simple or natural generalization.

### Definition of the $d-$sphere and $d$-ball.

Let us recap the standard definitions of spheres and balls in $d$-dimensions.

A unit $d-$dimensional sphere is defined such that:

$$S^d = \left\{ x \in \Bbb{R}^{d+1} : \left \lvert x \right \rvert = 1 \right\}$$

And a unit $d-$dimensional ball is defined such that:

$$B^d = \left\{ x \in \Bbb{R}^{d} : \left \lvert x \right \rvert \leq 1 \right\}$$

So the perimeter of a circle is a 1-sphere, and the interior of the circle (a disk) is a 2-ball.

And if the earth was perfectly spherical, than the surface of earth would be a 2-sphere, and the interior of  the earth would be a 3-ball.

The way I remember these definitions, is that for both the $d$-sphere and the $d$-ball, the $d$ signifies how many degrees of freedom it has.

### Uniform Random Sampling

In this post, we adopt the convention that ‘uniform random sampling‘, ‘(continuous) simple random sampling‘, and even ‘uniform sampling‘ are all fully synonymous. And that for discrete probabilities, this means that all possible elements of $S$ have an equal probability of being selected. For continuous probabilities, this means that the likelihood of an element falling in any subinterval is directly proportional to the length of the subinterval.

Virtually all computer languages have a built-in function for this concept. For example , $\text{rand}(\cdot)$, that produces a random number that is (pseudo)-randomly drawn from uniform distribution $[0,1)$.

### Note 1.

In contrast to many of my other posts on this blog, we are not talking about quasirandom sampling (aka ‘evenly distributed’), we are just talking about ‘plain old simple vanilla’ uniform random sampling.

### Note 2.

For the coding examples, I generally use readable python code (built on numpy), except for acceptance/rejection methods where I used pseudo-code. The purpose of the code is aimed for clarity and so does not necessarily include language-specific conventions or optimizations. It uses the notation that $x**y$ is equal to $x^y$.

Although each of them have their strengths and weaknesses, an asterisk (*) indicates methods that I believe are an excellent default option for that section.

# Uniformly sampling a 1-sphere (a circle).

That is, uniformly sampling points on the circumferende of a circle.

### *Method 1. Polar

This should be very clear to everyone, and is the foundation for many of the other methods.

theta = 2*PI * random()
x = cos(theta)
y = sin(theta)


### Method 2. Rejection Method

A lesser-known method (Cook, 1957) that does not directly require trigonometric functions.

You might notice that the expressions have almost identical structure to Pythagorean triplets!

(This method is better known when generalised to the 2-sphere.)

Select u,v ~ U(-1,1)
d2 = u^2+v^2
If d2 >1 then
reject and go back to step 1
Else
x = (u^2-v^2)/d2
y = (2*u*v)/d2
Return (x,y)


### Method 3. Muller , Marsaglia (‘Normalised Gaussians’)

This method was first proposed by Muller and then Marsaglia and the popularised by Knuth, it is very elegant. It naturally generalizes and remains efficient for higher dimensions.

Presumably, it is less well-known due to the less obvious (magical?!) relationship between a circle and the Normal Distribution.

Note that in this version (and its generalizations), the standard deviation does not have to be 1, it just has to be identical for all the random variates. However, in nearly all implementations, a standard error of 1 is picked due to its convenience.

Also, in the absence of a native function, a simple and common method to draw from a normal distribution is via the #

# Uniformly sampling a 2-ball (disk).

That is, uniformly sampling points inside a circle.

### *Method 4. Rejection Method

This is probably the most intuitive method, and is quite fast for a 2-ball.

However, (as discussed later) it generally gets a bad rap, because if you generalize this algorithm to higher dimensions, it can become catastrophically very inefficient.

## 6 Replies to “How to generate uniformly random points on n-spheres and in n-balls”

1. Dimitris Kechrakos says:

Excellent summary and presentation of algorithms. Thank you for this contribution.