MIT-Harvard-MSR Combinatorics Seminar: Optimal Mixing of Glauber Dynamics for Spin Systems via Spectral Independence

HARVARD-MIT COMBINATORICS

Speaker:

Zongchen Chen - MIT

Consider the Gibbs distribution of the hardcore model over all independent sets of a given graph, where the probability density of each independent set J is proportional to lambda^|J| where lambda is a parameter. We study the single-site update Markov chain known as the Glauber dynamics for generating independent sets from this distribution. In each step, the dynamics picks a vertex uniformly at random and updates its status (inside or outside the independent set) conditional on the status of all other vertices. We prove optimal (nearly linear) mixing time bounds of the Glauber dynamics on bounded-degree graphs when lambda < lambda_c, beyond which it is known the dynamics can be exponentially slow. To establish our
result, we utilize and improve the spectral independence approach of Anari, Liu, and Oveis Gharan (2020) and show optimal mixing time of the Glauber dynamics for spin systems when the maximum eigenvalues of
associated influence matrices are bounded.