Card guessing and the birthday problem for sampling without replacement

DOI10.1214/23-AAP1946MaRDI QIDQ6180369zbMATH OpenOpenAlexFDO

Authors Jimmy He, Andrea Ottolini

Publication date 19 January 2024

Published in The Annals of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

birthday problemcard guessing game

Mathematics Subject Classification ID

Combinatorial probability (60C05)

Abstract: Consider a uniformly random deck consisting of cards labelled by numbers from $1$ through $n$, possibly with repeats. A guesser guesses the top card, after which it is revealed and removed and the game continues. What is the expected number of correct guesses under the best and worst strategies? We establish sharp asymptotics for both strategies. For the worst case, this answers a recent question of Diaconis, Graham, He and Spiro, who found the correct order. As part of the proof, we study the birthday problem for sampling without replacement using Stein's method.

Recommendations

• The card guessing game: a generating function approach
• Card guessing with partial feedback
• A simple card guessing game revisited
• Chance Expectancy with Trial-By-Trial Feedback and Random Sampling Without Replacement
• Online card games

Cites work

• scientific article; zbMATH DE number 52632 (Why is no real title available?)
• scientific article; zbMATH DE number 3438144 (Why is no real title available?)
• A Bayesian peek into Feller volume. I
• A note on Blackwell and Hodges (1957) and Diaconis and Graham (1981)
• A simple card guessing game revisited
• Card guessing with partial feedback
• Design for the Control of Selection Bias
• Exchangeable pairs and Poisson approximation
• Forcing a sequential experiment to be balanced
• Fundamentals of Stein's method
• Guessing about guessing: practical strategies for card guessing with feedback
• Lattice paths, sampling without replacement, and limiting distributions
• No-feedback card guessing for dovetail shuffles
• On Birthday, Collectors', Occupancy and Other Classical Urn Problems
• On card guessing game with one time riffle shuffle and complete feedback
• Online card games
• Poisson approximation for dependent trials
• Sequential urn schemes and birth processes
• Size bias for one and all
• Size biased couplings and the spectral gap for random regular graphs
• The analysis of sequential experiments with feedback to subjects
• The card guessing game: a generating function approach
• The general birthday problem
• Two moments suffice for Poisson approximations: The Chen-Stein method
• Universal limit theorems in graph coloring problems with connections to extremal combinatorics

Cited in

(2)

• On Card guessing with two types of cards
• Semi-restricted rock, paper, scissors

This page was built for publication: Card guessing and the birthday problem for sampling without replacement

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