Speaker: Sam Spiro

Title: Card Guessing with Partial Feedback

Abstract: Consider the following experiment: a deck with $m$ copies of $n$ different card types is randomly shuffled, and a guesser attempts to guess the cards sequentially as they are drawn.  Each time a guess is made, some amount of ``feedback'' is given.  For example, one could tell the guesser the true identity of the card they just guessed (the complete feedback model) or they could be told nothing at all (the no feedback model).  

In this talk we explore a partial feedback model, where upon guessing a card, the guesser is only told whether or not their guess was correct. We show in this setting that, uniformly in $n$, at most $m+O(m^{3/4}\log m)$ cards can be guessed correctly in expectation, which is roughly the number of cards one gets by naively guessing the same card type $mn$ times.  This is joint work with Persi Diaconis, Ron Graham, and Xiaoyu He.