{"id":"4bd056ee-0803-4da8-8275-f94007c20063","arxiv_id":"1908.07718","paper_version":4,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For one riffle shuffle with complete feedback, the optimal expected number of correct guesses is n/2 + sqrt(2/pi) sqrt(n) + O(1).","lead":"This math paper finds the best strategy for guessing cards after one riffle shuffle when players are told the correct card after every guess. It proves that with a deck of n cards, the expected number of correct guesses is about half the deck plus a bonus that grows like the square root of n.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified","rationale":"I read the paper as proving two things: Algorithm 1.1 is optimal, and its expected reward is n/2 + sqrt(2/pi) sqrt(n) + O(1). Both survive scrutiny. Optimality is sound because under complete feedback the player's guess does not influence which card is revealed, so maximizing the immediate conditional probability at each state is optimal by backward induction. The consecutive-stage lemma, the nonconsecutive-stage conditioning (which forces the cut to be k-1 and leaves a uniform interleaving), and the final greedy interleaving policy all check out. Lemma 3.6 is the most compressed part: part (a) is justified by the standard dynamic-programming property that a globally optimal policy must be optimal after every reachable history, and part (b) follows from an explicit and correct total-variation computation. I independently re-derived the S(n) recurrence using the paper's definition of S as a sum over k=1..n and found no algebraic error; the simplification to the binomial-plus-2S(n-1) form is correct. The asymptotic solution of the resulting F(n) and G(n) recurrences gives exactly F(n) = n/4 + sqrt(n/(2pi)) + O(1) and G(n) = n/2 + sqrt(2/pi) sqrt(n) + O(1). The remaining issues are expository: the m=0 case in Algorithm 1.1 and the unproved greedy principle are not spelled out, but neither threatens the argument. Hence the reader's ACCEPT verdict should stand.","tokens_in":9807,"tokens_out":50027,"duration_ms":454479,"concrete_test":"Enumerate all riffle-shuffle permutations of [n+1] with first card 1 to form the conditional distribution g_n, compute R*(g_n) exactly for n up to 8, and verify numerically that it agrees with R*(f_n) within the stated total-variation bound; this directly tests Lemma 3.6.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No load-bearing concern identified. The most delicate step flagged by the reader, Lemma 3.6, holds on inspection: part (a) follows from the dynamic-programming principle applied to the global optimal strategy after the positive-probability history [1], and part (b) is a correct total-variation estimate (TV = (2^n - n - 1)/(2^n(2^n + 1)), giving a reward difference of at most 2n TV = o(1)). I also checked the recurrence derivation: with the paper's convention S(n) = sum_{k=1}^n C(n,k) f(k,n-k), the closed form S(n) = 2^{n-1} + C(n-1, floor((n-1)/2)) + n - 2 + 2S(n-1) is correct; for n=3 it gives 17, matching direct computation from (3.3). The only presentational gaps are that Algorithm 1.1 does not explicitly spell out the m=0 case when the first guess 1 is wrong, and the greedy optimality principle under complete feedback is stated rather than proved. Both are benign, because complete feedback makes the post-feedback state independent of the guess.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":10003,"tokens_out":24327,"duration_ms":208006,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Section 1.4 / Proposition 3.1"},{"comment":"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.","section":"Lemma 3.6(a)"},{"comment":"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.","section":"Equation (3.4)"},{"comment":"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}.","section":"Algorithm 1.1, step 2"},{"comment":"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.","section":"Lemma 3.2"},{"comment":"The expression written as 1 + 2^{n-1}/2^n should be (1 + 2^{n-1})/2^n; parentheses would remove a possible misreading.","section":"Equation (3.1) and surrounding display"}],"recommendation":"minor_revision","confidential_remarks":"The central claims are correct and the proof strategy is sound. The main issues are expositional: the dynamic-programming justification and the proof of Lemma 3.6(a) should be expanded, and a typo in Equation (3.4) should be corrected. I see no substantive obstacle to publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Pengda Liu has done what Bayer and Diaconis left open for the one-shuffle case: the optimal strategy is the three-phase algorithm (guess 1, then consecutive, then interleave from the longer pile), and the maximum expected reward is n/2 + sqrt(2/pi) sqrt(n) + O(1). The result is new and the proof is mostly clean.\n\nThe main technical work is the recurrence for f(a,b), the closed form for S(n), and the TV estimate in Lemma 3.6. None of the constants are fitted; the 1/2 and sqrt(2/pi) come out of solving the recurrences and Stirling's formula. The TV bound in Lemma 3.6(b) is explicit and gives o(1) as needed. The induction showing the O(1) error is uniform is standard and works, assuming a small typo in the displayed recurrence (a missing +1/2 in the G(n+1) line) is fixed; the original LaTeX probably has it right.\n\nSoft spots: the optimality proof is compressed. The greedy principle—after complete feedback the posterior does not depend on history beyond the revealed cards—is stated rather than proved. It is true, so this is a presentation gap, not a hole. Lemma 3.6(a) is also terse; it says the optimal strategy for the conditional shuffle is isomorphic to the original strategy, which follows from the dynamic programming principle once the global optimality of Algorithm 1.1 is established. The text circles back to Proposition 3.1 to justify it, so it is not circular, but a referee will want the steps spelled out. The O(1) constant is not identified; the author notes numerics keep it below 0.5 up to 10,000, which is fine for the theorem as stated.\n\nThe citation pattern is appropriate: Ciucu for zero feedback, Bayer and Diaconis for the open problem and the GSR distribution, Diaconis and Graham for the sequential-experiment framing. No self-citation issues.\n\nWho is this for? People working on card guessing, sequential experiments, and combinatorial probability more broadly. It does not resolve the k-shuffle problem, and the paper says so. The open problems at the end are honest.\n\nRecommendation: send it to a serious referee. It deserves refereeing, and with minor revisions it will be a clean, citable paper.","headline":"Solves the one-shuffle complete-feedback card guessing problem with a genuinely derived asymptotic; a few presentation gaps but no load-bearing flaws.","tokens_in":10517,"tokens_out":4472,"would_cite":true,"duration_ms":498600,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60C05","65C50"],"pacs":[],"model":"deepseek-v4-flash","headline":"Optimal guessing after one riffle shuffle scores n/2 + sqrt(2/pi) sqrt(n) + O(1).","keywords":["card guessing","riffle shuffle","complete feedback","optimal strategy","expected reward","rising sequences","dovetail shuffle","asymptotic analysis"],"falsifier":"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.","tokens_in":9605,"feed_emoji":"🃏","tokens_out":13225,"duration_ms":118996,"temperature":0.7,"pith_summary":"This paper gives the optimal strategy for guessing the cards of a deck that has been riffle-shuffled once, when after each guess the true top card is revealed. The strategy is a three-phase rule: guess the cards 1,2,3,... in order while they keep appearing; when a break appears, split the unseen cards into the two original piles; thereafter always name the first card of the longer pile. The paper proves this rule is optimal and computes its expected number of correct guesses as $n/2+\\sqrt{2/\\pi}\\sqrt{n}+O(1)$. This partially answers an open problem raised in [2] about guessing riffle-shuffled decks with complete feedback, and it gives an exact asymptotic for a natural interactive guessing problem.","feed_headline":"Optimal riffle-shuffle guessing scores n/2 + sqrt(2n/pi)","feed_subtitle":"A three-phase strategy—guess consecutive cards, then always name the longer pile's lead—is proved optimal.","key_machinery":"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)}$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the transition matrix for the riffle shuffle and the binomial-sum asymptotics used in the expected-reward calculation.","marker":"[1]"},{"why":"Raises the open problem and gives the distribution Q(pi) on permutations with at most two rising sequences.","marker":"[2]"},{"why":"Sets up sequential experiments with complete feedback and provides the recursive optimality equation used in the proof.","marker":"[3]"}],"fun_headline_variants":["Optimal riffle-shuffle guessing: expected score n/2 + √(2n/π) + O(1)","Proof: optimal guess for one riffle shuffle gives n/2 + √(2n/π) + O(1)","Riffle-shuffle guessing: optimal score is n/2 + √(2n/π) + O(1)","One riffle shuffle, full feedback: optimal expected score n/2 + √(2n/π) + O(1)"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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)$.","fun_headline_variants_meta":{"raw":{"variants":["Optimal riffle-shuffle guessing: expected score n/2 + √(2n/π) + O(1)","Proof: optimal guess for one riffle shuffle gives n/2 + √(2n/π) + O(1)","Riffle-shuffle guessing: optimal score is n/2 + √(2n/π) + O(1)","One riffle shuffle, full feedback: optimal expected score n/2 + √(2n/π) + O(1)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001054,"raw_usage":{"total_tokens":4399,"prompt_tokens":893,"completion_tokens":3506,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":509,"completion_tokens_details":{"reasoning_tokens":3382}},"tokens_in":509,"tokens_out":3506,"duration_ms":25578,"temperature":1.0,"reasoning_tokens":3382,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:00:52.487789+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the transition matrix for the riffle shuffle and the binomial-sum asymptotics used in the expected-reward calculation."},{"cited_title":"(1992) Trailing the dovetai l shuffle to its lair","cited_arxiv_id":null,"evidence_quote":"Raises the open problem and gives the distribution Q(pi) on permutations with at most two rising sequences."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Sets up sequential experiments with complete feedback and provides the recursive optimality equation used in the proof."}],"review_version":1}