Planting and MCMC Sampling from the Potts Model

Our main contribution is to do a delicate analysis of the Potts distribution and the random-cluster dynamics that goes beyond the threshold ${\beta }_u$, using planting. Planting is a technique used in the analysis of random CSPs to capture how the space of solutions is correlated with the structure of the random instance, see [1, 15, 4] for some applications. In terms of sampling however, there is no recipe for converting planting methods to efficient sampling algorithms, and typically some extra sampling step is needed on top, see for example [2, 17] for such approaches; even so, the resulting sample usually has some accuracy limitation, i.e., the TV-distance from the target distribution cannot be made arbitrarily small (typically it is required to be at least an inverse polynomial in $n$). Here, we instead use planting as a means to obtain sharp estimates that are used in the analysis of random-cluster dynamics; we thus show fast convergence of the latter, yielding automatically strong sampling guarantees. A different sampling idea that uses planting in a somewhat related manner has recently been considered in [27], in the context of sampling from spherical spin glasses.

Using this planting framework, we give an algorithm to sample from the Potts distribution on the random $d$-regular graph $𝔾$ that covers the optimal range of “high temperatures” for all integers $q,d\ge 3$; as we will explain in more detail later the algorithm is running random-cluster dynamics for $O(n\log n)$ steps, initialised appropriately (from the “empty” configuration).

Our analysis framework also applies to the ordered regime $\beta >{\beta }_c$ where we improve significantly upon various restrictions from previous works [11, 16, 26, 19]. For example, [26, 22] applied when $q\ge d^{\mathrm{\Omega }(d)}$ (and $d\ge 5$), whereas the recent work by Carlson et al [11] (see also [16]) applied when $d\ge d_0$ and $q\ge d^c$ for some large constants $d_0,c$. Using planting, we obtain a sampling result for all $d\ge 3$ when $q$ is roughly larger than $d^5$. We show the following.

Our algorithms are based on a well-known edge representation of the Potts model, the random-cluster (RC) model, where configurations are edge subsets weighted by the number of edges present and the number of induced components. We run the random-cluster dynamics (the analogue of Glauber dynamics in this edge setting), starting from the empty set of edges in the disordered regime and the full set of edges in the ordered regime $\beta >{\beta }_c$. The reason for working in the RC representation is that, in contrast to the Potts model, the RC model enjoys certain monotonicity properties that facilitate tracking the evolution of Glauber dynamics. In the next Preliminaries section we define the RC model and the relevant random-cluster chain. We also give a more detailed overview of the phases of the Potts model, and how planting gives a handle for the disordered and ordered settings. Most of these parts are largely imported from [14, 20]. In Section 3, we convert the planting for Potts into suitable planting for the RC model, giving the analogue of the ordered and disordered phases in that setting. Then, we state the main contribution of this work which is establishing weak spatial mixing within the disordered and ordered phases (a notion that originated in [21]). Sections 4 and 5 give the technical core of our arguments.

Roughly, in the disordered regime (Section 4), the key ingredient is to show that the dynamics converges to a set of configurations that do not form large components. For , Blanca and Gheissari [9] accomplished this by a very careful random-graph revealing process coupled with the evolution of random-cluster dynamics. Using planting, we are able to capture precisely the correlation between the random graph and a sample from stationarity for , reducing the study of the component structure to showing that the planted random graph is subcritical. Using the monotonicity of the RC model, this implies that the RC dynamics initialised from the empty set (“all-out”) enjoys the same component structure as the stationary distribution (for exponentially many steps). Having this in place (Lemma 14), the rest of the proof is more streamlined after some small reworking of certain correlation decay estimates up to the ordered/disordered threshold ${\beta }_c$ (Lemma 15).

