Double Coset Markov Chains
Autor: | Persi Diaconis, Arun Ram, Mackenzie Simper |
---|---|
Jazyk: | angličtina |
Rok vydání: | 2022 |
Předmět: |
Statistics and Probability
Computational Mathematics Algebra and Number Theory Probability (math.PR) FOS: Mathematics Discrete Mathematics and Combinatorics Geometry and Topology Representation Theory (math.RT) Mathematical Physics Analysis Mathematics - Probability Mathematics - Representation Theory Theoretical Computer Science |
Popis: | 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. working draft, comments welcome! |
Databáze: | OpenAIRE |
Externí odkaz: |