IMSc Webinar

Analysing a strategy for a card guessing game via continuously increasing subsequences in multiset permutations

Bishal Deb

University College London

Join Zoom Meeting
zoom.us/j/91288928049?pwd=WHNaUE9TZEdZWGR3aGNtN2JvWDNtZz09

Meeting ID: 912 8892 8049
Passcode: Macdonald

researchseminars.org/seminar/ARCSIN

Consider the following card guessing game introduced by Diaconis and Graham (1981): there is a shuffled deck of $mn$ cards with $n$ distinct cards numbered $1$ to $n$, each appearing with multiplicity $m$. In each round, the player has to guess the top card of the deck, and is then told whether the guess was correct or not, the top card is then discarded and then the game continues with the next card. This is known as the partial feedback model. The aim is to maximise the number of correct guesses. One possible strategy is the shifting strategy in which the player keeps guessing $1$ every round until the guess is correct in some round, and then keeps guessing $2$, and then $3$ and so on. We are interested in finding the expected score using this strategy.

We can restate this problem as finding the expectation of the largest value of $i$ such that $123\ldots i$ is a subsequence in a word formed using letters 1 to n where each letter occurs with multiplicity $m$. In this talk, we show that this number is $m+1 - 1/(m+2)$ plus an exponential error term. This confirms a conjecture of Diaconis, Graham, He and Spiro.

This talk will be at an interface between combinatorics, probability and analysis and will feature an unexpected appearance of the Taylor polynomials of the exponential function. This is based on joint work with Alexander Clifton, Yifeng Huang, Sam Spiro and Semin Yoo.