In the ordered regime (Section 5), the planted model is instead supercritical and a typical configuration has a “giant” component, whose presence complicates the arguments significantly. The goal now is roughly to show that bichromatic edges do not typically form large components; more precisely, the key ingredient is to show that every vertex $v$ is surrounded by close-by vertices (each at some distance ) that belong to the giant component, a so-called “wired” boundary. Planting here allows us to do a head-on analysis of the probability that, in a typical sample from stationarity, there exists a path of length $\mathrm{\ell }$ that does not include any vertex in the giant. We get a tight bound for this using careful first moment arguments and percolation bounds; then, for $q\ge {(5d)}^5$, a union bound over the paths starting at $v$ gives the existence of the desired wired boundary (in a typical configuration). Relative to the earlier works [26, 16, 11, 19], bichromatic components roughly correspond to so-called polymers; our techniques show that a smaller lower bound on the size of the giant component suffices in order to ensure that the polymers are not large.

The planting arguments that we use in this paper follow by careful first and second moment considerations in [20], which have been carried out for the ferromagnetic Potts model, see also [5] for similar-flavored “silent” planting results. The moment analysis has previously been used in [13] for sampling independent sets and proper colourings in random bipartite graphs, though there the approach ultimately relies on cluster-expansion type of arguments [29, 12]. Our more direct planting approach can be carried out for sampling independent sets on random bipartite graphs (that shares similar monotonicity and planting properties) and obtain sharper bounds for sampling using Glauber dynamics. Note however that, as pointed out in [13, Lemma 10], it is unlikely that current polymer-based techniques will achieve better asymptotic estimates in terms of the degree $d$. Our technique should also apply to the $G(n,d/n)$ setting (for arbitrary $q,d>1$) provided that the analogous “silent” planting is in place; this seems more easily feasible in the disordered regime but more difficult for the ordered regime where the Poisson-tree neighbourhoods are expected to cause bigger variance.

It is also relevant to note that the results we stated earlier for the cluster-expansion technique and fast mixing of the random-cluster dynamics in the literature apply to non-integer $q$, in the random-cluster representation. It is conceivable that a similar planting to the one we consider here for the Potts model can be carried out for non-integer $q$ in the random-cluster representation, though the related first and second moment computations will likely require careful arguments for the distribution of the number of components in random graph percolation; see [6] for some related developments.

To obtain a handle on the random $d$-regular $𝔾={𝔾}_{n,d}$, we work throughout in the configuration model. Formally, for integers $n,d\ge 1$ with $dn$ even, let $[n]\times [d]$ be a set of “half-edges”; we denote by $G\sim {𝒢}_{n,d}$ a (multi)graph on vertex set $[n]$ whose edges are obtained by taking a uniformly random perfect matching of the half-edges; we add an edge between $u,v\in [n]$ in $G$ whenever the half-edges $(u,i)$ and $(v,j)$ are matched together for some $i,j\in [d]$. For brevity, instead of $G\sim {𝒢}_{n,d}$ we sometimes use $𝑮$ to denote the random (multi)graph chosen. Any property that holds whp over $𝑮$ also holds whp over $𝔾$ (see, e.g., [28]), so henceforth we focus on the configuration model $𝑮$.

Given a graph $G=(V,E)$ and real parameters $q>0$ and $p\in [0,1]$, the random-cluster model is a probability distribution $\pi ={\pi }_{G,q,p}$ on the subsets of $E$. Let ${\mathrm{\Omega }}_G$ be the set of all configurations. Each configuration $F\subseteq E$ has probability $\pi (F)=q^{c(F)}{p}^{|F|}{(1-p)}^{|E\setminus F|}/Z_{RC,G}$ where $c(F)$ is the number of connected components in the graph $(V,F)$, and $Z_{RC,G}$ is a normalisation factor. For integer $q$ and $p=1-{\mathrm{e}}^{-\beta }$, it is well known that sampling from this probability distribution is equivalent to sampling from the $q$-state Potts model with parameter $\beta$, see Section 3 for details.

Let $\widehat{p}:=\frac{p}{(1-p)q+p}$. The random-cluster (RC) dynamics initialised from a configuration $X_0$ is a Markov chain ${(X_t)}_{t\ge 0}$ whose transition $X_t$ to $X_{t+1}$ is as follows:

1. 1.

   First choose an edge $e\in E$ uniformly at random.

