RANDOM CLUSTER DYNAMICS FOR THE ISING MODEL IS RAPIDLY
MIXING

arXiv:1605.00139v1 [cs.DS] 30 Apr 2016

HENG GUO AND MARK JERRUM
Abstract. We show that the mixing time of Glauber (single edge update) dynamics for the random
cluster model at q = 2 is bounded by a polynomial in the size of the underlying graph. As a
consequence, the Swendsen-Wang algorithm for the ferromagnetic Ising model at any temperature
has the same polynomial mixing time bound.

1. Introduction
The Ising model is perhaps the best known model in statistical physics, and it has also been
widely studied from an algorithmic perspective. An instance of the model is an undirected graph G,
together with a parameter β > 0. A configuration of the model is an assignment σ ∈ {0, 1}V of
“spins” to the vertices of G. The weight w(σ) of configuration σ is β m(σ) where m(σ) is the number
of monochromatic edges (edges {i, j} with σ(i) = σ(j)) in G. It is of importance to compute
the partition function of the system, which is the sum of weights w(σ) over all configurations
σ ∈ {0, 1}V .
If β < 1 then the system is antiferromagnetic, and the partition function is computationally
hard, even to approximate. However, when β > 1 the system is ferromagnetic, and the partition
function can be approximated in polynomial time to with any specified relative error [17]. A direct
approach using Markov chain Monte Carlo (MCMC) on the spin configurations described above
fails, as the spin model exhibits a phase transition for sufficiently large β. However, there is an
equivalent formulation of the Ising model in terms of “even subgraphs” which does form the basis
for a successful application of MCMC, as was shown by Jerrum and Sinclair [17]. (See Sections 2
and 3 for details of the various models referred to in this introduction.)
There is a third model which is equivalent to the Ising model in the sense of having the same
partition function up to an easily computable factor, namely the random cluster model introduced
by Fortuin and Kasteleyn [9]. In common with the even subgraphs model, the configurations of
the random cluster model are subsets of the edge set of G. However, the random cluster model
is more tightly related to the Ising model; in fact a random Ising configuration can be obtained
by colouring the connected components (clusters) of a random cluster configuration independently
and uniformly at random by 0 and 1. Although we already have a polynomial-time algorithm for
estimating the partition function of the Ising model, it is natural to wonder about the mixing time
of the Gibbs sampler for random cluster configurations, which makes single edge-flip moves with
Metropolis rejection probabilities. For one thing, this dynamics may potentially mix faster than
the standard dynamics for the even subgraphs model, and the same is true with even greater force
for the closely related Swendsen-Wang algorithm.
Another reason for focusing on the random cluster model is that it extends the other two models
in the following sense. There is a generalisation of the Ising model to q ≥ 2 spins, known as the qstate Potts model, of which the Ising model is the special case q = 2. Although the even subgraphs
and spin formulations are defined only for integer q, the random cluster model makes sense for
arbitrary positive real q. Thus, by studying the dynamics of the the random cluster model at
This work was partially supported by the EPSRC grant EP/N004221/1. This work was done (in part) while the
authors were visiting the Simons Institute for the Theory of Computing.
1

2

HENG GUO AND MARK JERRUM

q = 2, we may gain insight into the complexity of computing the partition function of the random
cluster model at other values of q, particularly (for reasons that will be explained presently) in the
range 0 ≤ q < 2. Stated in other terms, we would hope to gain information about the complexity
of approximating the Tutte polynomial T (G; x, y) in the region 0 ≤ (x − 1)(y − 1) < 2, and x, y ≥ 1,
about which nothing is currently known except for the point x = y = 1 and the (trivial) hyperbola
(x − 1)(y − 1) = 1 [10, 12].
In this paper we prove for the first time that the Gibbs sampler (single edge-flip dynamics) for
the random cluster model on an arbitrary graph mixes in time polynomial in n = |V (G)|, the
number of vertices of G. (See Theorem 7.) One main tool is the well known canonical paths
technique for bounding mixing time via a parameter known as congestion (in the form presented
by Sinclair [20], building on work of Diaconis and Stroock [6]). Another tool is a coupling between
random cluster and even subgraph configurations discovered by Grimmett and Janson [15]. The
existence of this coupling invites us to bound the congestion of the edge-flip dynamics on random
cluster configurations in terms of the known bounds on congestion for the edge-flip dynamics on
(augmented) even subgraph configurations, established by Jerrum and Sinclair [17]. Unfortunately,
this translation between the models cannot be handled by existing comparison techniques [6, 7],
and an extension of comparison methods to the current situation is a contribution of the paper,
and one that may find application elsewhere.
The Swendsen-Wang algorithm [22] is widely considered to be an efficient method for sampling
random cluster configurations (and Ising spin configurations) in practice. Ullrich has shown [23]
that the Swendsen-Wang dynamics mixes at least as fast as the edge-flip dynamics, so our result
provides the first polynomial upper bound on mixing time of the Swendsen-Wang algorithm. This
provides a partial answer to a problem that has been open since around 1990, when the Ising model
was first studied from a complexity-theoretic perspective. The answer is partial in the sense that
the exponent in the bound we derive here is likely to be well above the true answer, and is certainly
too high to be of practical interest. Hopefully, the result presented here may be the first step on
the road to a practically useful upper bound on the Swendsen-Wang dynamics.
Since the random cluster model is defined for all positive real q, it is natural to speculate on
the mixing time of the Glauber dynamics when q 6= 2. For q > 2, the mixing time cannot be
polynomial in general, owing to a first-order phase transition of the model on the complete graph
(the “mean-field” situation) identified by Bollobás, Grimmett and Janson [2]. This phase transition
is a barrier to rapid mixing when q > 2, as shown by Gore and Jerrum when q is an integer [13],
and by Blanca and Sinclair [1] for general q > 2. For q sufficiently large, Borgs et al. [3] prove
exponential time mixing even in the physically important case of the two-dimensional lattice. In
fact, there is no polynomial-time algorithm of any sort for evaluating the partition function of
the random cluster model on general graphs when q > 2, unless there is an FPRAS for counting
independent sets in a bipartite graph [11]. In contrast, in the range 0 ≤ q ≤ 2 there is no known
barrier to rapid mixing, and there is cause to be optimistic, particularly in the range 1 < q < 2, in
which the random cluster model is monotonic.
In this version of the paper, we do not try too hard to optimise the exponent in the mixing-time
bound, as the method we employ is unlikely to get close to the true answer.

