Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I want to pick a random direction in n-dimensional space. How can I do this?

The reason I want to do this is to pick a neighbor for hill climbing optimization.

share|improve this question

4 Answers 4

up vote 10 down vote accepted

You can proceed as explained at http://mathworld.wolfram.com/HyperspherePointPicking.html

share|improve this answer

The easiest way to do this efficiently is to rely on the fact that a gaussian distribution is spherically symmetric and also separable. So, what you need to do is :

1) Build a vector V where each element is a Gaussian distributed value of mean 0, choose any width that makes sense.

2) Normalize the vector V

This vector now is a random unit vector uniformly distributed across the hypersphere of the vector V. This algorithm is both fast and is linear in the dimension of V.

share|improve this answer
    
The Box–Muller transform may be used to generate independent pairs of normally distributed variables from independent pairs of (continuous) uniformly distributed ones (with no 'waste'). –  Rhubbarb Oct 14 at 7:52

A simple method is to pick $n$ random numbers $x_1, \ldots, x_n$ from the interval [-1,1]. If $\sum x_i^2 > 1$ throw those numbers out and try again. Otherwise, rescale so that $\sum x_i^2 = 1$.

For large $n$ this is inefficient with computer time (because $\sum x_i^2 > 1$ most of the time), but it might be more efficient with your time (because it's easy to program).

share|improve this answer
4  
That doesn't sound right. Can you give or refer to a proof? Anyway, I think the usual approach of "generate $n$ iid standard Gaussian and divide the resulting vector by its norm" is simpler to program and faster to run. –  Nate Eldredge May 27 '10 at 16:53
    
Those $\sum x_i$ are supposed to be $\sum x_i^2$. –  Ben Wieland May 27 '10 at 20:08
    
@Ben: Oops, you're right. That's what I meant but apparently not what I typed. Fixed now. @Nate: Does it sound right after the correction? I'm just choosing a random point in the unit ball and rescaling. –  Kevin Walker May 27 '10 at 21:32
3  
It sounds right. It also sounds truly inefficient ... in high dimensions you will have to sample a ridiculously large number of points to get one that works. –  Peter Shor May 28 '10 at 10:56
1  
Indeed, you should expect $(n/2)!(\pi/2)^{-n/2}$ trials before success. For $n=10$ it's about 1000, and for $n=100$... let's just say, too many. –  Nate Eldredge May 28 '10 at 13:42

The GNU Scientific Library (GSL) has an implementation for this. See http://www.gnu.org/software/gsl/manual/html_node/Spherical-Vector-Distributions.html in the manual. It even refers to where Knuth describes the algorithm.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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