2. 2.

   If $e$ is a cut edge of the graph $(V,X_t\cup \{e\})$, then with probability $\widehat{p}$, set $X_{t+1}:=X_t\cup \{e\}$. With all remaining probability set $X_{t+1}:=X_t\setminus \{e\}$

3. 3.

   Otherwise, with probability $p$, set $X_{t+1}:=X_t\cup \{e\}$. With all remaining probability set $X_{t+1}:=X_t\setminus \{e\}$.

It is a standard fact that the distribution of $X_t$ converges to ${\pi }_G$, regardless of the initialisation. To work around the slow convergence in the metastability window when $\beta \in ({\beta }_u,{\beta }_u^{\prime })$, we will later consider the RC dynamics starting from the two extreme configurations, the all-out ($X_0=\mathrm{\varnothing }$) and the all-in $(X_0=E)$.

Let $\nu =({\nu }_1,\mathrm{\dots },{\nu }_q)$ be a $q$-dimensional probability vector. For an $n$-vertex graph $G$, let

where $\theta =\theta (q,d,\beta )>0$ is a small constant which we will suppress from notation. Hence, $S_{\nu }(\theta )$ consists of these configurations where the colour frequencies are given by the vector $\nu$. Let also

where $w_G(\sigma )=e^{\beta m(\sigma )}$ is the weight of $\sigma$. In short, the function $\mathrm{\Psi }(\nu )$ captures the (logarithm of the) expected contribution to the partition function $Z(𝑮)$ of the random graph $𝑮$ given by the configurations in $S_{\nu }$. As we shall see shortly, the local/global maximisers of $\mathrm{\Psi }$ play a key role in determining the modes of the Gibbs distribution.

There are three relevant thresholds that come into play

For high temperatures (), there is a unique global maximiser of $\mathrm{\Psi }$, given by the uniform vector

which corresponds to the “disordered” configurations. As the temperature decreases and $\beta$ crosses the threshold ${\beta }_u$, another local maximum of $\mathrm{\Psi }$ emerges at an “ordered” vector ${\nu }_{\mathrm{o}}$ where one of the $q$ colours dominates over the others (which are roughly balanced). More precisely, ${\nu }_{\mathrm{o}}$ is given by¹¹1The value of ${\beta }_u$ is defined as the infinimum value of $\beta >0$ such that there exists $a\in (1/q,1)$ which satisfies (2.1); then it is simple to check that such an $a$ exists for all $\beta \ge {\beta }_u$. For certain values of $\beta$ (namely when $\beta \in ({\beta }_u,{\beta }_u^{\prime })$), there may be more than one values of $a\in (1/q,1)$ that satisfy the equation; when this is the case, the value of $a$ that is relevant for the ordered phase is the largest such value.

Interestingly, the local maximum at ${\nu }_{\mathrm{o}}$ does not become global until $\beta \ge {\beta }_c$ where ${\beta }_c=\ln \frac{q-2}{{(q-1)}^{1-2/d}-1}$ is known as the ordered/disordered threshold; notably, the only point where both ${\nu }_{\mathrm{o}}$ and ${\nu }_{\mathrm{d}}$ are global maxima is at $\beta ={\beta }_c$. Note also that ${\nu }_{\mathrm{d}}$ continues being a local maximum till where ${\beta }_u^{\prime }=\ln (1+\frac{q}{d-1})$; so, in the interval $({\beta }_u,{\beta }_u^{\prime })$ both ${\nu }_{\mathrm{d}}$ and ${\nu }_{\mathrm{o}}$ are local maxima of $\mathrm{\Psi }$ which causes the metastability phenomena mentioned in the introduction, see [14] for details.

