Lune

FOCS2021顶会

Rapid mixing of Glauber dynamics via spectral independence for all degrees

Xiaoyu Chen, Weiming Feng, Yitong Yin, Xinyuan Zhang

2021年份
16被引次数
17顶会引用

摘要

We prove an optimalΩ(n−1)\Omega(n^{-1})lower bound on the spectral gap of Glauber dynamics for anti-ferromagnetic two-spin systems withnnvertices in the tree uniqueness regime. This spectral gap holds for any, including unbounded, maximum degree Δ. Consequently, we have the following mixing time bounds for the models satisfying the uniqueness condition with a slackδ∈(0,1)\delta\in(0,1): •C(δ)n2log⁡nC(\delta)n^{2}\log nmixing time for the hardcore model with fugacity≤(1−δ)λc(Δ)=(1−δ)(Δ−1)Δ−1(Δ−2)Δ\leq(1-\delta)\lambda_{c}(\Delta)=(1-\delta)\frac{(\Delta-1)^{\Delta-1}}{(\Delta-2)^{\Delta}}; •C(δ)n2C(\delta)n^{2}mixing time for the Ising model with edge activityβ∈[Δ−2+δΔ−δ,Δ−δΔ−2+δ]\beta\in[\frac{\Delta-2+\delta}{\Delta-\delta},\frac{\Delta-\delta}{\Delta-2+\delta}]; where the maximum degree Δ may depend on the number of vertices n, and C(δ) depends only on δ. Our proof is built upon the recently developed connections between the Glauber dynamics for spin systems and the high-dimensional expander walks. In particular, we prove a stronger notion of spectral independence, called the complete spectral independence, and use a novel Markov chain called the field dynamics to connect this stronger spectral independence to the rapid mixing of Glauber dynamics for all degrees.

问问这篇 Paper

智能体会读完全文。

Lune 把这篇 Paper 索引到了每一个公式,引用它的顶会 Paper 也一样。你提问,回答直接引用原文。

可以从这些问题问起

智能体调用

Luneget_paper_fulltext

在 Lune 里问

免费开始,无需绑卡

引用它的顶会 Paper17

问问它们各自怎么用它

它引用的顶会 Paper8

相关 Paper

黄昏的海面,两侧是细线勾勒的悬崖