Return to Colloquia & Seminar listing
Mixing time of the overlapping cycles shuffle
Student-Run Discrete Math SeminarSpeaker: | Ben Morris, UC Davis |
Location: | 1147 MSB |
Start time: | Thu, May 19 2011, 11:00AM |
The overlapping cycles shuffle mixes a deck of n cards by moving either the nth card or (n-k)th card to the top of the deck, with probability half each. Angel, Peres and Wilson determined the spectral gap for the location of a single card and found the following surprising behaviour. Suppose that k is the closest integer to cn for a fixed c in (0,1). Then for rational c, the spectral gap is on the order of n^{-2}, while for poorly approximable irrational numbers c, such as the reciprocal of the golden ratio, the spectral gap is on the order of n^{-3/2}. We show that these bounds also apply, up to logarithmic factors, to the mixing time for all the cards. The talk is based on work in progress with Olena Bormashenko and Sukhada Fadnavis.