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

Let Q Q be a probability measure on a finite group G G, and let H H be a subgroup of G G. We show that a necessary and sufficient condition for the random walk driven by Q Q on G G to induce a Markov chain on the double coset space H ∖ G / H H G/H is that Q (g H) Q (gH) is constant as g g ranges over any double coset of H H in G G. We obtain this result as a corollary of a more general theorem on the double cosets H ∖ G / K H G / K for K K an arbitrary subgroup of G G. As an application we study a variation on the r r -top to random shuffle which we show induces an irreducible, recurrent, reversible and ergodic Markov chain on the double cosets of S y m r × S y m n − r Symᵣ Sym₍-ₑ in S y m n Symₙ. 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.