# Algorithm to generate points uniformly at random from a ball

Consider a 2-dimensional version of generating points in the circumference of a unit radius circle, independently generate each coordinate uniformly at random from the interval [-1,1].

How to generate a random point in a higher dimension? High level idea is also welcomed.

If we try to extend the above idea (2-dimensional version) it will not work as number of points inside the ball drops to zero as dimension become very high.

Note that this is not an assignment, I am reading data science currently and during reading I find out this question.

Edit: Uniformity means probability with equally likely outcomes enter link description here

• independently generate each coordinate [suitably from] [-1,1] and discard tuples outside the radius. In two dimensions, polar coordinates are a thought - too many points near the origin? Please add to the question: What is a suitable measure of uniformity? Points/probability per unit volume? Aug 2 at 12:15
• @greybeard Points/probability per unit vol. I did get the meaning of what do you mean by polar coordinates are thought?
– Shi
Aug 2 at 14:07
• I think the problem is finding a good definition of "random". Define "equally like outcome of what exactly?". Draw 100 random points on a football, then kick it. When it lands, the same 100 points should still meet your definition of "random". I would divide the ball into areas of equal size and require that the areas have uniform number of points. Aug 2 at 14:43
• For points on the earth, I'd divide earth into strips of one second of longitude each (one nautical mile), then into roughly squares each one nautical mile long. 21,600 squares at the equator, only one at the poles. Aug 2 at 14:47
• A relevant search yields, e.g., this overview, which looks like it contains the ideas you seek. Aug 2 at 15:01

The textbook that you linked outlines a solution, in the part that begins "The solution is".

1. Generate $$x_1, ..., x_d$$ independently at random with a Gaussian distribution centered at the origin. The distribution of the vector $$(x_1, ..., x_d)$$ is then rotationally invariant.
2. Normalize the vector. This gets you a distribution that is uniform on the unit sphere.
3. Multiply the normalized vector by a random scalar between $$0$$ and $$1$$ with the probability distribution $$ρ(r)=dr^{d-1}$$.

Normalizing the vector is numerically unstable if its norm is small, so you might want to discard it and reroll in that case.

Think of a sphere centered in the origin and describe the points using spherical coordinates $$(1, \theta, \phi)$$ with $$0 \le \theta \le \pi$$ and $$0 \le \phi < 2\pi$$.

Generate $$\phi$$ uniformly at random in its interval. Regarding $$\theta$$, pick it proportionally to the length of the circumference at angle $$\theta$$. I.e., its density function $$f$$ is such that $$f(\theta) \propto 2\pi |\cos(\theta)|.$$

You can compute the proportionality constant as follows: $$\int_{\theta=0}^{\pi} 2 \pi |\cos(\theta)| \, \text{d}\theta = 4\pi\int_{\theta=0}^{\pi/2} \cos(\theta) \, \text{d}\theta =4 \pi.$$

Then we have $$f(\theta) = \frac{1}{2} | \cos(\theta) |$$. The cumulative distribution function for $$\theta \le \pi/2$$ is: $$F(\theta) = \int_{\psi=0}^\theta \frac{1}{2} \cos(\psi) = \frac{1}{2}\sin(\theta),$$ and for $$\theta > \pi/2$$ it is $$F(\theta) = 1 - F(\pi-\theta) = 1-\frac{1}{2} \sin(\pi - \theta) = 1- \frac{1}{2}\sin(\theta)$$.

To choose $$\theta$$ you can first pick a number $$\psi$$ uniformly at random in $$[0,1]$$ and then let $$\theta = F^{-1}(\psi)$$, where: $$F^{-1}(\psi) = \begin{cases} \arcsin(2\psi) & \text{if } \psi \le \frac{1}{2}, \\ \arcsin( 2(1-\psi) ) & \text{if } \psi > \frac{1}{2}. \end{cases}$$

• This does not result in a uniform distribution. The points will be more dense at the poles. Aug 2 at 16:00
• @YvesDaoust. Oh yeah, I see it now. The length of the circumference at a certain angle $\theta$ changes with $\theta$ so $\theta$ needs to be sampled accordingly. I'll edit my answer. Aug 2 at 16:07