betaFeedback

WorksComputer Science

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

Abstract

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.

Paper details

vlnc:W_yaq2gdnp
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…