We consider the Glauber dynamics (also called Gibbs sampling) for sampling from a high-dimensional discrete distribution; e.g., selecting a random proper coloring or independent set in a given graph, or sampling a “typical” state of a given statistical physics model like the Ising model. In each step, the Glauber dynamics chooses a variable uniformly at random and updates its value conditional on all other variables. We show an optimal mixing time bound for the Glauber dynamics in a variety of settings. As an application of our results, for the hard-core model on weighted independent sets, we establish O(nlogn) mixing time for the Glauber dynamics on any n-vertex graph of constant maximum degree when the parameter of the model lies in the tree uniqueness region. Our results apply more broadly to other models including antiferromagnetic 2-spin systems (e.g., Ising model), random colorings, and weighted matchings.

To establish our results, we present an improved version of the spectral independence approach of Anari et al. (2020) and shows O(nlogn) mixing time for graphical models/spin systems on any n-vertex graph of bounded degree when the maximum eigenvalue of an associated influence matrix is bounded. Our proof approach combines classic tools like entropy tensorization/factorization and recent developments of high-dimensional expanders.

Based on joint work with Kuikui Liu and Eric Vigoda.