Rapid mixing of Glauber dynamics via spectral independence for all degrees
Xiaoyu Chen, Weiming Feng, Yitong Yin, Xinyuan Zhang
摘要
We prove an optimallower bound on the spectral gap of Glauber dynamics for anti-ferromagnetic two-spin systems withvertices in the tree uniqueness regime. This spectral gap holds for any, including unbounded, maximum degree Δ. Consequently, we have the following mixing time bounds for the models satisfying the uniqueness condition with a slack: •mixing time for the hardcore model with fugacity; •mixing time for the Ising model with edge activity; where the maximum degree Δ may depend on the number of vertices n, and C(δ) depends only on δ. Our proof is built upon the recently developed connections between the Glauber dynamics for spin systems and the high-dimensional expander walks. In particular, we prove a stronger notion of spectral independence, called the complete spectral independence, and use a novel Markov chain called the field dynamics to connect this stronger spectral independence to the rapid mixing of Glauber dynamics for all degrees.
问问这篇 Paper
智能体会读完全文。
Lune 把这篇 Paper 索引到了每一个公式,引用它的顶会 Paper 也一样。你提问,回答直接引用原文。
引用它的顶会 Paper17
- 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 次
- Entropic independence: optimal mixing of down-up random walksNima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham 等STOC 2022 · 被引用 21 次
- Optimal mixing for two-state anti-ferromagnetic spin systemsXiaoyu Chen, Weiming Feng, Yitong Yin, Xinyuan ZhangFOCS 2022 · 被引用 15 次
- Rapid Mixing at the Uniqueness ThresholdXiaoyu Chen, Zongchen Chen, Yitong Yin, Xinyuan ZhangSTOC 2025 · 被引用 15 次
它引用的顶会 Paper8
- 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 次
- 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 次
- Rapid Mixing for Colorings via Spectral IndependenceZongchen Chen, Andreas Galanis, Daniel Stefankovic, Eric VigodaSODA 2021 · 被引用 37 次
相关 Paper
- 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
- Rapid Mixing on Random Regular Graphs beyond UniquenessXiaoyu Chen, Zejia Chen, Zongchen Chen, Yitong Yin 等FOCS 2025 · 被引用 1 次
- Fast Sampling of b-Matchings and b-Edge CoversZongchen Chen, Yuzhou GuSODA 2024 · 被引用 5 次
- Flip Dynamics for Sampling Colorings: Improving (11/6 - ε) Using A Simple MetricCharlie Carlson, Eric VigodaSODA 2025 · 被引用 2 次
