14 Interacting Particles on Finite Graphs (March 10, 1994)

14.4 The antivoter model

Recall from section 14.3 the definition of the voter model on a rr-regular nn-vertex graph. We now change this in two ways. First, we suppose there are only two different opinions, which it is convenient to call ±1\pm 1. Second, the evolution rule is

For each person ii and each time interval [t,t+dt][t,t+dt], with chance dtdt the person chooses uniformly at random a neighbor (jj, say) and changes (if necessary) their opinion to the opposite of the opinion of person jj.

The essential difference from the voter model is that opinions don’t disappear. Writing ηv(t)\eta_{v}(t) for the opinion of individual vv at time tt, the process η(t)=(ηv(t),vG)\eta(t)=(\eta_{v}(t),v\in G) is a continuous-time Markov chain on state-space {-1,1}G\{-1,1\}^{G}. So, provided this chain is irreducible, there is a unique stationary distribution (ηv,vG)(\eta_{v},v\in G) for the antivoter model.

This model on infinite lattices was studied in the “interacting particle systems” literature [173, 232], and again the key idea is duality. In this model the dual process consists of annihilating random walks. We will not go into details about the duality relation, beyond the following definition we need later. For vertices v,wv,w, consider independent continuous-time random walks started at vv and at ww. We have previously studied Mv,wM_{v,w}, the time at which the two walks first meet, but now we define Nv,wN_{v,w} to be the total number of jumps made by the two walks, up to and including the time Mv,wM_{v,w}. Set Nv,v=0N_{v,v}=0.

Donnelly and Welsh [129] considered our setting of a finite graph, and showed that Proposition 14.19 is a simple consequence of the duality relation.

Proposition 14.19

The antivoter process has a unique stationary distribution (ηv)(\eta_{v}), which satisfies

(i) Eηv=0E\eta_{v}=0

(ii) c(v,w)Eηvηw=P(Nv,w is even )-P(Nv,w is odd ).c(v,w)\equiv E\eta_{v}\eta_{w}=P(N_{v,w}\mbox{ is even })-P(N_{v,w}\mbox{ is % odd }).

If GG is neither bipartite nor the nn-cycle, then the set of all 2n-22^{n}-2 non-unanimous configurations is irreducible, and the support of the stationary distribution is that set.

In particular, defining


so that SS or -S-S is the “margin of victory” in an election, we have ES=0ES=0 and

varS=vwc(v,w).{\rm var}\ \ S=\sum_{v}\sum_{w}c(v,w). (14.19)

On a bipartite graph with bipartition (A,Ac)(A,A^{c}) the stationary distribution is

P(ηv=1vA,ηv=-1vAc)=P(ηv=-1vA,ηv=1vAc)=1/2P(\eta_{v}=1\forall v\in A,\eta_{v}=-1\forall v\in A^{c})=P(\eta_{v}=-1\forall v% \in A,\eta_{v}=1\forall v\in A^{c})=1/2

and c(v,w)=-1c(v,w)=-1 for each edge. Otherwise c(v,w)>-1c(v,w)>-1 for every edge.

The antivoter process is in general a non-reversible Markov chain, because it can transition from a configuration in which vv has the same opinion as all its neighbors to the configuration where vv has the opposite opinion, but the reverse transition is impossible. Nevertheless we could use duality to discuss convergence time. But, following [129], the spatial structure of the stationary distribution is a more novel and hence more interesting question. Intuitively we expect neighboring vertices to be negatively correlated and the variance of SS to be smaller than nn (the variance if opinions were independent). In the case of the complete graph on nn vertices, Nv,wN_{v,w} has (for wvw\neq v) the geometric distribution

P(Nv,w>m)=(1-1n-1)m;m0P(N_{v,w}>m)=\left(1-\frac{1}{n-1}\right)^{m};m\geq 0

from which we calculate c(v,w)=-1/(2n-3)c(v,w)=-1/(2n-3) and varS=n(n-2)2n-3<n/2{\rm var}\ \ S=\frac{n(n-2)}{2n-3}<n/2. We next investigate varS{\rm var}\ \ S in general.

