Planting and MCMC Sampling from the Potts model

Abstract

We consider the problem of sampling from the ferromagnetic $q$-state Potts model on the random $d$-regular graph with parameter ${\hat{I}}^2>0$. A key difficulty that arises in sampling from the model is the existence of a metastability window $(β_u,β_u')$ where the distribution has two competing modes, the so-called disordered and ordered phases, causing MCMC-based algorithms to be slow mixing from worst-case initialisations. To this end, Helmuth, Jenssen and Perkins designed a sampling algorithm that works for all ${\hat{I}}^2$ when $q$ is large, using cluster expansion methods; more recently, their analysis technique has been adapted to show that random-cluster dynamics mixes fast when initialised more judiciously. However, a bottleneck behind cluster-expansion arguments is that they inherently only work for large $q$, whereas it is widely conjectured that sampling is possible for all $q,d\ge 3$. The only result so far that applies to general $q,d\ge 3$ is by Blanca and Gheissari who showed that the random-cluster dynamics mixes fast for ${\hat{I}}^2<{\hat{I}}_u^2$. For ${\hat{I}}^2>{\hat{I}}_u^2$, certain correlation phenomena emerge because of the metastability which have been hard to handle, especially for small $q$ and $d$. Our main contribution is to perform a delicate analysis of the Potts distribution and the random-cluster dynamics that goes beyond the threshold ${\hat{I}}_u^2$. We use planting as the main tool in our proofs, and combine it with the analysis of random-cluster dynamics. We are thus able to show that the random-cluster dynamics initialised from all-out mixes fast for all integers $q,d\ge 3$ beyond the uniqueness threshold ${\hat{I}}_u^2$; our analysis works all the way up to the threshold $β_c\in (β_u,β_u')$ where the dominant mode switches from disordered to ordered. We also obtain an algorithm in the ordered regime ${\hat{I}}^2>{\hat{I}}_c^2$ that refines significantly the range of $q,d$.

Abstract shortened to meet arXiv requirements