REVIEW 6 minor 5 references
On card guessing game with one time riffle shuffle and complete feedback
T0 review · 0 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Optimal guessing after one riffle shuffle scores n/2 + sqrt(2/pi) sqrt(n) + O(1).
desk verdict Solves the one-shuffle complete-feedback card guessing problem with a genuinely derived asymptotic; a few presentation gaps but no load-bearing flaws. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The supporting object is the support of the riffle-shuffle distribution: after one riffle, the shuffled permutation is either the identity or has exactly two rising sequences, where a rising sequence is a maximal consecutive increasing run in the shuffled order. The argument is carried by a recursion on the maximum expected reward $G(n)$, conditioned on the first revealed card. The key mechanism is Lemma 3.6: when the first card is 1, the resulting conditional shuffle $g_n$ is not identical to a fresh riffle shuffle $f_n$, but the two distributions have total variation distance about $(2^n-n-1)/(2^n(2^n+1))=o(1)$, so the same optimal guessing algorithm works and the expected rewards differ by $o(1)$. This replaces $g_n$ by $f_n$ in the recursion and leaves only the uniform-interleaving case $f(k-1,n-k)$ to be solved exactly through the recursion $S(n)=2^{n-1}+\binom{n-1}{\lfloor(n-1)/2\rfloor}+n-2+2S(n-1)$, whose central binomial term produces $\sqrt{n/(2\pi)}$.
What would settle it
Run exact backward induction over the $2^n$ possible one-riffle permutations for $n$ up to about 15, compare the value of Algorithm 1.1 with the dynamic-programming optimum at every prefix, and check whether $G(n)-n/2-\sqrt{2/\pi}\sqrt{n}$ stays bounded as $n$ grows. If any non-consecutive prefix makes a shorter-pile card the conditional mode, or if the error term diverges, the theorem fails.
Extended reading notes
Core claim
The central claim is Theorem 1.3: Algorithm 1.1 is optimal for the one-shot riffle shuffle with complete feedback, and its expected reward is $n/2+\sqrt{2/\pi}\sqrt{n}+O(1)$. Optimality is shown stage by stage: the first card is always most likely to be 1; while the revealed prefix stays consecutive, the next card is most likely to be the next consecutive value; once a non-consecutive card appears, the remaining deck is exactly a uniform interleaving of the two piles formed by the gap and the tail, and the card most likely to come next is the smallest card in the larger pile. The expected-reward computation reduces the game to a recursion $G(n)=\frac{1}{2}G(n-1)+F(n-1)+\frac{1}{2}+o(1)$, where $F(n)=S(n)/2^{n+1}$ is the normalized sum of the values $f(k,n-k)$ of uniform interleavings of two piles of sizes $k$ and $n-k$. $F(n)$ is evaluated in closed form with binomial identities, and solving the recursion yields the announced asymptotics.
Load-bearing premise
Everything rests on Lemma 3.6: after the first revealed card is 1, the remaining deck can be treated as a fresh riffle-shuffled deck of $n-1$ cards, with the same optimal strategy after relabeling and expected score within $o(1)$.
Editorial extensions
If this is right
- For decks of any size, the player never needs to compute posterior probabilities after the first break: the optimal guess is read off from which of the two remaining piles is longer.
- The expected number of correct guesses is about $n/2 + 0.7979\sqrt{n}$, so a player is correct on half the deck plus a square-root edge; for $n=10{,}000$ this is roughly $5079.8$ correct guesses.
- The $O(1)$ error term is bounded by a universal constant, so the formula is a uniform approximation for all large $n$; the paper's numerical check up to $n=10{,}000$ finds the error below $0.5$.
- For two or more riffle shuffles, the pile structure after a break is no longer determined by the revealed cards, so the same proof does not carry over; the paper leaves that case open.
Reading between the lines
- A natural extension of the proof's core rule, not proved in the paper, is that 'guess the longer pile' remains optimal for any shuffle that is a uniform interleaving of two known piles, even when the piles are not the consecutive blocks $A$ and $B$ arising here.
- Because the recursion is a linear ladder, a sharper expansion of $F(n)$ beyond the leading $\sqrt{n}$ term would convert the $O(1)$ in the theorem into an explicit computable constant; this is a concrete route to pinning down the error term.
- The same total-variation comparison used to relate $g_n$ to $f_n$ might help analyze fluctuations of the optimal score, for instance whether its variance is $O(n)$, a quantity the paper leaves open.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies a card-guessing game in which a deck labeled 1..n is riffle-shuffled once and the player receives complete feedback after every guess. It proposes Algorithm 1.1: guess the consecutive cards 1,2,... until the first non-consecutive card appears, then repeatedly guess the first card of the longer of the two remaining interleaved piles. The two main claims are that this algorithm is optimal and that its expected reward is n/2 + sqrt(2/pi) sqrt(n) + O(1). The proof uses the GSR characterization of riffle shuffling, the conditional distribution of the deck after the first card is revealed, a coupling between the conditional shuffle g_n and the original shuffle f_n via total variation distance, and an exact recurrence for the value f(a,b) of a uniformly interleaved pair of piles. The recurrence is solved in closed form with binomial sums, and Stirling's formula yields the stated asymptotics.
Significance. If correct, the theorem resolves the one-shuffle case of an open problem raised by Bayer and Diaconis and provides a concrete optimal policy. The derivation is parameter-free: the constants 1/2 and sqrt(2/pi) emerge from solving the recurrences rather than from any fitting, and the asymptotic formula is not assumed as an input. The explicit total variation computation in Lemma 3.6 is a clean and verifiable quantitative step. The paper is a solid contribution to the sequential-card-guessing literature and gives a method that may extend to related shuffling models.
minor comments (6)
- [Section 1.4 / Proposition 3.1] The paper uses the principle that under complete feedback the myopic rule of maximizing the conditional probability of the next card is globally optimal, but this principle is only stated and not proved. A short proof, noting that the posterior distribution after each step is independent of the guess because the correct card is revealed, would make the optimality argument in Proposition 3.1 fully rigorous.
- [Lemma 3.6(a)] The proof of part (a) is one sentence and can easily be misread as circular. It should explicitly say that Algorithm 1.1 is optimal for the original shuffle f_{n+1}, so by the dynamic-programming principle its continuation after the positive-probability history [1] is optimal for the conditional shuffle g_n, and that continuation is isomorphic to Algorithm 1.1 for f_n after relabeling.
- [Equation (3.4)] The displayed formula appears to contain a typo: F(n) = n/4 + sqrt(n)/(2 pi) + O(1) is inconsistent with Lemma 3.5 and with the subsequent induction, which uses the coefficient sqrt(2/pi)/2. The correct term should be (1/2) sqrt(2/pi) sqrt(n); please check the typesetting.
- [Algorithm 1.1, step 2] The m = 0 case, when the first guess 1 is wrong and the revealed card is k > 1, is not explicitly described; the text should state that the separating stage then applies with A = {1,...,k-1} and B = {k+1,...,n}.
- [Lemma 3.2] After showing that the conditional probability of card m exceeds 1/2, the conclusion that m is the unique argmax relies on the fact that the conditional probabilities over all possible next cards sum to one; stating this explicitly would make the step clearer.
- [Equation (3.1) and surrounding display] The expression written as 1 + 2^{n-1}/2^n should be (1 + 2^{n-1})/2^n; parentheses would remove a possible misreading.
Circularity Check
No significant circularity: the derivation is self-contained, with the asymptotic constants emerging from recurrences rather than from fitted inputs or load-bearing self-citations.
full rationale
The paper's central claim, Theorem 1.3, is derived from an explicitly defined GSR riffle-shuffle distribution and a complete-feedback optimality recursion. The optimality of Algorithm 1.1 in Proposition 3.1 is established by direct conditional-probability computations (Lemma 3.2, Theorem 2.7), not by assuming the target reward formula. The expected reward is then obtained by solving exact recurrences for G(n), S(n), and F(n); the constants 1/2 and sqrt(2/pi) arise from evaluating the central binomial sum via Stirling's formula, and the O(1) bound is shown by an induction that does not presuppose the result. The delicate step Lemma 3.6, which identifies the conditional shuffle g_n with f_n for purposes of reward asymptotics, is justified by an explicit total-variation computation and by the dynamic-programming principle: since Algorithm 1.1 is globally optimal, its continuation after the positive-probability history 'first card is 1' is optimal for the conditional subgame. No parameter is fitted to data, no prediction is a renamed input, and the citations to Bayer-Diaconis and Ciucu provide context and supporting distribution facts rather than the paper's main conclusion. The proof is therefore self-contained and not circular.
Assumptions & free parameters
assumptions (4)
- domain assumption GSR model correctly describes a single riffle shuffle.
- domain assumption With complete feedback, optimal play can be found by choosing, at each step, the card with maximal conditional probability given the revealed prefix.
- standard math Stirling's formula holds in the form n! = sqrt(2 pi n) (n/e)^n e^{lambda_n} with 1/(12n+1) < lambda_n < 1/(12n).
- standard math The number of permutations of [r] with exactly two rising sequences is R_r = 2^r - r - 1.
Cite this review
Pith. "Pith review of On card guessing game with one time riffle shuffle and complete feedback." pith.science (2026). https://pith.science/paper/5TEIHJE2
@misc{pith2026190807718,
author = {Pith},
title = {Pith review of: On card guessing game with one time riffle shuffle and complete feedback},
year = {2026},
howpublished = {\url{https://pith.science/paper/5TEIHJE2}},
note = {Machine review of arXiv:1908.07718}
}
abstract
This paper studies the game of guessing riffle-shuffled cards with complete feedback. A deck of $n$ cards labelled 1 to $n$ is riffle-shuffled once and placed on a table. A player tries to guess the cards from top and is given complete feedback after each guess. The goal is to find the guessing strategy with maximum reward (expected number of correct guesses). We give the optimal strategy for this game and prove that the maximum expected reward is $n/2+\sqrt{2/\pi}\cdot\sqrt{n}+O(1)$, partially solving an open problem of Bayer and Diaconis.
Reference graph
Works this paper leans on
-
[1]
M. Ciucu. (1998) No-feedback card guessing for dovetail shuffles. Ann. Appl. Probab. Vol. 8, No. 4, 1251-1269
work page 1998
-
[2]
(1992) Trailing the dovetai l shuffle to its lair
Dave Bayer, Persi Diaconis. (1992) Trailing the dovetai l shuffle to its lair. Ann. Appl. Probab
work page 1992
-
[3]
Persi Diaconis, Ronald Graham. (1981). The analysis of s equential experiments with feedback to subjects. The Ann. Stats. 9 3-23
work page 1981
-
[4]
(2003) Mathematical developments from the analysis of riffle shuffling
Persi Diaconis. (2003) Mathematical developments from the analysis of riffle shuffling. Groups, Combinatorics and Geometry A. Ivanov, M. Liebeck and J. Saxl, eds, World Scientific, New Jersey, 73-97
work page 2003
-
[5]
Persi Diaconis. (1988). Group Representations in Probability and Statistics. IMS, Hayward, CA. Department of Mathematics, Stanford University, Stanford, C A 94305 E-mail address : pengda@stanford.edu
work page 1988
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.