Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Strong stationary times for small shuffles

Algebra & Discrete Mathematics

Speaker: Graham White, Stanford University
Location: MSB 2112
Start time: Mon, May 1 2017, 4:10PM

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.