14.4.1 Variances in the antivoter model

Write ξ=(ξv)\xi=(\xi_{v}) for a configuration of the antivoter process and write

a(ξ)= number of edges (v,w)(v,w) with ξv=ξw=1a(\xi)=\mbox{ number of edges $(v,w)$ with }\xi_{v}=\xi_{w}=1
b(ξ)= number of edges (v,w)(v,w) with ξv=ξw=-1.b(\xi)=\mbox{ number of edges $(v,w)$ with }\xi_{v}=\xi_{w}=-1.

A simple counting argument gives

2(a(ξ)-b(ξ))=rS(ξ).2(a(\xi)-b(\xi))=rS(\xi). (14.20)
Lemma 14.20

varS=2rE(a(η)+b(η)){\rm var}\ \ S=\frac{2}{r}E(a(\eta)+b(\eta)), where η\eta is the stationary distribution.

Proof. Writing (ηt)(\eta_{t}) for the stationary process and dSt=S(ηt+dt)-S(ηt)dS_{t}=S(\eta_{t+dt})-S(\eta_{t}), we have

P(dSt=+2|ηt)=b(ηt)dt\displaystyle P(dS_{t}=+2|\eta_{t})=b(\eta_{t})dt
P(dSt=-2|ηt)=a(ηt)dt\displaystyle P(dS_{t}=-2|\eta_{t})=a(\eta_{t})dt

and so

0\displaystyle 0 =\displaystyle= ES2(ηt+dt)-ES2(ηt) by stationarity\displaystyle ES^{2}(\eta_{t+dt})-ES^{2}(\eta_{t})\mbox{ by stationarity}
=\displaystyle= 2ES(ηt)dSt+E(dSt)2\displaystyle 2ES(\eta_{t})dS_{t}\ +E(dS_{t})^{2}
=\displaystyle= 4ES(ηt)(b(ηt)-a(ηt))dt+4E(a(ηt)+b(ηt))dt\displaystyle 4ES(\eta_{t})(b(\eta_{t})-a(\eta_{t}))dt\ +4E(a(\eta_{t})+b(\eta% _{t}))dt
=\displaystyle= -2rES2(ηt)dt+4E(a(ηt)+b(ηt))dt by (14.20)\displaystyle-2rES^{2}(\eta_{t})dt+4E(a(\eta_{t})+b(\eta_{t}))dt\mbox{ by }(% \ref{abrS})

establishing the Lemma.

Since the total number of edges is nr/2nr/2, Lemma 14.20 gives the upper bound which follows, and the lower bound is also clear.

Corollary 14.21

Let κ=κ(G)\kappa=\kappa(G) be the largest integer such that, for any subset AA of vertices, the number of edges with both ends in AA or both ends in AcA^{c} is at least κ\kappa. Then

2κrvarSn.\frac{2\kappa}{r}\leq{\rm var}\ \ S\leq n.

Here κ\kappa is a natural measure of “non-bipartiteness” of GG. We now show how to improve the upper bound by exploiting duality. One might expect some better upper bound for “almost-bipartite” graphs, but Examples 14.27 and 14.28 indicate this may be difficult.

Proposition 14.22

varS<n/2{\rm var}\ \ S<n/2.

Proof. Take two independent stationary continuous-time random walks on the underlying graph GG, and let (Xt(1),Xt(2);t=,-1,0,1,2,)(X^{(1)}_{t},X^{(2)}_{t};t=\ldots,-1,0,1,2,\ldots) be the jump chain, i.e. at each time we choose at random one component to make a step of the random walk on the graph. Say an “event’ happens at tt if Xt(1)=Xt(2)X^{(1)}_{t}=X^{(2)}_{t}, and consider the inter-event time distribution LL:


In the special case where GG is vertex-transitive the events form a renewal process, but we use only stationarity properties (c.f. Chapter 2 yyy) which hold in the general case. Write

