In his class Mathematics and Statistics of Gambling (MATH 231/STATS 334 in 2018), Persi Diaconis posed the following two problems as extra credit:
- Determine the optimal strategy for guessing the order of a deck of cards with feedback after one overhead shuffle.
- Provide a guess for what the optimal strategy is for guessing the order of a deck of cards with feedback after one riffle shuffle.
Note, in this setting, optimal means maximizing the expected number of cards guessed correctly. Both problems were "open". In Persi Diaconis’ paper “Trailing The Dovetail Shuffle To Its Lair”, Diaconis outlines a guessing strategy developed by McGrath for guessing the order of a deck of cards after k riffle shuffles. The 8th open problem in Diaconis’ paper “Mathematical Developments From the Analysis of Riffle Shuffling” is to prove that McGrath‘s strategy is optimal.
As my final project for his class, I began researching these problems. These are up to date notes on my findings. All work has been done independently.
We develop some theory surrounding how to construct an optimal guessing strategy with feedback. Then we find the provably optimal strategy for guessing the order of a deck of cards after one overhead shuffle, as well as a closed form for the expected number of cards that are guessed correctly. We also derive the provably optimal strategy for guessing the order of a deck of cards after one riffle shuffle, and doing so confirm that McGrath was correct in the case that k=1. We provide a brief discussion on how one may extend the riffle shuffle result to k > 1. This is the most promising avenue of future work.
Results can be found here