Random rotations: Characters and random walks on SO(N)
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.
- Hypergroup deformations and Markov chains
- Precise estimates on the rate at which certain diffusions tend to equilibrium
- \(L_ 2\)-lower bounds for a special class of random walks
- Rates of convergence to Gaussian measures on \(n\)-spheres and Jacobi hypergroups
- Optimal spherical deconvolution
- On the mixing time of Kac's walk and other high-dimensional Gibbs samplers with constraints
- New tests of uniformity on the compact classical groups as diagnostics for weak-\(^{*}\) mixing of Markov chains
- Bounds on lifting continuous-state Markov chains to speed up mixing
- Deconvolution density estimation on \(\text{SO}(N)\)
- Lévy processes and Fourier analysis on compact Lie groups.
- A spectral radius formula for the Fourier transform on compact groups and applications to random walks
- The cut-off phenomenon for random reflections. II: Complex and quaternionic cases
- The cut-off phenomenon for random reflections
- The cut-off phenomenon for Brownian motions on compact symmetric spaces
- Cut-off phenomenon for random walks on free orthogonal quantum groups
- Diaconis-Shahshahani upper bound lemma for finite quantum groups
- A Gibbs sampler on the \(n\)-simplex
- On random rotations
- Application of second generation wavelets to blind spherical deconvolution
- Random walks and approximate integration on compact homogeneous spaces
- Convergence of random walks on the circle generated by an irrational rotation
- Asymptotics of Heat Kernels on Projective Spaces of Large Dimensions and on Disk Hypergroups
- Bounds on Semigroups of Random Rotations on SO(n)
- Semi-classical limit for random walks
- Quantum reflections, random walks and cut-off
- Patterns in eigenvalues: the 70th Josiah Willard Gibbs lecture
- The ergodic theorem for random walks on finite quantum groups
- Ergodic properties of folding maps on spheres
- Localized spherical deconvolution
- Randomized numerical linear algebra: Foundations and algorithms
- Comparing limit profiles of reversible Markov chains
- Repeated differentiation and free unitary Poisson process
- Large scale behavior of semiflexible heteropolymers
- Orbit measures, random matrix theory and interlaced determinantal processes
- Interlaced processes on the circle
This page was built for publication: Random rotations: Characters and random walks on \(SO(N)\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1323299)
