Rapid Mixing of Glauber Dynamics for Monotone Systems via Entropic Independence
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911057606344704 |
|---|---|
| author | Feng, Weiming Yang, Minji |
| author_facet | Feng, Weiming Yang, Minji |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_11031 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Rapid Mixing of Glauber Dynamics for Monotone Systems via Entropic Independence Feng, Weiming Yang, Minji Discrete Mathematics Data Structures and Algorithms Mathematical Physics Probability 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. |
| title | Rapid Mixing of Glauber Dynamics for Monotone Systems via Entropic Independence |
| topic | Discrete Mathematics Data Structures and Algorithms Mathematical Physics Probability |
| url | https://arxiv.org/abs/2507.11031 |