Rapid Mixing of Glauber Dynamics for Monotone Systems via Entropic Independence

2025/07/15 by Weiming Feng, Feng, Weiming, Minji Yang +1
Computer Science · Physics and Astronomy · #Blind Source Separation Techniques #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Mathematical Physics (math-ph) #Probability (math.PR) #Quantum chaos and dynamical systems #Target Tracking and Data Fusion in Sensor Networks

paper · pdf · doi:10.48550/arxiv.2507.11031

openalex publication_date 2025/07/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the mixing time of Glauber dynamics on monotone systems. For monotone systems satisfying the entropic independence condition, we prove a new mixing time comparison result for Glauber dynamics. For concrete applications, we obtain O(n) mixing time for the random cluster model induced by the ferromagnetic Ising model with consistently biased external fields, and O(n²) mixing time for the bipartite hardcore model under the one-sided uniqueness condition, where n is the number of variables in corresponding models, improving the best known results in [Chen and Zhang, SODA'23] and [Chen, Liu, and Yin, FOCS'23], respectively. Our proof combines ideas from the stochastic dominance argument in the classical censoring inequality and the recently developed high-dimensional expanders. The key step in the proof is a novel comparison result between the Glauber dynamics and the field dynamics for monotone systems.

Citations

• Rapid Mixing at the Uniqueness Threshold
• Rapid Mixing via Coupling Independence for Spin Systems with Unbounded Degree
• Rapid mixing of global Markov chains via spectral independence: the unbounded degree case
• Uniqueness and Rapid Mixing in the Bipartite Hardcore Model
• On the tractability of sampling from the Potts model at low temperatures via random-cluster dynamics
• A Near-Linear Time Sampler for the Ising Model with External Field
• Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields
• Optimal mixing for two-state anti-ferromagnetic spin systems
• Localization Schemes: A Framework for Proving Mixing Bounds for Markov Chains
• Approximately counting independent sets in bipartite graphs via graph containers
• A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings
• Rapid mixing of Glauber dynamics via spectral independence for all degrees
• Sampling Colorings and Independent Sets of Random Regular Bipartite Graphs in the Non-Uniqueness Region
• Fractionally Log-Concave and Sector-Stable Polynomials: Counting Planar\n Matchings and More
• Spectral Independence in High-Dimensional Expanders and Applications to\n the Hardcore Model
• Counting independent sets in unbalanced bipartite graphs
• Swendsen-Wang Dynamics for General Graphs in the Tree Uniqueness Region
• Random cluster dynamics for the Ising model is rapidly mixing
• Can extra updates delay mixing?
• Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees
• Computational Transition at the Uniqueness Threshold

Related

• Rapid mixing of Glauber dynamics via spectral independence for all degrees
• Mixing times of Glauber dynamics via entropy methods
• Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion
• On the Mixing Time of Glauber Dynamics for the Hard-core and Related Models on G(n,d/n)
• Optimal Mixing Time for the Ising Model in the Uniqueness Regime