Double Coset Markov Chains

2022/08/23 by Persi Diaconis, Arun Ram, Diaconis, Persi +3
Computer Science · Mathematics · #Advanced Algebra and Geometry #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Representation Theory (math.RT) #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.2208.10699

openalex publication_date 2022/08/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let G be a finite group. Let H, K be subgroups of G and H \backslash G / K the double coset space. Let Q be a probability on G which is constant on conjugacy classes (Q(s^-1 t s) = Q(t)). 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. Some extensions and examples of double coset Markov chains with G a compact group are discussed.

Related

• A necessary and sufficient condition for double coset lumping of Markov chains on groups with an application to the random to top shuffle
• A necessary and sufficient condition for double coset lumping of Markov chains on groups with an application to the random to top shuffle
• Weak lumping of left-invariant random walks on left cosets of finite groups
• Markov chains on Weyl groups from the geometry of the flag variety
• Statistical Enumeration of Groups by Double Cosets