Optimal mixing for two-state anti-ferromagnetic spin systems
Xiaoyu Chen, Weiming Feng, Yitong Yin, Xinyuan Zhang
Abstract
We prove an optimal lower bound for modified -Sobolev (MLS) constant of the Glauber dynamics for anti-ferromagnetic two-spin systems with n vertices in the tree uniqueness regime. Specifically, this optimal MLS bound holds for the following classes of two-spin systems in the tree uniqueness regime: (1) all strictly anti-ferromagnetic two-spin systems (where both edge parameters 1), which cover the hardcore models and the anti-ferromagnetic Ising models; (2) general antiferromagnetic two-spin systems on regular graphs. Consequently, an optimal mixing time holds for these anti-ferromagnetic two-spin systems when the uniqueness condition is satisfied. These MLS and mixing time bounds hold for any bounded or unbounded maximum degree, and the constant factors in the bounds depend only on the gap to the uniqueness threshold. We prove this by showing a boosting theorem for MLS constant for distributions satisfying certain spectral independence and marginal stability properties.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Cited by top-tier papers14
- Localization Schemes: A Framework for Proving Mixing Bounds for Markov Chains (extended abstract)Yuansi Chen, Ronen EldanFOCS 2022 · 42 citations
- Rapid Mixing at the Uniqueness ThresholdXiaoyu Chen, Zongchen Chen, Yitong Yin, Xinyuan ZhangSTOC 2025 · 15 citations
- Universality of Spectral Independence with Applications to Fast Mixing in Spin GlassesNima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham et al.SODA 2024 · 9 citations
- Towards derandomising Markov chain Monte CarloWeiming Feng, Heng Guo, Chunyang Wang, Jiaheng Wang et al.FOCS 2023 · 5 citations
- Fast Sampling of b-Matchings and b-Edge CoversZongchen Chen, Yuzhou GuSODA 2024 · 5 citations
Builds on9
- Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore ModelNima Anari, Kuikui Liu, Shayan Oveis GharanFOCS 2020 · 97 citations
- Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansionZongchen Chen, Kuikui Liu, Eric VigodaSTOC 2021 · 61 citations
- Localization Schemes: A Framework for Proving Mixing Bounds for Markov Chains (extended abstract)Yuansi Chen, Ronen EldanFOCS 2022 · 42 citations
- On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy FactorizationAntonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Parisi et al.SODA 2022 · 41 citations
- Rapid Mixing of Glauber Dynamics up to Uniqueness via ContractionZongchen Chen, Kuikui Liu, Eric VigodaFOCS 2020 · 38 citations
Related papers
- Rapid mixing of Glauber dynamics via spectral independence for all degreesXiaoyu Chen, Weiming Feng, Yitong Yin, Xinyuan ZhangFOCS 2021 · 16 citations
- Rapid Mixing on Random Regular Graphs beyond UniquenessXiaoyu Chen, Zejia Chen, Zongchen Chen, Yitong Yin et al.FOCS 2025 · 1 citation
- On sampling two spin models using the local connective constantCharilaos EfthymiouSODA 2026
- Rapid Mixing of Glauber Dynamics for Monotone Systems via Entropic IndependenceWeiming Feng, Minji YangSODA 2026
- Entropy decay in the Swendsen-Wang dynamics on ℤdAntonio Blanca, Pietro Caputo, Daniel Parisi, Alistair Sinclair et al.STOC 2021 · 12 citations
