I want to pick a random direction in ndimensional space. How can I do this?
The reason I want to do this is to pick a neighbor for hill climbing optimization.
I want to pick a random direction in ndimensional 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. 


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


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

