How to pick a random direction in n-dimensional space

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.

-

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

-

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.

-
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 '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).

-
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
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
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.

-