Perfect sampling of $q$-spin systems on ${\mathbb{Z}}^2$ via weak spatial mixing

Abstract

We present a perfect marginal sampler of the unique Gibbs measure of a spin system on ${\mathbb{Z}}^2$. The algorithm is an adaptation of a previous “lazy depth-first” approach by the authors, but relaxes the requirement of strong spatial mixing to weak. Our result is a step towards methods of efficient sampling using only weak spatial mixing. The work exploits a classical result in statistical physics relating weak spatial mixing on ${\mathbb{Z}}^2$ to strong spatial mixing on squares. When the spin system exhibits weak spatial mixing, the run-time of our sampler is linear in the size of sample. Applications of note are the ferromagnetic Potts model at supercritical temperatures and the ferromagnetic Ising model with consistent non-zero external field at any non-zero temperature.