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

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

The essential difference from the voter model is that opinions don’t disappear. Writing $\eta_{v}(t)$ for the opinion of individual $v$ at time $t$, the process $\eta(t)=(\eta_{v}(t),v\in G)$ is a continuous-time Markov chain on state-space $\{-1,1\}^{G}$. So, provided this chain is irreducible, there is a unique stationary distribution $(\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,w$, consider independent continuous-time random walks started at $v$ and at $w$. We have previously studied $M_{v,w}$, the time at which the two walks first meet, but now we define $N_{v,w}$ to be the total number of jumps made by the two walks, up to and including the time $M_{v,w}$. Set $N_{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.

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

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

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

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

In particular, defining

$S\equiv\sum_{v}\eta_{v}$ |

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

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

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

$P(\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)=-1$ for each edge. Otherwise $c(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 $v$ has the same opinion as all its neighbors to the configuration where $v$ 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 $S$ to be smaller than $n$ (the variance if opinions were independent). In the case of the complete graph on $n$ vertices, $N_{v,w}$ has (for $w\neq v$) the geometric distribution

$P(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)$ and ${\rm var}\ \ S=\frac{n(n-2)}{2n-3}<n/2$. We next investigate ${\rm var}\ \ S$ in general.

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

$S(\xi)=\sum_{v}\xi_{v}$ |

$(v,w)$ |

$(v,w)$ |

A simple counting argument gives

$2(a(\xi)-b(\xi))=rS(\xi).$ | (14.20) |

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

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

$\displaystyle P(dS_{t}=+2|\eta_{t})=b(\eta_{t})dt$ | ||

$\displaystyle P(dS_{t}=-2|\eta_{t})=a(\eta_{t})dt$ |

and so

$\displaystyle 0$ | $\displaystyle=$ | $\displaystyle ES^{2}(\eta_{t+dt})-ES^{2}(\eta_{t})\mbox{ by stationarity}$ | ||

$\displaystyle=$ | $\displaystyle 2ES(\eta_{t})dS_{t}\ +E(dS_{t})^{2}$ | |||

$\displaystyle=$ | $\displaystyle 4ES(\eta_{t})(b(\eta_{t})-a(\eta_{t}))dt\ +4E(a(\eta_{t})+b(\eta% _{t}))dt$ | |||

$\displaystyle=$ | $\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/2$, Lemma 14.20 gives the upper bound which follows, and the lower bound is also clear.

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

$\frac{2\kappa}{r}\leq{\rm var}\ \ S\leq n.$ |

Here $\kappa$ is a natural measure of “non-bipartiteness” of $G$. 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.

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

Proof. Take two independent stationary continuous-time random walks on the underlying graph $G$, and let $(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 $t$ if $X^{(1)}_{t}=X^{(2)}_{t}$, and consider the inter-event time distribution $L$:

$P(L=l)=P(\min\{t>0:X^{(1)}_{t}=X^{(2)}_{t}\}=l|X^{(1)}_{0}=X^{(2)}_{0}).$ |

In the special case where $G$ 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\{t\geq 0:X^{(1)}_{t}=X^{(2)}_{t}\}$ |

where the stationary chain is used. Then

$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),

$\displaystyle{\rm var}\ \ S$ | $\displaystyle=$ | $\displaystyle\sum_{v}\sum_{w}(P_{v,w}(T\mbox{ is even})-P_{v,w}(T\mbox{ is odd% }))$ | ||

$\displaystyle=$ | $\displaystyle n^{2}(P(T\mbox{ is even})-P(T\mbox{ is odd})).$ |

If successive events occur at times $t_{0}$ and $t_{1}$, then

$\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=$ | $|t_{1}-t_{0}|$ | ||

$\displaystyle=$ | $|t_{1}-t_{0}|$ |

and an ergodic argument gives

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

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

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

Now consider

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

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

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

So

$\displaystyle n^{-1}(P(L\mbox{ is even})-P(L\mbox{ is odd}))$ | $\displaystyle=$ | $\displaystyle\frac{1}{EL}\sum_{l\geq 2}(-1)^{l}P(L=l)\mbox{ since }EL=n$ | (14.21) | ||

$\displaystyle=$ | $\displaystyle\sum_{l\geq 2}\frac{(-1)^{l}}{l-1}P(T+T^{-}=l).$ |

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

$\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 $(X^{(1)}_{0},X^{(2)}_{0})=(v,w)$ with $w\neq v$, we have that $T$ and $T^{-}$ are independent and identically distributed. So the sum in (14.21) is positive, implying $P(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 ${\rm var}\ \ S$ is in fact maximized on the complete graph. This might perhaps be provable by sharpening the inequality in (14.22).

On an edge-transitive graph, write $c_{\mbox{edge}}=c(v,w)=E\eta_{v}\eta_{w}$ for an arbitrary edge $(v,w)$. Then

${\rm var}\ \ S=n(1+c_{\mbox{edge}})/2$ |

$c_{\mbox{edge}}<0.$ |

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

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

$\displaystyle\rightarrow i-1$ | $\displaystyle\mbox{rate }\frac{i(i-1)}{n(n-1)}$ |

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

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

Distance-regular graphs.

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

$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)=-\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 $p_{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)=c_{\mbox{edge}}$. Note that the bipartite case is the case where $p_{i,i}\equiv 0$, which is the case where $f(i)\equiv(-1)^{i}$ and $c_{\mbox{edge}}=-1$. A simple example of a non-bipartite distance-regular graph is the “$2$-subsets of a $d$-set” example (Chapter 7 yyy) for $d\geq 4$. Here $\Delta=2$ and

$\displaystyle p_{1,0}=\frac{1}{2(d-2)}$ | $\displaystyle p_{1,1}=\frac{d-3}{2(d-2)}$ | $\displaystyle p_{1,2}=\frac{d-2}{2(d-2)}$ | ||

$\displaystyle p_{2,1}=\frac{4}{2(d-2)}$ | $\displaystyle p_{2,2}=\frac{2d-8}{2(d-2)}.$ |

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

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

An almost bipartite vertex-transitive graph.

Consider the $m+2$-regular graph on $2m$ vertices, made by taking $m$-cycles $(v_{1},\ldots,v_{m})$ and $(w_{1},\ldots,w_{m})$ and adding all edges $(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 $m\rightarrow\infty$

$\displaystyle c(v_{i},w_{j})$ | $\displaystyle\rightarrow$ | $\displaystyle-\frac{1}{9}$ | |||

$\displaystyle c(v_{i},v_{j})$ | $\displaystyle\rightarrow$ | $\displaystyle\frac{1}{9},\ j\neq i.$ | (14.24) |

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

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

So writing $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

$Q\equiv\min\{j:M_{j}\mbox{ is odd}\},$ |

we have

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

Writing $Q_{1}=Q,Q_{2},Q_{3},\ldots$ for the sucessive $j$’s at which $M_{j}$ changes parity, and

$L\equiv\max\{k:M_{Q_{k}}<\mbox{ meeting time}\}$ |

for the number of parity changes before meeting,

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

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

Another almost-bipartite graph.

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

Let $m\rightarrow\infty$ and consider the covariance $c(v_{m},w_{m})$ across edges $(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(v_{m},w_{m})\rightarrow-1$. In fact,

$\displaystyle c(v_{m},w_{m})$ | $\displaystyle\rightarrow$ | $\displaystyle-1,\ \ d=2$ | ||

$\displaystyle\rightarrow$ | $\displaystyle\beta(d)>-1,\ d\geq 3.$ |

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

Generated on Mon Jun 2 14:23:48 2014 by LaTeXML