Mathematics Colloquia and Seminars
Return to Colloquia & Seminar listing
An Upper Bound for the Mixing Time of the Random-to-Random Insertion ShuffleStudent-Run Applied & Math Seminar
|Speaker: ||Chuan Qin, UC Davis|
|Location: ||2112 MSB|
|Start time: ||Wed, Nov 13 2013, 12:10PM|
In each step of the random-to-random insertion shuffle, a card is chosen at random, removed from the deck and reinserted in a random position. Persi Diaconis conjectured that the mixing time for this shuffle on a deck of n cards is 3/4*n*log(n) for large n. We show that the mixing time is bounded above by C*n*log(n), where C = 1.532066..., while the best previously known upper bound is 2*n*log(n). The proof relies on the construction of a non-Markovian coupling. This is joint work with Ben Morris.