Swendsen‐Wang dynamics for general graphs in the tree uniqueness region. Issue 2 (16th April 2019)

• Record Type: Journal Article
• Authors: Blanca, Antonio; Chen, Zongchen; Vigoda, Eric
• Is Part Of: Random structures & algorithms. Volume 56:Issue 2(2020)
• Page Start: 373
• Page End: 400
• Publication Date: 2019-04-16
• Subjects: censoring -- mixing time -- relaxation time -- spatial mixing -- Swendsen‐Wang dynamics; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20858
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : 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.