4
$\begingroup$

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.

Improve this question
$\endgroup$

4 Answers 4

Reset to default
11
$\begingroup$

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

Improve this answer
$\endgroup$
7
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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'). $\endgroup$
    – Rhubbarb
    Commented Oct 14, 2014 at 7:52
2
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • 4
    $\begingroup$ 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. $\endgroup$
    – Nate Eldredge
    Commented May 27, 2010 at 16:53
  • $\begingroup$ Those $\sum x_i$ are supposed to be $\sum x_i^2$. $\endgroup$
    – Ben Wieland
    Commented May 27, 2010 at 20:08
  • $\begingroup$ @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. $\endgroup$
    – Kevin Walker
    Commented May 27, 2010 at 21:32
  • 3
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Commented May 28, 2010 at 10:56
  • 1
    $\begingroup$ 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. $\endgroup$
    – Nate Eldredge
    Commented May 28, 2010 at 13:42
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .