Optimal complete-feedback card guessing under nonincreasing valley weights: A proof of the Diaconis-Fulman-Holmes shelf-shuffling conjecture
Abstract
Let a random permutation W∈ Sn represent the order of n distinct cards. After each guess, the player learns the actual card, and the objective is to maximize the expected total number of correct guesses. Diaconis, Fulman, and Holmes conjectured that, after a single uniform, unbiased shelf shuffle, the direction-tracking strategy is optimal: first guess the smallest card, and thereafter choose the nearest remaining card in the direction of the most recent rise or fall. We prove a more general theorem: if ℙ(W=w)=f(v(w))/(∑σ∈ Snf(v(σ))), where v(w) is the number of interior valleys of the permutation, f is nonnegative and nonincreasing, and the denominator is positive, then direction tracking maximizes the conditional probability of correctly guessing the next card after every history of positive probability. It therefore maximizes the expected total number of correct guesses among all complete-feedback strategies. Here an interior valley is a position 2≤ i≤ n−1 satisfying wi−1>wi<wi+1. Combined with the known shelf-shuffling probability formula, this theorem proves the conjecture for every deck size and number of shelves. The key to the proof is a swap of adjacent remaining values that preserves the revealed prefix: starting from the preferred candidate, the swap leaves the valley count unchanged or increases it by one, thereby turning monotonicity of the weights into a conditional probability ordering after every history.
Related
- Limit Theorems for the Complete Feedback Card Guessing Game
- Optimal no-feedback card guessing after a fixed number of riffle shuffles
- Extremal expectations in card guessing with partial feedback: proofs of two conjectures of Diaconis-Graham-Spiro
- A Complete Solution to the Conjecture on the Inverse Collatz–Sinogowitz Irregularity Problem
- A complete solution to the Boots-Royle/Cao-Vince conjecture
BibTeX
@misc{luo2026optimal,
title = {{Optimal complete-feedback card guessing under nonincreasing valley weights: A proof of the Diaconis-Fulman-Holmes shelf-shuffling conjecture}},
author = {Congyi Luo},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.25063},
eprint = {2609.25063},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.25063},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal complete-feedback card guessing under nonincreasing valley weights: A proof of the Diaconis-Fulman-Holmes shelf-shuffling conjecture
AU - Congyi Luo
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.25063
UR - https://arxiv.org/abs/2609.25063
AB - Let a random permutation W∈ S_n represent the order of n distinct cards. After each guess, the player learns the actual card, and the objective is to maximize the expected total number of correct guesses. Diaconis, Fulman, and Holmes conjectured that, after a single uniform, unbiased shelf shuffle, the direction-tracking strategy is optimal: first guess the smallest card, and thereafter choose the nearest remaining card in the direction of the most recent rise or fall. We prove a more general theorem: if ℙ(W=w)=f(v(w))/(∑_σ∈ S_nf(v(σ))), where v(w) is the number of interior valleys of the permutation, f is nonnegative and nonincreasing, and the denominator is positive, then direction tracking maximizes the conditional probability of correctly guessing the next card after every history of positive probability. It therefore maximizes the expected total number of correct guesses among all complete-feedback strategies. Here an interior valley is a position 2≤ i≤ n−1 satisfying w_i−1>w_i<w_i+1. Combined with the known shelf-shuffling probability formula, this theorem proves the conjecture for every deck size and number of shelves. The key to the proof is a swap of adjacent remaining values that preserves the revealed prefix: starting from the preferred candidate, the swap leaves the valley count unchanged or increases it by one, thereby turning monotonicity of the weights into a conditional probability ordering after every history.
ER -