A necessary and sufficient condition for double coset lumping of Markov chains on groups with an application to the random to top shuffle

Abstract:

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 double cosets of $\mathrm {Sym}_r \times \mathrm {Sym}_{n-r}$ in $\mathrm {Sym}_n$. 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.