I’ve just arXived another revision of my paper on the PFAB algorithm: arXiv:1503.08066v3 [stat.CO]. It includes a rather elegant proof of the exact mean and variance of the sufficient statistic S(z) in the hottest state, when the inverse temperature β=0. The proof by my co-author Geoff Nicholls holds for any Potts model with first-order neighbours. That is, the nearest 4 neighbours in a 2D lattice (or 6 neighbours in 3D). For posterity, I present my rather clunkier proof below, which involves induction on dimension for a rectangular lattice.
The Potts (1952) model is an example of a Gibbs random field on a regular lattice, where each node yi can take values in the set {1,…,q}. The Ising model can be viewed as a special case, when q=2. The size of the configuration space |Y| is therefore qn, where n is the number of nodes. The dual lattice E defines undirected edges between neighbouring nodes i∼ℓ. If the nodes in a 2D lattice with c columns are indexed row-wise, the nearest (first-order) neighbours ∂(i) are ℓ∈{i−1,i−c,i+c,i+1}, except at the boundary. Nodes situated on the boundary of the domain have less than four neighbours. The total number of unique edges is thus #E=2(n−√n) for a square lattice, or 2n−r−c if the lattice is rectangular.
The sufficient statistic of the Potts model is the sum of all like neighbour pairs: S(y)=∑i∼ℓ∈Eδ(yi,yℓ) where δ(a,b) is the Kronecker delta function, which equals 1 if a=b and equals 0 otherwise. S(y) ranges from 0, when all of the nodes form a chequerboard pattern, to #E when all of the nodes have the same value. The likelihood of the Potts model is thus: p(y∣β)=exp{βS(y)−logC(β)} The normalising constant of the Potts model is intractable for any non-trivial lattice, since it requires a sum over the configuration space: C(β)=∑y∈Yexp{βS(y)}When the inverse temperature β=0, p(y∣β=0) simplifies to (∑y∈Yexp{0})−1=q−n, hence the labels yi are independent and uniformly-distributed.
Theorem 1
The sum over configuration space of the sufficient statistic of the q-state Potts model on a rectangular 2D lattice is ∑y∈Y∑i∼ℓ∈Eδ(yi,yℓ)=qn−1#E.
Proof
For a q=2 state Potts model on a lattice with n=4 nodes and #E=4 edges, Y contains 16 possible configurations: ∑y∈YS(y)=2×4+12×2+2×0=32. This can also be written as 23×4=32.
Now consider a rectangular lattice with r>1 rows and c>1 columns, so that n∘=r×c and the dual lattice #E∘=2r⋅c−r−c. The size of the configuration space is |Y∘|=qn∘. Assume that the sum over configuration space is equal to qn∘−1#E∘. This sum can be decomposed into (qc)rr(c−1)/q within each row, plus (qc)rc(r−1)/q between rows.
If this lattice is extended by adding another row (or equivalently, another column), then n′=n∘+c (or otherwise, n′=n∘+r) and the dual lattice #E′=2(n∘+c)−r−c−1=#E∘+2c−1. The nodes in this new row can take qc possible values, so the size of the configuration space is now |Y′|=qcqn∘=qn′. ∑y∈Y′S(y) will increase proportional to r+1rqc for the new row, plus rr−1qc for the connections with its adjacent row: ∑y∈Y′S(y)=r+1rqc(qc)rrq(c−1)+rr−1qc(qc)rcq(r−1)=r+1q(qc)r+1(c−1)+rcq(qc)r+1=qrc+c−1(2rc+c−r−1)=qn∘+c−1(#E∘+2c−1)=qn′−1#E′Q.E.D.
Theorem 2
The expectation of the q-state Potts model on a rectangular 2D lattice is Ey|β=0[S(y)]=#E/q when the inverse temperature β=0.
Proof
The proof follows from Theorem 1 by noting that p(y|β=0)=q−n and hence: Ey|β=0[S(y)]=∑y∈YS(y)p(y∣β=0)=qn−1#Eq−n=#EqQ.E.D.
Theorem 3
The sum over configuration space of the square of the sufficient statistic of the q-state Potts model on a rectangular 2D lattice is ∑y∈YS(y)2=qn#E(q−2#E+q−1(1−q−1)).
Proof
For a q=2 state Potts model on a lattice with n=4 nodes and #E=4 edges, ∑y∈YS(y)2=2×42+12×22+2×02=80. This can also be written as 24×4(4/22+0.5(1−0.5))=26(1+0.25)=80.
Now assume for a rectangular lattice with r>1 rows and c>1 columns that ∑y∈Y∘S(y)2=qrc−2(2rc−r−c)2+qrc−1(1−1q)(2rc−r−c). This can be decomposed into ((qc)rr(c−1)/q+(qc)rc(r−1)/q)2+(qc)r(1−q−1)(2rc−r−c)/q. If we extend the lattice by adding another row, then ∑y∈Y′S(y)2=(r+1q(qc)r+1(c−1)+rcq(qc)r+1)2+(qc)r+1(1−q−1)(2rc−r+c−1)q=(qn∘+c−1(#E∘+2c−1))2+qn∘+c−1(1−q−1)(#E∘+2c−1)=(qn′−1#E′)2+qn′−1(1−q−1)#E′=qn′#E′(q−2#E′+q−1(1−q−1))Q.E.D.
Theorem 4
The variance of the q-state Potts model on a rectangular 2D lattice is Vy|β=0[S(y)]=I(0)=#Eq−1(1−q−1) when the inverse temperature β=0.
Proof
The proof follows from Theorems 1 and 3: Vy|β=0[S(y)]=Ey|β=0[S(y)2]−Ey|β=0[S(y)]2=∑y∈YS(y)2p(y∣β=0)−(#Eq)2=qn#E(q−2#E+q−1(1−q−1))q−n−#E2q2=#E2q2+#Eq−1(1−q−1)−#E2q2=#Eq−1(1−q−1)Q.E.D.