# The card-cyclic to random shuffle

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.

Advertisement

This site uses Akismet to reduce spam. Learn how your comment data is processed.