UBC Probability Seminar: Zongchen Chen

We consider the Glauber dynamics (also called Gibbs sampling) for sampling from a discrete high-dimensional space, where in each step one variable is chosen uniformly at random and gets updated conditional on all other variables. We show an optimal mixing time bound for the Glauber dynamics in a variety of settings. Our work presents 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 of entropy tensorization/factorization and recent developments of high-dimensional expanders.

As an application of our results, for the hard-core model on independent sets weighted by a fugacity lambda, we establish O(nlogn) mixing time for the Glauber dynamics on any n-vertex graph of constant maximum degree D when lambda aD where a = 1.763…, and O(mlogn) mixing for generating random matchings of any graph with bounded degree and m edges. Based on joint work with Kuikui Liu and Eric Vigoda.