A necessary and sufficient condition for double coset lumping of Markov chains on groups with an application to the random to top shuffle
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909120752254976 |
|---|---|
| author | Britnell, John R. Wildon, Mark |
| author_facet | Britnell, John R. Wildon, Mark |
| contents | Let $Q$ be a probability measure on a finite group $G$, and let $H$ be a subgroup of $G$. We show that a necessary and sufficient condition for the random walk driven by $Q$ on $G$ to induce a Markov chain on the double coset space $H\backslash G/H$, is that $Q(gH)$ is constant as $g$ ranges over any double coset of $H$ in $G$. We obtain this result as a corollary of a more general theorem on the double cosets $H \backslash G / K$ for $K$ an arbitrary subgroup of $G$. As an application we study a variation on the $r$-top to random shuffle which we show induces an irreducible, recurrent, reversible and ergodic Markov chain on the relevant double cosets. The transition matrix of the induced walk has remarkable spectral properties: we find its invariant distribution and its eigenvalues and hence determine its rate of convergence. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_02723 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A necessary and sufficient condition for double coset lumping of Markov chains on groups with an application to the random to top shuffle Britnell, John R. Wildon, Mark Group Theory Combinatorics Probability 20A05 (Primary), 15A18, 15B51, 60G10, 60J10 (Secondary) Let $Q$ be a probability measure on a finite group $G$, and let $H$ be a subgroup of $G$. We show that a necessary and sufficient condition for the random walk driven by $Q$ on $G$ to induce a Markov chain on the double coset space $H\backslash G/H$, is that $Q(gH)$ is constant as $g$ ranges over any double coset of $H$ in $G$. We obtain this result as a corollary of a more general theorem on the double cosets $H \backslash G / K$ for $K$ an arbitrary subgroup of $G$. As an application we study a variation on the $r$-top to random shuffle which we show induces an irreducible, recurrent, reversible and ergodic Markov chain on the relevant double cosets. The transition matrix of the induced walk has remarkable spectral properties: we find its invariant distribution and its eigenvalues and hence determine its rate of convergence. |
| title | A necessary and sufficient condition for double coset lumping of Markov chains on groups with an application to the random to top shuffle |
| topic | Group Theory Combinatorics Probability 20A05 (Primary), 15A18, 15B51, 60G10, 60J10 (Secondary) |
| url | https://arxiv.org/abs/2311.02723 |