{"id":"arxiv/2611.03959","url":"https://arxiv.org/abs/2611.03959","tags":["cs.DM","math.PR"],"score":0,"title":"Mixing Time of the Random-Pair Monte Shuffle","domain":"cs.DM","source":"arxiv","authors":["Ilya Mironov"],"reviews":0,"subject":"cs.DM","summary":"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 $2n\\log 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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-02","reactions":{}}