Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

An Upper Bound for the Mixing Time of the Random-to-Random Insertion Shuffle

Student-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.