Card guessing and the birthday problem for sampling without replacement
Угадывание карт и задача о днях рождения при выборке без возвращения
2023-12-01
SCID: 54.1/pkaxtv93
Discuss with AI
Stein's methodbirthday problemcard guessingsampling without replacementsharp asymptotics
Figures from the paper
Abstract (AI)
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.
Key Findings
1
It establishes sharp asymptotics for the expected number of correct guesses under both optimal and worst guessing strategies.
2
The paper analyzes expected correct guesses when sequentially guessing cards from a uniformly random deck with repeated labels and sampling without replacement.
3
The proofs develop a Stein’s method analysis of the birthday problem for sampling without replacement.
4
The worst-case analysis resolves a recent question by Diaconis, Graham, He, and Spiro after their work identified the correct order of magnitude.
Research Object
a uniformly random deck of cards labeled 1 through n, possibly with repeated labels, sampled without replacement
Research Subject
the expected number of correct sequential card guesses under optimal and pessimal strategies, including its sharp asymptotics, and the associated birthday-collision behavior for sampling without replacement
Publication Details
Publication Date
2023-12-01
Journal
Publisher
ISSN
Cited by
4
Access Type
Author Information
Download PDF
Subscribe to digest