Random rotations: Characters and random walks on \(SO(N)\) (Q1323299): Difference between revisions

For a positive integer \(N\), let \(S=SO(N)\) denote the infinite, compact group consisting of all real, orthogonal, \(N\times N\) matrices with determinant 1, and let \(\lambda\) be normalized Haar measure on \(S\). The author considers a Markov chain \(\{X_ k\}^ \infty_{k=0}\), with state space \(S\), a transition of which may roughly be described as the random choice of a plane in \({\mathbb{R}}^ N\) followed by a rotation of the unit sphere of \({\mathbb{R}}^ N\) through a fixed angle \(\theta\) in that plane. Let \(Q_ k\) be the distribution of \(X_ k\), which we regard as a Borel measure on \(S\). (It turns out that \(Q_ k\) is the \(k\)-fold convolution of \(Q_ 1\) with itself.) Then the variation distance \(D_ k=\| Q_ k-\lambda\|=\sup_ A| Q_ k(A)-\lambda(A)|\) converges to zero, but may remain close to maximal (i.e. close to 1) for an unexpectedly large number of early \(k\)-values. With Fourier analysis on \(S\) as the principal tool, the paper gives the most information about the case \(\theta=\pi\). In this case, \(D_ k\) commences an exponential decrease to 0 when \(k\) passes the cutoff value \(K_ 0={1\over 4} N \text{ ln } N\). More specifically, there are positive constants \(A\), \(B\), \(C\) such that, whenever \(k=K_ 0-xN\) for some \(x>0\), then \(D_ k\geq 1-Ae^{-8x}-(B\text{ ln } N)/N\); and whenever \(k=K_ 0+xN\), then \(D_ k\leq Ce^{-x/8}\). From an examination of the author's calculations, it appears that, for \(N\) (odd) sufficiently large, we can take \(A=200\), \(B=2175\), \(C=253\). Assuming, for purposes of illustration, that \(N\approx 10^ 6\) is ``sufficiently large'', these inequalities would tell us that the exponential decrease commences after 3.5 million trials or so, that \(D_ k\) reaches .05 after about 72 million trials, but that \(D_ k\geq .95\) for the first 2.3 million trials or so. This large-distance-before-exponential-decrease property is called the Diaconis cutoff phenomenon. It occurs in a surprising number of Markov chains, the first examples coming from card shuffling processes, and the author has provided the first (nontrivial) example with an infinite state space.