The “Burnside process” converges slowly^{∗}

Leslie Ann Goldberg^{†} Department of Computer Science University of Warwick

Mark Jerrum^{‡} Department of Computer Science University of Edinburgh

June 11, 1998

Abstract

We consider the problem of sampling “unlabelled structures”, i.e., sampling combinatorial structures modulo a group of symmetries. The main tool which has been used for this sampling problem is Burnside’s lemma. In situations where a significant proportion of the structures have no nontrivial symmetries, it is already fairly well understood how to apply this tool. More generally, it is possible to obtain nearly uniform samples by simulating a Markov chain that we call the Burnside process; this is a random walk on a bipartite graph which essentially implements Burnside’s lemma. For this approach to be feasible, the Markov chain ought to be “rapidly mixing”, i.e., converge rapidly to equilibrium. The Burnside process was known to be rapidly mixing for some special groups, and it has even been implemented in some computational group theory algorithms. In this paper, we show that the Burnside process is not rapidly mixing in general. In particular, we construct an infinite family of permutation groups for which we show that the mixing time is exponential in the degree of the group.

∗This work was supported in part by the ESPRIT Working Group 21726 “RAND2”, and ESPRIT LTR Project 20244 “ALCOM-IT”.

†leslie@dcs.warwick.ac.uk, http://www.dcs.warwick.ac.uk/∼leslie/, Department of Computer Science, University of Warwick, Coventry, CV4 7AL, United Kingdom.

‡mrj@dcs.ed.ac.uk, http://www.dcs.ed.ac.uk/∼mrj/, Department of Computer Science, University of Edinburgh, The King’s Buildings, Edinburgh EH9 3JZ, United Kingdom.

1 Introduction

The computational task considered in this article is that of sampling “unlabelled structures”, i.e., sampling combinatorial structures modulo a group of symmetries. We work within the framework of Pólya theory: “Structures” are taken to be length-m words over a finite alphabet Σ, and the group of symmetries is taken to be a permutation group G of degree m which acts on the words by permuting positions. (See Section 2 for precise definitions.) The image of α ∈ Σ^{m} under g is conventionally denoted α^{g}. Words α and β are in the same orbit if there is a permutation g ∈ G which maps α to α^{g} = β. The orbits partition the set of words into equivalence classes, and the computational problem is to sample words in such a way that each orbit is equally likely to be output.^{1}

The main tool which has been used for sampling orbits is Burnside’s Lemma,^{2} which says that each orbit comes up |G| times (as the first component) in the set of pairs

Υ(Σ, G) := {(α, g) | α ∈ Σ^{m}, g ∈ G and α^{g} = α}.  (1)

Thus, we are interested in the computational problem of sampling uniformly at random from Υ(Σ, G), given (an efficient representation of) G.

Wormald [16] has shown how to solve this sampling problem for rigid structures. That is, he has given an efficient random sampling algorithm that works whenever a high fraction of the pairs in Υ(Σ, G) have g equal to the identity permutation. Wormald’s method does not extend to the case in which the identity permutation contributes only a small fraction^{3} of the pairs in Υ(Σ, G). However, Jerrum proposed a natural approach based on Markov chain simulation which does extend to this case [7].

We give the details of the Markov chain simulation approach in Section 2. In brief, the idea is to consider the following bipartite graph: The vertices on the left-hand side are all words in Σ^{m}. The vertices on the right-hand side are all permutations in G. There is an edge from word α to permutation g if and only if α^{g} = α. This graph essentially implements Burnside’s Lemma: The lemma shows that the stationary distribution of a random walk on the graph assigns equal weight to each orbit, i.e., to each unlabelled structure. The Markov chain that we consider, which we refer to as the “Burnside process”, is the random walk on this graph observed on alternate steps.

We may obtain a nearly uniform unlabelled sample by simulating the Burnside process from a fixed initial state for sufficiently many steps, and returning the final state. The efficiency of this sampling method is dependent on the so-called mixing time of the Burnside process: in rough terms, how many steps is “sufficiently many”? The aim of this article is to show that the mixing time of the Burnside process is sometimes very large. We now make that statement precise.

1Here is a concrete example: Let Σ be a binary alphabet. Encode the adjacency matrix of an n-vertex graph as a word of length m = \binom{n}{2}. The relevant permutation group is the group (acting on words) which is induced by the group of all permutations of the n vertices. Note that two graphs are in the same orbit if and only if they are isomorphic.

2Although this lemma is commonly referred to as “Burnside’s Lemma”, it is really due to Cauchy and Frobenius [13].

3Specifically, Wormald’s approach can be used when the fraction of pairs in Υ(Σ, G) which are due to the identity is at least the inverse of some polynomial in m.

For any two probability distributions π and π′ on a finite set Ψ, define the total variation distance between π and π′ to be

D_{tv}(π, π′) := max_{A⊆Ψ} |π(A) − π′(A)| = \frac{1}{2} ∑_{x∈Ψ} |π(x) − π′(x)|.

