Cutoff for the Swendsen–Wang Dynamics on the Complete Graph

The $q$-state ferromagnetic Potts model is a classical spin system model central in statistical physics, theoretical computer science, and discrete probability. Given a finite graph $G=(V,E)$, a set of spins or colors $𝒮=\{1,\mathrm{\dots },q\}$, and an edge interaction parameter $\beta >0$, it is defined as a probability distribution over the configurations in $\mathrm{\Omega }={\{1,\mathrm{\dots },q\}}^V$, which correspond to the spin assignments from $𝒮$ to the vertices of $G$. Formally, the probability of a configuration $\sigma \in \mathrm{\Omega }$ is given by:

where $M(\sigma )$ denotes the number of edges of $G$ with the same spin in both of its endpoints in $\sigma$ (i.e., the monochromatic edges of $G$ in $\sigma$), and $Z$ is the normalizing constant or partition function. The edge interaction parameter $\beta$ is proportional to the inverse temperature in physical applications; the $q=2$ case corresponds to the classical ferromagnetic Ising model.

The algorithmic problem of efficiently generating approximate samples from $\mu$ has attracted much attention in theoretical computer science. For the Ising model (i.e., for $q=2$), seminal results from the 1990s [30, 39] provide a polynomial-time approximate sampling algorithm for $\mu$. Additional approximate-sampling algorithms have been discovered since then for the ferromagnetic Ising setting [15, 24], but all have a large running time of at least $O(n^{10})$ where $n=|V|$. For $q\ge 3$, the sampling problem is computationally hard, specifically #BIS-hard [22, 20], but efficient approximate sampling algorithms are still possible for many interesting families of graphs; see [25, 29, 13, 12, 1].

An algorithm with the potential of providing both faster algorithms for the $q=2$ case and a technology for understanding the feasibility boundary of approximate sampling for $q\ge 3$ is the Swendsen–Wang (SW) dynamics [40]. This sophisticated Markov chain exploits the connection between the ferromagnetic Potts model and the random-cluster model [18] and was designed to bypass some of the key difficulties associated with sampling from $\mu$ at low temperatures (large $\beta$). In particular, the SW dynamics is conjectured to converge to $\mu$ in $O(n^{1/4})$ steps when $q=2$ on any graph $G$ for any $\beta >0$. This Markov chain was also recently used to the expand the graph families for which approximately sampling can be efficiently done for $q\ge 3$ and $\beta$ large [1].

The SW dynamics transitions from a configuration ${\sigma }_t\in \mathrm{\Omega }$ to ${\sigma }_{t+1}\in \mathrm{\Omega }$ as follows:

1. 1.

   Independently, for every $e=\{u,v\}\in E$ if ${\sigma }_t(u)={\sigma }_t(v)$ include $e$ in $M_t$ with probability $p=1-e^{-\beta }$;

2. 2.

   Independently, for every connected component $𝒞$ in $(V,M_t)$, draw a spin $s\in \{1,\mathrm{\dots },q\}$ uniformly at random, and set ${\sigma }_{t+1}(v)=s$ for all $v\in 𝒞$.

The SW dynamics is ergodic and reversible with respect to $\mu$ and thus converges to it [40, 18]. We refer to Step 1 as the percolation step and to Step 2 as the coloring step.

The SW dynamics is a highly non-local Markov chain, updating and potentially changing the spin of each vertex in each step, making its analysis quite difficult in most settings. Still, significant progress has been made in understanding the speed of convergence of this dynamics in various geometries, including the complete graph [16, 23, 34, 19, 21], finite subsets of the $d$-dimensional integer lattice graph ${\mathbb{Z}}^d$ [41, 9, 4, 38, 3], trees [27, 5], random graphs [7, 14, 8], locally-tree-like graphs [1], graphs with sub-exponential growth [1], graphs of bounded [6, 2] or unbounded degree [11], as well as general graphs when $q=2$ [24]. A setting that has attracted particular interest and that will be the focus of this work is the complete graph, also known as the mean-field model.

On the complete graph, it is natural to re-parametrize the model and use $\beta /n$ instead of $\beta$; i.e., $\mu (\sigma )\propto \exp (\frac{\beta }{n}\cdot M(\sigma ))$. A detailed connection between the phase transition of the mean-field model, which we describe in detail in Remark 2, and the mixing time of the SW dynamics emerged from [34, 19, 21]. The mixing time of a Markov chain is defined as the number of steps until the Markov chain is close in total variation distance to its stationary distribution starting from the worst possible initial configuration, and it is the most standard notion of speed of convergence to stationarity. Formally, if $P$ is the transition matrix of the chain, for $\epsilon \in (0,1)$,