T=min{t0:Xt(1)=Xt(2)}T=\min\{t\geq 0:X^{(1)}_{t}=X^{(2)}_{t}\}

where the stationary chain is used. Then

Pv,w(T=t)P(T=t|X0(1)=v,X0(2)=w)=P(Nv,w=t)P_{v,w}(T=t)\equiv P(T=t|X^{(1)}_{0}=v,X^{(2)}_{0}=w)=P(N_{v,w}=t)

and so by (14.19) and Proposition 14.19(ii),

varS\displaystyle{\rm var}\ \ S =\displaystyle= vw(Pv,w(T is even)-Pv,w(T is odd))\displaystyle\sum_{v}\sum_{w}(P_{v,w}(T\mbox{ is even})-P_{v,w}(T\mbox{ is odd% }))
=\displaystyle= n2(P(T is even)-P(T is odd)).\displaystyle n^{2}(P(T\mbox{ is even})-P(T\mbox{ is odd})).

If successive events occur at times t0t_{0} and t1t_{1}, then

|{s:t0<st1:t1-s is even }|-{s:t0<st1:t1-s is odd}|\displaystyle|\{s:t_{0}<s\leq t_{1}:t_{1}-s\mbox{ is even }\}|-\{s:t_{0}<s\leq t% _{1}:t_{1}-s\mbox{ is odd}\}| =\displaystyle= 0 if |t1-t0||t_{1}-t_{0}| is even\displaystyle 0\mbox{ if $|t_{1}-t_{0}|$ is even}
=\displaystyle= 1 if |t1-t0||t_{1}-t_{0}| is odd\displaystyle 1\mbox{ if $|t_{1}-t_{0}|$ is odd}

and an ergodic argument gives

P(T is even)-P(T is odd)=P(L is odd)/EL.P(T\mbox{ is even})-P(T\mbox{ is odd})=P(L\mbox{ is odd})/EL.

But EL=1/P(event)=nEL=1/P(\mbox{event})=n, so we have established

Lemma 14.23

n-1varS=P(L is odd)n^{-1}{\rm var}\ \ S=P(L\mbox{ is odd}).

Now consider

T-=min{t0:X-t(1)=X-t(2)}.T^{-}=\min\{t\geq 0:X^{(1)}_{-t}=X^{(2)}_{-t}\}.

If successive events occur at t0t_{0} and t1t_{1}, then there are t1-t0-1t_{1}-t_{0}-1 times ss with t0<s<t1t_{0}<s<t_{1}, and another ergodic argument shows

P(T+T-=l)=(l-1)P(L=l)EL,l2.P(T+T^{-}=l)=\frac{(l-1)P(L=l)}{EL},\ l\geq 2.


n-1(P(L is even)-P(L is odd))\displaystyle n^{-1}(P(L\mbox{ is even})-P(L\mbox{ is odd})) =\displaystyle= 1ELl2(-1)lP(L=l) since EL=n\displaystyle\frac{1}{EL}\sum_{l\geq 2}(-1)^{l}P(L=l)\mbox{ since }EL=n (14.21)
=\displaystyle= l2(-1)ll-1P(T+T-=l).\displaystyle\sum_{l\geq 2}\frac{(-1)^{l}}{l-1}P(T+T^{-}=l).

Now let ϕ(z)\phi(z) be the generating function of a distribution on {1,2,3,}\{1,2,3,\ldots\} and let Z,Z-Z,Z^{-} be independent random variables with that distribution. Then

l2(-1)ll-1P(Z+Z-=l)=-10ϕ2(z)z2dz>0.\sum_{l\geq 2}\frac{(-1)^{l}}{l-1}P(Z+Z^{-}=l)=\int_{-1}^{0}\frac{\phi^{2}(z)}% {z^{2}}\ dz>0. (14.22)

Conditional on (X0(1),X0(2))=(v,w)(X^{(1)}_{0},X^{(2)}_{0})=(v,w) with wvw\neq v, we have that TT and T-T^{-} are independent and identically distributed. So the sum in (14.21) is positive, implying P(L is odd)<1/2P(L\mbox{ is odd})<1/2, so the Proposition follows from the Lemma.