2. Ising and Random Cluster model
The ferromagnetic Ising model on a graph G = (V, E) with parameter β > 1 is defined by the
following: for any σ ∈ {0, 1}V , the probability of being in configuration σ is
(1)

π(σ) =

β m(σ)
,
ZIsing (β)

RANDOM CLUSTER DYNAMICS FOR THE ISING MODEL IS RAPIDLY MIXING

3

where m(σ) is the number of mono-chromatic edges in σ, and its normalizing factor, the so-called
partition function, is defined as
X
ZIsing (β) =
β m(σ) .
σ∈{0,1}V

The random cluster model with parameters (p, q) is defined on subsets of edges S ⊆ E such that
(2)

πRC (S) ∝ p|S| (1 − p)|E\S| q κ(S) ,

and its partition function is
ZRC (p, q) =

X

p|S| (1 − p)|E\S|q κ(S) .

S⊆E

Denote this measure by πRC;p,q (·) or simply πRC (·) when there is no confusion. We use Ω throughout
this article to denote the state space of random cluster models, namely {0, 1}E . It is well known
that, for q = 2 and p = 1− β1 , the random cluster model is equivalent to the Ising model in the sense
that their partition functions are equal up to some easily computable factor (see (9)). The random
cluster model was introduced by Fortuin and Kastelyn [9], who also described its relationship to
the Ising model. The connection between the two models was further elucidated by Edwards and
Sokal [8].
The (lazy) single bond flip dynamics PRC is defined as follows based on the Metropolis filter.
n
o

πRC (y)
1

min
1,
if |x ⊕ y| = 1;

πRC (x) n
 2m
o
P
πRC (x⊕{e})
(3)
PRC (x, y) = 1 − 1
if x = y;
e∈E min 1,
2m
πRC (x)



0
otherwise,
where x, y ∈ Ω. It is not hard to see, for example, by checking the detailed balance condition, that
πRC (·) is the stationary distribution of PRC . Note that the Markov chain is lazy, i.e., it remains at
its current state with probability at least 21 . This eliminates the possibility of the transition matrix
having P having negative eigenvalues, and simplifies the analysis later.
For a Markov chain with transition matrix P and stationary distribution π, we are interested in
its mixing time, that is, how fast it converges to the stationary distribution, defined as follows:


(4)
τε (P ) := min t : max ||P t (x, ·) − π|| ≤ ε ,
x∈Ω

where || · || is the total variation distance, namely
1X
|π(x) − π ′ (x)|.
||π − π ′ || =
2
x∈Ω

Canonical paths are a useful technique to bound the mixing time of Markov chains, introduced
by Jerrum and Sinclair [21, 16]. Let Γ = {γxy : x, y ∈ Ω} be a collection of paths, where γxy is a
“canonical” path from x to y using transitions of the Markov chain. The congestion ̺(Γ) associated
with these paths is
X
L
(5)
π(x)π(y),
̺(Γ) :=
max
(z,z ′ )∈Ω2 ,P (z,z ′)>0 π(z)P (z, z ′ )
2
x,y∈Ω
γxy ∋(z,z ′ )

where L = L(Γ) denotes the maximum length of paths in Γ.

4

HENG GUO AND MARK JERRUM

A more general technique is provided by the flow formulation for congestion. A flow Γ is a
collection of paths, and each path γ ∈ Γ is assigned a weight wt(γ), such that
X
(6)
wt(γ) = π(x)π(y).
γ is from x to y

The congestion of Γ is defined as
(7)

̺(Γ) :=

max

(z,z ′ )∈Ω2 ,P (z,z ′ )>0

L
π(z)P (z, z ′ )

X

wt(γ).

γ∈Γ, (z,z ′ )∈γ

The canonical paths are just a flow where for each pair (x, y) there is only one path with positive
weight.
It is standard that the mixing time of a Markov chain P can be bounded by the congestion of
any flow Γ [20].
Theorem 1. For a lazy, ergodic, reversible Markov chain P and any initial state x0 ∈ Ω,
τε (P ) ≤ ̺(Γ)(ln π(x0 )−1 + ln ε−1 ).
Our goal is to bound τε (PRC ). We can choose the initial state to be the empty set of edegs,
|E| 2|V |
1
which has weight π(∅) = (1−p)
. Also for β = 1−p
we have ZRC (p, 2) = β −|E| ZIsing (β) ≤ 2|V | ,
ZRC
and therefore π(∅) ≥ (1 − p)|E| . Hence, ln π(x0 )−1 ≤ m ln(1 − p)−1 . The main task is to design a
good flow ΓRC so that ̺(ΓRC ) is bounded by a polynomial.
3. Random Even Subgraphs
There is yet another formalism of the Ising model, that is, the so-called “high-temperature
expansion” or even subgraphs model. We still pick a subset of edges S ⊆ E but with the further
restriction that every vertex in the induced subgraph (V, S) has even degree. Denote by Ωeven (G)
the state space of all such even subgraphs of G. We usually simply write Ωeven when there is no
confusion. In this even subgraphs model we want to sample from Ωeven with parameter p ≤ 1/2,
so that edges are more inclined to be “out” than “in”. That is, for any S ∈ Ωeven ,
(8)

