Cutoff for the Overhand Shuffle

Abstract

We study the overhand shuffle with a fixed cut probability $p\in (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 \[ \frac{p^2}{2(1-p)π^2}\,n^2\log 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){\pi }^2/(p^2{n}^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 $\sqrt{n}\exp \{O(\sqrt{\log n\log \log (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.