Torpid mixing of some Monte Carlo Markov chain algorithms in statistical physics

Abstract

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.