Swendsen‐Wang dynamics for general graphs in the tree uniqueness region. Issue 2 (16th April 2019) - Blanca, Antonio; Chen, Zongchen; Vigoda, Eric
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.