π(S) ∝ p|S| (1 − p)|E\S|

and
Zeven (p) =

X

p|S| (1 − p)|E\S|.

S∈Ωeven

Distributions (1), (2), and (8) have in fact the same partition function, up to certain scaling factors:



 
1
1
1
|E|
|V | |E|
ZIsing (β) = β ZRC 1 − , 2 = 2 β Zeven
(9)
1−
.
β
2
β
The first equivalence is well-known, cf. [14]. The second one is also a classical result, cf. [24]. More
detailed explanations can be found in Appendix A.
Grimmett and Janson [15, Thm 3.5] discovered the following coupling between even subgraphs
and random cluster configurations. Take a random even subgraph S from distribution (8) with
p
to get R.
parameter p ≤ 1/2. Then we add each edge e 6∈ S independently with probability 1−p
Theorem 2. [15, Thm 3.5] The subgraph R is a random cluster configuration, that is, it satisfies
(2) with parameters (2p, 2).
For completeness we give a proof of Theorem 2.

RANDOM CLUSTER DYNAMICS FOR THE ISING MODEL IS RAPIDLY MIXING

5

Proof. The number of even subgraphs of a (not necessarily simple) graph G = (V, E) is well known
to be
|Ωeven (G)| = 2|E|−|V |+κ(G)

(10)

where κ(G) is the number of connected components of G.
For each r ⊆ E,
X  p |s|  p |r\s|  1 − 2p |E\r|
Pr(R = r) ∝
1−p
1−p
1−p
s⊆r,s even

∝ p|r| (1 − 2p)|E\r| N (r),

where N (r) is the number of even subgraphs of (V, r). By (10), N (r) = 2|r|−|V |+κ(r) . Hence,
Pr(R = r) ∝ (2p)|r| (1 − 2p)|E\r| 2κ(r) .



