Hitting-time mixing for the star transposition shuffle

Abstract

We prove a hitting-time analogue of cutoff for the star transposition shuffle on the symmetric group S_n. Let tau be the first time at which every non-top card has been selected. We show that the shuffle is asymptotically mixed at time tau: more precisely, the total variation distance between the law of Y_tau and the uniform distribution on S_n is at most exp(-(log n)^(1/2+o(1))). Our proof compares the star transposition shuffle with the random transposition shuffle using simultaneous diagonalization of the two transition kernels, and then adapts the hitting-time strategy of Jain and Sawhney. This introduces a technique that can be applied to card shuffles that are not necessarily conjugacy invariant.

30 pages