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 Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-15 Page: https://delphi.science/r/arxiv/2611.19829 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.…