Rapid Mixing of Glauber Dynamics for Monotone Systems via Entropic Independence
By: Weiming Feng, Minji Yang
Potential Business Impact:
Makes computer models learn faster and better.
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 $\tilde{O}(n)$ mixing time for the random cluster model induced by the ferromagnetic Ising model with consistently biased external fields, and $\tilde{O}(n^2)$ 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.
Similar Papers
Subexponential and Parameterized Mixing Times of Glauber Dynamics on Independent Sets
Data Structures and Algorithms
Finds patterns faster in complex networks.
Rapid Mixing on Random Regular Graphs beyond Uniqueness
Data Structures and Algorithms
Makes computers solve hard problems much faster.
On the Glivenko-Cantelli theorem for real-valued empirical functions of stationary $α$-mixing and $β$-mixing sequences
Statistics Theory
Makes math work even when data is linked.