跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.19829 · v1

Optimal mixing of random-to-random shuffling on linear extensions

首次提交 2026-11-15 14:17
版本更新 2026-11-15 14:17
雷达观测 2026-11-17 12:06
arXiv ↗PDF ↗

摘要

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(nlog⁡n+nlog⁡(1/ε))O(n\log n+n\log(1/\varepsilon)) steps on every nn-element poset, establishing their conjectured mixing order. With constant-time order queries, this gives an ε\varepsilon-approximate uniform sampler using O(n2(log⁡n+log⁡(1/ε)))O(n^2(\log n+\log(1/\varepsilon))) elementary operations after preprocessing. The proof establishes relative-entropy contraction by a factor 1−1/n1-1/n for the promotion half-step. Consequently, the uniform extended-promotion chain has the same mixing order. We represent complete promotion scans as reflected coordinate paths in the order polytope and prove that a convex potential with gradients in the same polytope has diagonal Hessian mass at most one along each path. Applying this estimate to an optimal transport potential yields a sharp entropy factorization for every finite-entropy input. Linearization also gives the spectral-gap lower bound (n+1)/n2(n+1)/n^2.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-15 14:17 · 最新观测版本

Optimal mixing of random-to-random shuffling on linear extensions

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(nlog⁡n+nlog⁡(1/ε))O(n\log n+n\log(1/\varepsilon)) steps on every nn-element poset, establishing their conjectured mixing order. With constant-time order queries, this gives an ε\varepsilon-approximate uniform sampler using O(n2(log⁡n+log⁡(1/ε)))O(n^2(\log n+\log(1/\varepsilon))) elementary operations after preprocessing. The proof establishes relative-entropy contraction by a factor 1−1/n1-1/n for the promotion half-step. Consequently, the uniform extended-promotion chain has the same mixing order. We represent complete promotion scans as reflected coordinate paths in the order polytope and prove that a convex potential with gradients in the same polytope has diagonal Hessian mass at most one along each path. Applying this estimate to an optimal transport potential yields a sharp entropy factorization for every finite-entropy input. Linearization also gives the spectral-gap lower bound (n+1)/n2(n+1)/n^2.

查看此版本解读 →查看此版本原文 ↗