Suppose M is an ergodic Markov chain with state space Ψ and stationary distribution π, and let the t-step distribution of M, when started in state x_{0}, be π_{t}. The mixing time of M, given initial state x_{0}, is a function τ_{x_{0}} : (0, 1) → ℕ, from tolerances δ to simulation times, defined as follows: for each δ ∈ (0, 1), let τ_{x_{0}}(δ) be the smallest t such that D_{tv}(π_{t′}, π) ≤ δ for all t′ ≥ t. If the initial state is not significant or is unknown, it is appropriate to define τ(δ) = max_{x} τ_{x}(δ), where the maximum is over all x ∈ Ψ. By rapid mixing, we mean that τ(δ) ≤ poly(m, log δ^{−1}), where m is the input size—in our case the degree of the group G—and δ the tolerance. Stuart Anderson has suggested the phrase torpid mixing to describe the contrasting situation where mixing time is exponential in the input size.

The Burnside process was shown to be rapidly mixing for some very special groups G [7]. However, it was an open question whether it is rapidly mixing in general. The precise result of this article (Theorem 11) is a construction of an infinite family of permutation groups G for which we show that the mixing time τ(\frac{1}{3}) is exponential in the degree of G. Thus, if we use the t-step distribution to estimate the probability π(A) of some event A ⊂ Ψ in the stationary distribution, the result may be out by as much as \frac{1}{3}, unless we take t exponentially large.

The main idea of the proof is to relate the mixing time of the Burnside process to the “Swendsen-Wang process”, a particular dynamics for the Potts model in statistical physics. The Swendsen-Wang process was shown by Gore and Jerrum [5] to have exponential mixing time at a certain critical value of a parameter called “temperature”. It turns out that the Swendsen-Wang process defined on a graph Γ at a different (lower, non-critical) temperature has exactly the same dynamics as the Burnside process on a derived permutation group G_{3}(Γ ). Thus we only have to relate the Swendsen-Wang process at the two different temperatures, which we do using the “l-stretch” construction used by other authors [6]. The dynamics of the Swendsen-Wang process is not perfectly preserved by the lstretch construction, but the correspondence is close enough to yield the claimed result.

Sections 2 and 3 describe the Burnside and Swendsen-Wang processes; Section 4 describes the relationship between the two; Section 5 relates the Swendsen-Wang process at two different temperatures via the l-stretch construction, thus completing the “torpid mixing” proof; finally, Section 6 concludes with some open problems.

2 The Burnside process

Let Σ = {0, …, k −1} be a finite alphabet of cardinality k, and G a permutation group on [m] = {0, …, m − 1}. For g ∈ G and i ∈ [m], denote by i^{g} the image of i under g. The group G has a natural action on the set Σ^{m} of all words of length m over the alphabet Σ, induced by permutations of the “positions” 0, …, m − 1. Under this induced action, the permutation g ∈ G maps the word α = a_{0}a_{1} … a_{m−1} to the word α^{g} = β = b_{0}b_{1} … b_{m−1} defined by b_{j} = a_{i} for all i, j ∈ [m] satisfying i^{g} = j. The action of G partitions Σ^{m} into a number of orbits, these being the equivalence classes of Σ^{m} under the equivalence relation that identifies α and β whenever there exists g ∈ G mapping α to β. The orbit {α^{g} : g ∈ G} containing the word α ∈ Σ^{m} is denoted α^{G}. As we indicated in the introduction, Burnside’s Lemma says that each orbit comes up |G| times in the set Υ(Σ, G) defined in equation (1). Thus, we are interested in the problem of uniformly sampling elements of Υ(Σ, G).

A standard attack on combinatorial sampling problems [9] is to design a Markov chain whose states are the structures of interest (in this case the state space is G) and whose transition probabilities are chosen so that the stationary distribution is the required sampling distribution. The following natural Markov chain was proposed by Jerrum [7]. As we noted in the introduction, it is essentially a random walk on the bipartite graph which corresponds to Burnside’s Lemma. The state space of the Markov chain M_{B} = M_{B}(G, Σ) is just G. The transition probabilities from a state g ∈ G are specified by the following conceptually simple two-step experiment:

(B1) Sample α uniformly at random (u.a.r.) from the set Fix g := {α ∈ Σ^{m} : α^{g} = α}.

(B2) Sample h u.a.r. from the point stabiliser G_{α} := {h ∈ G : α^{h} = α}.

The new state is h. Algorithmically, it is not difficult to implement (B1). However, Step (B2) is apparently difficult in general. (It is equivalent under randomised polynomial-time reductions to the Setwise Stabiliser problem, which includes Graph Isomorphism as a special case.) Nevertheless, there are significant classes of groups G for which an efficient (polynomial time) implementation exists. Luks has shown that p-groups—groups in which every element has order a power of p for some prime p—is an example of such a class [10].

Returning to the Markov chain itself, we note immediately that M_{B} is ergodic, since every state (permutation) can be reached from every other in a single transition, by selecting the word α = 0^{m} in step (B1). Let π : G → [0, 1] denote the stationary distribution of M_{B}. Then π(g) is proportional to the degree of vertex g in the bipartite graph corresponding to Burnside’s Lemma, which is | Fix g| = k^{c(g)}, where c(g) denotes the number of cycles in the permutation g. We have therefore established the following Lemma from [8]:

