OpenAlex ·
A subquadratic upper bound for the mixing time of the Thorp shuffle
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.18884
- Original
- Read it at the publisher
- Topics
Abstract
Let $n=2^d$. We prove that the worst-start total-variation mixing time of the full labelled Thorp shuffle satisfies, for every fixed $0<\varepsilon<1$, \[ t_{\mathrm{mix}}(\varepsilon) \le C_* d^{5/3}+O_\varepsilon\!\left(d^{4/3}\log(d+2)\right), \qquad C_*=5.1536951454\ldots . \] Time is measured in ordinary Thorp shuffles. This improves the previously published full-deck upper bound $O(d^3)$ of Morris. The geometric starting point is elementary: label the $n=2^d$ positions by binary strings. One physical Thorp shuffle is a random swap layer on one coordinate matching of the $d$-dimensional cube, followed by a deterministic cyclic rotation of the coordinates. In a rotating frame that deterministic rotation disappears, so $d$ successive physical shuffles become one \emph{sweep}: one independent random swap layer in each coordinate direction. The proof then combines five ingredients. First, a collision-graph representation and negative dependence give pointwise smoothing for ordered marked cards. Second, an entropy argument is sharpened by moving an endpoint moment up to the critical exponent $β_c=\log_2(3/2)$, yielding an entropy-preparation clock $s^2/(2\log(3/2))+O(s\log s)$. Third, exact multiplicities in the ordered $h$-tuple permutation representation amplify marked-card bounds into Fourier operator and energy estimates on low representation levels. Fourth, entropy truncation produces a positive mixture whose regular component retains the marked-card budget. Finally, only two long blocks need this entropy regularization: a shorter third block is used solely for additional low-level smoothing. Optimizing the three block lengths gives the constant above.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Mathematical Physics
The Right Wing of the SABR Smile with an Absorbing Boundary: Resolution of Conjectures of Henry-Labordère
When the noncommutative AM-GM inequality holds
Efficient Mass Matrix Estimation with Gaussian Cooling
Buying at Support: The Entry Problem under Multi-Skew Brownian Motion
On some concepts of convergence and their connections
Get the few papers worth your time in Mathematical Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.