Card guessing and the birthday problem for sampling without replacement
From MaRDI portal
Publication:6180369
DOI10.1214/23-AAP1946arXiv2108.07355OpenAlexW4389674530MaRDI QIDQ6180369FDOQ6180369
Authors: Jimmy He, Andrea Ottolini 
Publication date: 19 January 2024
Published in: The Annals of Applied Probability (Search for Journal in Brave)
Abstract: Consider a uniformly random deck consisting of cards labelled by numbers from through , 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.
Full work available at URL: https://arxiv.org/abs/2108.07355
Recommendations
Cites Work
- Two moments suffice for Poisson approximations: The Chen-Stein method
- Design for the Control of Selection Bias
- A Bayesian peek into Feller volume. I
- Forcing a sequential experiment to be balanced
- Title not available (Why is that?)
- Fundamentals of Stein's method
- Title not available (Why is that?)
- Poisson approximation for dependent trials
- On Birthday, Collectors', Occupancy and Other Classical Urn Problems
- No-feedback card guessing for dovetail shuffles
- Exchangeable pairs and Poisson approximation
- The card guessing game: a generating function approach
- Size bias for one and all
- Universal limit theorems in graph coloring problems with connections to extremal combinatorics
- The general birthday problem
- The analysis of sequential experiments with feedback to subjects
- A note on Blackwell and Hodges (1957) and Diaconis and Graham (1981)
- Lattice paths, sampling without replacement, and limiting distributions
- Sequential urn schemes and birth processes
- Size biased couplings and the spectral gap for random regular graphs
- Online card games
- On card guessing game with one time riffle shuffle and complete feedback
- Guessing about guessing: practical strategies for card guessing with feedback
- Card guessing with partial feedback
- A simple card guessing game revisited
Cited In (2)
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)