Lemma 1 Let π be the stationary distribution of the Markov chain M_{B}(G, Σ). Then π(g) = k^{c(g)}/|Υ(Σ, G)| for all g ∈ G.

Although the Markov chain M_{B} on G is the most convenient one for us to work with, it is clear that we can invert the order of steps (B1) and (B2) to obtain a dual Markov chain M′_{B}(G, Σ) with state space Σ^{m}. The dual Markov chain^{4} has greater practical appeal, as it gives a uniform sampler for orbits (i.e., unlabelled structures):

Lemma 2 Let π′ be the stationary distribution of the Markov chain M′_{B}(G, Σ). Then

π′(α) = \frac{|G|}{|α^{G}| |Υ(Σ, G)|}

for all α ∈ Σ^{m}; in particular, π′ assigns equal probability to each orbit α^{G}.

The result again follows from a consideration of the random walk on the bipartite graph, using the elementary group-theoretic fact that |G_{α}| × |α^{G}| = |G|.

Peter Cameron has observed that a Markov chain similar to M′_{B} may be defined for any group action, not just the special case of a permutation group G acting on Σ^{m} by permutation of positions. In the general setting: given a point α, select u.a.r. a group element g that fixes α, and then select a point that is fixed by g. Thus, the generalisation of M′_{B} to arbitrary group actions provides a potentially efficient procedure for uniformly sampling unlabelled structures (i.e., sampling structures up to symmetry). This procedure has been implemented in certain algorithms for determining the conjugacy classes of a finite group [15].

Of course, the effectiveness of M′_{B} (equivalently M_{B}) as a basis for a general purpose sampling procedure for unlabelled structures depends on its mixing time. It was known that M_{B} mixes rapidly in some special cases (see Jerrum [7]), but it was not previously known whether M_{B} mixes rapidly for all groups G. Specifically, it was not known whether the mixing time of M_{B}(G, Σ) is uniformly bounded by a polynomial in m, the degree of G. The result in this article is a construction of an infinite family of permutation groups for which we show that the mixing time of M_{B} grows exponentially in the degree m.

4In references [7] and [8], the primed and unprimed versions are reversed.

3 The Swendsen-Wang process

As noted in the Introduction, our strategy is to relate the mixing time of the Burnside process to that of the Swendsen-Wang process. In this section we describe the latter process, which provides a particular dynamics for the q-state Potts model. In fact, we need only consider the special case q = 3. See Martin’s book [12] for background on the Potts model.

A (3-state) Potts system is defined by a graph Γ = (V, E) and a real number (“inverse temperature”) β. For compactness, we will sometimes denote an edge (i, j) ∈ E by ij. A configuration of the system is an assignment σ : V → {0, 1, 2} of “spins” or colours to the vertices of Γ . The set of all 3^{|V |} possible configurations is denoted by Ω. We associate each configuration σ ∈ Ω with an energy H(σ) := ∑_{ij∈E} [1 − δ(σ(i), σ(j))], where δ is the Kronecker-δ function which is 1 if its arguments are equal, and 0 otherwise. Thus the energy of a configuration is just the number of edges connecting unlike colours. The (Boltzmann) weight of a configuration σ is exp(−β H(σ)). The partition function of the 3-state Potts model is

Z = Z(Γ , β) := ∑_{σ∈Ω} exp ( − β H(σ));  (2)

it is the normalising factor in the Gibbs distribution on configurations, which assigns probability exp(−β H(σ))/Z to configuration σ. To avoid the exponentials, we will define the edge weight λ of the Potts system to be e^{−β}, so the partition function (2) may be rewritten as

Z = Z(Γ , λ) = ∑_{σ∈Ω} ∏_{ij∈E} λ^{[1−δ(σ(i),σ(j))]}.  (3)

Thus the weight of a configuration is λ^{b}, where b is the number of bichromatic edges.

The Swendsen-Wang process specifies a Markov chain M_{SW}(Γ , λ) on Ω. Let the current Potts configuration be denoted by σ. The next configuration σ′ is obtained as follows.

(SW1) Let \overline{A} = \{ij ∈ E : σ(i) = σ(j)\} be the set of monochromatic edges. Select a subset A ⊆ \overline{A} by retaining each edge in \overline{A} independently with probability p = 1 − λ.

(SW2) The graph (V, A) consists of a number of connected components. For each connected component, a colour is chosen u.a.r. from {0, 1, 2}, and all vertices within the component are assigned that colour.

That the Markov chain with transitions defined by this experiment is ergodic is immediate; that it has the correct (i.e., Gibbs) distribution is not too difficult to show. (See, for example, Edwards and Sokal [3].)

4 The relationship between the Burnside process and the Swendsen-Wang process

Let Σ be a finite alphabet of size k, and let Γ = (V, E) be an undirected graph defining a 3-state Potts system with edge weight λ = k^{−2}. We will construct an associated permutation group G_{3}(Γ ) such that the dynamics of the Burnside process on (G_{3}(Γ ), Σ) is essentially the same as the Swendsen-Wang dynamics on (Γ , λ). This construction generalises a construction from [7], which deals with the case k = 2 (i.e., the binary alphabet case).

