| A Shuffle That Mixes Sets Of Any Fixed Size Much Faster Than It Mixes The Whole Deck (2007) | |||||||||||||||
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 =2 and cn 2 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 3 ln(k) 2 . This is established via coupling; no attempt is made to get a good constant. Keywords: shuffle, array, randomization time, coupling, eigenvalue Subject classification: 60B15 , 60J15 1 Research supported in part by a National Science Foundation Grant # DMS 1 Introduction Consider n 2 playing cards, numbered 1; : : : ; n 2 , in an... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||