Implicit in the proof are a corollary and an open problem. The open problem is to show that varS{\rm var}\ \ S is in fact maximized on the complete graph. This might perhaps be provable by sharpening the inequality in (14.22).

Corollary 14.24

On an edge-transitive graph, write c𝑒𝑑𝑔𝑒=c(v,w)=Eηvηwc_{\mbox{edge}}=c(v,w)=E\eta_{v}\eta_{w} for an arbitrary edge (v,w)(v,w). Then

varS=n(1+c𝑒𝑑𝑔𝑒)/2{\rm var}\ \ S=n(1+c_{\mbox{edge}})/2

Proof. In an edge-transitive graph, conditioning on the first jump from (v,v)(v,v) gives

P(L is odd)=P(Nv,w is even)P(L\mbox{ is odd})=P(N_{v,w}\mbox{ is even})

for an edge (v,w)(v,w). But P(Nv,w is even )=(1+cedge)/2P(N_{v,w}\mbox{ is even })=(1+c_{\mbox{edge}})/2 by Proposition 14.19(ii), so the result follows from Lemma 14.23 and Proposition 14.22.

14.4.2 Examples and Open Problems

In the case of the complete graph, the number of +1+1 opinions evolves as the birth-and-death chain on states {1,2,,n-1}\{1,2,\ldots,n-1\} with transition rates

ii+1\displaystyle i\rightarrow i+1 rate (n-i)(n-1-i)n(n-1)\displaystyle\mbox{rate }\frac{(n-i)(n-1-i)}{n(n-1)}
i-1\displaystyle\rightarrow i-1 rate i(i-1)n(n-1)\displaystyle\mbox{rate }\frac{i(i-1)}{n(n-1)}

From the explicit form of the stationary distribution we can deduce that as nn\rightarrow\infty the asymptotic distribution of SS is Normal. As an exercise in technique (see Notes) we ask

Open Problem 14.25

Find sufficient conditions on a sequence of graphs which imply SS has asymptotic Normal distribution.

Example 14.26

Distance-regular graphs.

On a distance-regular graph of diameter Δ\Delta, define 1=f(0),f(1),,f(Δ)1=f(0),f(1),\ldots,f(\Delta) by

f(i)=c(v,w)=P(Nv,w is even )-P(Nv,w is odd ), where d(x,y)=i.f(i)=c(v,w)=P(N_{v,w}\mbox{ is even })-P(N_{v,w}\mbox{ is odd }),\mbox{ where % }d(x,y)=i.

Conditioning on the first step of the random walks,

f(i)=-(pi,i+1f(i+1)+pi,if(i)+pi,i-1f(i-1)), 1iΔf(i)=-\left(p_{i,i+1}f(i+1)+p_{i,i}f(i)+p_{i,i-1}f(i-1)\right),\ 1\leq i\leq\Delta (14.23)

where (c.f. Chapter 7 yyy) the pi,jp_{i,j} are the transition probabilities for the birth-and-death chain associated with the discrete-time random walk. In principle we can solve these equations to determine f(1)=cedgef(1)=c_{\mbox{edge}}. Note that the bipartite case is the case where pi,i0p_{i,i}\equiv 0, which is the case where f(i)(-1)if(i)\equiv(-1)^{i} and cedge=-1c_{\mbox{edge}}=-1. A simple example of a non-bipartite distance-regular graph is the “22-subsets of a dd-set” example (Chapter 7 yyy) for d4d\geq 4. Here Δ=2\Delta=2 and

p1,0=12(d-2)\displaystyle p_{1,0}=\frac{1}{2(d-2)} p1,1=d-32(d-2)\displaystyle p_{1,1}=\frac{d-3}{2(d-2)} p1,2=d-22(d-2)\displaystyle p_{1,2}=\frac{d-2}{2(d-2)}
p2,1=42(d-2)\displaystyle p_{2,1}=\frac{4}{2(d-2)} p2,2=2d-82(d-2).\displaystyle p_{2,2}=\frac{2d-8}{2(d-2)}.