and by convention ${\tau }_{\mathrm{mix}}:={\tau }_{\mathrm{mix}}(1/4)$.

When $q\ge 3$, the mixing time ${\tau }_{\mathrm{mix}}^{\mathrm{SW}}$ of the SW dynamics satisfies:

see [19, 21]. It is known that ${\beta }_{\text{r}}=q$, but ${\beta }_{\text{l}}$ does not have a closed form, and it is given instead implicitly as the root of a certain equation [19, 37]. When $q=2$, ${\beta }_{\text{l}}={\beta }_{\text{r}}=q$ and there is no slow-mixing window, and the mixing time of the mean-field SW dynamics for $q=2$ is $\mathrm{\Theta }(1)$ for , $\mathrm{\Theta }(n^{1/4})$ at the critical point $\beta =q$, and $\mathrm{\Theta }(\log n)$ for $\beta >q$ [34].

In this work, we provide sharper results for the mixing time of the mean-field SW dynamics in the $\beta >{\beta }_{\text{r}}=q$ regime, further refining our understanding of this dynamics. We show that there exists a constant $c(\beta ,q)>0$ such that ${\tau }_{\mathrm{mix}}^{\mathrm{SW}}=c(\beta ,q)\log n+\mathrm{\Theta }(1)$, which implies that this Markov chain exhibits cutoff. A Markov chain exhibits cutoff if there is a sharp drop in the total variation distance from close to $1$ to close $0$ in an interval of time of smaller order than ${\tau }_{\mathrm{mix}}$ which is called the cutoff window; i.e., we say that there is cutoff if as $n\to \mathrm{\infty }$, for any fixed $\epsilon \in (0,1)$,

We can now state our main result.

We provide the expression for the constant $c(\beta ,q)$ in (4).

The only previously known mixing time cutoff result for the SW dynamics was on the integer lattice graph for sufficiently small enough $\beta$ [38]; ours is the first such result in the low-temperature SW dynamics. For the local Glauber dynamics, which updates a single randomly chosen vertex in each step, cutoff is known in the mean-field through the high-temperature regime [32, 17]. For the special case of the Ising model, cutoff has also been established for the Glauber dynamics for several graph families; see [35, 36, 31, 42].

Recall from (2) that the mixing time of the SW dynamics is $\mathrm{\Theta }(1)$ when and exponentially slow when $\beta \in ({\beta }_{\text{l}},{\beta }_{\text{r}})$, so the question of whether the chain exhibits cutoff is of limited significance in those parameter regimes. It is an interesting open question, however, whether the SW dynamics exhibits cutoff at the dynamical critical points $\beta ={\beta }_{\text{l}}$ or $\beta ={\beta }_{\text{r}}$. In the former, mixing is not entirely governed by a “strong drift” towards a typical spin count distribution and relies on the variance of the dynamics as well; as such, it is unlikely that the dynamics exhibits cutoff at $\beta ={\beta }_{\text{l}}$. For $\beta ={\beta }_{\text{r}}$, the SW dynamics exhibits a first-order drift towards typical configurations, but the percolation step is critical, which significantly complicates even the asymptotic mixing time analysis.

From an algorithmic perspective, for a Markov chain like the SW dynamics that exhibits cutoff at $c(\beta ,q)\log n$, knowing only the asymptotic mixing time, e.g., that ${\tau }_{\mathrm{mix}}^{\mathrm{SW}}=\mathrm{\Theta }(\log n)$, is insufficient in practice, since simulating the dynamics for say $\frac{c(\beta ,q)}{2}\log n$ steps, is guaranteed to result in a sample with total variation distance close to $1$.

We conclude this introduction with some brief remarks about our proof and techniques. We construct a multi-phase coupling that converges to a pair of configurations with roughly the correct (expected) number of vertices in each spin class. (In the mean-field setting when $\beta >{\beta }_{\text{r}}$, under the stationary distribution $\mu$, there is one dominant spin and all other spins are assigned to roughly the same number of vertices.) Our coupling gradually contracts the distance to this type of configuration over two phases: first to a linear distance and then to within $O(\sqrt{n})$ distance. The second phase determines the leading order of the mixing time. Earlier analyses (i.e., [19]) yield the $O(\log n)$ mixing time bound but treat step deviations “pessimistically” and cannot provide the sharper bound we derive here. Our analysis carefully accounts for how deviations are amortized over time and account for the fact that early fluctuations do not matter as much.

