Algorithm to generate an uniform distribution of points in the volume of an hypersphere/on the surface of an hypersphere.

I am searching two simple/efficient/generic algorithms to generate a uniform distribution of random points:

• in the volume of a n-dimensional hypersphere
• on the surface of a n-dimensional hypersphere

knowing the dimension $n$, the center of the hypersphere $\vec{x}$ and its radius $r$.

How to do that ?

• What kind of a random number generator are you using? Can you only generate uniformly in [0,1]? Or can you generate normally distributed random numbers as well? Aug 6, 2013 at 9:06

Aperantly, for picking points on the surface of a hypersphere is to generate $n$ Gaussian random variables $x_1, x_2, ...x_n$, and then use the vectors:

$$\frac{1}{\sqrt{x_1^2+x_2^2+...+x_n^2}} \left( \begin{array}{c} x_1\\ x_2\\ ..\\ x_n\\ \end{array} \right)$$ Which will be uniformly distributed on the the surface of the hypersphere.

• The Gaussian random variables should be standard normal, i.e. N(0,1). The above formula gives a random vector on the unit n-sphere. This can be generalized to the n-sphere of radius r by simply scaling the resulting vector.
– alw
Feb 1, 2016 at 4:41

For the volume I'd say the simlest algorithm would be a standard accept-reject algorithm.

(1) draw a uniform random point within an n-dimensional hypercube
(2) repeat (1) if the distance exceeds $r$, otherwise done


if im not mistaken though, accept-rates decrease as $n$ increases, maybe there is something more efficient

edit you can also find some ideas here: Picking random points in the volume of sphere with uniform probability

edit2 thanks to @awkward for pointing out that my suggestion to draw uniformly distributed angles is not a valid method to obtain points on the surface

• Welcome to Math@SE!! Do note that this is a highly unoptimized way of generating points, especially for large $n$. Jul 19, 2013 at 0:25
• the accpet-reject-method, yes. but for the surface points?
– sheß
Jul 19, 2013 at 0:28
• Beware! Generating uniformly distributed angles (latitude and longitude) will not give you uniformly distributed points on the surface of the three-dimensional sphere. Jul 19, 2013 at 0:40

You have an answer for the surface of the sphere, so I'll just address the question about the interior of the $$n$$-ball.

For sufficiently small $$n,$$ the rejection method is a reasonably efficient way to get a uniformly distributed random point in the unit ball of $$n$$ dimensions.

For larger $$n,$$ a more efficient way to get a uniform distribution within an $$n$$-dimensional ball is to first find a point uniformly distributed on the surface of an $$n$$-dimensional sphere, and then take a point in the same direction from the origin but at a random distance. Given that the ball has unit radius, a concentric smaller ball of radius $$x$$ has volume $$x^n$$ times the volume of the unit ball, so if $$X$$ is the distance from the center to a randomly chosen point inside the unit ball, the probability distribution function of $$X$$ should be $$F_X(x) = \mathbb P(X \leq x) = \begin{cases} 0 & x < 0, \\ x^n & 0 \leq x \leq 1, \\ 1 & x > 1. \end{cases}$$

The probability density function of $$X$$ then is the derivative of the distribution (almost everywhere), $$f_X(x) = \begin{cases} n x^{n - 1} & 0 \leq x \leq 1, \\ 0 & \text{otherwise}. \end{cases}$$

In order to produce a variable $$X$$ with such a distribution, given a variable $$U$$ that is uniformly distributed on $$[0,1],$$ note that for $$0 \leq x \leq 1,$$ $$\mathbb P(X \leq x) = x^n = \mathbb P(U \leq x^n) = \mathbb P(U^{1/n} \leq x),$$ so you can set $$X = U^{1/n}.$$

For a ball of radius $$r$$ around an arbitrary center, just take the unit ball, scale it to radius $$r$$ and translate it so its center is at the desired location.

• How do you relate $x$ and $r$ in your pdf?
– user494522
Dec 25, 2020 at 9:40
• @Saeed Thanks for spotting that. It should have been just $x$. That typo was there for a long time. Dec 25, 2020 at 14:37
• My pleasure! Can you please explain how did you come up with the pdf function? Also, let $p \in \mathbb{R}^n$ and $p \sim N(0, I)$, then a random point on the surface is $p_s=p/||p||$, how would you use f$(x)$ to map $p_s$ inside the ball?
– user494522
Dec 25, 2020 at 19:59
• @Saeed I think it's a more complete answer now. Hope that helps. Dec 25, 2020 at 20:28
• Thank you for the quick response. There is a problem with scaling factor $X=U^{1/n}$ when $n$ gets larger since no matter how small $U$ is $X \rightarrow 1$ which means points will not be mapped inside the unit ball but they will accumulate near the surface. Let's say $n=256$, then, e.g., $U^{1/n}=0.000001^{(1/256)}=0.9474635$.
– user494522
Dec 25, 2020 at 22:20