Torpid Mixing of Some Monte Carlo Markov Chain Algorithms in Statistical Physics

We study two widely used algorithms, Glauber dynamics and the Swendsen-Wang algorithm, on rectangular subsets of the hypercubic lattice Z 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 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 Swendsen-Wang is torpid at the phase transition point.