Return to Colloquia & Seminar listing
Strong stationary times for small shufflesAlgebra & Discrete Mathematics
|Speaker:||Graham White, Stanford University|
|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.