Mathematical Sciences Research Institute

Home » Mixing time of the card-cyclic to random shuffle


Mixing time of the card-cyclic to random shuffle February 28, 2012 (11:30 AM PST - 12:30 PM PST)
Parent Program: --
Location: MSRI: Simons Auditorium
Speaker(s) Ben Morris - UC Davis
Description No Description
No Video Uploaded

We analyze the following method for shuffling $n$ cards.
First, remove card 1 (i.e., the card with label 1) and then re-insert it randomly into the deck. Then repeat with cards 2, 3,..., $n$. Call this a round. R. Pinsky showed, somewhat surprisingly, that the mixing time is greater than one round. We show that in fact the mixing time is on the order of $\log n$ rounds.

Joint work with Weiyang Ning and Yuval Peres.

No Notes/Supplements Uploaded No Video Files Uploaded