14.4 The antivoter model

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

A simple counting argument gives

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

and so

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.

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.

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$:

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

where the stationary chain is used. Then

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

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

and an ergodic argument gives

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

Now consider

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

So

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

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).

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

for an edge $(v,w)$. But $P(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.

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

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

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

Conditioning on the first step of the random walks,

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

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.

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$

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

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

we have

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

for the number of parity changes before meeting,

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

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,

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.