Leírás
Abstract:
Consider the following game: Alice shuffles together m
identical decks of cards, each consisting of n distinct types.
At each step, Bob tries to guess the type of card that sits on
the top of the deck, and then Alice shows it to him and removes
it from the deck. The game continues this way until there are no
cards left, and it is referred to as the complete feedback game
since Bob is aware of the composition of the leftover cards in the
deck at each step. If his goal is to maximize/minimize (in expectation)
the number of correct guesses, how well can he perform? In joint work
with Jimmy He, we give sharp asymptotic for fixed m and large n that
improve results from Diaconis, Graham, He and Spiro. The main ingredient
is a careful analysis of a variant of the birthday problem for sampling
without replacement.
For Zoom access please contact Miklos Rasonyi (rasonyi.miklos[a]renyi.hu).