Presented on October 2, 2017 at 11:00 a.m. in the Klaus Advanced Computing Building, room 1116E.
As for Swendsen--Wang, comparison estimates due to Ullrich @cite_2 @cite_39 imply that its inverse gap is at most that of Glauber dynamics on any graph and at any temperature (see Theorem ); thus for @math on @math it also has @math for all @math and for all @math thanks to duality, and similarly at @math it has @math .
@cite_39 @cite_2
1980404829 1982190141 2126692288 2963060913
We prove comparison results for the Swendsen-Wang (SW) dynamics, the heat-bath (HB) dynamics for the Potts model and the single-bond (SB) dynamics for the random-cluster model on arbitrary graphs. In particular, we prove that rapid mixing of HB implies rapid mixing of SW on graphs with bounded maximum degree and that rapid mixing of SW and rapid mixing of SB are equivalent. Additionally, the spectral gap of SW and SB on planar graphs is bounded from above and from below by the spectral gap of these dynamics on the corresponding dual graph with suitably changed temperature. As a consequence we obtain rapid mixing of the Swendsen-Wang dynamics for the Potts model on the two-dimensional square lattice at all non-critical temperatures as well as rapid mixing for the two-dimensional Ising model at all temperatures. Furthermore, we obtain new results for general graphs at high or low enough temperatures. We prove that the spectral gap of the Swendsen-Wang process for the Potts model on graphs with bounded degree is bounded from below by some constant times the spectral gap of any single-spin dynamics. This implies rapid mixing for the two-dimensional Potts model at all temperatures above the critical one, as well as rapid mixing at the critical temperature for the Ising model. After this we introduce a modified version of the Swendsen-Wang algorithm for planar graphs and prove rapid mixing for the two-dimensional Potts models at all non-critical temperatures. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 520–535, 2013 Studies two widely used algorithms, Glauber dynamics and the Swendsen-Wang (1987) algorithm, on rectangular subsets of the hypercubic lattice Z sup d . We prove that, under certain circumstances, the mixing time in a box of side length L with periodic boundary conditions can be exponential in L sup d-1 . In other words, under these circumstances, the mixing in these widely used algorithms is not rapid; instead it is torpid. The models we study are the independent set model and the q-state Potts model. For both models, we prove that Glauber dynamics is torpid in the region with phase coexistence. For the Potts model, we prove that the Swendsen-Wang mixing is torpid at the phase transition point. We show for the first time that the mixing time of Glauber (single edge update) dynamics for the random cluster model at q = 2 is bounded by a polynomial in the size of the underlying graph. As a consequence, the Swendsen-Wang algorithm for the ferromagnetic Ising model at any temperature has the same polynomial mixing time bound.