We introduce a generating-function framework for analyzing the no-feedback card-guessing game after $ k $ Gilbert–Shannon–Reeds riffle shuffles. We show that the distribution of the card appearing in position $ i $ can be expressed as a structured mixture of $ 2^k $ tractable components, each corresponding to a sum of independent Bernoulli trials. From this decomposition, we derive an explicit closed-form expression for the probability generating function, represented as a product of binomial-type polynomials with a clear and systematic structure, valid for any number of cards $ n $ and any number of shuffles $ k $. This formulation replaces recursive convolutions with a single analytic expression, enabling efficient computation and revealing the combinatorial–probabilistic structure underlying riffle shuffles. Beyond exact evaluation, the framework connects optimal no-feedback strategies with the generating functions and suggests asymptotic behavior in both the fixed-$ k $, large-$ n $ and fixed-$ n $, large-$ k $ regimes.
Citation: Tipaluck Krityakierne, Thotsaporn Aek Thanatipanonda. A generating function framework for the no-feedback card guessing game after riffle shuffles[J]. AIMS Mathematics, 2025, 10(10): 24257-24269. doi: 10.3934/math.20251075
We introduce a generating-function framework for analyzing the no-feedback card-guessing game after $ k $ Gilbert–Shannon–Reeds riffle shuffles. We show that the distribution of the card appearing in position $ i $ can be expressed as a structured mixture of $ 2^k $ tractable components, each corresponding to a sum of independent Bernoulli trials. From this decomposition, we derive an explicit closed-form expression for the probability generating function, represented as a product of binomial-type polynomials with a clear and systematic structure, valid for any number of cards $ n $ and any number of shuffles $ k $. This formulation replaces recursive convolutions with a single analytic expression, enabling efficient computation and revealing the combinatorial–probabilistic structure underlying riffle shuffles. Beyond exact evaluation, the framework connects optimal no-feedback strategies with the generating functions and suggests asymptotic behavior in both the fixed-$ k $, large-$ n $ and fixed-$ n $, large-$ k $ regimes.
| [1] |
P. Diaconis, R. Graham, X. He, S. Spiro, Card guessing with partial feedback, Comb. Probab. Comput., 31 (2022), 1–20. https://doi.org/10.1017/S0963548321000134 doi: 10.1017/S0963548321000134
|
| [2] |
P. Diaconis, R. Graham, S. Spiro, Guessing about guessing: Practical strategies for card guessing with feedback, Am. Math. Mon., 129 (2022), 607–622. https://doi.org/10.1080/00029890.2022.2069986 doi: 10.1080/00029890.2022.2069986
|
| [3] |
D. Bayer, P. Diaconis, Trailing the dovetail shuffle to its lair, Ann. Appl. Probab., 2 (1992), 294–313. https://doi.org/10.1214/aoap/1177005705 doi: 10.1214/aoap/1177005705
|
| [4] |
T. Krityakierne, T. A. Thanatipanonda, The card guessing game: A generating function approach, J. Symb. Comput., 115 (2023), 1–17. https://doi.org/10.1016/j.jsc.2022.07.001 doi: 10.1016/j.jsc.2022.07.001
|
| [5] |
M. Ciucu, No-feedback card guessing for dovetail shuffles, Ann. Appl. Probab., 8 (1998), 1251–1269. https://doi.org/10.1214/aoap/1028903379 doi: 10.1214/aoap/1028903379
|
| [6] |
T. Krityakierne, P. Siriputcharoen, T. A. Thanatipanonda, C. Yapolha, Moments of the one-shuffle no-feedback card guessing game, Discrete Math. Lett., 12 (2023), 110–117. https://doi.org/10.47443/dml.2023.119 doi: 10.47443/dml.2023.119
|
| [7] |
M. Kuba, A. Panholzer, On card guessing games: Limit law for no-feedback one-time riffle shuffle, Adv. Appl. Math., 156 (2024), 102689. https://doi.org/10.1016/j.aam.2024.102689 doi: 10.1016/j.aam.2024.102689
|
| [8] | P. Flajolet, R. Sedgewick, Analytic combinatorics, Cambridge: Cambridge University Press, 2009. https://doi.org/10.1017/CBO9780511801655 |
| [9] | H. S. Wilf, Generatingfunctionology, New York: Academic Press, 1990. https://doi.org/10.1016/C2013-0-11714-X |
| [10] |
J. M. Holte, Carries, combinatorics, and an amazing matrix, Am. Math. Mon., 104 (1997), 138–149. https://doi.org/10.1080/00029890.1997.11990612 doi: 10.1080/00029890.1997.11990612
|
| [11] |
P. Diaconis, M. McGrath, J. Pitman, Riffle shuffles, cycles, and descents, Combinatorica, 15 (1995), 11–29. https://doi.org/10.1007/BF01294457 doi: 10.1007/BF01294457
|
| [12] |
P. Diaconis, J. Fulman, Carries, shuffling, and an amazing matrix, Am. Math. Mon., 116 (2009), 788–803. https://doi.org/10.4169/000298909X474864 doi: 10.1007/BF01294457
|
| [13] |
S. P. Lalley, Riffle shuffles and their associated dynamical systems, J. Theor. Probab., 12 (1999), 903–932. https://doi.org/10.1023/A:1021636902356 doi: 10.1023/A:1021636902356
|
| [14] | P. Diaconis, Group representations in probability and statistics, Hayward, CA: Institute of Mathematical Statistics, 1988. https://doi.org/10.1214/lnms/1215467407 |
| [15] |
J. Fulman, Applications of symmetric functions to cycle and increasing subsequence structure after shuffles, J. Algebr. Comb., 16 (2002), 165–194. https://doi.org/10.1023/A:1021177012548 doi: 10.1023/A:1021177012548
|
Figures(4)
Tipaluck Krityakierne, Thotsaporn Aek Thanatipanonda. A generating function framework for the no-feedback card guessing game after riffle shuffles[J]. AIMS Mathematics, 2025, 10(10): 24257-24269. doi: 10.3934/math.20251075
DownLoad: