Cutoff for the cyclic adjacent transposition shuffle

Abstract

We study the cyclic adjacent transposition (CAT) shuffle of $n$ cards, which is a systematic scan version of the random adjacent transposition (AT) card shuffle. In this paper, we prove that the CAT shuffle exhibits cutoff at $\frac{n^3}{2{\pi }^2}\log n$, which concludes that it is twice as fast as the AT shuffle.

26 pages, 3 figures