Nayantara Bhatnagar and Dana Randall
Torpid Mixing of Simulated Tempering on the Potts Model

Abstract: Simulated tempering and swapping are two families of sampling algorithms in which a parameter corresponding to temperature is varied during the simulation. The hope is that we will be able to overcome bottlenecks that cause Glauber (local) dynamics to be prohibitively slow at low temperatures, due to the existence of bad cuts in the state space of configurations.
The Ising model, and its generalization the Potts model, are models from statistical physics for magnetism. Glauber dynamics and the Swendsen-Wang algorithm have been shown to be slowly mixing for the Potts model. On the other hand, it has been shown that the swapping and tempering algorithms allow efficient sampling at low temperatures for the mean-field Ising model. It is reasonable therefore to ask if swapping or tempering can speed up sampling for the Potts model.

In this paper, we show that in fact there are temperatures at which tempering (and hence swapping) for the 3-state ferromagnetic Potts model on the complete graph convereges slowly. Using this insight, we are able to define a variant of the swapping algorithm that samples efficiently from a class of bimodal distributions including the q-state Potts model on the complete graph.