A Shuffle that Mixes Sets of any Fixed Size much Faster than it Mixes the Whole Deck

2004/04/02 by Robin Pemantle
Mathematics · #math.PR #msc:60B15 #msc:60J15

paper · pdf

published as Rand. Struct. Alg., 9, 609 - 625 (1994) · 20 pages

arxiv created 2004/04/02 · arxiv updated 2009/12/01

Abstract

Consider an n by n array of cards shuffled in the following manner. An element x of the array is chosen uniformly at random; Then with probability 1/2 the rectangle of cards above and to the left of x is rotated 180 degrees, and with probability 1/2 the rectangle of cards below and to the right of x is rotated 180 degrees. It is shown by an eigenvalue method that the time required to approach the uniform distribution is between n²/2 and cn² ln n for some constant c. On the other hand, for any k it is shown that the time needed to uniformly distribute a set of cards of size k is at most c(k)n, where c(k) is a constant times k³ ln(k)². This is established via coupling; no attempt is made to get a good constant.

Related

• Mixing time of the torus shuffle
• Mixing time of the Card-Cyclic-to-Random shuffle
• A Lower Bound for the Mixing Time of the Random-to-Random Insertions Shuffle
• Mixing times via super-fast coupling
• Cutoff for random to random card shuffle