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.
| Original language | English |
|---|---|
| Pages (from-to) | 1292-1313 |
| Number of pages | 22 |
| Journal | Annals of Applied Probability |
| Volume | 28 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - 11 Apr 2018 |
Keywords / Materials (for Non-textual outputs)
- Random cluster
- Markov chains
- Ising model
- Swendsen-Wang dynamics
Fingerprint
Dive into the research topics of 'Random Cluster Dynamics for the Ising Model is Rapidly Mixing'. Together they form a unique fingerprint.Profiles
-
Heng Guo
- School of Informatics - Reader in Algorithms and Complexity
- Laboratory for Foundations of Computer Science - Lecturer in Algorithms and Complexity
- Foundations of Computation
Person: Academic: Research Active (Teaching)