Random cluster dynamics for the Ising model is rapidly mixing

Heng Guo, Mark Jerrum

Type: Article

Publication Date: 2018-04-01

Citations: 28

DOI: https://doi.org/10.1214/17-aap1335

Abstract

We show that the mixing time of Glauber (single edge update) dynamics for the random cluster model at $q=2$ on an arbitrary $n$-vertex graph is bounded by a polynomial in $n$. As a consequence, the Swendsen–Wang algorithm for the ferromagnetic Ising model at any temperature also has a polynomial mixing time bound.

Locations

arXiv (Cornell University) - View - PDF
Edinburgh Research Explorer (University of Edinburgh) - View - PDF
Edinburgh Research Explorer (University of Edinburgh) - View - PDF
Queen Mary Research Online (Queen Mary University of London) - View - PDF
Project Euclid (Cornell University) - View - PDF
The Annals of Applied Probability - View

Similar Works

Action	Title	Year	Authors
+	Random cluster dynamics for the Ising model is rapidly mixing	2016	Heng Guo Mark Jerrum
+	Random cluster dynamics for the Ising model is rapidly mixing	2017	Heng Guo Mark Jerrum
+	Random cluster dynamics for the ising model is rapidly mixing	2017	Heng Guo Mark Jerrum
+	Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields	2022	Weiming Feng Heng Guo Jiaheng Wang
+	Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields	2023	Weiming Feng Heng Guo Jiaheng Wang
+	Mixing time for the Ising model: a uniform lower bound for all graphs	2009	Jian Ding Yuval Peres
+	Random-Cluster Dynamics in $\mathbb{Z}^2$	2015	Antonio Blanca Alistair Sinclair
+	Random-Cluster Dynamics in $\mathbb{Z}^2$	2015	Antonio Blanca Alistair Sinclair
+	A Near-Linear Time Sampler for the Ising Model with External Field	2022	Xiaoyu Chen Xinyuan Zhang
+	Swendsen-Wang Algorithm on the Mean-Field	2015	Andreas Galanis Eric Vigoda
+	Swendsen-Wang Algorithm on the Mean-Field Potts Model	2015	Andreas Galanis Daniel Štefankovič Eric Vigoda
+	Swendsen-Wang Algorithm on the Mean-Field Potts Model	2015	Andreas Galanis Daniel Štefankovič Eric Vigoda
+ PDF Chat	Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics	2023	Antonio Blanca Reza Gheissari
+	Swendsen-Wang Dynamics for General Graphs in the Tree Uniqueness Region	2018	Antonio Blanca Zongchen Chen Eric Vigoda
+ PDF Chat	The Worm Process for the Ising Model is Rapidly Mixing	2016	Andrea Collevecchio Timothy M. Garoni Timothy Hyndman Daniel Tokarev
+	Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics	2021	Antonio Blanca Reza Gheissari
+	Rapid Mixing of Gibbs Sampling on Graphs that are Sparse on Average	2007	Elchanan Mossel Allan Sly
+	On the tractability of sampling from the Potts model at low temperatures via Swendsen--Wang dynamics	2023	Antonio Blanca Reza Gheissari
+	Random-cluster dynamics in Z2	2016	Antonio Blanca Alistair Sinclair
+	Random-Cluster Dynamics in ℤ<sup>2</sup>	2015	Antonio Blanca Alistair Sinclair

Works That Cite This (27)

Action	Title	Year	Authors
+ PDF Chat	Dynamic Sampling from Graphical Models	2021	Weiming Feng Nisheeth K. Vishnoi Yitong Yin
+	Quasi‐polynomial mixing of critical two‐dimensional random cluster models	2019	Reza Gheissari Eyal Lubetzky
+ PDF Chat	Efficient sampling and counting algorithms for the Potts model on <i>ℤ</i><sup><i>d</i></sup> at all temperatures	2022	Christian Borgs Jennifer Chayes Tyler Helmuth Will Perkins Prasad Tetali
+ PDF Chat	Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs	2023	Tyler Helmuth Matthew Jenssen Will Perkins
+	Efficient sampling and counting algorithms for the Potts model on $\mathbb Z^d$ at all temperatures	2019	Christian Borgs Jennifer Chayes Tyler Helmuth Will Perkins Prasad Tetali
+ PDF Chat	Cutoff for the Swendsen–Wang dynamics on the lattice	2019	Danny Nam Allan Sly
+ PDF Chat	Perfect sampling from spatial mixing	2022	Weiming Feng Heng Guo Yitong Yin
+ PDF Chat	Algorithmic Pirogov–Sinai theory	2019	Tyler Helmuth Will Perkins Guus Regts
+	Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields	2023	Weiming Feng Heng Guo Jiaheng Wang
+ PDF Chat	Understanding population annealing Monte Carlo simulations	2021	Martin Weigel Lev Barash Lev Shchur Wolfhard Janke

Works Cited by This (20)

Action	Title	Year	Authors
+ PDF Chat	Random Even Graphs	2009	Geoffrey Grimmett Svante Janson
+	None	1999	Vivek Gore Mark Jerrum
+ PDF Chat	Approximating the partition function of the ferromagnetic Potts model	2012	Leslie Ann Goldberg Mark Jerrum
+ PDF Chat	Comparison Theorems for Reversible Markov Chains	1993	Persi Diaconis Laurent Saloff‐Coste
+ PDF Chat	Worm Algorithms for Classical Statistical Models	2001	Nikolay Prokof’ev Boris Svistunov
+	Generalization of the Fortuin-Kasteleyn-Swendsen-Wang representation and Monte Carlo algorithm	1988	Robert G. Edwards Alan D. Sokal
+	Polynomial-Time Approximation Algorithms for the Ising Model	1993	Mark Jerrum Alistair Sinclair
+	Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow	1992	Alistair Sinclair
+ PDF Chat	The random-cluster model on the complete graph	1996	B Bollobás Geoffrey Grimmett Svante Janson
+ PDF Chat	Geometric Bounds for Eigenvalues of Markov Chains	1991	Persi Diaconis Daniel W. Stroock