Double coset Markov chains. (5th January 2023)

• Record Type: Journal Article
• Authors: Diaconis, Persi; Ram, Arun; Simper, Mackenzie
• Is Part Of: Forum of mathematics. Volume 11(2023)
• Publication Date: 2023-01-05
• Subjects: 60J10 -- 20C08 -- 05E05; Mathematics -- Periodicals; 510
• DOI: 10.1017/fms.2022.106
• Languages: English
• ISSNs: 2050-5094

Abstract

Abstract: Let G be a finite group. Let $H, K$ be subgroups of G and $H \backslash 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 \backslash 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.