On the convergence to equilibrium of Kac's random walk on matrices
Roberto Imbuzeiro Oliveira
Markov chains | Wasserstein distance | SO(n) | Haar measure
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 uniform (Haar) measure in the (Wasserstein) transportation cost metric in O(n^2 ln n) steps. This improves on previous results of Diaconis/Saloff Coste and Pak/Sidenko and is a ln n factor away from being optimal. Our proof method includes a general result 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)<< 1 there is a coupling (X,Y) of one step from P from x and y (respectively) that is (c+o(1))-contracting on average. Then the map from a initial distribution m to the distribution mP after one step is c-contracting in the transportation cost metric. Other applications of this result are also presented.