For convenience, let $S_{\mathrm{d}}$ and $S_{\mathrm{o}}$ denote the sets of configurations $S_{\nu }$ when $\nu ={\nu }_{\mathrm{d}}$ and $\nu ={\nu }_{\mathrm{o}}$, respectively. For a graph $G$, define $Z_{\mathrm{d}}(G)$ and $Z_{\mathrm{o}}(G)$ analogously, and let ${\mu }_{G,\mathrm{d}}={\mu }_G(\cdot \mid S_{\mathrm{d}})$ and ${\mu }_{G,\mathrm{o}}={\mu }_G(\cdot \mid S_{\mathrm{o}})$ denoted the conditional Gibbs distributions. The following lemma from [20] gives some sharp concentration estimates for $Z_{\mathrm{d}}(𝑮)$ and $Z_{\mathrm{o}}(𝑮)$ (derived using moments and the small subgraph conditioning method) and are the key behind our planting approach.

We now introduce the planting distribution which will be the key in obtaining our results. Recall that $𝑮$ denotes a graph chosen according to the configuration model ${𝒢}_{n,d}$; in the expressions below, expectations are taken with respect to the choice of $𝑮$. For $\sigma \in {[q]}^n$, define a random graph $\widehat{𝑮}(\sigma )$ by letting

Furthermore, for $\theta >0$, recalling the disordered and ordered partition functions $Z_{\mathrm{d}},Z_{\mathrm{o}}$ from the previous section, we define random configurations ${\widehat{𝝈}}_{\mathrm{d}}={\widehat{𝝈}}_{\mathrm{d}}(\theta )\in {[q]}^n$ and ${\widehat{𝝈}}_{\mathrm{o}}={\widehat{𝝈}}_{\mathrm{o}}(\theta )\in {[q]}^n$ with distributions

We refer to $(\widehat{𝑮}({\widehat{𝝈}}_{\mathrm{d}}),{\widehat{𝝈}}_{\mathrm{d}})$ and $(\widehat{𝑮}({\widehat{𝝈}}_{\mathrm{o}}),{\widehat{𝝈}}_{\mathrm{o}})$ as the disordered and ordered planted distributions respectively.

The following lemma allows us to relate the planted distributions with the distributions of the (conditional) disordered ${𝝈}_{𝑮,\mathrm{d}}\sim {\mu }_{𝑮,\mathrm{d}}$ and ordered ${𝝈}_{𝑮,\mathrm{o}}\sim {\mu }_{𝑮,\mathrm{o}}$ configurations of the random graph $𝑮$. Recall that ${𝒢}_{n,d}$ denotes the set of all $n$-vertex regular (multi)graphs with degree $d$.

The proof is given in the full version [18]. To utilise Lemma 4, the key observation is that, for the planted models, once we condition on the vertex and edge statistics, the models become uniformly distributed. Formally, for a graph $G\in {𝒢}_{n,d}$ and a configuration $\sigma \in {[q]}^n$, let ${\nu }^{\sigma }$ be vertex colour statistics under $\sigma$, i.e.,

Similarly, let ${\rho }^{G,\sigma }$ be the $[q]\times [q]$ matrix with the following half-edge colour statistics under $\sigma$, i.e.,

Recall that $2|E(G)|=dn$. So, for a colour class $i\in [q]$, out of the $dn{\nu }_i^{\sigma }$ half-edges incident to it, there are $dn{\rho }_{ij}^{G,\sigma }$ “going” to a colour class $j\in [q]$ (note, for $i=j$, there are $\frac{dn}{2}{\rho }_{ii}^{G,\sigma }$ edges in $G$ that lie inside the colour class $i$). We have that ${\rho }^{G,\sigma }$ is symmetric with ${\sum }_{i,j}{\rho }_{ij}^{G,\sigma }=1$. Observe further that, conditioned on ${\nu }^{{\widehat{𝝈}}_{\mathrm{d}}}=\nu$ and ${\rho }^{\widehat{𝑮}({\widehat{𝝈}}_{\mathrm{d}}),{\widehat{𝝈}}_{\mathrm{d}}}=\rho$ the pair $(\widehat{𝑮}({\widehat{𝝈}}_{\mathrm{d}}),{\widehat{𝝈}}_{\mathrm{d}})$ is uniformly distributed over the pairs $(G,\sigma )\in {𝒢}_{n,d}\times {[q]}^n$ with ${\nu }^{\sigma }=\nu$ and ${\rho }^{G,\sigma }=\rho$. Similarly for the pair $(\widehat{𝑮}({\widehat{𝝈}}_{\mathrm{o}}),{\widehat{𝝈}}_{\mathrm{o}})$ conditioned on ${\nu }^{{\widehat{𝝈}}_{\mathrm{o}}}$ and ${\rho }^{\widehat{𝑮}({\widehat{𝝈}}_{\mathrm{o}}),{\widehat{𝝈}}_{\mathrm{o}}}$.

