random unit vector in multi-dimensional space

Question

I'm working on a data mining algorithm where i want to pick a random direction from a particular point in the feature space.

If I pick a random number for each of the n dimensions from [-1,1] and then normalize the vector to a length of 1 will I get an even distribution across all possible directions?

I'm speaking only theoretically here since computer generated random numbers are not actually random.

Answer 1

One simple trick is to select each dimension from a gaussian distribution, then normalize:

from random import gauss  def make_rand_vector(dims):     vec = [gauss(0, 1) for i in range(dims)]     mag = sum(x**2 for x in vec) ** .5     return [x/mag for x in vec] 

For example, if you want a 7-dimensional random vector, select 7 random values (from a Gaussian distribution with mean 0 and standard deviation 1). Then, compute the magnitude of the resulting vector using the Pythagorean formula (square each value, add the squares, and take the square root of the result). Finally, divide each value by the magnitude to obtain a normalized random vector.

If your number of dimensions is large then this has the strong benefit of always working immediately, while generating random vectors until you find one which happens to have magnitude less than one will cause your computer to simply hang at more than a dozen dimensions or so, because the probability of any of them qualifying becomes vanishingly small.

Answer 2

You will not get a uniformly distributed ensemble of angles with the algorithm you described. The angles will be biased toward the corners of your n-dimensional hypercube.

This can be fixed by eliminating any points with distance greater than 1 from the origin. Then you're dealing with a spherical rather than a cubical (n-dimensional) volume, and your set of angles should then be uniformly distributed over the sample space.

Pseudocode:

Let n be the number of dimensions, K the desired number of vectors:

vec_count=0 while vec_count < K    generate n uniformly distributed values a[0..n-1] over [-1, 1]    r_squared = sum over i=0,n-1 of a[i]^2    if 0 < r_squared <= 1.0       b[i] = a[i]/sqrt(r_squared)  ; normalize to length of 1       add vector b[0..n-1] to output list       vec_count = vec_count + 1    else       reject this sample end while