The card guessing game: A generating function approach. (March 2023)

• Record Type: Journal Article
• Authors: Krityakierne, Tipaluck; Thanatipanonda, Thotsaporn Aek
• Is Part Of: Journal of symbolic computation. Volume 115(2023)
• Page Start: 1
• Page End: 17
• Publication Date: 2023-03
• Subjects: Generating function -- Symbolic computation -- Combinatorics -- Card shuffling; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2022.07.001
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: Consider a card guessing game with complete feedback in which a deck of n cards ordered 1, …, n is riffle-shuffled once. With the goal to maximize the number of correct guesses, a player guesses cards from the top of the deck one at a time under the optimal strategy until no cards remain. We provide an expression for the expected number of correct guesses with arbitrary number of terms, an accuracy improvement over the results of Liu (2021) . In addition, using generating functions, we give a unified framework for systematically calculating higher-order moments. Although the extension of the framework to k ≥ 2 shuffles is not immediately straightforward, we are able to settle a long-standing McGrath's conjectured optimal strategy described in Bayer and Diaconis (1992) by showing that the optimal guessing strategy for k = 1 riffle shuffle does not necessarily apply to k ≥ 2 shuffles.