CARD GUESSING AND THE BIRTHDAY PROBLEM FOR SAMPLING WITHOUT REPLACEMENT

• 成果类型: Article
• 署名作者: He, Jimmy; Ottolini, Andrea
• 署名单位: Massachusetts Institute of Technology (MIT); University of Washington; University of Washington Seattle
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/23-AAP1946
• 发表日期: 2023
• 页码: 5208-5232
• 关键词: feedback

摘要

Consider a uniformly random deck consisting of cards labelled by num-bers 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 an-swers 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 sam-pling without replacement using Stein's method.