Double coset Markov chains
Forum of Mathematics, Sigma, Tome 11 (2023)
Voir la notice de l'article provenant de la source Cambridge University Press
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.
@article{10_1017_fms_2022_106,
author = {Persi Diaconis and Arun Ram and Mackenzie Simper},
title = {Double coset {Markov} chains},
journal = {Forum of Mathematics, Sigma},
publisher = {mathdoc},
volume = {11},
year = {2023},
doi = {10.1017/fms.2022.106},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2022.106/}
}
Persi Diaconis; Arun Ram; Mackenzie Simper. Double coset Markov chains. Forum of Mathematics, Sigma, Tome 11 (2023). doi: 10.1017/fms.2022.106
Cité par Sources :