License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.32
URN: urn:nbn:de:0030-drops-94365
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9436/
Blanca, Antonio ;
Chen, Zongchen ;
Vigoda, Eric
Swendsen-Wang Dynamics for General Graphs in the Tree Uniqueness Region
Abstract
The Swendsen-Wang dynamics is a popular algorithm for sampling from the Gibbs distribution for the ferromagnetic Ising model on a graph G=(V,E). The dynamics is a "global" Markov chain which is conjectured to converge to equilibrium in O(|V|^{1/4}) steps for any graph G at any (inverse) temperature beta. It was recently proved by Guo and Jerrum (2017) that the Swendsen-Wang dynamics has polynomial mixing time on any graph at all temperatures, yet there are few results providing o(|V|) upper bounds on its convergence time.
We prove fast convergence of the Swendsen-Wang dynamics on general graphs in the tree uniqueness region of the ferromagnetic Ising model. In particular, when beta < beta_c(d) where beta_c(d) denotes the uniqueness/non-uniqueness threshold on infinite d-regular trees, we prove that the relaxation time (i.e., the inverse spectral gap) of the Swendsen-Wang dynamics is Theta(1) on any graph of maximum degree d >= 3. Our proof utilizes a version of the Swendsen-Wang dynamics which only updates isolated vertices. We establish that this variant of the Swendsen-Wang dynamics has mixing time O(log{|V|}) and relaxation time Theta(1) on any graph of maximum degree d for all beta < beta_c(d). We believe that this Markov chain may be of independent interest, as it is a monotone Swendsen-Wang type chain. As part of our proofs, we provide modest extensions of the technology of Mossel and Sly (2013) for analyzing mixing times and of the censoring result of Peres and Winkler (2013). Both of these results are for the Glauber dynamics, and we extend them here to general monotone Markov chains. This class of dynamics includes for example the heat-bath block dynamics, for which we obtain new tight mixing time bounds.
BibTeX - Entry
@InProceedings{blanca_et_al:LIPIcs:2018:9436,
author = {Antonio Blanca and Zongchen Chen and Eric Vigoda},
title = {{Swendsen-Wang Dynamics for General Graphs in the Tree Uniqueness Region}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
pages = {32:1--32:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-085-9},
ISSN = {1868-8969},
year = {2018},
volume = {116},
editor = {Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9436},
URN = {urn:nbn:de:0030-drops-94365},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.32},
annote = {Keywords: Swendsen-Wang dynamics, mixing time, relaxation time, spatial mixing, censoring}
}
|
Keywords: |
|
Swendsen-Wang dynamics, mixing time, relaxation time, spatial mixing, censoring |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
13.08.2018 |
