论文标题
GLAUBER动力学的最佳混合：通过高维膨胀的熵分解
Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion
论文作者
论文摘要
我们证明了在单点更新链上绑定的最佳混合时间，即在各种设置中被称为Glauber Dynamics或Gibbs采样。我们的工作提出了Anari等人的光谱独立方法的改进版本。 （2020）并显示$ o（n \ log {n}）$混合时间在任何$ n $ vertex图上的限制性影响时的最大特征值矩阵的最大特征值时。作为我们结果的应用，对于独立集合的硬核模型，由逃逸性$λ$加权，我们建立了$ o（n \ log {n}）$混合时间在任何$ n $ vertex上的glauber动态时间的恒定最大度$δ$的$λ_c（Δ）$/λ_c（δ）$λ_-cotementique（δ）$λ_-uny nes the undemique（δ） $δ$ - 型树。更一般而言，对于任何反铁磁2旋转系统，我们证明$ o（n \ log {n}）$在相应的树独特区域中的任何有限度图上混合Glauber动力学的时间。我们的结果更广泛地适用；例如，我们还获得$ o（n \ log {n}）$混合，以$ q $ - 最高$δ$的三角形图的颜色，当颜色的数量满足$ q>αδ$，其中$αΔ$其中$α\ y $α\约1.763 $，大约1.763 $，以及$ o（m \ log {n}）$ coding $ $ $ $ y $ $ y ground y ground y y y dragend ytraged ndraged n arted and yraged and dougned and y Mor的$ M.M.M.M.
We prove an optimal mixing time bound on the single-site update Markov chain known as the Glauber dynamics or Gibbs sampling in a variety of settings. Our work presents an improved version of the spectral independence approach of Anari et al. (2020) and shows $O(n\log{n})$ mixing time on any $n$-vertex graph of bounded degree when the maximum eigenvalue of an associated influence matrix is bounded. As an application of our results, for the hard-core model on independent sets weighted by a fugacity $λ$, we establish $O(n\log{n})$ mixing time for the Glauber dynamics on any $n$-vertex graph of constant maximum degree $Δ$ when $λ<λ_c(Δ)$ where $λ_c(Δ)$ is the critical point for the uniqueness/non-uniqueness phase transition on the $Δ$-regular tree. More generally, for any antiferromagnetic 2-spin system we prove $O(n\log{n})$ mixing time of the Glauber dynamics on any bounded degree graph in the corresponding tree uniqueness region. Our results apply more broadly; for example, we also obtain $O(n\log{n})$ mixing for $q$-colorings of triangle-free graphs of maximum degree $Δ$ when the number of colors satisfies $q > αΔ$ where $α\approx 1.763$, and $O(m\log{n})$ mixing for generating random matchings of any graph with bounded degree and $m$ edges.
