Strong stationary times for small shuffles

Strong stationary times for small shuffles

-
Graham White , Stanford University
Jadwin Hall 111

Consider shuffling a deck of cards by at each step, choosing two random cards and either swapping them or not. This random walk is well understood. A natural generalisation is to choose three (or more) cards at each step, and shuffle them amongst themselves. I will show how one may construct a strong stationary time for such a random walk, giving an asymptotic upper bound on the mixing time. The resulting bounds will be similar to conjectures of Roichman.