The permutation group G_{3}(Γ ) acts on the set Δ = ⋃_{e∈E} Δ_{e}, which is the disjoint union of three-element sets Δ_{e}. Arbitrarily orient the edges of Γ , so that each edge e ∈ E has a defined start-vertex e^{−} and end-vertex e^{+}. For e ∈ E and v ∈ V, denote by h_{e} some fixed permutation that induces a 3-cycle on Δ_{e} and leaves everything else fixed, and denote by g_{v} the generator

g_{v} := ∏_{e:e^{+}=v} h_{e} × ∏_{e:e^{−}=v} h_{e}^{−1}.

Finally, define G_{3}(Γ ) = ⟨g_{v} : v ∈ V ⟩, the group generated by {g_{v}}.

Observe that the generators of G_{3}(Γ ) commute and have order three, so each permutation g ∈ G_{3}(Γ ) can be expressed as

g = g(σ) := ∏_{v∈V} g_{v}^{σ(v)} = ∏_{e∈E} h_{e}^{σ(e^{+})−σ(e^{−})},  (4)

where σ : V → {0, 1, 2}. Provided the graph Γ is connected, this expression is essentially canonical, in that σ is uniquely determined up to addition (mod 3) of a constant function. To see this, note that g uniquely determines the exponent of h_{e} in expansion (4), which in turn determines the difference between the colours (viewed as integers) at the endpoints of edge e. Note that all three of the configurations associated with g induce the same set \overline{A} in (SW1). Thus, the transition probabilities from the three configurations are the same, and we can therefore think of g as being associated with all three configurations.

Lemma 3 Suppose Γ is a graph, Σ a finite alphabet, and let k = |Σ|. Then

M_{B}(G_{3}(Γ ), Σ) ≅ M_{SW}(Γ , k^{−2});

that is to say, each permutation g in the state space of M_{B}(G_{3}(Γ ), Σ) can be associated with exactly three configurations in the state space of M_{SW}(Γ , k^{−2}) in such a way that transition probabilities are preserved.

Proof. We associate each permutation g ∈ G_{3}(Γ ) with three configurations as described above. As we observed, the transition probabilities of the three configurations in SW are identical.

Perhaps the easiest way to show that these transition probabilities are the same as those in M_{B} is to combine the experiment defining the Burnside process (see (B1) and (B2)) with that defining the Swendsen-Wang process (see (SW1) and (SW2)) into a single coupled version. Start with the pair (g, σ_{g}), where σ_{g} is one of the three configurations associated with g.

(C1) Sample α u.a.r. from the set Fix g = {α ∈ Σ^{m} : α^{g} = α} of words fixed by g. Let A := {e ∈ E : α is not constant on Δ_{e}}. The pair (α, A) is the intermediate state.

(C2) Sample h u.a.r. from the point stabiliser G_{α} = {h ∈ G : α^{h} = α}.

The new pair is (h, σ_{h}) (again, choose σ_{h} arbitrarily from the three configurations associated with h.).

By construction, the transitions g → α → h occur with the probabilities dictated by (B1) and (B2). We must check that the induced transitions σ_{g} → A → σ_{h} match (SW1) and (SW2) in probability. Let e = uv ∈ E be any edge, and consider the action of g on Δ_{e}. If σ_{g}(u) = σ_{g}(v) then the action of g on Δ_{e} is the identity, and probability that α is constant on Δ_{e} is k^{−2}. Thus the probability that e ∈ A is 1−k^{−2}, independent of the other edge choices, as required by (SW1), where λ = k^{−2}. Otherwise, σ_{g}(u) ≠ σ_{g}(v) and the action of g on Δ_{e} is a 3-cycle. Necessarily, α is constant on Δ_{e}, and e ∉ A, again as required by (SW1). So the distribution of A ⊆ E is correct.

To verify the second step, again let e = uv ∈ E be any edge. If e ∈ A then α is not constant on Δ_{e}, entailing that the action of h on Δ_{e} is the identity and σ_{h}(u) = σ_{h}(v). Conversely, if e ∉ A then α is constant on Δ_{e}, and σ_{h}(u) − σ_{h}(v) is unconstrained. Thus h ↦ σ_{h} is a bijection from G_{α} to configurations that are constant on connected components of (V, A), and the distribution of σ_{h} is as demanded by (SW2).

5 Torpid mixing

We have seen that the Burnside process is equivalent to the Swendsen-Wang process at a particular edge-weight λ; and it is known that the Swendsen-Wang process at a different edge weight (which is approximately 1 − (4 ln 2)/|V |, where V is the vertex set of Γ ) has exponential mixing time [5]. In this section we bridge the gap between the different edge weights.

Denote by P_{l} the path of length l or l-path, i.e., the graph with vertex set [l + 1] and edge set {{i, i + 1} : 0 ≤ i < l}.

Lemma 4 Consider a randomly sampled configuration of the 3-state Potts model on P_{l} with edge weight λ. The induced distribution of colours on the two end vertices of P_{l} is identical to the distribution of configurations of the 3-state Potts model on P_{1} (= K_{2}) with edge weight

λ̂(l) := \frac{(1 + 2λ)^{l} − (1 − λ)^{l}}{(1 + 2λ)^{l} + 2(1 − λ)^{l}} .  (5)

