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 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. [ABSTRACT FROM AUTHOR]