How can I generate a random walk on $U(n)$? I asked this question here on math.SE: https://math.stackexchange.com/q/2250448/78169
I'm asking in the physics forum in order to get a different perspective, and also as I suspect it's likely that many physicists have encountered this topic in the past for modeling purposes.
I'm interested in generating a random walk on $U(n)$ using a computer: any references on this topic or related / requisite topics would be helpful. Specific suggestions that discuss the problem technically are welcome as well. Thank you!
I'm not looking for trivial random walks. For example, randomly alternating between $U$ and $−U$ would technically be a discrete random walk. I'd like to be able to generate a random walk that can access a dense subset of the group elements; and/or I'd like an analytical description of a continuous random walk (like a diffusion process / Brownian motion), and/or a way to simulate / approximate such a continuous process.
I also asked this related question on math.SE: https://math.stackexchange.com/q/2250455/78169
$\rightarrow$ Is there a relationship or connection between compact groups like $U(n)$ and manifolds like $S^{n−1}$ (unit sphere)? If so, what is it?
I am interested in simulating a random walk on unitary groups using a computer and am wondering if it bears any similarity to a random walk on a recognizable manifold like the unit sphere in some number of dimensions. More generally, I'm wondering if the group is isomorphic or in some way similar / analogous / related to such a manifold or geometric object.
 A: The answer for this problem is given by Francesco Mezzadri for all classical compact groups. (I have mentioned that in my answer to a similar question on Mathoverflow) 
For $U(N)$ and $O(N)$, the answer is very simple based on the QR decomposition with a little extra care due to the non-uniqueness of the QR decomposition.
The algorithm for $U(N)$ is given in the article is quite simple


*

*Start from a GL(N) matrix with random independent Gaussian  identically distributed entries (i.e., disqualify cases where the determinant happens to be zero).

*Perform a QR decomposition.

*For all $j$, multiply the $j$-th row of Q by the sign of the diagonal element $R_{jj}$

*The matrices $Q$ become Haar measure distributed unitary matrices.
A: The efficient way to generate random matrix in $O(n)$, distributed according to the Haar measure, is adapted from theorem 3.3 in [1] (*). See section 9.1 in [2] for an efficient implementation working for the both of $U(n)$ and $O(n)$. This is only one step of a random walk implementation. The method would then be something along the lines of:
generate random matrix Q in U(n)
for k=1:n
    generate random matrix Q' in U(n)
    Q := QQ'

The sequence of Q's would then be your random walk. Of course, you would probably need to restrict the size of the step introduced by Q', i.e. keeping Q' in a neighbourhood of the identity matrix. I think I remember the LAPACK algorithm in [2] can be modified to do that but I need to refresh my memory. I'll update my answer if I manage.
[1] G.W. Stewart. The efficient generation of random orthogonal matrices with an application to con- dition estimators. SIAM Journal on Numerical Analysis, 17(3):403–409, 1980.
[2] LAPACK Working Note 9. A Test Matrix Generation Suite.
http://www.netlib.org/lapack/lawnspdf/lawn09.pdf
(*) This is the same idea as the one in David Bar Moshe's answer but this is a more efficient implementation, which would matter a lot for the application to random walk as the hot spot will be random matrix generation.