Proof. Define w^{(l)} ∈ ℝ^{2} to be the vector whose first (respectively, second) component w_{0}^{(l)} (respectively, w_{1}^{(l)}) is the total weight of those configurations on P_{l} whose (ordered) endpoints have colours (0, 0) (respectively, (0, 1)). Clearly, there is nothing special in the particular choice of colours; the pair (0, 0) could be replaced by any pair of like colours, and (0, 1) by any pair of unlike ones. Introduce the matrix

T := ( \begin{matrix}1 & 2λ \\ λ & 1 + λ \end{matrix} );

a straightforward induction on l establishes

w^{(l)} = T^{l} \binom{1}{0} .

The matrix T has eigenvalues 1−λ and 1+2λ. Introduce two further matrices

D := ( \begin{matrix}1 − λ & 0 \\ 0 & 1 + 2λ \end{matrix} ) and S := ( \begin{matrix}2 & 1 \\ −1 & 1 \end{matrix} ) .

Then T = SDS^{−1} and hence T^{l} = SD^{l}S^{−1}. Noting that

S^{−1} = \frac{1}{3} ( \begin{matrix}1 & −1 \\ 1 & 2 \end{matrix} ) ,

we obtain

w^{(l)} = SD^{l}S^{−1} \binom{1}{0} = \frac{1}{3} ( \begin{matrix}(1 + 2λ)^{l} + 2(1 − λ)^{l} \\ (1 + 2λ)^{l} − (1 − λ)^{l} \end{matrix} ) .  (6)

Since P_{l} is equivalent—in the sense of the statement of the lemma—to a single edge with effective weight w_{1}^{(l)}/w_{0}^{(l)}, the result follows immediately.

Denote by K_{n} ⊗ P_{l} the graph obtained from the complete graph on n vertices by subdividing each edge by l − 1 intermediate vertices of degree two. Thus each edge of K_{n} becomes in K_{n} ⊗ P_{l} a copy of the l-path P_{l}. We refer to the vertices of degree n − 1 as exterior vertices and those of degree two as interior. (Assume n > 3 to avoid trivialities.) We remark that this construction is just the “l-stretch”, used in related situations by Jaeger, Vertigan and Welsh [6]. The l-stretch operation allows us to move between different edge weights, at least if we forget for a moment the specific dynamics imposed by the Swendsen-Wang process.

Lemma 5 Consider a randomly sampled configuration of the 3-state Potts model on K_{n}⊗P_{l} with edge weight λ. The induced distribution of colours on the exterior vertices of K_{n} ⊗ P_{l} is identical to the distribution of configurations of the 3-state Potts model on K_{n} with edge weight λ̂, where λ̂ = λ̂(l) is as in (5).

Proof. Suppose σ is any Potts configuration on the graph K_{n} ⊗ P_{l}, and S is any subset of its vertices. Denote by σ|_{S} ∈ {0, 1, 2}^{|S|} the restriction of σ to the set S. Through some elementary algebraic manipulation, we may express the partition function of a Potts system on K_{n} ⊗ P_{l} in terms of the partition function of a Potts system on K_{n} with edge weight closer to 1. In the following manipulation, we assume that the vertices of K_{n} ⊗ P_{l} are numbered 0, …, N − 1 and that the exterior vertices receive numbers in the range 0, …, n − 1. Furthermore, U_{ij} ⊂ [N] denotes the set of l − 1 interior vertices lying on the l-path between exterior vertices i and j, and E_{ij} denotes the set of edges on that path.

Z(K_{n} ⊗ P_{l}, λ)

= ∑_{σ} ∏_{uv∈E} λ^{[1−δ(σ(u),σ(v))]}

= ∑_{σ|_{[n]}} ∑_{σ|_{U_{0,1}}} ⋯ ∑_{σ|_{U_{n−2,n−1}}} ( ∏_{uv∈E_{0,1}} λ^{[1−δ(σ(u),σ(v))]} ⋯ ∏_{uv∈E_{n−2,n−1}} λ^{[1−δ(σ(u),σ(v))]})

= ∑_{σ|_{[n]}} ( ∑_{σ|_{U_{0,1}}} ∏_{uv∈E_{0,1}} λ^{[1−δ(σ(u),σ(v))]}) ⋯ ( ∑_{σ|_{U_{n−2,n−1}}} ∏_{uv∈E_{n−2,n−1}} λ^{[1−δ(σ(u),σ(v))]})

= ∑_{σ|_{[n]}} ∏_{0≤i<j≤n−1} C λ̂^{[1−δ(σ(i),σ(j))]}

= C^{n(n−1)/2} Z(K_{n}, λ̂),

where C is a constant (actually w_{0}^{(l)}). The penultimate equality above uses Lemma 4.

Let σ̂ ∈ {0, 1, 2}^{n} be any configuration on K_{n}. From the above manipulation, we see that the weight of the configuration σ̂ on K_{n} is equal—modulo the constant factor C^{n(n−1)/2}—to the sum of the weights of configurations σ of K_{n} ⊗ P_{l} that agree with σ̂ on the exterior vertices or, symbolically, σ|_{[n]} = σ̂.

Lemma 6 There exists an infinite sequence of pairs (n, l) = {(n(l), l) : l = 1, 2, …} such that

