Probability Seminar

Jimmy HeMassachusetts Institute of Technology
Card guessing and a variant of the birthday problem

Monday, November 1, 2021 - 3:45pm
Malott 406

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? I will discuss recent work establishing sharp asymptotics for both strategies. For the worst case, this answers a recent question of Diaconis, Graham, He and Spiro. As part of the proof, we study a variant of the birthday problem for sampling without replacement using Stein’s method. This work is joint with Andrea Ottolini.