However, it is not clear how to sample from Ωeven with edge weights directly in an efficient way,
partly because of the rigid structure of the all even requirement. On the other hand, Jerrum and
Sinclair [17] designed a Markov chain to do so by moving among all subgraphs, but with each odd
degree vertex incurring a penalty. Note that the Jerrum-Sinclair Markov chain together with the
Grimmett-Janson coupling (Theorem 2) yields an efficient sampler for random cluster models and
Ising configurations. It is more straightforward and efficient than the one given by Randall and
Wilson [19], which also uses the Jerrum-Sinclair chain.
A slightly simpler Markov chain is to move between even subgraphs and near-even subgraphs, for
which we allow exactly two odd degree vertices (or “holes”). This is the so-called “worm” process,
introduced by Prokof’ev and Svistunov [18].
Let Ωk be the collection of subgraphs where k many vertices have odd degrees. Then Ω0 = Ωeven
and the state space Ωworm of the “worm” process is Ωworm := Ω0 ∪ Ω2 . For each pair of vertices
(u, v) such that u 6= v, denote by Ω(u, v) the set of subgraphs of G in which u and v have odd
degrees and all other vertices are even. Then
[
Ω2 =
Ω(u, v).
u,v∈V

For a subset of edges S ⊆ E, let wp (S) := p|S|(1 − p)|E\S| . We give a penalty of n−2 to each
near-even subgraph:


if S ∈ Ω0 ;
wp (S)
−2
(11)
wworm (S) := n wp (S) if S ∈ Ω2 ;


0
otherwise.
The “worm” measure is defined as the following:
(
(12)

πworm (S) :=

wworm (S)
Zworm (p)

if S ∈ Ωworm ;

0

otherwise,

P

where Zworm (p) = S∈Ωworm wworm (S).
The winding idea of [17] provides a way to design canonical paths between states in Ωworm with
low congestion. We will not need to analyze it in full detail for the worm process. Instead, we only
care about paths from an even subgraph to another.
Theorem 3. There is a collection of paths
Γworm = {γxy | x, y ∈ Ω0 }

6

HENG GUO AND MARK JERRUM

such that wt(γxy ) = πeven (x)πeven (y), and for any γ ∈ Γworm and any state w ∈ γ, w ∈ Ωworm.
Each state w appears at most once in γ and L(Γworm ) ≤ m. Moreover, for any transition (w, w′ )
where w′ = w ⊕ {e},
X
wt(γ) ≤ n4 πworm (w).
γ∋(w,w ′ )

In the special case w′ = w ∪ {e} for some e 6∈ w, we have the additional bound
X
p
wt(γ) ≤ n4 πworm (w)
.
1−p
′
γ∋(w,w )

Note that Γworm is not a complete collection of canonical paths for πworm(·). The proof of
Theorem 3 is an adaptation of [17] and is given in Appendix B. Note that Collevecchio et al. [5]
give an analysis of a complete set of canonical paths for the worm process, but their result does
not quite fit our situation.
Since paths in Γworm go through Ωworm instead of Ωeven , we need to extend Theorem 2 to Ωworm .
It will no longer be exact.
Take a random subgraph S from distribution (12) with parameter p ≤ 1/2. Again we add each
p
to get R. Call this measure π
b(·).
edge e 6∈ S independently with probability 1−p

Lemma 4. For any R ⊆ E,

π
b(R)
3
≤ .
πRC;2p,2 (R)
2
Proof. Similarly to the proof of Theorem 2, it is not hard to see that
π
b(R) ∝ p|R| (1 − 2p)|E\R| (N (R) + n−2 N ′ (R)),

where N (R), as before, is the number of even subgraphs of (V, R), and N ′ (R) is the number of
subgraphs of R that belong to Ω2 . Note that for each near-even subgraph there is a penalty of
n−2 for its weight (see (11)). We use (10) to count the number of even subgraphs of R, which is
2|R|−|V |+κ(R) .
Let ΩR (u, v) be the set of near even subgraphs of R with holes u and v. If u, v are in different
connected components of (V, R), then there is no possible such subgraph and |ΩR (u, v)| = 0.
Otherwise u, v are in the same component of (V, R), and we can add an extra edge (u, v) to R to
get a graph R′ . Applying (10) to R′ we get that
N (R′ ) = 2|E|+1−|V |+κ(R) = N (R) + |ΩR (u, v)|.
The second equality is because each even subgraph of R′ either uses the new edge (u, v) or not. If
it uses (u, v), then it is an even subgraph of R. Otherwise it is a near even subgraph of R with
holes u and v. Hence,
|ΩR (u, v)| = 2|E|−|V |+κ(R) ,
as N (R) = 2|E|−|V |+κ(R) .
Let c(R) be the number of pairs of vertices from every component of (V, R). That is,
(13)

X ni 
c(R) :=
,
2
κ(R) 
i=1

RANDOM CLUSTER DYNAMICS FOR THE ISING MODEL IS RAPIDLY MIXING

where ni is the size of the ith component of (V, R) with the convention that
that
N ′ (R) = 2|R|−|V |+κ(R) c(R),
and
|R|

π
b(R) ∝ (2p)

|E\R| κ(R)

(1 − 2p)

The lemma follows by noticing that 0 ≤ c(R) ≤

2

1
2

7

= 0. Then we have



c(R)
1+ 2
.
n

n(n−1)
.
2



4. Lifting Canonical Paths
Let p ≤ 1/2 be the parameter of the even subgraph and the worm measure. Let Γworm be the
collection of paths as in Theorem 3. We will use Lemma 4 to lift Γworm to a flow ΓRC for PRC , the
single edge-flip Markov chain for the random cluster model with parameter 2p.
We first construct a flow Γ′RC from Γworm. Let γ = {w0 , w1 , · · · , wℓ } be a path in Γworm where
w0 , wℓ ∈ Ω0 , and ℓ ≤ L(Γworm ). We lift γ to a flow (random path) as follows. First we add each
p
independently as in Lemma 4, to obtain the starting state Z0
edge e 6∈ w0 with probability p′ = 1−p
of the path. In other words, letting
δ(w, z) := (p′ )z\w (1 − p′ )E\z ,
for subsets of edges w ⊆ z ⊆ E, we draw a superset Z0 of w0 such that Pr(Z0 = z) = δ(w0 , z) for
any z ⊇ w0 . Note that
X
πeven (w)δ(w, z)
πRC (z) =
w⊆z,w∈Ω0

by Theorem 2, and

π
b(z) =

X

πworm(w)δ(w, z)

w⊆z,w∈Ωworm

by definition.
We construct Z1 , · · · , Zℓ inductively. Given Zk−1 for 1 ≤ k ≤ ℓ, we construct Zk by mimicking
the transition from wk−1 to wk while ensuring that
Prγ (Zk = z) = δ(wk , z),
for any z ⊇ wk at the same time. Here the subscript γ emphasises that probabilities are with
respect to a fixed path γ. By induction hypothesis, Prγ (Zk−1 = z) = δ(wk−1 , z) for any z ⊇ wk−1 .
For Zk , there are two cases:
• If wk = wk−1 ∪ {e} for some edge e 6∈ wk−1 , then let Zk = Zk−1 ∪ {e}. We have that
Prγ (Zk = z) = Prγ (Zk−1 = z) + Prγ (Zk−1 = z\{e})
= δ(wk−1 , z) + δ(wk−1 , z\{e})
= δ(wk , z)p′ + δ(wk , z)(1 − p′ ) = δ(wk , z),
for any z ⊇ wk .
• If wk = wk−1 \{e} for some edge e ∈ wk−1 , then let Zk = Zk−1 with probability p′ and
Zk = Zk−1 \{e} with probability 1 − p′ . For any z ⊇ wk such that e ∈ z,
Prγ (Zk = z) = Prγ (Zk−1 = z)p′ = δ(wk−1 , z)p′ = δ(wk , z),
and for any z ⊇ wk such that e 6∈ z,
Prγ (Zk = z) = Prγ (Zk−1 = z ∪ {e})(1 − p′ ) = δ(wk−1 , z ∪ {e})(1 − p′ ) = δ(wk , z).

8

HENG GUO AND MARK JERRUM

Given γ, the random flow path Z = {Z0 , Z1 , · · · , Zℓ } is constructed as above. For a particular
flow path ζ = {z0 , z1 , · · · , zℓ } lifted from some path γ, assign its weight to be
X
wt(γ) Prγ (Z = ζ).
wt(ζ) =
γ∈Γworm

Γ′RC .

This finishes the construction of
However, Γ′RC is not a valid flow for πRC (·). If we randomly draw a path from Γ′RC according
to wt(·), then Z0 and Zℓ both are distributed according to πRC (·). However, Zℓ is correlated with
Z0 and is not distributed correctly conditional on Z0 .
We resolve this issue next by constructing ΓRC . Given γ ∈ Γworm with length ℓ, we construct
Z0 , · · · , Zℓ the same as in Γ′RC . To repair the distribution of Zℓ , we append further transitions
to re-randomize edges that are not in wℓ . More precisely, let {e1 , e2 , · · · , ek } be the edges that
′
are not in wℓ where k = |E\wℓ |. Given Zℓ+i−1 for 1 ≤ i ≤ k, let Zℓ+i−1
= Zℓ+i−1 \{ei }. Then
′
′
′
Zℓ+i = Zℓ+i−1 with probability 1 − p and Zℓ+i = Zℓ+i−1 ∪ {ei } with probability p′ . As in Γ′RC , for
a particular flow path ζ = {z0 , z1 , · · · , zℓ+k } lifted from some γ, its weight is defined to be
X
wt(γ)Prγ (Z = ζ).
wt(ζ) =
γ∈Γworm

This finishes the construction of ΓRC . The longest path in ΓRC has length at most L(Γworm ) + m,
that is, L(ΓRC ) ≤ L(Γworm ) + m ≤ 2m.
Fix a path γ = {w0 , w1 , · · · , wℓ }. For any 0 ≤ i ≤ ℓ and z ⊇ wi , we have Prγ (Zi = z) = δ(wi , z),
because of the construction of Γ′RC . Moreover, for any 1 ≤ i ≤ |E\wℓ | and z ⊇ wℓ , we have
Prγ (Zℓ+i = z) = δ(wℓ , z). This can be shown by inductively going through the construction
above. The re-randomization does not change the marginal distribution but removes the correlation
between Z0 and Zℓ′ , where ℓ′ = ℓ + |E\wℓ | (conditional on γ).
The flow ΓRC is valid for πRC (·). We verify (6) as follows:
X
X
X
wt(ζ) =
wt(γ)Prγ (Z0 = x, Zℓ′ = y)
w⊆x, w ′ ⊆y γ is from w to w ′
w,w ′ ∈Ω0

ζ is from x to y

=

X

X

X

X

wt(γ)Prγ (Z0 = x)Prγ (Zℓ′ = y)

w⊆x, w ′ ⊆y γ is from w to w ′
w,w ′ ∈Ω0

=

wt(γ)δ(w, x)δ(w′ , y)

w⊆x, w ′ ⊆y γ is from w to w ′
w,w ′ ∈Ω0

X

=

πeven (w)πeven (w′ )δ(w, x)δ(w′ , y)

w⊆x, w ′ ⊆y
w,w ′ ∈Ω0



=

X

w⊆x, w∈Ω0



πeven (w)δ(w, x) 

= πRC (x)πRC (y),

X

w ′ ⊆y, w ′ ∈Ω0

where in the last step we use Theorem 2.
Lemma 5. Let 2p ≤ 1 be the parameter for the random cluaster model.
(1) For a transition (z, z ′ ) where z ′ = z ∪ {e} for some e 6∈ z,
X
p
· 2n4 πRC (z).
wt(ζ) ≤
1
−
p
′
ζ∈ΓRC , ζ∋(z,z )



πeven (w′ )δ(w′ , y)

RANDOM CLUSTER DYNAMICS FOR THE ISING MODEL IS RAPIDLY MIXING

9

(2) For a transition (z, z ′ ) where z ′ = z\{e} for some e ∈ z,
X

1 − 2p
· 2n4 πRC (z).
1−p

wt(ζ) ≤

ζ∈ΓRC , ζ∋(z,z ′ )

(3) For a transition (z, z),
X

wt(ζ) ≤ 2mn4 πRC (z).

ζ∈ΓRC , ζ∋(z,z)

Proof. Fix γ, let Z be a random path lifted from γ and ℓ be the length of γ. Thus the path is
γ = (w1 , . . . , wℓ ) and, in particular, the final state of the path is wℓ . For a state w ∈ γ, let i(γ, w)
be index of w in γ and k(w, e) be the index of e in |E\w|. Any w only appears once in γ ∈ Γworm
and hence i(γ, w) is well defined.
We want to bound the traffic in ΓRC that goes through (z, z ′ ). Depending on z ′ , we have three
cases.
(1) First assume that z ′ = z ∪ {e} where e 6∈ z. The traffic may be from Γ′RC transitions or
from the part we append at the end of each Γ′RC path. Hence we have the following bound:
X

wt(ζ) =

ζ∈ΓRC , ζ∋(z,z ′ )

X

w⊆z

X

wt(γ)Prγ Zi(γ,w) = z, Zi(γ,w)+1 = z ′

γ∋(w,w∪{e})

X

+



wt(γ)Prγ Zℓ+k(w,e)−1 = z, Zℓ+k(w,e) = z

γ=(w1 ,...,wℓ ), wℓ =w

=

X

w⊆z

X

wt(γ)Prγ Zi(γ,w) = z

γ∋(w,w∪{e})

+

X



wt(γ)Prγ Zℓ+k(w,e)−1 = z p

γ, wℓ =w

=

X

w⊆z

where p′ =
X

ζ∈ΓRC ,

p
1−p .

ζ∋(z,z ′ )



δ(w, z) 

X

wt(γ) +

X

γ, wℓ =w

γ∋(w,w∪{e})

Hence by Theorem 3,

wt(ζ) =

X

w⊆z





δ(w, z) 


X

γ∋(w,w∪{e})

wt(γ) +

′

!



wt(γ)p′  ,
X

γ, wℓ =w



wt(γ)p′ 


p
′
≤
δ(w, z) n πworm (w)
+ πeven (w)p
1−p
w⊆z
X
X
δ(w, z)πeven (w)
δ(w, z)πworm (w) + p′
= p′ n 4
X

4

w⊆z

′ 4

w⊆z,w∈Ω0

′

=pn π
b(z) + p πRC (z)

≤ 2p′ n4 πRC (z),

where we use Lemma 4 in the last line. Also note that πeven (w) = 0 if w 6∈ Ω0 .

′



!

10

HENG GUO AND MARK JERRUM

(2) Next assume that z ′ = z\{e} where e ∈ z. Similar to the previous case, we have that
X
X
X

wt(ζ) =
wt(γ)Prγ Zi(γ,w) = z, Zi(γ,w)+1 = z ′
ζ∈ΓRC , ζ∋(z,z ′ )

w⊆z, w∋e γ∋(w,w\{e})

X

+

X

w⊆z, w∋e γ∋(w,w\{e})

X

+
=

X

wt(γ)Prγ Zℓ+k(w,e)−1 = z, Zℓ+k(w,e) = z ′

X


wt(γ)Prγ Zℓ+k(w,e)−1 = z (1 − p′ )

w⊆z, w6∋e γ, wℓ =w

X

=

X


wt(γ)Prγ Zi(γ,w) = z (1 − p′ )

w⊆z, w6∋e γ, wℓ =w

(1 − p′ )δ(w, z)

w⊆z, w∋e

wt(γ)

γ∋(w,w\{e})

X

+

X

(1 − p′ )δ(w, z)

X

wt(γ).

γ, wℓ =w

w⊆z, w6∋e

Again we use Theorem 3 and Lemma 4:
X
X

wt(ζ) ≤
δ(w, z)(1 − p′ ) n4 πworm (w) + πeven (w)

ζ∈ΓRC , ζ∋(z,z ′ )

w⊆z

≤ (1 − p′ )n4

X

δ(w, z)πworm (w) + (1 − p′ )n4

w⊆z
′

4



X

δ(w, z)πeven (w)

w⊆z,w∈Ω0
′

= (1 − p )n π
b(z) + (1 − p )πRC (z)

≤ 2(1 − p′ )n4 πRC (z).

(3) At last we handle the case that z = z ′ . Then we have the following bound
X

wt(ζ) =

X

w⊆z

ζ∈ΓRC , ζ∋(z,z)

X

wt(γ)Prγ Zi(γ,w) = z, Zi(γ,w)+1 = z

+

X

γ∋w
|E\w|

wt(γ)

γ, wℓ =w

≤

X

w⊆z

=

X

w⊆z

X

γ∋w

X

Prγ Zℓ(γ)+i−1 = z, Zℓ(γ)+i = z

i=1



wt(γ)Prγ Zi(γ,w) = z +


δ(w, z) 

X



X

e∈z γ∋(w,w⊕{e})

X

X

γ, wℓ =w



w⊆z

= 2mn4 πRC (z).

Lemma 6. ̺(ΓRC ) ≤ 8m2 n4 .

!

wt(γ) .

By Theorem 3 and Lemma 4,
X
X

wt(ζ) ≤ m
δ(w, z) n4 πworm (w) + πeven (w)
ζ∈ΓRC , ζ∋(z,z)

!

wt(γ)δ(w, z)|E\w|

γ, wℓ =w

wt(γ) + |E\w|





RANDOM CLUSTER DYNAMICS FOR THE ISING MODEL IS RAPIDLY MIXING

11

Proof. For any transition (z, z ′ ) where z ′ = z ∪ {e} for some e 6∈ z,
X
L(ΓRC )
L(ΓRC )
p
wt(ζ) ≤
·
· 2n4 πRC (z)
′
′
πRC (z)PRC (z, z )
π
(z)P
(z,
z
)
1
−
p
RC
RC
′
ζ∈ΓRC , ζ∋(z,z )

≤ 2mn4 ·

p
2m
·
2p
1 − p min{1, 2(1−2p)
}

≤ 4m2 n4 ,
where we use Lemma 5 in the first line and p ≤ 1/2 in the last.
Similarly, for a transition (z, z ′ ) where z ′ = z\{e} for some e ∈ z,
X
L(ΓRC )
L(ΓRC )
1 − 2p
wtRC (ζ) ≤
·
· 2n4 πRC (z)
′
′
πRC (z)PRC (z, z )
π
(z)P
(z,
z
)
1
−
p
RC
RC
′
ζ∈ΓRC , ζ∋(z,z )

≤ 2mn4 ·

1 − 2p
2m
·
1 − p min{1, 1−2p
2p }

≤ 8m2 n4 ,
where we use Lemma 5 in the first line and p ≤ 1/2 in the last.
For any transition (z, z ′ ) where z ′ = z, since the chain is lazy, PRC (z, z ′ ) ≥ 1/2 and
X
L(ΓRC )
L(ΓRC )
wtRC (ζ) ≤
· 2mn4 πRC (z)
′
′)
πRC (z)PRC (z, z )
π
(z)P
(z,
z
RC
RC
′
ζ∈ΓRC , ζ∋(z,z )

≤ 4m2 n4 ,

where we use Lemma 5 in the first line.



Combining Theorem 1 and Lemma 6 gives us desired mixing time bound for PRC .
Theorem 7. For the random cluster model with parameters 0 < p < 1 and q = 2,
τε (PRC ) ≤ 8n4 m2 (m ln(1 − p)−1 + ln ε−1 ).

References
[1] Antonio Blanca and Alistair Sinclair. Dynamics for the Mean-field Random-cluster Model. In RANDOM, pages
528–543. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015.
[2] Belá Bollobás, Geoffrey Grimmett, and Svante Janson. The random-cluster model on the complete graph. Probab.
Theory Related Fields, 104(3):283–317, 1996.
[3] Christian Borgs, Jennifer T. Chayes, Alan Frieze, Jeong Han Kim, Prasad Tetali, Eric Vigoda, and Van Ha Vu.
Torpid mixing of some Monte Carlo Markov chain algorithms in statistical physics. In FOCS, pages 218–229.
1999.
[4] Jin-Yi Cai, Heng Guo, and Tyson Williams. A complete dichotomy rises from the capture of vanishing signatures
(extended abstract). In STOC, pages 635–644. ACM, 2013. Available at abs/1204.6445.
[5] Andrea Collevecchio, Timothy M. Garoni, Timothy Hyndman, and Daniel Tokarev. The worm process for the
Ising model is rapidly mixing. ArXiv e-prints, 2015. Available at abs/1509.03201.
[6] Persi Diaconis and Laurent Saloff-Coste. Comparison theorems for reversible Markov chains. Ann. Appl. Probab.,
3(3):696–730, 08 1993.
[7] Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, and Russell Martin. Markov chain comparison. Probab. Surv.,
3:89–111, 2006.
[8] Robert G. Edwards and Alan D. Sokal. Generalization of the Fortuin-Kasteleyn-Swendsen-Wang representation
and Monte Carlo algorithm. Phys. Rev. D (3), 38(6):2009–2012, 1988.
[9] C. M. Fortuin and P. W. Kasteleyn. On the random-cluster model. I. Introduction and relation to other models.
Physica, 57:536–564, 1972.

12

HENG GUO AND MARK JERRUM

[10] Leslie Ann Goldberg and Mark Jerrum. Inapproximability of the Tutte polynomial. Inform. and Comput.,
206(7):908–929, 2008.
[11] Leslie Ann Goldberg and Mark Jerrum. Approximating the partition function of the ferromagnetic Potts model.
J. ACM, 59(5):Art. 25, 31, 2012.
[12] Leslie Ann Goldberg and Mark Jerrum. The complexity of computing the sign of the Tutte polynomial. SIAM
J. Comput., 43(6):1921–1952, 2014.
[13] Vivek K. Gore and Mark R. Jerrum. The Swendsen-Wang process does not always mix rapidly. J. Statist. Phys.,
97(1-2):67–86, 1999.
[14] Geoffrey Grimmett. The random-cluster model. Springer, 2006.
[15] Geoffrey Grimmett and Svante Janson. Random even graphs. Electron. J. Combin., 16(1):Research Paper, 46,
19, 2009.
[16] Mark Jerrum and Alistair Sinclair. Approximating the permanent. SIAM J. Comput., 18(6):1149–1178, 1989.
[17] Mark Jerrum and Alistair Sinclair. Polynomial-time approximation algorithms for the Ising model. SIAM J.
Comput., 22(5):1087–1116, 1993.
[18] Nikolay Prokof’ev and Boris Svistunov. Worm algorithms for classical statistical models. Phys. Rev. Lett.,
87:160601, 2001.
[19] Dana Randall and David Wilson. Sampling spin configurations of an Ising system. In SODA, pages 959–960,
1999.
[20] Alistair Sinclair. Improved bounds for mixing rates of Markov chains and multicommodity flow. Comb. Probab.
Comp., 1:351–370, 1992.
[21] Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing Markov chains.
Inform. and Comput., 82(1):93–133, 1989.
[22] Robert Swendsen and Jian-Sheng Wang. Nonuniversal critical dynamics in Monte Carlo simulations. Phys. Rev.
Lett., 58:86–88, Jan 1987.
[23] Mario Ullrich. Swendsen-Wang is faster than single-bond dynamics. SIAM J. Discrete Math., 28(1):37–48, 2014.
[24] Bartel L. van der Waerden. Die lange Reichweite der regelmäßigen Atomanordnung in Mischkristallen. Zeitschrift
für Physik, 118(7):473–488, 1941.

Appendix A. Equivalence of the three views
The equivalence between the Ising model and the random cluster model with q = 2 can be found
in [14]. It can also be seen as the following. Instead of assigning vertices 0 or 1, we may assign
“equal” or “independent” to edges. Each “equal” edge has an weight of β − 1, and “independent”
has weight 1. This is the same as the Ising model, since for each edge, if the two end points are
equal, the weight is β − 1 + 1 = β, whereas if the two endpoints are not equal, the weight is 1.
For a subset S ⊆ E of edges being “equal”, each component of S has two possible assignments.
Therefore the weight of S is (β − 1)|S| 2κ(S) . After rescaling by β |E| this matches the random cluster
formulation (2) with p = 1 − β1 and q = 2. This gives the first equality of (9).
The equivalence between the Ising model and even subgraphs
model can be explained via a
1
1
1
holographic transformation by Hadamard matrix H = 1 −1 . In the Ising model, vertices have
functions Equality on its adjacent d many half-edges, which after the transformation becomes
Even function, defined as follows:
(
L
2 if
i xi = 0;
Even(x1 , · · · , xd ) =
0 otherwise.
On the edges, the function (on the two half-edges) is
(
β if x1 = x2 ;
Ising(x1 , x2 ) =
1 otherwise,
1For basics of holographic transformations, see e.g. [4].

RANDOM CLUSTER DYNAMICS FOR THE ISING MODEL IS RAPIDLY MIXING

whereas after the transformation it is
WEQ(x1 , x2 ) =


β+1

 2

β−1
 2



0

13

if x1 = x2 = 0;
if x1 = x2 = 1;
otherwise,

a weighted equality function. Therefore, for a subset S of edges (both half-edges are 1), its weight
is


 

 |V | β−1 |S| β+1 |E\S|
2
if S ∈ Ωeven ;
2
2
wt(S) =
0
otherwise.

The requirement of S ∈ Ωeven arises because each vertex requires even degree, and when all degree
constraints are satisfied, the vertices contribute 2|V | in total. We may rewrite the weight of S ∈
Ωeven :
|S| 

|S|  
|E\S|
 

β + 1 |E\S|
1
1
1
|V | |E| 1
|V | β − 1
=2 β
1−
1+
2
2
2
2
β
2
β


Hence setting p = 12 1 − β1 matches (8) and taking out appropriate scaling factor yields the second
equality of (9).
Appendix B. Congestion of the worm process
Throughout this section fix p ≤ 1/2. Recall that Ωk is the collection of subgraphs where k many
vertices have odd degrees. Then Ω0 = Ωeven , and Ω0 ∪ Ω2 = Ωworm . Define
X
Zk :=
wp (S),
S∈Ωk

where wp (S) = p|S|(1 − p)|E\S| . Then Z0 = Zeven (p) and Zworm (p) = Z0 + n−2 Z2 .
If we adopt the holographic transformation view of the even subgraphs model, then a vertex that
only allows odd degrees is equivalent to the following function:
(
L
2 if
i xi = 1;
Odd(x1 , · · · , xd ) =
0 otherwise.
Transforming back to the Ising model, this vertex is still an Equality on all adjacent half-edges,
but with a weight of −1 when all half-edges are assigned 1. Hence for every u, v ∈ V ,
X
(14)
Zu,v :=
wp (S) ≤ Z0 ,
S∈Ω(u,v)

because the left hand side can be transformed to the original Ising with u and v having weights −1.
We can sum over all possible pairs of vertices in (14), getting Z2 ≤ n2 Z0 .

Lemma 8. Z2 ≤ n2 Z0 .

Lemma 8 implies that Zworm = Z0 + n−2 Z2 ≤ Z0 + n−2 n2 Z0 ≤ 3Z0 /2.
Now we are ready to prove Theorem 3.
Proof of Theorem 3. Let I and F be two configurations in Ω0 , denoting the initial and final states.
Then I ⊕F ∈ Ω0 . The canonical path from I to F will be identical to those in [17]. Fix an arbitrary
ordering of all cycles in G. For each cycle we designate a starting vertex and a direction around the
cycle. Hence each cycle is an ordered tuple of edges. Since I ⊕ F is an even subgraph, we can cover
I ⊕ F by a collection of edge-disjoint cycles. Let {C1 , · · · , Cr } be the first such in our ordering.
Let e1 , · · · , ek be the edges of {C1 , · · · , Cr } taken in order (first order the edges according to the

14

HENG GUO AND MARK JERRUM

cycle they occur in, and then by their position within the cycle, counting from the start vertex).
The canonical path γ from I to F is defined to be Z0 = I, Zi = Zi−1 ⊕ ei , and Zk = F . Intuitively
the canonical path unwinds Ci one by one from i = 1 to i = r. Clearly L = L(Γworm ) ≤ m as it
can use every edge at most once.
This path is always in Ω0 ∪ Ω2 because if we start to unwind a cycle, then the current state is
an even subgraph. If we are unwinding a path, then we always flip an edge that is adjacent to an
odd degree vertex.
For any transition (w, w′ ) where w′ = w ⊕ e for some edge e ∈ E, we use a combinatorial
encoding as in [17] for all paths passing through (w, w′ ). For any two configurations I, F ∈ Ω0 , let
ϕ(I, F ) = I ⊕ F ⊕ w. We claim that ϕ : Ω20 → Ω0 ∪ Ω2 is an injection. This is because given (w, w′ )
and U = ϕ(I, F ), we can recover the unique (I, F ). First, since w ⊕ U = I ⊕ F , all edges not in
w ⊕ U have the same state in both I and F , and their states are the same as those in w. Then for
edges in w ⊕ U , due to the construction of the canonical path, there is a unique ordering among
those edges, including e = w ⊕ w′ . For any edge before e, its status in w has been changed to that
in F , and its status in U is still the same as that in I. For any edge after e (including e itself), its
status in w is still the same as that in I, and in U is the same as in F .
Recall that wp (S) = p|S| (1 − p)|E\S| for any subset of edges S ⊂ E. Since I ⊕ F = w ⊕ U and
I ∩ F = w ∩ U , we have that
wp (I)wp (F ) = wp (w)wp (U ).
Therefore,
X

wt(γ) =

γ∋(w,w ′ )

X

πeven (I)πeven (F ) =

X

wp (w)wp (ϕ(I, F ))
Z02

I,F ∈Ω20
γIF ∋(w,w ′ )

=

I,F ∈Ω20
γIF ∋(w,w ′ )

≤ wp (w)

I,F ∈Ω20
γIF ∋(w,w ′ )

X

U ∈Ω0 ∪Ω2

=

γ∋(w,w ′ )

(by Lemma 8)

wp (I)wp (F )
Z02

wp (U )
Z02

Z0 + Z2
· wp (w).
Z02

By the definition of πworm (11) and (12), πworm(w) =
X

X

wworm (w)
Zworm

≥

wp (w)
.
n2 Zworm

This implies that

Z0 + Z2 Zworm 2
·
· n πworm(w)
Z0
Z0

  
 

n
n −2
≤ 1+
1+
n
n2 πworm (w)
2
2

wt(γ) ≤

≤ n4 πworm (w).

For the last claim of the theorem, let w′ = w ∪ {e} for some e 6∈ w. We can do the same
combinatorial encoding for w′ . That is, let U ′ = ϕ′ (I, F ) = I ⊕ F ⊕ w′ . It is easy to verify as above

RANDOM CLUSTER DYNAMICS FOR THE ISING MODEL IS RAPIDLY MIXING

15

that ϕ′ is an injection. Then as above,
X
Z0 + Z2
wt(γ) ≤
· wp (w′ )
2
Z0
′
γ∋(w,w )

p
Z0 + Z2
· wp (w) ·
2
1
−
p
Z0
p
.
≤ n4 πworm (w)
1−p
=



School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London E1
4NS, United Kingdom.