|(1 − λ̂(l)) − \frac{4 ln 2}{n(l)}| ≤ \frac{3}{n(l)^{2}}

for all pairs, where λ̂(l) is defined as in (5).

Proof. The function 1 − λ̂(l) decreases monotonically to 0, as l → ∞. Given l, choose n to be the unique natural number satisfying

\frac{4 ln 2}{n(l) + 1} < 1 − λ̂(l) ≤ \frac{4 ln 2}{n(l)}.

The upper and lower bounds differ by less than 3n(l)^{−2}.

Let Ω be the set of configurations of the 3-state Potts model on K_{n} ⊗ P_{l}. For each configuration σ ∈ Ω, define γ(σ) ∈ ℝ^{3} be the 3-vector whose ith component is the proportion of exterior vertices of K_{n} ⊗ P_{l} given colour i by σ. Then let Ω_{1:1:1}(ε) (respectively, Ω_{4:1:1}(ε)) denote the set of configurations σ such that γ(σ) lies within an ε-ball centred at (\frac{1}{3}, \frac{1}{3}, \frac{1}{3}) (respectively, one of the three ε-balls centred at (\frac{2}{3}, \frac{1}{6}, \frac{1}{6}), (\frac{1}{6}, \frac{2}{3}, \frac{1}{6}), or (\frac{1}{6}, \frac{1}{6}, \frac{2}{3})).

Lemma 7 Let a configuration σ be sampled from the 3-state Potts model on K_{n} ⊗ P_{l} with edge weight λ, and suppose that 1 − λ̂(l) = (4 ln 2)/n + O(n^{−2}). Then, for any ε > 0:

(i) Pr(σ ∈ Ω_{1:1:1}(ε)) = Ω(n^{−2});

(ii) Pr(σ ∈ Ω_{4:1:1}(ε)) = Ω(n^{−2}); and

(iii) Pr(σ ∉ Ω_{1:1:1}(ε) ∪ Ω_{4:1:1}(ε)) = e^{−Ω(n)}.

The implicit constants depend only on ε.

Proof. By Lemma 4, we may equivalently work with the Potts model on K_{n} with edge weight λ̂(l).

When 1 − λ̂(l) = (4 ln 2)/n, i.e., the error term is 0, this is precisely the result of Gore and Jerrum [5, Prop 3]. See also Bollobás, Grimmett and Janson [1]. The validity of the proof given in [5] is unaffected by the error term: an additive error O(n^{−2}) in λ̂(l) translates to an additive perturbation O(n^{−1}) in the function f in [5, eq. (2)]. This perturbation may be absorbed into the error term Δ appearing in that equation, which is Ω(1).

We now need to compare the dynamics of the Swendsen-Wang processes on K_{n} ⊗ P_{l} and K_{n}, more precisely, the Markov chains M_{SW}(K_{n} ⊗ P_{l}, λ) and M_{SW}(K_{n}, λ̂). The correspondence will not be exact, as in Proposition 3, but it will be close enough for our purposes.

Let G_{ν,p} denote the standard random graph model in which an undirected ν-vertex graph is formed by adding, independently with probability p, for each unordered pair of vertices (i, j), an edge connecting i and j. Suppose that p < d/ν, with d < 1 a constant, and Γ is selected according to the model G_{ν,p}. It is a classical result that, with probability tending to 1 as ν → ∞, the connected components of Γ all have size O(log ν). We require a (fairly crude) large deviation version of this result.

Lemma 8 Let Γ be selected according to the model G_{ν,p}, where p < d/ν and 0 < d < 1 is a constant. Then the probability that Γ contains a component of size exceeding \sqrt{ν} is exp(−Ω(\sqrt{ν})).

Proof. This result in exactly this form appears as [5, Lemma 4]. See O’Connell [14, Thm 3.1] for a much more precise large-deviation result for the “giant component” of a sparse random graph.

We also need:

Lemma 9 (Hoeffding) Let Z_{1}, …, Z_{s} be independent r.v’s with a_{i} ≤ Z_{i} ≤ b_{i}, for suitable constants a_{i}, b_{i}, and all 1 ≤ i ≤ s. Also let Ẑ = ∑_{i=1}^{s} Z_{i}. Then for any t > 0,

Pr (|Ẑ − Exp Ẑ| ≥ t) ≤ exp(−2t^{2} / ∑_{i=1}^{s}(b_{i} − a_{i})^{2})

Proof. See McDiarmid [11, Thm 5.7].

Lemma 10 Let a configuration σ ∈ Ω be sampled from the 3-state Potts model on K_{n} ⊗ P_{l} with edge weight λ, and suppose that 1 − λ̂(l) = (4 ln 2)/n + O(n^{−2}). Let σ′ ∈ Ω be the result of applying one step of the Swendsen-Wang process, starting at σ. Then, for any ε > 0,

Pr(σ′ ∈ Ω_{1:1:1}(ε) | σ ∈ Ω_{1:1:1}(ε)) = 1 − e^{−Ω(\sqrt{n})},

and

Pr(σ′ ∈ Ω_{4:1:1}(ε) | σ ∈ Ω_{4:1:1}(ε)) = 1 − e^{−Ω(\sqrt{n})}.

