Lune

FOCS2021Top-tier venue

Rapid mixing of Glauber dynamics via spectral independence for all degrees

Xiaoyu Chen, Weiming Feng, Yitong Yin, Xinyuan Zhang

2021Year
16Citations
17Top-tier citations

Abstract

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.

Ask about this paper

Your agent reads all of it.

Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.

Questions to start from

Your agent calls

Luneget_paper_fulltext

Ask in Lune

Free to start. No credit card required.

lune papers fulltext dfe5d062-5eca-4270-9451-b87c1fbdd5e9

Cited by top-tier papers17

Ask how each one uses it

Builds on8

Related papers

Dusk over the sea between two cliffs drawn in fine vertical lines