{"id":"arxiv/2611.19829","url":"https://arxiv.org/abs/2611.19829","tags":["cs.DS","math.PR"],"score":0,"title":"Optimal mixing of random-to-random shuffling on linear extensions","domain":"cs.DS","source":"arxiv","authors":["Haoran Wang"],"reviews":0,"subject":"cs.DS","summary":"Uniform sampling of linear extensions is a basic problem in randomized algorithms and the study of finite posets. We prove that the random-to-random shuffle of Ayyer, Schilling, and Thiéry mixes in $O(n\\log n+n\\log(1/\\varepsilon))$ steps on every $n$-element poset, establishing their conjectured mixing order. With constant-time order queries, this gives an $\\varepsilon$-approximate uniform sampler using $O(n^2(\\log n+\\log(1/\\varepsilon)))$ elementary operations after preprocessing. The proof establishes relative-entropy contraction by a factor $1-1/n$ for the promotion half-step.…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-15","reactions":{}}