The implicit constants depend only on ε.

Proof. For i, j exterior vertices of K_{n} ⊗ P_{l} satisfying σ(i) = σ(j).

Pr(Path i ↔ j is monochromatic) = \frac{1}{w_{0}^{(l)}} = \frac{3}{(1 + 2λ)^{l} + 2(1 − λ)^{l}} ,

where the second equality is from (6). After step (SW1),

Pr(Path i ↔ j is contained in A)

= Pr(Path i ↔ j is monochromatic) × (1 − λ)^{l}

= \frac{3(1 − λ)^{l}}{(1 + 2λ)^{l} + 2(1 − λ)^{l}}

= 1 − λ̂(l).

For convenience, set p̂ = 1 − λ̂(l). Consider the set of exterior vertices of some given colour, and let ν ≤ (\frac{1}{3} + ε)n be the size of that set. Provided ε is small enough (ε = 1/40 will do), p̂ν ≤ d < 1. By Lemma 8, with probability 1 − exp(−Ω(\sqrt{ν})), the maximum number of exterior vertices in any connected component of the graph ([N], A) restricted to this colour-class is at most \sqrt{ν}. (Recall that [N] is the vertex set of K_{n} ⊗ P_{l}.) Combining this observation for all three colours, and noting ν = Θ(n), we obtain the following: with probability 1 − exp(−Ω(\sqrt{n})), the number of external vertices in any connected component of ([N], A) is at most \sqrt{n}.

Let s be the number of such components, and n_{1}, …, n_{s} be their respective sizes. The expected size of a colour-class constructed in step (SW2) is n/3, and because there are many components (at least \sqrt{n}) we expect the actual size of each colour-class to be close to the expectation. We quantify this intuition by appealing to the Hoeffding bound. Fix a colour, say 0, and define the random variables Y_{1}, …, Y_{s} and Ŷ by

