Premium
Swendsen‐Wang dynamics for general graphs in the tree uniqueness region
Author(s) -
Blanca Antonio,
Chen Zongchen,
Vigoda Eric
Publication year - 2020
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20858
Subject(s) - mathematics , spectral gap , monotone polygon , combinatorics , uniqueness , markov chain , expander graph , discrete mathematics , markov chain mixing time , graph , inverse , markov property , mathematical analysis , markov model , statistics , geometry
The Swendsen‐Wang (SW) dynamics is a popular Markov chain for sampling from the Gibbs distribution for the ferromagnetic Ising model on a graph G = ( V , E ). The dynamics is conjectured to converge to equilibrium in O (| V | 1/4 ) steps at any (inverse) temperature β , yet there are few results providing o (| V |) upper bounds. We prove fast convergence of the SW dynamics on general graphs in the tree uniqueness region. In particular, when β < β c ( d ) where β c ( d ) denotes the uniqueness/nonuniqueness threshold on infinite d ‐regular trees, we prove that the relaxation time (i.e., the inverse spectral gap) of the SW dynamics is Θ(1) on any graph of maximum degree d ≥ 3. Our proof utilizes a monotone version of the SW dynamics which only updates isolated vertices. We establish that this variant of the SW dynamics has mixing time O ( log | V | ) and relaxation time Θ(1) on any graph of maximum degree d for all β < β c ( d ). Our proof technology can be applied to general monotone Markov chains, including for example the heat‐bath block dynamics , for which we obtain new tight mixing time bounds.