Cutoff for the Overhand Shuffle
Abstract
We study the overhand shuffle with a fixed cut probability p∈(0,1). In the packet-reversal convention, each gap is cut independently with probability p, and each resulting packet is reversed in place. We prove total-variation cutoff at p2/(2(1−p)π2) n2log n. The lower bound uses an exact finite-deck cosine eigenfunction and a uniform conditional-variance estimate. For the upper bound, a coalescing coupling reduces a transposition discrepancy to a symmetric killed two-card chain. Its principal decay rate is (1−p)π2/(p2n2)+o(n−2). A boundary-flux identity bounds the sum of adjacent discrepancy probabilities without a factor equal to the deck size. The remaining ingredient is a two-sided L1 inequality on permutations, with constant at most √nexp{O(√(log nloglog(n+2)))}. Its proof decomposes a fixed block-table fiber into assignment words and independent smaller permutations, and closes a recursion using a multivariate hypergeometric inequality and an explicit routing comparison. We also prove relative-entropy cutoff with an Op(n2) window about the intrinsic entropy transition time. Its leading coefficient lies between the total-variation coefficient and twice that value; a sharp entropy location is not obtained. The proof states the normalization and hypotheses of its established functional-inequality inputs. An appendix proves the intermediate static bounds and explains the change from one-scale averaging to recursive fibers.
Related
BibTeX
@misc{jiang2026cutoff,
title = {{Cutoff for the Overhand Shuffle}},
author = {Yunjiang Jiang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.00137},
eprint = {2610.00137},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.00137},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Cutoff for the Overhand Shuffle
AU - Yunjiang Jiang
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.00137
UR - https://arxiv.org/abs/2610.00137
AB - We study the overhand shuffle with a fixed cut probability p∈(0,1). In the packet-reversal convention, each gap is cut independently with probability p, and each resulting packet is reversed in place. We prove total-variation cutoff at p^2/(2(1−p)π^2) n^2log n. The lower bound uses an exact finite-deck cosine eigenfunction and a uniform conditional-variance estimate. For the upper bound, a coalescing coupling reduces a transposition discrepancy to a symmetric killed two-card chain. Its principal decay rate is (1−p)π^2/(p^2n^2)+o(n^−2). A boundary-flux identity bounds the sum of adjacent discrepancy probabilities without a factor equal to the deck size. The remaining ingredient is a two-sided L^1 inequality on permutations, with constant at most √nexp{O(√(log nloglog(n+2)))}. Its proof decomposes a fixed block-table fiber into assignment words and independent smaller permutations, and closes a recursion using a multivariate hypergeometric inequality and an explicit routing comparison. We also prove relative-entropy cutoff with an O_p(n^2) window about the intrinsic entropy transition time. Its leading coefficient lies between the total-variation coefficient and twice that value; a sharp entropy location is not obtained. The proof states the normalization and hypotheses of its established functional-inequality inputs. An appendix proves the intermediate static bounds and explains the change from one-scale averaging to recursive fibers.
ER -