7
$\begingroup$

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 ?

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – Fixed Point
    Aug 6, 2013 at 9:06

3 Answers 3

Reset to default
2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – alw
    Feb 1, 2016 at 4:41
1
$\begingroup$

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

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

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.

$\endgroup$
9
  • $\begingroup$ How do you relate $x$ and $r$ in your pdf? $\endgroup$
    – user494522
    Dec 25, 2020 at 9:40
  • $\begingroup$ @Saeed Thanks for spotting that. It should have been just $x$. That typo was there for a long time. $\endgroup$
    – David K
    Dec 25, 2020 at 14:37
  • $\begingroup$ 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? $\endgroup$
    – user494522
    Dec 25, 2020 at 19:59
  • $\begingroup$ @Saeed I think it's a more complete answer now. Hope that helps. $\endgroup$
    – David K
    Dec 25, 2020 at 20:28
  • $\begingroup$ 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$. $\endgroup$
    – user494522
    Dec 25, 2020 at 22:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .