We analyze the most commonly used method for shuffling cards. The main result is a simple expression for the chance of any arrangement after any number of shuffles. This is used to give sharp bounds on the approach to randomness: $\frac{3}{2} \log_2 n + \theta$ shuffles are necessary and sufficient to mix up $n$ cards. Key ingredients are the analysis of a card trick and the determination of the idempotents of a natural commutative subalgebra in the symmetric group algebra.
Publié le : 1992-05-14
Classification:
Card shuffling,
symmetric group algebra,
total variation distance,
20B30,
60B15,
60C05,
60F99
@article{1177005705,
author = {Bayer, Dave and Diaconis, Persi},
title = {Trailing the Dovetail Shuffle to its Lair},
journal = {Ann. Appl. Probab.},
volume = {2},
number = {4},
year = {1992},
pages = { 294-313},
language = {en},
url = {http://dml.mathdoc.fr/item/1177005705}
}
Bayer, Dave; Diaconis, Persi. Trailing the Dovetail Shuffle to its Lair. Ann. Appl. Probab., Tome 2 (1992) no. 4, pp. 294-313. http://gdmltest.u-ga.fr/item/1177005705/