×

A rule of thumb for riffle shuffling. (English) Zbl 1226.60005

The paper is concerned with the mixing properties of the Gilbert-Shannon-Reeds model for riffle shuffling of \(n\) cards. The authors study how many riffle shuffles are required to mix \(n\) cards if only certain features of the deck are of interest, for example, suits can be disregarded or only the colors are of interest. For these features, the number of shuffles drops from \(\frac23\log_2n\) to \(\log_2n\). A main result is a unified “rule of thumb” formula.

MSC:

60B15 Probability measures on groups or semigroups, Fourier transforms, factorization
60C05 Combinatorial probability
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aldous, D. (1983). Random walks on finite groups and rapidly mixing Markov chains. In Seminar on Probability , XVII. Lecture Notes in Math. 986 243-297. Springer, Berlin. · Zbl 0514.60067
[2] Aldous, D. and Diaconis, P. (1986). Shuffling cards and stopping times. Amer. Math. Monthly 93 333-348. JSTOR: · Zbl 0603.60006 · doi:10.2307/2323590
[3] Aldous, D. and Diaconis, P. (1987). Strong uniform times and finite random walks. Adv. in Appl. Math. 8 69-97. · Zbl 0631.60065 · doi:10.1016/0196-8858(87)90006-6
[4] Athanasiadis, C. and Diaconis, P. (2010). Functions of hyperplane walks. Adv. in Appl. Math. 45 410-437. · Zbl 1239.60071 · doi:10.1016/j.aam.2010.02.001
[5] Bayer, D. and Diaconis, P. (1992). Trailing the dovetail shuffle to its lair. Ann. Appl. Probab. 2 294-313. · Zbl 0757.60003 · doi:10.1214/aoap/1177005705
[6] Boyd, S., Diaconis, P., Parrilo, P. and Xiao, L. (2005). Symmetry analysis of reversible Markov chains. Internet Math. 2 31-71. · Zbl 1087.60057 · doi:10.1080/15427951.2005.10129100
[7] Ceccherini-Silberstein, T., Scarabotti, F. and Tolli, F. (2008). Harmonic Analysis on Finite Groups : Representation Theory , Gelfand Pairs and Markov Chains. Cambridge Studies in Advanced Mathematics 108 . Cambridge Univ. Press, Cambridge. · Zbl 1149.43001
[8] Chen, G.-Y. and Saloff-Coste, L. (2008). The cutoff phenomenon for randomized riffle shuffles. Random Structures Algorithms 32 346-374. · Zbl 1146.60010 · doi:10.1002/rsa.20195
[9] Chen, G.-Y. and Saloff-Coste, L. (2010). The L 2 cutoff for reversible Markov processes. J. Funct. Anal. 258 2246-2315. · Zbl 1192.60088 · doi:10.1016/j.jfa.2009.10.017
[10] Ciucu, M. (1998). No-feedback card guessing for dovetail shuffles. Ann. Appl. Probab. 8 1251-1269. · Zbl 0945.60002 · doi:10.1214/aoap/1028903379
[11] Conger, M. and Viswanath, D. (2006). Riffle shuffles of decks with repeated cards. Ann. Probab. 34 804-819. · Zbl 1099.60007 · doi:10.1214/009117905000000675
[12] Conger, M. and Viswanath, D. (2006). Shuffling cards for blackjack, bridge, and other card games. · Zbl 1099.60007 · doi:10.1214/009117905000000675
[13] Conger, M. and Viswanath, D. (2007). Normal approximations for descents and inversions of permutations of multisets. J. Theoret. Probab. 20 309-325. · Zbl 1124.60022 · doi:10.1007/s10959-007-0070-5
[14] Conger, M. A. (2007). Shuffling decks with repeated card values. Ph.D. thesis, Univ. Michigan.
[15] Diaconis, P. (1988). Group Representations in Probability and Statistics. Institute of Mathematical Statistics Lecture Notes-Monograph Series 11 . IMS, Hayward, CA. · Zbl 0695.60012
[16] Diaconis, P. (2003). Mathematical developments from the analysis of riffle shuffling. In Groups , Combinatorics and Geometry ( Durham , 2001) 73-97. World Scientific, River Edge, NJ. · Zbl 1026.60005
[17] Diaconis, P. and Fulman, J. (2009). Carries, shuffling, and an amazing matrix. Amer. Math. Monthly 116 788-803. · Zbl 1229.60011 · doi:10.4169/000298909X474864
[18] Diaconis, P. and Holmes, S. P. (2002). Random walks on trees and matchings. Electron. J. Probab. 7 17 pp. (electronic). · Zbl 1007.60071
[19] Diaconis, P., McGrath, M. and Pitman, J. (1995). Riffle shuffles, cycles, and descents. Combinatorica 15 11-29. · Zbl 0828.05003 · doi:10.1007/BF01294457
[20] Diaconis, P. and Shahshahani, M. (1981). Generating a random permutation with random transpositions. Z. Wahrsch. Verw. Gebiete 57 159-179. · Zbl 0485.60006 · doi:10.1007/BF00535487
[21] Ding, J., Lubetzky, E. and Peres, Y. (2010). Total variation cutoff in birth and death chains. Probab. Theory Related Fields 146 61-85. · Zbl 1190.60005 · doi:10.1007/s00440-008-0185-3
[22] Fässler, A. and Stiefel, E. (1992). Group Theoretical Methods and Their Applications . Birkhäuser, Boston, MA. Translated from the German by Baoswan Dzung Wong. · Zbl 0769.20002
[23] Fulman, J. (2002). Applications of symmetric functions to cycle and increasing subsequence structure after shuffles. J. Algebraic Combin. 16 165-194. · Zbl 1012.05154 · doi:10.1023/A:1021177012548
[24] Fulman, J. (2004). A card shuffling analysis of deformations of the Plancherel measure of the symmetric group. Electron. J. Combin. 11 Research Paper 21, 15. · Zbl 1056.05003
[25] Gardner, M. (1966). Martin Gardner’s New Mathematical Diversions from Scientific American . Simon and Schuster, New York.
[26] Gibbs, A. and Su, F. (2002). On choosing and bounding probability metrics. Int. Statis. Inst. Rev. 70 419-435. · Zbl 1217.62014 · doi:10.2307/1403865
[27] Gilbert, E. (1955). Theory of shuffling. Technical memorandum, Bell Laboratories, Murray Hill, NJ. · Zbl 0066.11004
[28] Holte, J. M. (1997). Carries, combinatorics, and an amazing matrix. Amer. Math. Monthly 104 138-149. JSTOR: · Zbl 0889.15021 · doi:10.2307/2974981
[29] Lalley, S. (1999). Riffle shuffles and their associated dynamical systems. J. Theoret. Probab. 12 903-932. · Zbl 0965.60022 · doi:10.1023/A:1021636902356
[30] Reeds, J. (1976). Theory of shuffling. Unpublished manuscript, Univ. California, Berkeley.
[31] Reyes, J.-C. U. (2002). Random walk, semi-direct products, and card shuffling. Ph.D. thesis, Stanford Univ.
[32] Serre, J.-P. (1977). Linear Representations of Finite Groups. Graduate Texts in Mathematics 42 . Springer, New York. Translated from the second French edition by Leonard L. Scott. · Zbl 0355.20006
[33] Weaver, J. R. (1985). Centrosymmetric (cross-symmetric) matrices, their basic properties, eigenvalues, and eigenvectors. Amer. Math. Monthly 92 711-717. JSTOR: · Zbl 0619.15021 · doi:10.2307/2323222
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.