Mixing times of one-sided $k$-transposition shuffles

Abstract

We study mixing times of the one-sided $k$-transposition shuffle. We prove that this shuffle mixes relatively slowly, even for $k$ big. Using the recent "lifting eigenvectors" technique of Dieker and Saliola and applying the $\ell^2$ bound, we prove different mixing behaviors and explore the occurrence of cutoff depending on $k$.

Locations

• arXiv (Cornell University) - View - PDF