A subquadratic upper bound for the mixing time of the Thorp shuffle
Abstract
Let n=2d. We prove that the worst-start total-variation mixing time of the full labelled Thorp shuffle satisfies, for every fixed 0<ε<1, tmix(ε) ≤ C* d5/3+Oε (d4/3log(d+2)), C*=5.1536951454… . Time is measured in ordinary Thorp shuffles. This improves the previously published full-deck upper bound O(d3) of Morris. The geometric starting point is elementary: label the n=2d 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=log2(3/2), yielding an entropy-preparation clock s2/(2log(3/2))+O(slog 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.
Related
- Mixing Time of the Random-Pair Monte Shuffle
- Almost sure upper bound for random multiplicative functions
- A double-logarithmic upper bound on the chromatic number of the associahedron
- Lee-Huang-Yang Energy for Dilute Bose Gases: an Upper Bound for General Potentials
- A New Upper Bound for 7-Universal Tournaments
BibTeX
@misc{jiang2026subquadratic,
title = {{A subquadratic upper bound for the mixing time of the Thorp shuffle}},
author = {Yunjiang Jiang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.18884},
eprint = {2610.18884},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.18884},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A subquadratic upper bound for the mixing time of the Thorp shuffle
AU - Yunjiang Jiang
PY - 2026
DA - 2026/10/03
PB - arXiv
DO - 10.48550/arxiv.2610.18884
UR - https://arxiv.org/abs/2610.18884
AB - 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<ε<1, t_mix(ε) ≤ C_* d^5/3+O_ε (d^4/3log(d+2)), C_*=5.1536951454… . 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/(2log(3/2))+O(slog 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.
ER -