Riffle shuffles of decks with repeated cards. (English) Zbl 1099.60007

Conger, Mark; Viswanath, D.

Ann. Probab. 34, No. 2, 804-819 (2006).

This paper considers the problem of shuffling cards: How many shuffles mix a deck of cards? It deals with riffle shuffling, which is the most common way of shuffling cards. In many instances, not all cards in the deck are distinct and only the sets of cards dealt out of players, and not the order in which they are dealt out to each player, need to be random. The authors derive transition probabilities under riffle shuffles between decks with repeated cards to cover some instances of the type just described. They focus on decks with cards all of which are labeled either 1 or 2 and describe the consequences of having a symmetric starting deck of the form \(1,\dots,1,2,\dots,2\) or \(1,2,\dots,1,2\). Finally, mixing times for common card games are considered.

Reviewer: Nicko G. Gamkrelidze (Moskva)

MSC:

60C05	Combinatorial probability
60J20	Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)

Keywords:

mixing times

References:

[1]	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
[2]	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
[3]	Diaconis, P. (1988). Group Representations in Probability and Statistics . IMS, Hayward, CA. · Zbl 0695.60012
[4]	Diaconis, P., McGrath, M. and Pitman, J. (1995). Riffle shuffles, cycles and descents. Combinatorica 15 11–29. · Zbl 0828.05003 · doi:10.1007/BF01294457
[5]	Epstein, E. (1977). The Theory of Gambling and Statistical Logic , rev. ed. Academic Press, New York.
[6]	Foata, D. and Schützenberger, M.-P. (1970). Théorie Géométrique des Polynômes Eulériens . Springer, Berlin. · Zbl 0214.26202 · doi:10.1007/BFb0060799
[7]	Fulman, J. (1998). The combinatorics of biased riffle shuffles. Combinatorica 18 173–184. · Zbl 0932.60007 · doi:10.1007/PL00009814
[8]	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
[9]	Graham, R. L., Knuth, D. E. and Patashnik, O. (1994). Concrete Mathematics , 2nd ed. Addison–Wesley, Reading, MA. · Zbl 0836.00001
[10]	Knuth, D. E. (1998). The Art of Computer Programming 3 , 3rd ed. Addison–Wesley, Reading, MA. · Zbl 0895.68054
[11]	Lalley, S. P. (1996). Cycle structure of riffle shuffles. Ann. Probab. 24 49–73. · Zbl 0854.05007 · doi:10.1214/aop/1042644707
[12]	MacMahon, P. A. (1915). Combinatory Analysis 1 . Cambridge Univ. Press. · JFM 45.1271.01
[13]	Reyes, J.-C. U. (2002). Random walks, semidirect products, and card shuffling. Ph.D. dissertation, Stanford Univ.
[14]	Trefethen, L. N. and Trefethen, L. M. (2000). How many shuffles to randomize a deck of cards? Proc. Roy. Soc. Lond. Ser. A 456 2561–2568. JSTOR: · Zbl 0968.60080 · doi:10.1098/rspa.2000.0625