Card guessing and the birthday problem for sampling without replacement
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909117064413184 |
|---|---|
| author | He, Jimmy Ottolini, Andrea |
| author_facet | He, Jimmy Ottolini, Andrea |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2108_07355 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Card guessing and the birthday problem for sampling without replacement He, Jimmy Ottolini, Andrea Probability Combinatorics 60C05 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. |
| title | Card guessing and the birthday problem for sampling without replacement |
| topic | Probability Combinatorics 60C05 |
| url | https://arxiv.org/abs/2108.07355 |