A Shuffle that Mixes Sets of any Fixed Size much Faster than it Mixes the Whole Deck
| dc.creator | Pemantle, Robin | |
| dc.date | 2004-04-02 | |
| dc.date.accessioned | 2026-07-07T05:07:03Z | |
| dc.date.available | 2026-07-07T05:07:03Z | |
| dc.description | 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. | |
| dc.description | 20 pages | |
| dc.identifier | https://arxiv.org/abs/math/0404052 | |
| dc.identifier | http://arxiv.org/abs/math/0404052 | |
| dc.identifier | Rand. Struct. Alg., 9, 609 - 625 (1994) | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/70708 | |
| dc.subject | Probability | |
| dc.subject | 60B15, 60J15 | |
| dc.title | A Shuffle that Mixes Sets of any Fixed Size much Faster than it Mixes the Whole Deck | |
| dc.type | text |