Zongchen Chen, Massachusetts Institute of Technology

Abstract

Spin systems, also known as undirected graphical models, are important tools for modeling joint distributions of discrete random variables. We study the single-site update Markov chain known as the Glauber dynamics or Gibbs sampling for generating samples from the equilibrium distribution of the model (called the Gibbs distribution). In each step, the dynamics picks a single variable uniformly at random and updates it conditional on all other variables. We prove optimal mixing time bounds of the Glauber dynamics in a variety of settings, including hardcore model (weighted independent sets), Ising model, proper colorings, and monomer-dimer model (weighted matchings). To establish our results, we utilize and improve the spectral independence approach of Anari, Liu, and Oveis Gharan (2020) and show optimal mixing time of the Glauber dynamics on bounded-degree graphs when the maximum eigenvalues of associated influence matrices are bounded.

[Video]