Back to search

Georgia Institute of Technology

Optimal Mixing of Markov Chains for Spin Systems via Spectral Independence

Abstract

dc:description.abstract

Spin systems, or undirected graphical models, are important tools for modeling joint distributions of discrete random variables, and are broadly used in statistical physics, machine learning, and theoretical computer science. One of the most important computational tasks for spin systems is to generate random samples approximately from the equilibrium distribution of the model called the Gibbs distribution. We study the single-site update Markov chain known as the Glauber dynamics or Gibbs sampling for sampling from the Gibbs distribution. In each step, the dynamics picks a single variable uniformly at random and updates it conditional on all other variables. Despite its popularity, theoretical guarantees of the convergence rate of the Glauber dynamics are only known in a few special cases. We prove optimal mixing time of the Glauber dynamics in a variety of settings. As an application of our results, for the hardcore model (weighted independent sets) on any n-vertex graph of constant maximum degree, we establish O(n log n) mixing time of the Glauber dynamics when the fugacity (vertex weight) lies in the tree uniqueness region. For the Ising model, and more generally any antiferromagnetic 2-spin system, we prove O(n log n) mixing time of the Glauber dynamics on any bounded degree graph in the corresponding tree uniqueness region. Our results apply more broadly; for example, we also obtain O(n log n) mixing for q-colorings on graphs of maximum degree d when q>(11/6)d, and O(n log n) mixing for the monomer-dimer model (weighted matchings) and weighted partial even subgraphs (corresponding to the ferromagnetic Ising model with nonzero external fields) on any graph with bounded degrees. Our work presents an improved version of the spectral independence approach of Anari, Liu, and Oveis Gharan (2020) and shows optimal mixing time of the Glauber dynamics on bounded-degree graphs when the maximum eigenvalues of associated influence matrices are bounded.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Computer Science
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Chen, Zongchen
Advisor dc:contributor.advisor
  • Vigoda, Eric
Committee members dc:contributor.committeemember
  • Randall, Dana
  • ≈†tefankoviƒç, Daniel
  • Tetali, Prasad
  • Vempala, Santosh

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/65071

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Chen, Zongchen. Optimal Mixing of Markov Chains for Spin Systems via Spectral Independence. Doctoral thesis, Georgia Institute of Technology, 2021. http://hdl.handle.net/1853/65071