Premium
A shuffle that mixes sets of any fixed size much faster than it mixes the whole deck
Author(s) -
Pemantle Robin
Publication year - 1994
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240050502
Subject(s) - rectangle , deck , constant (computer programming) , combinatorics , mathematics , set (abstract data type) , probability distribution , element (criminal law) , discrete mathematics , distribution (mathematics) , mathematical analysis , geometry , statistics , computer science , engineering , structural engineering , political science , programming language , law
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 n 2 /2 and cn 2 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 k 3 In( k ) 2 . This is established via coupling; no attempt is made to get a good constant. © 1994 John Wiley & Sons, Inc.