MSRI - Mixing time of the card-cyclic to random shuffle

Site Search

For Scientists

MSRI Home > Scientific

Main

Mixing time of the card-cyclic to random shuffle

Tue, February 28, 2012 11:30AM - 12:30PM

Tags: Scientific

Time:	11:30AM - 12:30PM
Location:	MSRI, Simons Auditorium
Speaker:	Ben Morris - UC Davis
Abstract:	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.