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

By Roberto Imbuzeiro Oliveira. 2007

48 citations recorded by the source corpus.

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 $\mathit{SO}(n)$ in the $L^2$ transportation cost (Wasserstein) metric in $O(n^2\ln n)$ steps. We also prove that our bound is at most a $O(\ln n)$ 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,y\in M$ 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 $\mu\mapsto\mu P$ is $\xi$-contracting in the transportation cost metric.

Subfields: Applied Mathematics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/d4ba7254c596450a7cc98e826acb3cc4de2a2d50

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Statistics and Probability

Citations in the corpus

Ricci curvature of Markov chains on metric spaces (2007, unknown): “Example 16 (Kac’s random walk on orthogonal matrices, after [ Oli ]).”
Local random quantum circuits are approximate polynomial-designs: numerical results (2012, methodology): “(81) We now state Oliveira’s result (in fact a particular case of Theorem 3 of [68]), which offers a version of the path coupling method for Markov chains on the unitary group.”
Unifying Orthogonal Monte Carlo Methods (2019, background): “More recently, ﬁnite-time analysis of Kac’s random walk has established its mixing time as O ( d 2 log d ) (Oliveira, 2009).”
Statistical Aspects of Wasserstein Distances (2018, background): “In studying convergence of the Kac random walk on the orthogonal group SO( n ), Oliveira (2009) showed that for some ξ 1, where D is a distance between matrices, leading to exponential convergence to equilibrium.”
Curvature and transport inequalities for Markov chains in discrete spaces (2015, background): “Previous works considering contraction rates in transport distance include [12,36,40].”
Randomized numerical linear algebra: Foundations and algorithms (2020, methodology): “R. I. Oliveira (2009b), ‘On the convergence to equilibrium of Kac’s random walk on matrices’, Ann.”
CURVATURE, CONCENTRATION AND ERROR ESTIMATES FOR MARKOV CHAIN MONTE CARLO (2009, unknown): “This property or similar ones can be traced back to Dobrushin [Dob70, DS85], and have been used a few times in the Markov chain literature [CW94, Dob96, BD97, DGW04, Jou07, Oll07, Oll09, Jou, Oli ].”