3
$\begingroup$

I want to generate k n-dimensional vectors which are all inside a r-radius n-sphere and the most important : I want something uniformly distributed inside the n-sphere.

My initial idea is to generate a n-dimensional vector with n random values uniformly distributed between [-1, 1], then normalize the vector and multiply it by a random number from an uniform distribution [0,r].

However, I did some research and for example Boost lib (http://www.boost.org/doc/libs/1_47_0/boost/random/uniform_on_sphere.hpp) uses a normal distribution (0, 1) in order to generate points uniformly distributed on a n-sphere. So it seems that I should use a normal distribution if I want something uniform and I do not understand it.

I written a simple code and tried it for 2 dimensions but the result is not uniform and I do not understand why: example

def genVectorNormal(count, dim, radius) :
result = []
for i in range(count) :
    vec = np.random.normal(0, 1, dim)
    #vec = np.random.uniform(-1, 1, dim)
    vec = (vec / np.linalg.norm(vec)) * np.random.uniform(0,radius,1)[0]
    result.append(vec)
    return np.array(result)

radius = 1
data = genVectorNormal(100000, 2, radius)
fig, ax = plt.subplots() 
plt.plot(data[:,0], data[:,1], 'ro',  alpha=0.005)

I tried with a uniform and a normal distribution for the direction vector.

$\endgroup$
  • $\begingroup$ I have not read the code in details. There will be a substantial difference between you generate vectors inside a $n$-ball, or just on the surface. Because the multivariate normal is an elliptical distribution, and for the independent, standard normal case the distribution has a spherical symmetry. The value of the joint pdf only depends on the distance from the origin, so it can be used to generate random number on the surface of a sphere. $\endgroup$ – BGM Nov 9 '18 at 6:26
  • $\begingroup$ You might want to look at Knuth, The Art of Computer Programming, which discusses generating uniform random points on the sphere and in the ball. (The latter is relatively easy, given the former.) As I recall, it uses a normal distribution in some clever way, and is probably the source of the ideas in the BOOST library. $\endgroup$ – John Hughes Jun 25 at 20:51
  • $\begingroup$ Generate random vector on the unit $n$-sphere as you do; multiply it by $u^{1/n}$, where $u$ is uniformly distributed in $(0,1)$; and finally, multiply by the radius. $\endgroup$ – metamorphy Jun 25 at 20:52
2
$\begingroup$

The direction is not uniform

Consider choosing points at random in a square in $2$ dimensional space. If they are uniformly distributed then the probability of choosing a given direction will be proportional to the number of points in that direction from the centre of the square. A line from the centre to a vertex will be $\sqrt{2}$ times longer than a line from the centre to the middle of an edge. The probability of choosing a direction pointing towards a vertex will therefore be $\sqrt{2}$ times greater than a direction pointing towards the middle of an edge. Therefore the distribution of directions will not be uniform in $2$ dimensions.

Consider choosing points at random in a cube in $3$ dimensional space. If they are uniformly distributed then the probability of choosing a given direction will be proportional to the number of points in that direction from the centre of the cube. A line from the centre to a vertex will be $\sqrt{3}$ times longer than a line from the centre to the middle of a face. The probability of choosing a direction pointing towards a vertex will therefore be $\sqrt{3}$ times greater than a direction pointing towards the middle of a face. Therefore the distribution of directions will not be uniform in $3$ dimensions.

As the number of dimensions increases, the same applies but biased by $\sqrt{N}$ for $N$ dimensional space. The higher the number of dimensions, the worse the bias.

The Normal or Gaussian distribution gives a uniform distribution of directions for any number of dimensions, so in theory solves your problem exactly. In practice it gives a good approximation to uniform distribution, even though it cannot be exact as computer generated Gaussian random numbers only cover a finite part of the infinite domain.

Uniform distance from the centre might not be what you want

Once you have a uniformly distributed direction, choosing a uniformly random distance from the centre will not give points uniformly distributed in space. Instead there will be a roughly equal number of points at each distance from the centre, which means they will be more densely arranged near the centre, and more spread out at the outer surface of the sphere. This is because closer to the centre, the same number of points have to fit into the surface of a smaller sphere.

If what you want is uniformly distributed points in space, rather than uniformly distributed radii, you can reverse this effect by generating a uniform radius in $[0, 1]$ and then taking its $N^{th}$ root. This will cancel out the increasing size of larger spheres and make the points uniformly distributed in the volume.

In writing this I also found a more in depth explanation if you want further information.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.