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

Oliveira, Roberto Imbuzeiro

Ann. Appl. Probab., Tome 19 (2009) no. 1, p. 1200-1231 / Harvested from Project Euclid

Résumé

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 SO(n) in the L² transportation cost (Wasserstein) metric in O(n²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¹ 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∈M with d(x, y)≪1 there is a coupling (X, Y) of one step of P from x and y (resp.) that contracts distances by a (ξ+o(1)) factor on average. Then the map μ↦μP is ξ-contracting in the transportation cost metric.

Publié le : 2009-06-15
Classification: Markov chain, mixing time, path coupling, Kac’s random walk, 60J27, 65C40

@article{1245071024,
     author = {Oliveira, Roberto Imbuzeiro},
     title = {On the convergence to equilibrium of Kac's random walk on matrices},
     journal = {Ann. Appl. Probab.},
     volume = {19},
     number = {1},
     year = {2009},
     pages = { 1200-1231},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1245071024}
}

Oliveira, Roberto Imbuzeiro. On the convergence to equilibrium of Kac’s random walk on matrices. Ann. Appl. Probab., Tome 19 (2009) no. 1, pp.  1200-1231. http://gdmltest.u-ga.fr/item/1245071024/