A Study of Shuffling Cards and Stopping Times for Randomness

10.29973/JCSA.200707.0002

Chin-San Lee；Jin-Long Huang；Chia-Hui Lin

shuffle times ； randomness ； goodness of fit test ； simulation

中國統計學報

45卷3期（2007 / 07 / 01）

236 - 253

英文

In this paper we analyze how many shuffles are necessary to get close to randomness for a deck of n cards. Aldous (1983), Bayer and Diaconis (1992) assert that approximately 1.5 log2n shuffles are necessary when n is large. Bayer and Diaconis (1992) use the variation distance as a measure of randomness to analyze the most commonly used method of shuffling cards, and claim that seven shuffles are enough when n=52. We provide another idea to measure the distance from randomness for repeated shuffles. The proposed method consists of a goodness of fit test and a simple simulation. Simulation results show that we have a similar conclusion to that of Bayer and Diaconis.

1. Aldous, D.(1983).Seminaire de Probabilites XVII. Lecture Notes in Math.New York:Springer.
2. Bayer, D.,Diaconis, P.(1992).Trailing the dovetail shuffle to its lair.Annals of Applied Probability,2,294-313.
3. Gilbert, E.(1955).Technical memorandum.Bell Laboratories.
4. Golomb, S. W.(1961).Permutations by cutting and shuffling.Society for Industrial and Applied Mathematics Review,3,293-297.
5. Mann, B.,Snell, J. L.(Ed.)(1995).Topics in contemporary probability and its applications, Probability and Stochastics Series.Boca Raton, FL.:CRC Press.
6. Pearson, K.(1900).On the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random samplig.Philosophical Magazine,50,157-175.
7. Tanny, S.(1973).A probability interpretation of the Eulerian numbers.Duke Mathematical Journal,40,717-722.