An innovation of the present argument is the use of a $q\times q$ projection to a partition $\{V_1,\mathrm{\dots },V_q\}$ of $V$ at low temperatures. This projection contains information about the number of vertices assigned each spin in each $V_i$ and its convergence is known to imply that of the SW dynamics due to the symmetry of the mean-field model. This idea was used before in [17, 34, 19] in the high-temperature setting where the percolation steps of the SW dynamics result in subcritical random (sub)graphs with trivial connected component structures. In the $\beta >{\beta }_{\text{r}}$ regime, we must account for the existence of a linear-sized connected component and how it is distributed in the partition $\{V_1,\mathrm{\dots },V_q\}$. To address this, we have an additional step in our analysis in which we argue that the fraction of vertices assigned each spin in each $V_i$ coalesces to the overall fraction of vertices with that spin in the full configuration before the full configuration reaches a typical spin count (i.e., before the end of second phase of the coupling). This allows us to analyze the final phase of our coupling.

We gather here a number of standard definitions and results that we will use in our proofs.

We assume through the remainder of the paper that $\beta >{\beta }_{\text{r}}=q$. Let $a=a(\beta ,q)>1/q$ be the unique fixed point of the drift function $F$ in $(1/q,1]$; see Fact 7. We use in our analysis two different low-dimensional projections of the SW dynamics. The first is the $q$-dimensional proportions vector. For a configuration $X\in \mathrm{\Omega }$, let $\alpha (X)$ be a $q$-dimensional vector, where each coordinate of $\alpha (X)$ corresponds to the fraction of vertices assigned a given spin in $X$. We will assume that ${\alpha }_1(X)$ contains the fraction of vertices assigned the dominant spin in $X$, breaking ties arbitrarily; that is, ${\alpha }_1(X)\ge {\alpha }_i(X)$ for all $i\in [q]$.

When $\beta >{\beta }_{\text{r}}$, for a configuration $X\sim \mu$, $\alpha (X)$ will concentrate around the $q$-dimensional majority vector

or one of its permutations.

We will design a multi-phase coupling, and in the first two phases, we bound the time it takes a copy of the SW dynamics to reach the neighborhood of $m$ from an arbitrary initial configuration. We use the first phase to argue that the SW dynamics reaches constant distance from $m$ and the second phase to further contract the distance to $O(1/\sqrt{n})$; the latter will dominate the order of the mixing time.

Let $X_0\in \mathrm{\Omega }$ be an arbitrary configuration and $Y_0\sim \mu$. We will bound the probability that $\{X_t\}$ and $\{Y_t\}$ have not coupled after $c(\beta ,q)\log n+O(1)$ steps, where

see Fact 10. From (3), we know that $\theta (a\beta )$ is the unique root in $(0,1]$ of the equation

In the first two phases ${\{X_t\}}_{t\ge 0}$, ${\{Y_t\}}_{t\ge 0}$ evolve independently. We claim that after $T_1=O(1)$ steps ${\Vert \alpha (X_{T_1})-m\Vert }_{\mathrm{\infty }}\le \epsilon$ and ${\Vert \alpha (Y_{T_1})-m\Vert }_{\mathrm{\infty }}\le \epsilon$ for any desired constant $\epsilon \in (0,1)$.

A version of this lemma was established in [19], but we require a slight refinement here so that the probability of success is any constant arbitrarily close to $1$.

In the second phase, we claim that after an additional $T_2=c(\beta ,q)\log n+O(1)$ steps, in which both copies of the chain continue to evolve independently, for any constant $\delta \in (0,1)$ there exists a constant $C=C(\delta )>0$ such that with with probability at least $\delta$:

This is established in the following lemma.

A similar convergence result was proved in [19], where it is required that $T=A\log n$ with $A>c(\beta ,q)$. This allowed for a simpler analysis. To obtain our sharper bound, we use the fact that deviations from the expected proportions vector after one step are amortized over the remaining steps of the dynamics, so that early (larger) deviations end up contributing less to the overall separation from $m$.

In the analysis of the third phase of coupling, we use an additional “stationary-like” property for both copies of the chain. Let $𝒱=\{V_1,\mathrm{\dots },V_q\}$ be a partition of $V$ where $V_i$ contains all vertices of $X_{T_1}$ assigned spin $i$. For constant $\lambda \in (0,1)$, we say that $𝒱$ is a $\lambda$-partition if ${\min }_i|V_i|\ge \lambda |V|$. From Lemma 11 we know that $𝒱$ is a $\lambda$-partition with constant probability arbitrarily close to $1$.

