Return to Colloquia & Seminar listing
An Upper Bound for the Mixing Time of the Random-to-Random Insertion Shuffle
Student-Run Research 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.