License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.43
URN: urn:nbn:de:0030-drops-147366
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14736/
Blanca, Antonio ;
Chen, Zongchen ;
Štefankovič, Daniel ;
Vigoda, Eric
The Swendsen-Wang Dynamics on Trees
Abstract
The Swendsen-Wang algorithm is a sophisticated, widely-used Markov chain for sampling from the Gibbs distribution for the ferromagnetic Ising and Potts models. This chain has proved difficult to analyze, due in part to the global nature of its updates. We present optimal bounds on the convergence rate of the Swendsen-Wang algorithm for the complete d-ary tree. Our bounds extend to the non-uniqueness region and apply to all boundary conditions. We show that the spatial mixing conditions known as Variance Mixing and Entropy Mixing, introduced in the study of local Markov chains by Martinelli et al. (2003), imply Ω(1) spectral gap and O(log n) mixing time, respectively, for the Swendsen-Wang dynamics on the d-ary tree. We also show that these bounds are asymptotically optimal. As a consequence, we establish Θ(log n) mixing for the Swendsen-Wang dynamics for all boundary conditions throughout the tree uniqueness region; in fact, our bounds hold beyond the uniqueness threshold for the Ising model, and for the q-state Potts model when q is small with respect to d. Our proofs feature a novel spectral view of the Variance Mixing condition inspired by several recent rapid mixing results on high-dimensional expanders and utilize recent work on block factorization of entropy under spatial mixing conditions.
BibTeX - Entry
@InProceedings{blanca_et_al:LIPIcs.APPROX/RANDOM.2021.43,
author = {Blanca, Antonio and Chen, Zongchen and \v{S}tefankovi\v{c}, Daniel and Vigoda, Eric},
title = {{The Swendsen-Wang Dynamics on Trees}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
pages = {43:1--43:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-207-5},
ISSN = {1868-8969},
year = {2021},
volume = {207},
editor = {Wootters, Mary and Sanit\`{a}, Laura},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14736},
URN = {urn:nbn:de:0030-drops-147366},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.43},
annote = {Keywords: Markov Chains, mixing times, Ising and Potts models, Swendsen-Wang dynamics, trees}
}
|
Keywords: |
|
Markov Chains, mixing times, Ising and Potts models, Swendsen-Wang dynamics, trees |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
15.09.2021 |
