Double coset Markov chains. (5th January 2023) - Diaconis, Persi; Ram, Arun; Simper, Mackenzie
Abstract: Let G be a finite group. Let H, K be subgroups of G and H G / K the double coset space. If Q is a probability on G which is constant on conjugacy classes ( Q(s^-1 t s) = Q(t) ), then the random walk driven by Q on G projects to a Markov chain on H G /K . This allows analysis of the lumped chain using the representation theory of G . Examples include coagulation-fragmentation processes and natural Markov chains on contingency tables. Our main example projects the random transvections walk on GL_n(q) onto a Markov chain on S_n via the Bruhat decomposition. The chain on S_n has a Mallows stationary distribution and interesting mixing time behavior. The projection illuminates the combinatorics of Gaussian elimination. Along the way, we give a representation of the sum of transvections in the Hecke algebra of double cosets, which describes the Markov chain as a mixture of Metropolis chains. Some extensions and examples of double coset Markov chains with G a compact group are discussed.