To put this observation into use, we will need more quantitative information on the vertex and edge colour statistics in the planted models. By definition of ${\widehat{𝝈}}_{\mathrm{d}},{\widehat{𝝈}}_{\mathrm{o}}$, we already know that ${\Vert {\nu }^{{\widehat{𝝈}}_{\mathrm{d}}}-{\nu }_{\mathrm{d}}\Vert }_1\le \theta$ and ${\Vert {\nu }^{{\widehat{𝝈}}_{\mathrm{o}}}-{\nu }_{\mathrm{o}}\Vert }_1\le \theta$. Analogously, ${\rho }^{\widehat{𝑮}({\widehat{𝝈}}_{\mathrm{d}}),{\widehat{𝝈}}_{\mathrm{d}}}$ and ${\rho }^{\widehat{𝑮}({\widehat{𝝈}}_{\mathrm{o}}),{\widehat{𝝈}}_{\mathrm{o}}}$ are concentrated around the vectors ${\rho }_{\mathrm{d}}$ and ${\rho }_{\mathrm{o}}$ where

We have the following concentration statement.

For a graph $G\in {𝒢}_{n,d}$ and $\sigma \in {[q]}^n$, let $𝑭(G,\sigma )$ denote the random subset of edges obtained by keeping each monochromatic edge of $G$ under $\sigma$ with probability $p$. It is a standard fact (see, e.g., [25]) that, for integer $q\ge 3$, we can obtain a sample $𝑭\sim {\pi }_G$ by first sampling $𝝈\sim {\mu }_G$ and then keeping each monochromatic edge of $G$ under $\sigma$ with probability $p=1-{\mathrm{e}}^{-\beta }$ (the so-called percolation step).

We use this for the random graph $𝑮$ to get a handle on the random cluster model on $𝑮$, i.e., $𝑭(𝑮,𝝈)$ has distribution ${\pi }_{𝑮}$. From Lemma 5, we can figure out in particular how many monochromatic edges we should expect from each phase, so we can translate the phases for the Potts model to the random cluster model. More precisely, set

With a bit of algebra, we can derive the following expressions for ${𝔪}_{\mathrm{d}}$ and ${𝔪}_{\mathrm{o}}$ from (2.5): for , we have ${𝔪}_{\mathrm{d}}(\beta )=\frac{d}{2}\frac{{\mathrm{e}}^{\beta }-1}{{\mathrm{e}}^{\beta }+q-1}$, while, for $\beta >{\beta }_u$, we have ${𝔪}_{\mathrm{o}}(\beta )=\frac{d}{2}\frac{({\mathrm{e}}^{\beta }-1)(x^2+\frac{{(1-x)}^2}{q-1})}{1+({\mathrm{e}}^{\beta }-1)(x^2+\frac{{(1-x)}^2}{q-1})}$ with $x=\frac{t^{d-1}}{t^{d-1}+q-1}$ and $t>1$ defined from ${\mathrm{e}}^{\beta }-1=\frac{(t-1)(t^{d-1}+q-1)}{t^{d-1}-t}$, as in (2.1).

We are now ready to define the ordered/disordered phases for the random-cluster model. Due to monotonicity properties (and in contrast to the phases of the Potts model), we can just use the values of ${𝔪}_{\mathrm{d}}$ and ${𝔪}_{\mathrm{o}}$ at the critical temperature $\beta ={\beta }_c$; this will be convenient later on.

Using the translation between the Potts and random-cluster models, we have the following.

Treading a path initiated in [21], to prove Theorems 1 and Theorem 2 it suffices to show the following results for the disordered and ordered regimes, respectively.