A shuffle that mixes sets of any fixed size much faster than it mixes the whole deck
Robin Pemantle · Random Structures and Algorithms · 1994
Abstract Consider an n by n array of cards shufled 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 180deg;, and with probability 1/2 the rectangle of cards below and to the right of x is rotated 180°. It is shown by an eigenvalue method that the time required to approach‐ the uniform distribution is between n2/2 and cn2 in 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 k3 In(k)2. This is established via coupling; no attempt is made to get a good constant. © 1994 John Wiley & Sons, Inc.