Optimal mixing for two-state anti-ferromagnetic spin systems
Xiaoyu Chen, Weiming Feng, Yitong Yin, Xinyuan Zhang
摘要
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.
问问这篇 Paper
智能体会读完全文。
Lune 把这篇 Paper 索引到了每一个公式,引用它的顶会 Paper 也一样。你提问,回答直接引用原文。
引用它的顶会 Paper14
- Localization Schemes: A Framework for Proving Mixing Bounds for Markov Chains (extended abstract)Yuansi Chen, Ronen EldanFOCS 2022 · 被引用 42 次
- Rapid Mixing at the Uniqueness ThresholdXiaoyu Chen, Zongchen Chen, Yitong Yin, Xinyuan ZhangSTOC 2025 · 被引用 15 次
- Universality of Spectral Independence with Applications to Fast Mixing in Spin GlassesNima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham 等SODA 2024 · 被引用 9 次
- Towards derandomising Markov chain Monte CarloWeiming Feng, Heng Guo, Chunyang Wang, Jiaheng Wang 等FOCS 2023 · 被引用 5 次
- Fast Sampling of b-Matchings and b-Edge CoversZongchen Chen, Yuzhou GuSODA 2024 · 被引用 5 次
它引用的顶会 Paper9
- Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore ModelNima Anari, Kuikui Liu, Shayan Oveis GharanFOCS 2020 · 被引用 97 次
- Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansionZongchen Chen, Kuikui Liu, Eric VigodaSTOC 2021 · 被引用 61 次
- Localization Schemes: A Framework for Proving Mixing Bounds for Markov Chains (extended abstract)Yuansi Chen, Ronen EldanFOCS 2022 · 被引用 42 次
- On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy FactorizationAntonio Blanca, Pietro Caputo, Zongchen Chen, Daniel Parisi 等SODA 2022 · 被引用 41 次
- Rapid Mixing of Glauber Dynamics up to Uniqueness via ContractionZongchen Chen, Kuikui Liu, Eric VigodaFOCS 2020 · 被引用 38 次
相关 Paper
- Rapid mixing of Glauber dynamics via spectral independence for all degreesXiaoyu Chen, Weiming Feng, Yitong Yin, Xinyuan ZhangFOCS 2021 · 被引用 16 次
- Rapid Mixing on Random Regular Graphs beyond UniquenessXiaoyu Chen, Zejia Chen, Zongchen Chen, Yitong Yin 等FOCS 2025 · 被引用 1 次
- 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 等STOC 2021 · 被引用 12 次
