Online card games

DOI10.1214/22-EJP768MaRDI QIDQ2136089zbMATH OpenOpenAlexFDO

Authors Sam Spiro

Publication date 10 May 2022

Published in Electronic Journal of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2106.11866

zbMATH Keywords

card shufflingdiscrete probabilitygame theory

Mathematics Subject Classification ID

Combinatorial probability (60C05)

Abstract: Consider the following one player game. A deck containing $m$ copies of $n$ different card types is shuffled uniformly at random. Each round the player tries to guess the next card in the deck, and then the card is revealed and discarded. It was shown by Diaconis, Graham, He, and Spiro that if $m$ is fixed, then the maximum expected number of correct guesses that the player can achieve is asymptotic to $H_{m}logn$, where $H_m$ is the $m$th harmonic number. In this paper we consider an adversarial version of this game where a second player shuffles the deck according to some (possibly non-uniform) distribution. We prove that a certain greedy strategy for the shuffler is the unique optimal strategy in this game, and that the guesser can achieve at most $logn$ expected correct guesses asymptotically for fixed $m$ against this greedy strategy.

Review text

For the one player game, a deck containing \(m\) copies of \(n\) different card types is shuffled uniformly at random. Each round the player tries to guess the next card in the deck, and then the card is revealed and discarded. It is known that if \(m\) is fixed, then the maximum expected number of correct guesses that the player can achieve is asymptotic to \(H_m \log n\). This paper considers an adversarial version of this one player game, where a second player shuffles the deck according to some (possibly non-uniform) distribution. The author proves that a certain greedy strategy for the shuffler is the unique optimal strategy in this game, and that the guesser can achieve at most \(\log n\) expected correct guesses asymptotically for fixed \(m\) against this greedy strategy.

Recommendations

• The card guessing game: a generating function approach
• On card guessing game with one time riffle shuffle and complete feedback
• Guessing about guessing: practical strategies for card guessing with feedback
• A simple card guessing game revisited
• Card guessing with partial feedback

Cites work

• Design for the Control of Selection Bias
• Forcing a sequential experiment to be balanced
• Generating a random permutation with random transpositions
• Guessing about guessing: practical strategies for card guessing with feedback
• No-feedback card guessing for dovetail shuffles
• On card guessing game with one time riffle shuffle and complete feedback
• Shuffling Cards and Stopping Times
• The analysis of sequential experiments with feedback to subjects
• The card guessing game: a generating function approach
• The coupon-collector's problem revisited
• The hyperharmonic numbers and the phratry of the coupon collector
• The overhand shuffle mixes in \(\Theta(n^2\log n)\) steps
• Trailing the dovetail shuffle to its lair

Cited in

(12)

• On card guessing game with one time riffle shuffle and complete feedback
• The card guessing game: a generating function approach
• scientific article; zbMATH DE number 4066897 (Why is no real title available?)
• How to Beat Your Kids at Their Own Game
• Guessing about guessing: practical strategies for card guessing with feedback
• What to expect in a game of memory
• How to play Dundee.
• Card guessing with partial feedback
• A simple card guessing game revisited
• Semi-restricted rock, paper, scissors
• Guessing cards with complete feedback
• Card guessing and the birthday problem for sampling without replacement

This page was built for publication: Online card games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2136089)