On the convergence to equilibrium of Kac's random walk on matrices

DOI10.1214/08-AAP550MaRDI QIDQ2389608zbMATH OpenOpenAlexFDO

Authors Roberto I. Oliveira

Publication date 17 July 2009

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0705.2253

zbMATH Keywords

Markov chainmixing timepath couplingKac's random walk

Mathematics Subject Classification ID

Numerical analysis or methods applied to Markov chains (65C40) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Continuous-time Markov processes on discrete state spaces (60J27)

Abstract: We consider Kac's random walk on $n$-dimensional rotation matrices, where each step is a random rotation in the plane generated by two randomly picked coordinates. We show that this process converges to the Haar measure on $mathitSO(n)$ in the $L^2$ transportation cost (Wasserstein) metric in $O(n^{2}lnn)$ steps. We also prove that our bound is at most a $O(lnn)$ factor away from optimal. Previous bounds, due to Diaconis/Saloff-Coste and Pak/Sidenko, had extra powers of $n$ and held only for $L^1$ transportation cost. Our proof method includes a general result of independent interest, akin to the path coupling method of Bubley and Dyer. Suppose that $P$ is a Markov chain on a Polish length space $(M,d)$ and that for all $x,yinM$ with $d(x,y)ll1$ there is a coupling $(X,Y)$ of one step of $P$ from $x$ and $y$ (resp.) that contracts distances by a $(xi+o(1))$ factor on average. Then the map $mumapstomuP$ is $xi$-contracting in the transportation cost metric.

Recommendations

• Total variation bound for Kac's random walk
• Kac's random walk on the special orthogonal group mixes in polynomial time
• Bounds for Kac's master equation
• Cut-off phenomenon in the uniform plane Kac walk
• Kac's walk on \(n\)-sphere mixes in \(n\log n\) steps

Cites work

• scientific article; zbMATH DE number 3121490 (Why is no real title available?)
• scientific article; zbMATH DE number 6472599 (Why is no real title available?)
• Bounds for Kac's master equation
• Cercignani's conjecture is sometimes true and always almost true
• Determination of the spectral gap for Kac's master equation and related stochastic evolution.
• Deterministic and randomized polynomial‐time approximation of radii
• Monte Carlo sampling methods using Markov chains and their applications
• On the geometry of metric measure spaces. I
• On the geometry of metric measure spaces. II
• Optimal Transport
• Ricci curvature for metric-measure spaces via optimal transport
• Ricci curvature of Markov chains on metric spaces
• Spectral gap for Kac's model of Boltzmann equation.
• The eigenvalues of Kac's master equation
• The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
• Transport inequalities, gradient estimates, entropy and Ricci curvature

Cited in

(18)

• Bounds on Semigroups of Random Rotations on SO(n)
• On the mixing time of Kac's walk and other high-dimensional Gibbs samplers with constraints
• Brownian processes for Monte Carlo integration on compact Lie groups
• Uniform contractivity in Wasserstein metric for the original 1D Kac's model
• Repeated averages on graphs
• Ricci curvature of metric spaces
• Grain rotations and distortions in the asymptotic variance of vacancy of the Boolean model
• Impact of regularization on spectral clustering
• New tests of uniformity on the compact classical groups as diagnostics for weak-\(^{*}\) mixing of Markov chains
• Randomized numerical linear algebra: Foundations and algorithms
• Curvature, concentration and error estimates for Markov chain Monte Carlo
• Kac's random walk on the special orthogonal group mixes in polynomial time
• Ricci curvature of Markov chains on metric spaces
• Kac's walk on \(n\)-sphere mixes in \(n\log n\) steps
• Total variation bound for Kac's random walk
• Local random quantum circuits are approximate polynomial-designs
• A Gibbs sampler on the \(n\)-simplex
• Fast and memory-optimal dimension reduction using Kac's walk

This page was built for publication: On the convergence to equilibrium of Kac's random walk on matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2389608)