Solving equations (14.23) gives cedge=-1/(3d-7)c_{\mbox{edge}}=-1/(3d-7).

Corollary 14.24 said that in an edge-transitive graph, cedge<0c_{\mbox{edge}}<0. On a vertex-transitive graph this need not be true for every edge, as the next example shows.

Example 14.27

An almost bipartite vertex-transitive graph.

Consider the m+2m+2-regular graph on 2m2m vertices, made by taking mm-cycles (v1,,vm)(v_{1},\ldots,v_{m}) and (w1,,wm)(w_{1},\ldots,w_{m}) and adding all edges (vi,wj)(v_{i},w_{j}) between the two “classes”. One might guess that, under the stationary distribution, almost all individuals in a class would have the same opinion, different for the two classes. But in fact the tendency for agreement between individuals in the same class is bounded: as mm\rightarrow\infty

c(vi,wj)\displaystyle c(v_{i},w_{j}) \displaystyle\rightarrow -19\displaystyle-\frac{1}{9}
c(vi,vj)\displaystyle c(v_{i},v_{j}) \displaystyle\rightarrow 19,  ji.\displaystyle\frac{1}{9},\ j\neq i. (14.24)

To prove this, consider two independent continuous-time random walks, started from opposite classes. Let NN be the number of jumps before meeting and let M1M\geq 1 be the number of jumps before they are again in opposite classes. Then

P(M is odd )=4m+O(m-2);P(N<M)=1m+O(m-2).P(M\mbox{ is odd })=\frac{4}{m}+O(m^{-2});\ \ P(N<M)=\frac{1}{m}+O(m^{-2}).

So writing M1=M,M2,M3,M_{1}=M,M_{2},M_{3},\ldots for the cumulative numbers of jumps each time the two walks are in opposite components, and writing

Qmin{j:Mj is odd},Q\equiv\min\{j:M_{j}\mbox{ is odd}\},

we have

P( walks meet before Q)=15+O(m-1).P(\mbox{ walks meet before }Q)=\frac{1}{5}+O(m^{-1}).

Writing Q1=Q,Q2,Q3,Q_{1}=Q,Q_{2},Q_{3},\ldots for the sucessive jj’s at which MjM_{j} changes parity, and

Lmax{k:MQk< meeting time}L\equiv\max\{k:M_{Q_{k}}<\mbox{ meeting time}\}

for the number of parity changes before meeting,

P(L=l)=15(45)l+O(m-1),l0P(L=l)=\frac{1}{5}\left(\frac{4}{5}\right)^{l}+O(m^{-1}),\ \ l\geq 0

So P(ηvi,wj is odd)=P(L is even)59P(\eta_{v_{i},w_{j}}\mbox{ is odd})=P(L\mbox{ is even})\rightarrow\frac{5}{9} and (14.24) follows easily.

Example 14.28

Another almost-bipartite graph.

Consider the torus ZmdZ^{d}_{m} with d2d\geq 2 and with even m4m\geq 4, and make the graph non-bipartite by moving two edges as shown.

Let mm\rightarrow\infty and consider the covariance c(vm,wm)c(v_{m},w_{m}) across edges (vm,wm)(v_{m},w_{m}) whose distance from the modified edges tends to infinity. One might suspect that the modification had only “local” effect, in that c(vm,wm)-1c(v_{m},w_{m})\rightarrow-1. In fact,

c(vm,wm)\displaystyle c(v_{m},w_{m}) \displaystyle\rightarrow -1, d=2\displaystyle-1,\ \ d=2
\displaystyle\rightarrow β(d)>-1,  d3.\displaystyle\beta(d)>-1,\ d\geq 3.

We don’t give details, but the key observation is that in d3d\geq 3 there is a bounded-below chance that independent random walks started from vmv_{m} and wmw_{m} will traverse one of the modified edges before meeting.