Y_{i} = \{ \begin{matrix}n_{i}, & if the ith component receives colour 0 in step (SW2); \\ 0, & otherwise, \end{matrix}

and Ŷ = ∑_{i=1}^{s} Y_{i}. Then Exp Ŷ = n/3 and, by Lemma 9, for any t > 0,

Pr (|Ŷ − Exp Ŷ| ≥ t) ≤ exp(−2t^{2} / ∑_{i=1}^{s} n_{i}^{2})
≤ exp(−2t^{2}n^{−3/2}),

since

∑_{i=1}^{s} n_{i}^{2} ≤ ∑_{i=1}^{s} n_{i}\sqrt{n} = n^{3/2}.

Similar bounds apply, of course, to the other colours. Choosing t = εn/\sqrt{3} we see that, with probability 1−exp(−Ω(\sqrt{n})), the size of every colour class in σ′ lies in the range ((\frac{1}{3} − ε/\sqrt{3} )n, (\frac{1}{3} + ε/\sqrt{3} )n); but this condition implies σ′ ∈ Ω_{1:1:1}(ε).

This proves the first part of the result, concerning Ω_{1:1:1}(ε); the second part follows from the first by Proposition 7 and time-reversibility. In particular, it follows from the fact that M_{SW} satisfies the detailed balance condition:

Pr(σ = σ_{1} ∧ σ′ = σ_{2}) = Pr(σ = σ_{2} ∧ σ′ = σ_{1}),

for all configurations σ_{1} and σ_{2}, where σ is sampled from the stationary distribution.

It is now a short step to the main theorem. Recall that τ(\frac{1}{3}) denotes the number of steps t before the t-step distribution is within variation distance \frac{1}{3} of the stationary distribution (maximised over the choice of starting state).

Theorem 11 Let Σ be a finite alphabet of size at least two. There exists an infinite family of permutation groups G such that the mixing time of the Burnside process M_{B}(G, Σ) is exponential in the degree m of G; specifically τ(1/3) = Ω(exp(m^{1/(4+ε)})) for any ε > 0.

Proof. By Proposition 3, it is enough to exhibit an infinite family of graphs Γ such that M_{SW}(Γ , λ) has exponential mixing time, where λ = k^{−2}. This family of graphs will of course be (K_{n(l)} ⊗ P_{l} : l ∈ ℕ) where n(l) is as defined in lemma 6. The family of permutation groups promised by the theorem will then be (G_{3}(K_{n(l)} ⊗ P_{l}) : l ∈ ℕ).

Consider a trajectory (σ_{t} : t ∈ ℕ) of M_{SW}(K_{n}⊗P_{l}, λ) starting in the stationary distribution. We say that the trajectory escapes at step t if

(σ_{t} ∈ Ω_{1:1:1}(ε) ∧ σ_{t+1} ∉ Ω_{1:1:1}(ε)) ∨ (σ_{t} ∈ Ω_{4:1:1}(ε) ∧ σ_{t+1} ∉ Ω_{4:1:1}(ε)).

For each t, by Proposition 10, the probability of escape at time t is bounded by exp(−Ω(\sqrt{n})). Furthermore, by Proposition 7 the probability of the event

σ_{0} ∉ Ω_{1:1:1}(ε) ∪ Ω_{4:1:1}(ε)

is also bounded by exp(−Ω(\sqrt{n})).

Thus there is a function T = T (n) = exp(Ω(\sqrt{n})) such that, with probability at least \frac{9}{10}, the initial segment of the trajectory (σ_{t} : 0 ≤ t ≤ T) lies either entirely within Ω_{1:1:1}(ε) or entirely within Ω_{4:1:1}(ε). Hence there is an initial state s ∈ Ω_{1:1:1}(ε) such that Pr(σ_{T} ∉ Ω_{1:1:1}(ε) | σ_{0} = s) ≤ \frac{1}{10}, and similarly for s ∈ Ω_{4:1:1}(ε). Choose such an initial state s from whichever of Ω_{1:1:1}(ε) or Ω_{4:1:1}(ε) has the smaller total weight in the stationary distribution. Then the variation distance of the T -step distribution from the stationary distribution is at least \frac{1}{2} − e^{−Ω(n)} − \frac{1}{10} ≥ \frac{1}{3}. Finally note that m = O(n^{2}l) = O(n^{2} log n). (It is straightforward to see from Lemma 6 that l = O(log n).)

Although the definition of τ contains an existential quantification over initial states, it will be seen that Theorem 11 is not very sensitive to the initial state: τ(\frac{1}{3}) can be replaced by τ_{s}(\frac{1}{3}), where s ranges over almost every state in Ω_{1:1:1}(ε) or Ω_{4:1:1}(ε), as appropriate (“almost every” being interpreted with respect to the stationary distribution).

6 Open problems

In this paper, we have shown that the Burnside process is not rapidly mixing in general. It remains an open question whether there is some other polynomialtime method which achieves the same distribution as the Burnside process, either on permutations (as in Lemma 1) or on words (as in Lemma 2). Since (B1) is easy to implement in polynomial-time, a polynomial-time sampling algorithm for the stationary distribution π of Lemma 1 would yield a polynomial-time sampler for the stationary distribution π′ of Lemma 2 (i.e., the uniform distribution on orbits). If there is a polynomial-time sampling algorithm for the distribution π this will imply [8] that there is a fully polynomial randomised approximation scheme for the single-variable cycle index polynomial for every integer k (see [2]). Such a result would be a striking contrast to the result of the authors (see [4]) which shows that, unless NP = RP, no such approximation algorithm exists for any fixed rational non-integer k.

References

[1] B. Bollobás, G. Grimmett and S. Janson, The random-cluster model on the complete graph, Probability Theory and Related Fields 104 (1996), 283–317.

[2] N. G. de Bruijn, Pólya’s theory of counting, in Applied Combinatorial Mathematics (E. F. Beckenbach, ed.), John Wiley and Sons, 1964, 144–184.

[3] R. G. Edwards and A. D. Sokal, Generalizations of the Fortuin-Kasteleyn-Swendsen-Wang representation and Monte Carlo algorithm, Physical Review D 38 (1988), 2009–2012.

[4] Leslie Ann Goldberg, Automating Pólya theory: the computational complexity of the cycle index polynomial, Information and Computation 105 (1993), 268–288.

[5] Vivek Gore and Mark Jerrum, The Swendsen-Wang process does not always mix rapidly, Proceedings of the 29th ACM Symposium on Theory of Computation (STOC), ACM Press, 1997, 674–681. (Theorem numbers cited here are from the proceedings version, not from the Edinburgh University technical report version (ECS-LFCS-96-349, 1996).)

[6] F. Jaeger, D. L. Vertigan, and D. J. A. Welsh, On the computational complexity of the Jones and Tutte polynomials, Mathematical Proceedings of the Cambridge Philosophical Society 108 (1990), 35–53.

[7] Mark Jerrum, Uniform sampling modulo a group of symmetries using Markov chain simulation. In “Expanding Graphs” (Joel Friedman, ed.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science 10, American Mathematical Society, 1993, 37–47.

[8] Mark Jerrum, Computational Pólya theory. In “Surveys in Combinatorics 1995,” London Mathematical Society Lecture Note Series 218, Cambridge University Press, 1995, 103–118.

[9] Mark Jerrum and Alistair Sinclair, The Markov chain Monte Carlo method: an approach to approximate counting and integration. In Approximation Algorithms for NP-hard Problems (Dorit Hochbaum, ed.), PWS, 1996, 482–520.

[10] Eugene M. Luks, Isomorphism of graphs of bounded valence can be tested in polynomial time, Journal of Computer and System Sciences 25 (1982), 42–65.

[11] Colin McDiarmid, On the method of bounded differences, London Mathematical Society Lecture Note Series 141, Cambridge University Press, 1989, 148–188.

[12] Paul Martin, Potts Models and Related Problems in Statistical Mechanics, World Scientific, Singapore, 1991.

[13] P. M. Neumann, A lemma that is not Burnside’s, Mathematical Scientist 4 (1979), 133–141.

[14] Neil O’Connell, Some large deviation results for sparse random graphs, Probability Theory and Related Fields 110 (1998), 277–285.

[15] Leonard Soicher, personal communication.

[16] N.C. Wormald, Generating random unlabelled graphs, SIAM Journal of Computing 16 (1987) 717–727.