Let ${\alpha }_{1,i}(X_t)$ denote the fraction of vertices of $V_i$ assigned the dominant spin in $X_t$; i.e., there are ${\alpha }_{1,i}(X_t)|V_i|$ such vertices. The following lemma ensures that during the second phase, in parallel to making progress towards $m$, at some time $T_1+T_2$, the fraction of vertices assigned the spin from the dominant spin class in each $V_i$ is roughly the same fraction as that from the full configuration $X_T$ in $V$. This additional property will allow us to couple the two process in $O(1)$ additional steps in the third phase.

We note that by Fact (10), and so at time $T_1+T_2$ we reached two configurations that are close to $m$, i.e., satisfy (5), but that also have $\approx a|V_i|$ vertices assigned the dominant spin in each partition set $V_i$.

For the third phase, we consider another lower-dimensional projection of the SW dynamics; in particular, we zoom into a projection of dimension $q\times q$. For ${\{X_t\}}_{t\ge 0}$, let $A_t:={\{A_{ij,t}\}}_{i,j\in [q]},$ with $A_{ij,t}$ denoting the number of vertices in $V_i$ assigned color $j$ in $X_t$. Similarly, define $A_t^{\prime }$ for ${\{Y_t\}}_{t\ge 0}$.

We have shown that after the first two phases of the coupling, for any constant $\widehat{\delta }\in (0,1)$ there is a suitable constant $\widehat{C}>0$ such that at time $T=T_1+T_2$ with probability at least $\widehat{\delta }$ the following holds:

1. A1.

   ${\Vert \alpha (X_T)-m\Vert }_{\mathrm{\infty }}\le \widehat{C}/\sqrt{n}$ and ${\Vert \alpha (Y_T)-m\Vert }_{\mathrm{\infty }}\le \widehat{C}/\sqrt{n}$;

2. A2.

   $|{\alpha }_{1,i}(X_T)-{\alpha }_{1,i}(Y_T)|\le \widehat{C}/\sqrt{V_i}$ for all $i\in [q]$.

Under these assumptions, we design a coupling such that $A_{T+1}=A_{T+1}^{\prime }$ with probability $\mathrm{\Omega }(1)$.

Similar couplings were also designed in [34, 19] but for the high-temperature setting where all the spin classes have roughly the same number of vertices and the percolation steps are subcritical. Here, we have to contend with the presence of a dominant spin class and a supercritical percolation step; this is the reason for the additional step in our analysis (Lemma 14) that guarantees that the extra assumption A2 holds after the first two phases.

The final step of our coupling is a simple boosting phase so that the overall probability of success is at least $\ge 3/4$.

In summary, we have shown that there exists a $T=c(\beta ,q)\log n+O(1)$ such that ${\Vert A_T-A_T^{\prime }\Vert }_{\text{tv}}\le 1/4.$ It was already noted in [34, 19] that the symmetry of the mean-field setting implies that $\Vert X_T-Y_T\Vert ={\Vert A_T-A_T^{\prime }\Vert }_{\text{tv}}$ and thus

which completes the proof of the upper bound in Theorem 1. The lower bound in this theorem follows straightforwardly from some of the same facts required to establish Lemma 12, and it is provided later in Appendix A.

We comment briefly in the organization of the rest of the paper. The proofs of Lemmas 11 and 12, as well as that of the mixing time lower bound, are provided in Section 4. Section 5 contains the proof of Lemma 13, and Section 6 those of Lemmas 14 and 15.

We provide next the the proofs of Lemmas 11 and 12, which ensure that SW dynamics reaches an $O(1/\sqrt{n})$ ball around $m$ after $T=c(\beta ,q)\log n+O(1)$ steps. For $b\in (0,1)$, let

Let $F^k(x)=F^{k-1}(F(x))$ with $F^1=F$. We show first that $\alpha (X_t)$ is close to $\kappa (F^t({\alpha }_1(X_0)))$ for $t\ge 0$ and then that, for an appropriate choice of $t$, $\kappa (F^t({\alpha }_1(X_0)))$ is close to $m$.

A key step in the proof of Lemma 16, which is also useful for proving Lemma 11 is the following concentration guarantee on the fluctuations.

Before proving these lemmas, we show how use them to establish Lemmas 11 and 12.