Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields

Weiming Feng; Heng Guo; Jiaheng Wang

doi:10.1016/j.ic.2023.105066

Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields  

Weiming Feng, Heng Guo, Jiaheng Wang^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

Abstract / Description of output

We study the sampling problem for the ferromagnetic Ising model with consistent external fields, and in particular, Swendsen-Wang dynamics on this model. We introduce a new grand model unifying two closely related models: the subgraph world and the random cluster model. Through this new viewpoint, we show:

(1) polynomial mixing time bounds for Swendsen-Wang dynamics and (edge-flipping) Glauber dynamics of the random cluster model, generalising the bounds and simplifying the proofs for the no-fieldcase by Guo and Jerrum (2018);

(2) near linear mixing time for the two dynamics above if the maximum degree is bounded and all fields are (consistent and) bounded away from 1.

Original language	English
Article number	105066
Pages (from-to)	1-34
Journal	Information and Computation
Volume	294
Early online date	3 Jul 2023
DOIs	https://doi.org/10.1016/j.ic.2023.105066
Publication status	Published - 12 Jul 2023

Keywords / Materials (for Non-textual outputs)

Ising model
random cluster model
Markov chain
mixing time
Swendsen-Wang dynamics
holographic transformation

Access to Document

10.1016/j.ic.2023.105066Licence: Creative Commons: Attribution (CC-BY)

Swensden-Wang_FENG_DOA27062023_VOR_CC BYFinal published version, 787 KBLicence: Creative Commons: Attribution (CC-BY)

https://www.sciencedirect.com/science/article/pii/S089054012300069XLicence: Creative Commons: Attribution (CC-BY)

New Approaches to Counting and Sampling
Guo, H.
EU government bodies
1/01/21 → 31/12/25
Project: Research

Cite this

@article{269041d8759b4c49a3f74c62eb5b4ca9,

title = "Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields  ",

abstract = "We study the sampling problem for the ferromagnetic Ising model with consistent external fields, and in particular, Swendsen-Wang dynamics on this model. We introduce a new grand model unifying two closely related models: the subgraph world and the random cluster model. Through this new viewpoint, we show:(1) polynomial mixing time bounds for Swendsen-Wang dynamics and (edge-flipping) Glauber dynamics of the random cluster model, generalising the bounds and simplifying the proofs for the no-fieldcase by Guo and Jerrum (2018);(2) near linear mixing time for the two dynamics above if the maximum degree is bounded and all fields are (consistent and) bounded away from 1.",

keywords = "Ising model, random cluster model, Markov chain, mixing time, Swendsen-Wang dynamics, holographic transformation",

author = "Weiming Feng and Heng Guo and Jiaheng Wang",

note = "Funding Information: We thank Mary Cryan for bringing this question to our attention and for some preliminary discussion. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 947778 ). Publisher Copyright: {\textcopyright} 2023 The Author(s)",

year = "2023",

month = jul,

day = "12",

doi = "10.1016/j.ic.2023.105066",

language = "English",

volume = "294",

pages = "1--34",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier",

}

TY - JOUR

T1 - Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields  

AU - Feng, Weiming

AU - Guo, Heng

AU - Wang, Jiaheng

N1 - Funding Information: We thank Mary Cryan for bringing this question to our attention and for some preliminary discussion. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 947778 ). Publisher Copyright: © 2023 The Author(s)

PY - 2023/7/12

Y1 - 2023/7/12

N2 - We study the sampling problem for the ferromagnetic Ising model with consistent external fields, and in particular, Swendsen-Wang dynamics on this model. We introduce a new grand model unifying two closely related models: the subgraph world and the random cluster model. Through this new viewpoint, we show:(1) polynomial mixing time bounds for Swendsen-Wang dynamics and (edge-flipping) Glauber dynamics of the random cluster model, generalising the bounds and simplifying the proofs for the no-fieldcase by Guo and Jerrum (2018);(2) near linear mixing time for the two dynamics above if the maximum degree is bounded and all fields are (consistent and) bounded away from 1.

AB - We study the sampling problem for the ferromagnetic Ising model with consistent external fields, and in particular, Swendsen-Wang dynamics on this model. We introduce a new grand model unifying two closely related models: the subgraph world and the random cluster model. Through this new viewpoint, we show:(1) polynomial mixing time bounds for Swendsen-Wang dynamics and (edge-flipping) Glauber dynamics of the random cluster model, generalising the bounds and simplifying the proofs for the no-fieldcase by Guo and Jerrum (2018);(2) near linear mixing time for the two dynamics above if the maximum degree is bounded and all fields are (consistent and) bounded away from 1.

KW - Ising model

KW - random cluster model

KW - Markov chain

KW - mixing time

KW - Swendsen-Wang dynamics

KW - holographic transformation

U2 - 10.1016/j.ic.2023.105066

DO - 10.1016/j.ic.2023.105066

M3 - Article

SN - 0890-5401

VL - 294

SP - 1

EP - 34

JO - Information and Computation

JF - Information and Computation

M1 - 105066

ER -

Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields

Abstract / Description of output

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Projects

New Approaches to Counting and Sampling

Cite this

Swendsen-Wang dynamics for the ferromagnetic Ising model with external fields  