# Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion

arXiv: https://arxiv.org/abs/2011.02075 · HTML: https://mlsanity.com/paper/2011.02075/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Nov 2020.

## Built on by (most cited first, 12 of 12)

- [Statistical Efficiency of Score Matching: The View from Isoperimetry](https://mlsanity.com/paper/2210.00726/) (2022)
- [Learning Hard-Constrained Models with One Sample](https://mlsanity.com/paper/2311.03332/) (2023)
- [From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization](https://mlsanity.com/paper/2102.05347/) (2021)
- [A Sublinear-Time Quantum Algorithm for Approximating Partition Functions](https://mlsanity.com/paper/2207.08643/) (2022)
- [Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling](https://mlsanity.com/paper/2207.09102/) (2022)
- [Estimating Ising Models in Total Variation Distance](https://mlsanity.com/paper/2511.21008/) (2025)
- [Approximating the total variation distance between spin systems](https://mlsanity.com/paper/2502.05437/) (2025)
- [Sampling and Identity-Testing Without Approximate Tensorization of Entropy](https://mlsanity.com/paper/2506.23456/) (2025)
- [On approximating the f-divergence between two Ising models](https://mlsanity.com/paper/2509.05016/) (2025)
- [Rapid mixing in positively weighted restricted Boltzmann machines](https://mlsanity.com/paper/2604.00963/) (2026)
- [On McDiarmid's Inequality under Dependence via Approximate Tensorization of Entropy](https://mlsanity.com/paper/2606.12720/) (2026)
- [Definition Grounding in Theory-Level Auto-formalization](https://mlsanity.com/paper/2610.19223/) (2026)

## Abstract (arXiv)

We prove an optimal mixing time bound on the single-site update Markov chain known as the Glauber dynamics or Gibbs sampling 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 on any n-vertex graph of bounded degree when the maximum eigenvalue of an associated influence matrix is bounded. As an application of our results, for the hard-core model on independent sets weighted by a fugacity λ, we establish O(nlogn) mixing time for the Glauber dynamics on any n-vertex graph of constant maximum degree Delta when λ<λc(Delta) where λc(Delta) is the critical point for the uniqueness/non-uniqueness phase transition on the Delta-regular tree. More generally, for any antiferromagnetic 2-spin system we prove O(nlogn) 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(nlogn) mixing for q-colorings of triangle-free graphs of maximum degree Delta when the number of colors satisfies q > α Delta where α ≈ 1.763, and O(mlogn) mixing for generating random matchings of any graph with bounded degree and m edges.