Cutoff for the asymmetric riffle shuffle. (English) Zbl 1500.60042
Summary: In the Gilbert-Shannon-Reeds shuffle, a deck of \(N\) cards is cut into two approximately equal parts which are riffled together uniformly at random. D. Bayer and P. Diaconis [Ann. Appl. Probab. 2, No. 2, 294–313 (1992; Zbl 0757.60003)] famously showed that this Markov chain undergoes cutoff in total variation after \(\frac{3\log (N)}{2\log (2)}\) shuffles. We establish cutoff for the more general asymmetric riffle shuffles in which one cuts the deck into differently sized parts. The value of the cutoff point confirms a conjecture of S. P. Lalley from 2000 [Ann. Appl. Probab. 10, No. 4, 1302–1321 (2000; Zbl 1073.60535)]. Some appealing consequences are that asymmetry always slows mixing and that total variation mixing is strictly faster than separation and \(L^{\infty}\) mixing.
MSC:
| 60J10 | Markov chains (discrete-time Markov processes on discrete state spaces) |
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 · doi:10.1007/BFb0068322 |
| [2] | ASSAF, S., DIACONIS, P. and SOUNDARARAJAN, K. (2012). Riffle shuffles with biased cuts. In 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012). Discrete Math. Theor. Comput. Sci. Proc., AR 445-456. Assoc. Discrete Math. Theor. Comput. Sci., Nancy. · Zbl 1412.05195 |
| [3] | BAYER, D. and DIACONIS, P. (1992). Trailing the dovetail shuffle to its lair. Ann. Appl. Probab. 2 294-313. · Zbl 0757.60003 |
| [4] | BIDIGARE, P., HANLON, P. and ROCKMORE, D. (1999). A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements. Duke Math. J. 99 135-174. · Zbl 0955.60043 · doi:10.1215/S0012-7094-99-09906-4 |
| [5] | Boucheron, S., Lugosi, G. and Massart, P. (2013). Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford Univ. Press, Oxford. With a foreword by Michel Ledoux. · Zbl 1337.60003 · doi:10.1093/acprof:oso/9780199535255.001.0001 |
| [6] | BROWN, K. S. and DIACONIS, P. (1998). Random walks and hyperplane arrangements. Ann. Probab. 26 1813-1854. · Zbl 0938.60064 · doi:10.1214/aop/1022855884 |
| [7] | CANFIELD, E. R. (1980). Application of the Berry-Esséen inequality to combinatorial estimates. J. Combin. Theory Ser. A 28 17-25. · Zbl 0429.05007 · doi:10.1016/0097-3165(80)90056-4 |
| [8] | CSISZAR, I. and SHIELDS, P. (2004). Information theory and statistics: A tutorial. Found. Trends Commun. Inf. Theory 1 417-417. · Zbl 1156.62300 |
| [9] | DIACONIS, P. (2003). Mathematical developments from the analysis of riffle shuffling. In Groups, Combinatorics & Geometry (Durham, 2001) 73-97. World Sci. Publ., River Edge, NJ. · Zbl 1026.60005 · doi:10.1142/9789812564481_0005 |
| [10] | DIACONIS, P., FILL, J. A. and PITMAN, J. (1992). Analysis of top to random shuffles. Combin. Probab. Comput. 1 135-155. · Zbl 0798.60008 · doi:10.1017/S0963548300000158 |
| [11] | Dvoretzky, A., Kiefer, J. and Wolfowitz, J. (1956). Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. Ann. Math. Stat. 27 642-669. · Zbl 0073.14603 · doi:10.1214/aoms/1177728174 |
| [12] | FULMAN, J. (1998). The combinatorics of biased riffle shuffles. Combinatorica 18 173-184. · Zbl 0932.60007 · doi:10.1007/PL00009814 |
| [13] | JONASSON, J. and MORRIS, B. (2015). Rapid mixing of dealer shuffles and clumpy shuffles. Electron. Commun. Probab. 20 no. 20, 11. · Zbl 1328.60172 · doi:10.1214/ECP.v20-3682 |
| [14] | LALLEY, S. P. (1996). Cycle structure of riffle shuffles. Ann. Probab. 24 49-73. · Zbl 0854.05007 · doi:10.1214/aop/1042644707 |
| [15] | LALLEY, S. P. (2000). On the rate of mixing for \(p\)-shuffles. Ann. Appl. Probab. 10 1302-1321. · Zbl 1073.60535 · doi:10.1214/aoap/1019487618 |
| [16] | LUBETZKY, E. and SLY, A. (2015). An exposition to information percolation for the Ising model. Ann. Fac. Sci. Toulouse Math. (6) 24 745-761. · Zbl 1333.60207 · doi:10.5802/afst.1462 |
| [17] | LUBETZKY, E. and SLY, A. (2016). Information percolation and cutoff for the stochastic Ising model. J. Amer. Math. Soc. 29 729-774. · Zbl 1342.60173 · doi:10.1090/jams/841 |
| [18] | Lubetzky, E. and Sly, A. (2017). Universality of cutoff for the Ising model. Ann. Probab. 45 3664-3696. · Zbl 1405.60148 · doi:10.1214/16-AOP1146 |
| [19] | MASSART, P. (1990). The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality. Ann. Probab. 18 1269-1283. · Zbl 0713.62021 |
| [20] | MILLER, J. and PERES, Y. (2012). Uniformity of the uncovered set of random walk and cutoff for lamplighter chains. Ann. Probab. 40 535-577. · Zbl 1251.60058 · doi:10.1214/10-AOP624 |
| [21] | MORRIS, B. (2009). Improved mixing time bounds for the Thorp shuffle and \(L\)-reversal chain. Ann. Probab. 37 453-477. · Zbl 1170.60028 · doi:10.1214/08-AOP409 |
| [22] | MORRIS, B. (2013). Improved mixing time bounds for the Thorp shuffle. Combin. Probab. Comput. 22 118-132. · Zbl 1263.60066 · doi:10.1017/S0963548312000478 |
| [23] | PITMAN, J. (1997). Probabilistic bounds on the coefficients of polynomials with only real zeros. J. Combin. Theory Ser. A 77 279-303. · Zbl 0866.60016 · doi:10.1006/jcta.1997.2747 |
| [24] | STANLEY, R. P. (2001). Generalized riffle shuffles and quasisymmetric functions. Ann. Comb. 5 479-491. Dedicated to the memory of Gian-Carlo Rota (Tianjin, 1999). · Zbl 1010.05078 · doi:10.1007/s00026-001-8023-7 |
| [25] | THORP, E. O. (1973). Nonrandom shuffling with applications to the game of Faro. J. Amer. Statist. Assoc. 68 842-847. · Zbl 0274.90086 |
| [26] | ZHAO, Y. (2009). Biased riffle shuffles, quasisymmetric functions, and the RSK algorithm. Available at https://yufeizhao.com/research/shuffling.pdf. |
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.
