I heard about this cool-sounding seminar at the Berkeley Statistics department:

Mixing time of the card-cyclic to random shuffle
Ben Morris

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.

The talk is based on a paper with Weiyang Ning (a student at UW) and Yuval Peres. The description the results is somewhat different because it’s \log n rounds of n moves, or n \log n moves. From the intro to the paper:

To prove the lower bound we introduce the concept of a barrier between two parts of the deck that moves along with the cards as the shuffling is performed. Then we show that the trajectory of this barrier can be well-approximated by a deterministic function f… we relate the mixing rate of the chain to the rate at which f converges to a constant.

The key is to use path coupling, a technique pioneered by Bubley and Dyer. It’s a cute result and would be a fun paper to read for a class project or something, I bet.

About these ads