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

DOI10.1214/08-AAP550zbMATH Open1173.60343arXiv0705.2253OpenAlexW3103301792MaRDI QIDQ2389608FDOQ2389608

Authors: Roberto I. Oliveira 

Publication date: 17 July 2009

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

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.

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

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

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)

Cites Work

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

Cited In (18)

• Bounds on Semigroups of Random Rotations on SO(n)
• A Gibbs sampler on the \(n\)-simplex
• Randomized numerical linear algebra: Foundations and algorithms
• Uniform contractivity in Wasserstein metric for the original 1D Kac's model
• Ricci curvature of Markov chains on 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
• Total variation bound for Kac's random walk
• Curvature, concentration and error estimates for Markov chain Monte Carlo
• Repeated averages on graphs
• On the mixing time of Kac's walk and other high-dimensional Gibbs samplers with constraints
• Kac's random walk on the special orthogonal group mixes in polynomial time
• Brownian processes for Monte Carlo integration on compact Lie groups
• Ricci curvature of metric spaces
• Local random quantum circuits are approximate polynomial-designs
• Fast and memory-optimal dimension reduction using Kac's walk
• Kac's walk on \(n\)-sphere mixes in \(n\log n\) steps

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)