Haar measure on $O(n)$ reduced to simpler probability space

The background of this question is how a random variable $X$ on the orthogonal group $O(n)$ whose distribution is the normalized Haar measure $\mu$, i.e., $\mu( O(n) ) = 1$, can be realized on a computer that has access to a number of "simpler" random variables, like:

• a perfect coin
• the uniform probability measure on $[0,1]$ or $S^1$
• Gaussian variables on $\mathbb R$ with arbitrary standard deviation.

An algorithm needs to use the random variable $X$, but I am not aware of an explicit formula that would allow for such a reduction.

-
Pick a first unitary vector $v_1$ at random by renormalising a standard Gaussian random variable in $\mathbb{R}^n$. Generate a second vector $v_2$ by generating a standard Gaussian vector, project it onto $v_1^{\perp}$ and renormalize it. Generate a third vector $v_3$ by generating a standard Gaussian vector, project it onto $\text{span}(v_1,v_2)^{\perp}$ and renormalize, etc... The vectors $v_1, \ldots, v_n$ are the column of the matrix you are looking for. – Alekk Jun 12 '13 at 7:30
@Alekk: Gram-Schmidt is a numerically unstable algorithm for producing a QR decomposition. It is better to used a canned QR decomposition routine from a numerical library. – Yoav Kallus Jun 12 '13 at 18:03

Starting from a real $N\times N$ matrix and essentially performing a $QR$ decomposition, then if the initial real matrix elements are independent identically distributed Gaussian, then the matrices $Q$ will be Haar-distributed on $O(N)$. Please see the full construction in the following article by: Francesco Mezzadri