Rapid mixing of Glauber dynamics via spectral independence for all degrees

Abstract

We prove an optimal $\Omega (n^{-1})$ lower bound on the spectral gap of Glauber dynamics for anti-ferromagnetic two-spin systems with $n$ vertices in the tree uniqueness regime. This spectral gap holds for all, including unbounded, maximum degree $\Delta$. Consequently, we have the following mixing time bounds for the models satisfying the uniqueness condition with a slack $\delta \in (0,1)$: $\bullet$ $C(\delta )n^2\log n$ mixing time for the hardcore model with fugacity $\lambda \le (1-\delta ){\lambda }_c(\Delta )=(1-\delta )\frac{(\Delta -1{)}^{\Delta -1}}{(\Delta -2{)}^{\Delta }}$; $\bullet$ $C(\delta )n^2$ mixing time for the Ising model with edge activity $\beta \in \left[\frac{\Delta -2+\delta }{\Delta -\delta },\frac{\Delta -\delta }{\Delta -2+\delta }\right]$; where the maximum degree $\Delta$ may depend on the number of vertices $n$, and $C(\delta )$ depends only on $\delta$. 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.

arXiv commentResolve formatting issues in v2