Mixing Time of the Random-Pair Monte Shuffle
Abstract
In the random-pair Monte shuffle on n cards, each step chooses two positions independently and uniformly and exchanges their cards with probability 1/2. The chosen positions are public; the decisions to exchange cards remain hidden. We prove that the mixing time in expected conditional total variation distance is 2nlog n+O(n), with an exact leading constant and an O(n) cutoff window. To our knowledge, this is the first public-schedule Monte shuffle whose full-permutation mixing time has been determined up to an additive O(n) term. The upper bound follows by comparing two executions with the same public schedule to a classical random-transposition walk. For the lower bound, we construct a schedule-dependent test function and estimate its variance using a matrix-averaging operator. Combined with the depth bound of Czumaj and Lingas, the mixing estimate gives public switching networks with at most 2nlog n+O(n) switches and O(log n) depth for fixed error and failure probabilities. The author obtained this result through interaction with GPT-6 Astra.
Related
- A subquadratic upper bound for the mixing time of the Thorp shuffle
- Mixing time of the lazy and simple random walk on a randomly twisted hypercube
- Mixing Time of Conditional Two Star Exponential Random Graphs
- Exponential mixing time for the Davies dynamics of the quantum random energy model
- Local Geometric Mixing via Dobrushin Contraction with Applications to Diffusion Path Monte Carlo and the Proximal Sampler
BibTeX
@misc{mironov2026mixing,
title = {{Mixing Time of the Random-Pair Monte Shuffle}},
author = {Ilya Mironov},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03959},
eprint = {2611.03959},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03959},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Mixing Time of the Random-Pair Monte Shuffle
AU - Ilya Mironov
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03959
UR - https://arxiv.org/abs/2611.03959
AB - In the random-pair Monte shuffle on n cards, each step chooses two positions independently and uniformly and exchanges their cards with probability 1/2. The chosen positions are public; the decisions to exchange cards remain hidden. We prove that the mixing time in expected conditional total variation distance is 2nlog n+O(n), with an exact leading constant and an O(n) cutoff window. To our knowledge, this is the first public-schedule Monte shuffle whose full-permutation mixing time has been determined up to an additive O(n) term. The upper bound follows by comparing two executions with the same public schedule to a classical random-transposition walk. For the lower bound, we construct a schedule-dependent test function and estimate its variance using a matrix-averaging operator. Combined with the depth bound of Czumaj and Lingas, the mixing estimate gives public switching networks with at most 2nlog n+O(n) switches and O(log n) depth for fixed error and failure probabilities. The author obtained this result through interaction with GPT-6 Astra.
ER -