Is there an efficient way to sample uniformly points from the unit n-sphere? Informally, by "uniformly" I mean the probability of picking a point from a region is proportional to the area of that region on the surface of the sphere. Formally, I guess I'm referring to the Haar measure.


I guess "efficient" means the algorithm should take poly(n) time. Of course, it's not clear what I mean by an algorithm since real numbers cannot be represented on a computer to arbitrary precision, so instead we can imagine a model where real numbers can be stored, and arithmetic can be performed on them in constant time. Also, we're given access to a random number generator which outputs a real in [0,1]. In such a model, it's easy to sample from the surface of the n-hypercube in O(n) time, for example. 


If you prefer to stick with the standard model of computation, you can consider the approximate version of the problem where you have to sample from a discrete set of vectors that $\epsilon$-approximate the surface of the n-sphere.



Efficiently sampling points uniformly from the surface of an n-sphere
Generate $X\_1, X\_2, \ldots, X\_n$ independent, normally distributed random variables See [wikipedia](http://en.wikipedia.org/wiki/Normal_distribution#Generating_values_from_normal_distribution) for information on how to do this given some standard source of randomness, for example uniform(0,1) random variables.


Then let $Y\_i = X\_i/\sqrt{X\_1^2 + \cdots + X\_n^2}$ for $i = 1, \ldots, n$. Then $(Y\_1, \ldots, Y\_n)$ is uniformly distributed on the surface of the sphere. The time this takes is linear in $n$.


This works because the multivariate normal $(X\_1, \ldots, X\_n)$ with covariance matrix the identity (that is, $n$ independent unit normals) is rotationally symmetric around the origin.


