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

14.3 Coalescing random walks and the voter model

Sections 14.3 and 14.4 treat some models whose behavior relates “by duality” to random-walk-type processes. It is possible (see Notes) to fit all our examples into an abstract duality framework, but for the sake of concreteness I haven’t done so. Note that for simplicity we work in the setting of regular graphs, though the structural results go over to general graphs and indeed to weighted graphs.

Fix a rr-regular nn-vertex graph GG. In the voter model we envisage a person at each vertex. Initially each person has a different opinion (person ii has opinion ii, say). As time passes, opinions change according to the following rule. 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 current opinion of person jj. Note that the total number of existing opinions can only decrease with time, and at some random time C𝐯𝐦C_{{\bf vm}} there will be only one “consensus” opinion.

In the coalescing random walk process, at time 00 there is one particle at each vertex. These particles perform independent continuous-time random walks on the graph, but when particles meet they coalesce into clusters and the cluster thereafter sticks together and moves as a single random walk. So at time tt there are clusters, composed of one or more particles, at distinct vertices, and during [t,t+dt][t,t+dt] each cluster has chance dtdt to move to a random neighbor and (if that neighbor is occupied by another cluster) to coalesce with that other cluster. Note that the total number of clusters can only decrease with time, and at some random time C𝐜𝐫𝐰C_{{\bf crw}} the particles will have all coalesced into a single cluster.

Remarkably, the two random variables C𝐯𝐦C_{{\bf vm}} and C𝐜𝐫𝐰C_{{\bf crw}} associated with the two models turn out to have the same distribution, depending only on the graph GG. The explanation is that the two processes can be obtained by looking at the same picture in two different ways. Here’s the picture. For each edge ee and each direction on ee, create a Poisson process of rate 1/r1/r. In the figure, GG is the 88-cycle, “time” is horizontal and an event of the Poisson process for edge (i,j)(i,j) at time tt is indicated by a vertical arrow iji\rightarrow j at time tt.

012345678=0vertices012345678=0vertices0t0t_{0}time for voter modelt0t_{0}0time for coalescing RW

In the voter model, we interpret time as increasing left-to-right from 00 to t0t_{0}, and we interpret an arrow jij\rightarrow i at time tt as meaning that person jj adopts ii’s opinion a time tt. In the coalescing random walk model, we interpret time as increasing right-to-left from 00 to t0t_{0}, and we interpret an arrow jij\rightarrow i at time tt as meaning that the cluster (if any) at state jj at time tt jumps to state ii, and coalesces with the cluster at ii (if any).

So for fixed t0t_{0}, we can regard both processes as constructed from the same Poisson process of “arrows”. For any vertices i,j,ki,j,k the event (for the voter model)

The opinions of persons ii and jj at time t0t_{0} are both the opinion initially held by kk

is exactly the same as the event (for the coalescing random walk process)

The particles starting at ii and at jj have coalesced before time t0t_{0} and their cluster is at vertex kk at time t0t_{0}.

The horizontal lines in the figure indicate part of the trajectories. In terms of the coalescing random walks, the particles starting at 55 and 77 coalesce, and the cluster is at 44 at time t0t_{0}. In terms of the voter model, the opinion initially held by person 44 is held by persons 55 and 77 at time t0t_{0}. The reader may (provided this is not a library book) draw in the remaining trajectories, and will find that exactly 33 of the initial opinions survive, i.e. that the random walks coalesce into 33 clusters.

In particular, the event (for the voter model)

By time t0t_{0} everyone’s opinion is the opinion initially held by person kk

is exactly the same as the event (for the coalescing random walk process)

All particles have coalesced by time t0t_{0}, and the cluster is at kk at time t0t_{0}.

So P(C𝐯𝐦t0)=P(C𝐜𝐫𝐰t0)P(C_{{\bf vm}}\leq t_{0})=P(C_{{\bf crw}}\leq t_{0}), and these two times (which we shall now call just CC) do indeed have the same distribution.

We now discuss bounds on ECEC. It is interesting that the two models give us quite different ways to prove bounds. Bounding ECEC here is somewhat analogous to the problem of bounding mean cover time, discussed in Chapter 6.

14.3.1 A bound using the voter model

Recall from Chapter 4 yyy the definition of the Cheeger time constant τc\tau_{c}. In the present setting of a rr-regular graph, the definition implies that for any subset AA of vertices

number of edges linking AA and AcA^{c} r|A|(n-|A|)nτc.\mbox{number of edges linking $A$ and $A^{c}$ }\geq\frac{r|A|(n-|A|)}{n\tau_{c% }}. (14.11)
Proposition 14.9

(a) If GG is ss-edge-connected then ECrn24sEC\leq\frac{rn^{2}}{4s}.

(b) EC2log2τcnEC\leq 2\log 2\ \tau_{c}n.

Proof. The proof uses two ideas. The first is a straightforward comparison lemma.

Lemma 14.10

Let (Xt)(X_{t}) be a continuous-time chain on states II. Let f:I{0,1,,n}f:I\rightarrow\{0,1,\ldots,n\} be such that f(Xt)f(X_{t}) never jumps by more than 11, and such that there exist strictly positive constants γ,a(1),,a(n-1)\gamma,a(1),\ldots,a(n-1) such that, for each 1in-11\leq i\leq n-1 and each state xx with f(x)=if(x)=i,

P(f(Xt+dt)=i+1|Xt=x)dt=P(f(Xt+dt)=i-1|Xt=x)dtγa(i).\frac{P(f(X_{t+dt})=i+1|X_{t}=x)}{dt}=\frac{P(f(X_{t+dt})=i-1|X_{t}=x)}{dt}% \geq\gamma a(i).



where E*T*E^{*}T^{*} refers to mean hitting time for the chain X*X^{*} on states {0,1,,n}\{0,1,\ldots,n\} with transition rates


The second idea is that our voter model can be used to define a less-informative “two-party” model. Fix an initial set BB of vertices, and group the opinions of the individuals in BB into one political party (“Blues”) and group the remaining opinions into a second party (“Reds”). Let NtBN^{B}_{t} be the number of Blues at time tt and let CBCC^{B}\leq C be the first time at which everyone belongs to the same party. Then

P(Nt+dtB=NtB+1| configuration at time t)\displaystyle P(N^{B}_{t+dt}=N^{B}_{t}+1|\mbox{ configuration at time }t)
=P(Nt+dtB=NtB-1| configuration at time t)\displaystyle=P(N^{B}_{t+dt}=N^{B}_{t}-1|\mbox{ configuration at time }t)
= number of edges linking Blue - Red vertices at time ttrdt.\displaystyle=\frac{\mbox{ number of edges linking Blue - Red vertices at time% $t$}}{r}\ dt. (14.12)

Cases (a) and (b) now use Lemma 14.10 with different comparison chains. For (a), while both parties coexist, the number of edges being counted in (14.12) is at least ss. To see this, fix two vertices v,xv,x of different parties, and consider (c.f. Chapter 6 yyy) a collection of ss edge-disjoint paths from vv to xx. Each path must contain at least one edge linking Blue to Red. Thus the quantity (14.12) is at least srdt\frac{s}{r}\ dt. If that quantity were 12dt\frac{1}{2}\ dt then NtBN^{B}_{t} would be continuous time random walk on {0,,n}\{0,\ldots,n\} and the quantity ECBEC^{B} would be the mean time, starting at |B||B|, for simple random walk to hit 00 or nn, which by Chapter 5 yyy we know equals |B|(n-|B|)|B|(n-|B|). So using Lemma 14.10

ECBr2s|B|(n-|B|)rn28s.EC^{B}\leq\frac{r}{2s}|B|(n-|B|)\leq\frac{rn^{2}}{8s}. (14.13)

For (b), use (14.11) to see that the quantity (14.12) must be at least NtB(n-NtB)nτcdt\frac{N^{B}_{t}(n-N^{B}_{t})}{n\tau_{c}}\ dt. Consider for comparison the chain on {0,,n}\{0,\ldots,n\} with transition rates qi,i+1=qi,i-1=i(n-i)/nq_{i,i+1}=q_{i,i-1}=i(n-i)/n. For this chain

Ei*T{0,n}*\displaystyle E^{*}_{i}T^{*}_{\{0,n\}} =\displaystyle= j=1n-1Ei( time spent in jj before T{0,n}*T^{*}_{\{0,n\}}\displaystyle\sum_{j=1}^{n-1}E_{i}(\mbox{ time spent in $j$ before $T^{*}_{\{0% ,n\}}$ }
=\displaystyle= j=1n-1mi(j)12j(n-j)/n\displaystyle\sum_{j=1}^{n-1}m_{i}(j)\frac{\frac{1}{2}}{j(n-j)/n}

where mi(j)m_{i}(j) is the mean occupation time for simple symmetric random walk and the second term is the speed-up factor for the comparison chain under consideration. Using the formula for mi(j)m_{i}(j) from Chapter 5 yyy,

Ei*T{0,n}*=ij=in-11j+(n-i)j=1i-11n-jnlog2.E^{*}_{i}T^{*}_{\{0,n\}}=i\sum_{j=i}^{n-1}\frac{1}{j}+(n-i)\sum_{j=1}^{i-1}% \frac{1}{n-j}\leq n\log 2.

So using Lemma 14.10

ECBτcnlog2.EC^{B}\leq\tau_{c}n\log 2. (14.14)

Finally, imagine choosing 𝐁{\bf B} at random by letting each individual initially be Blue or Red with probability 1/21/2 each, independently for different vertices. Then by considering some two individuals with different opinions at time tt,

P(C𝐁>t)12P(C>t).P(C^{\bf B}>t)\geq\frac{1}{2}P(C>t).

Integrating over tt gives EC2EC𝐁EC\leq 2EC^{\bf B}. But EC𝐁maxBECBEC^{\bf B}\leq\max_{B}EC^{B}, so the Proposition follows from (14.13) and (14.14).

14.3.2 A bound using the coalescing random walk model

The following result bounds the mean coalescing time in terms of mean hitting times of a single random walk.

Proposition 14.11

ECe(logn+2)maxi,jEiTjEC\leq e(\log n+2)\max_{i,j}E_{i}T_{j}

Proof. We can construct the coalescing random walk process in two steps. Order the vertices arbitrarily as i1,,ini_{1},\ldots,i_{n}. First let the nn particles perform independent random walks for ever, with the particles starting at i,ji,j first meeting at time Mi,jM_{i,j}, say. Then when two particles meet, let them cluster and follow the future path of the lower-labeled particle. Similarly, when two clusters meet, let them cluster and follow the future path of the lowest-labeled particle in the combined cluster. Using this construction, we see

C𝐜𝐫𝐰maxjMi1,j.C_{{\bf crw}}\leq\max_{j}M_{i_{1},j}. (14.15)

Now let m*maxi,jEMi,jm^{*}\equiv\max_{i,j}EM_{i,j}. Using subexponentiality as in Chapter 2 section yyy,

P(Mi,j>t)exp(-tem*).P(M_{i,j}>t)\leq\exp(-\lfloor{t\over em^{*}}\rfloor). (14.16)

and so

EC\displaystyle EC =\displaystyle= 0P(C>t)dt\displaystyle\int_{0}^{\infty}P(C>t)dt
\displaystyle\leq 0min(1,jP(Mi1,j>t))dt by (14.15)\displaystyle\int_{0}^{\infty}\min(1,\sum_{j}P(M_{i_{1},j}>t))\ dt\mbox{ by }(% \ref{CM})
\displaystyle\leq 0min(1,neexp(-tem*))dt by (14.16)\displaystyle\int_{0}^{\infty}\min(1,ne\exp(-\frac{t}{em^{*}}))\ dt\mbox{ by }% (\ref{Mij})
=\displaystyle= em*(2+logn)\displaystyle em^{*}(2+\log n)

where the final equality is the calculus fact

0min(1,Ae-at)dt=a-1(1+logA),   A1.\int_{0}^{\infty}\min(1,Ae^{-at})\ dt=a^{-1}(1+\log A),\ \ \ A\geq 1.

The result now follows from Proposition 14.5.

14.3.3 Conjectures and examples

The complete graph. On the complete graph, the number KtK_{t} of clusters at time tt in the coalescing random walk model is itself the continuous-time chain with transition rates

qk,k-1=k(k-1)/(n-1); nk2.q_{k,k-1}=k(k-1)/(n-1);\ \ n\geq k\geq 2.

Since C𝐜𝐫𝐰C_{{\bf crw}} is the time taken for KtK_{t} to reach state 11,

EC=k=2mn-1k(k-1)=(n-1)2nn.EC=\sum_{k=2}^{m}\frac{n-1}{k(k-1)}=\frac{(n-1)^{2}}{n}\sim n.

Recall from Chapter 7 yyy that in a vertex-transitive graph with τ2/τ0\tau_{2}/\tau_{0} small, the first hitting time to a typical vertex has approximately exponential distribution with mean τ0\tau_{0}. Similarly, the meeting time Mi,jM_{i,j} for typical i,ji,j has approximately exponential distribution with mean τ0/2\tau_{0}/2. It seems intuitively clear that, for fixed small kk, when the number of clusters first reaches kk these clusters should be approximately uniformly distributed, so that the mean further time until one of the k(k-1)/2k(k-1)/2 pairs coalesce should be about τ0k(k-1)\frac{\tau_{0}}{k(k-1)}. Repeating the analysis of the complete graph suggests

Open Problem 14.12

Prove that for a sequence of vertex-transitive graphs with τ2/τ00\tau_{2}/\tau_{0}\rightarrow 0, we have ECτ0EC\sim\tau_{0}.

In the general setting, there is good reason to believe that the log term in Proposition 14.11 can be removed.

Open Problem 14.13

Prove there exists an absolute constant KK such that on any graph

ECKmaxv,wEvTw.EC\leq K\max_{v,w}E_{v}T_{w}.

The assertion of Open Problem 14.12 in the case of the torus ZmdZ^{d}_{m} for d2d\geq 2 was proved by Cox [104]. A detailed outline is given in [132] Chapter 10b, so we will not repeat it here, but see the remark in section 14.3.5 below.

xxx discuss d=1d=1?

14.3.4 Voter model with new opinions

For a simple variation of the voter model, fix a parameter 0<λ<0<\lambda<\infty and suppose that each individual independently decides at rate λ\lambda (i.e. with chance λdt\lambda dt in each time interval [t,t+dt][t,t+dt]) to adopt a new opinion, not previously held by anyone. For this process we may take as state space the set of partitions 𝐀={A1,A2,}{\bf A}=\{A_{1},A_{2},\ldots\} of the vertex-set of the underlying graph GG, where two individuals have the same opinion iff they are in the same component AA of 𝐀{\bf A}. The duality relationship holds with the following modification. In the dual process of coalescing random walks, each cluster “dies” at rate λ\lambda. Thus in the dual process run forever, each “death” of a cluster involves particles started at some set AA of vertices, and this partition 𝐀={Ai}{\bf A}=\{A_{i}\} of vertices into components is (by duality) distributed as the stationary distribution of the voter model with new opinions. This is the unique stationary distribution, even though (e.g. on the nn-cycle) the Markov chain may not be irreducible because of the existence of transient states.

The time to approach stationarity in this model is controlled by the time C~\tilde{C} for the dual process to die out completely. Clearly EC~EC+1/λE\tilde{C}\leq EC+1/\lambda, where CC is the coalescing time discussed in previous sections, and we do not have anything new to say beyond what is implied by previous results. Instead, we study properties of the stationary distribution 𝐀={Ai}{\bf A}=\{A_{i}\}. A natural parameter is the chance, γ\gamma say, that two random individuals have the same opinion, i.e.

γEi|Ai|2n2.\gamma\equiv E\sum_{i}\frac{|A_{i}|^{2}}{n^{2}}. (14.17)
Lemma 14.14
γ=2Eλrn2+1n,\gamma=\frac{2E\mbox{${\cal E}$}}{\lambda rn^{2}}+\frac{1}{n},

where {\cal E} is the number of edges with endpoints in different components, under the stationary distribution.

Proof. Run the stationary process, and let 𝐀(t){\bf A}(t) and (t)\mbox{${\cal E}$}(t) be the partition and the number of edges linking distinct components, at time tt, and let S(t)=i|Ai(t)|2S(t)=\sum_{i}|A_{i}(t)|^{2}. Then

E(S2(t+dt)-S2(t)| configuration at time t)dt\frac{E(S^{2}(t+dt)-S^{2}(t)|\mbox{ configuration at time }t)}{dt}
=4r(t)+2λi|Ai(t)|(1-|Ai(t)|).=\frac{4}{r}\mbox{${\cal E}$}(t)+2\lambda\sum_{i}|A_{i}(t)|(1-|A_{i}(t)|). (14.18)

The first term arises from the “voter” dynamics. If an opinion change involves an edge linking components of sizes aa and bb, then the change in S2S^{2} has expectation


and for each of the (t)\mbox{${\cal E}$}(t) edges linking distinct components, opinion changes occur at rate 2/r2/r. The second term arises from new opinions. A new opinion occurs in a component of size aa at rate λa\lambda a, and the resulting change in S2S^{2} is


Stationarity implies that the expectation of (14.18) equals zero, and so

4rE=2λiE|Ai|(|Ai|-1)=2λ(n2γ-n)\frac{4}{r}E\mbox{${\cal E}$}=2\lambda\sum_{i}E|A_{i}|(|A_{i}|-1)=2\lambda(n^{% 2}\gamma-n)

and the lemma follows.

Corollary 14.15

1+λτc1+λτcnγλ+1λn\frac{1+\lambda\tau_{c}}{1+\lambda\tau_{c}n}\leq\gamma\leq\frac{\lambda+1}{% \lambda n}.

Proof. Clearly EE\mbox{${\cal E}$} is at most the total number of edges, nr/2nr/2, so the upper bound follows from the lemma. For the lower bound, (14.11) implies


and hence

Er2nτc(n2-n2γ)E\mbox{${\cal E}$}\geq\frac{r}{2n\tau_{c}}(n^{2}-n^{2}\gamma)

and the bound follows from the lemma after brief manipulation.

We now consider bounds on γ\gamma obtainable by working with the dual process. Consider the meeting time MM of two independent random walks started with the stationary distribution. Then by duality (xxx explain)


where ξ(2λ)\xi_{(2\lambda)} denotes a random variable with exponential (2λ)(2\lambda) distribution independent of the random walks. Now MM is the hitting time of the stationary “product chain” (i.e. two independent continuous-time random walks) on the diagonal A={(v,v)}A=\{(v,v)\}, so by Chapter 3 yyy MM has completely monotone distribution, and we shall use properties of complete monotonicity to get

Corollary 14.16
11+2λEMγ11+2λEM+τ2EM.\frac{1}{1+2\lambda EM}\leq\gamma\leq\frac{1}{1+2\lambda EM}+\frac{\tau_{2}}{% EM}.

Proof. We can write M=dRξ(1)M\ \stackrel{d}{=}\ R\xi_{(1)}, where ξ(1)\xi_{(1)} has exponential(1)(1) distribution and RR is independent of ξ(1)\xi_{(1)}. Then

γ\displaystyle\gamma =\displaystyle= P(Rξ(1)<ξ(2λ)\displaystyle P(R\xi_{(1)}<\xi_{(2\lambda)}
=\displaystyle= EP(Rξ(1)<ξ(2λ)|R)\displaystyle E\ P(R\xi_{(1)}<\xi_{(2\lambda)}|R)
=\displaystyle= E11+2λR\displaystyle E\frac{1}{1+2\lambda R}
\displaystyle\geq 11+2λER by Jensen’s inequality\displaystyle\frac{1}{1+2\lambda ER}\mbox{ by Jensen's inequality}
=\displaystyle= 11+2λEM.\displaystyle\frac{1}{1+2\lambda EM}.

For the upper bound, apply Chapter 3 yyy to the product chain to obtain


(recall that τ2\tau_{2} is the same for the product chain as for the underlying random walk). So

1-γ\displaystyle 1-\gamma =\displaystyle= P(Mξ(2λ))\displaystyle P(M\geq\xi_{(2\lambda)})
=\displaystyle= 0P(Mt) 2λe-2λtdt\displaystyle\int_{0}^{\infty}P(M\geq t)\ 2\lambda e^{-2\lambda t}dt
\displaystyle\geq 2λEM1=2λEM-τ2EM\displaystyle\frac{2\lambda EM}{1=2\lambda EM}-\frac{\tau_{2}}{EM}

and the upper bound follows after rearrangement.

Note that on a vertex-transitive graph Proposition 14.5 implies EM=τ0/2EM=\tau_{0}/2. So on a sequence of vertex-transitive graphs with τ2/τ00\tau_{2}/\tau_{0}\rightarrow 0 and with λτ0θ\lambda\tau_{0}\rightarrow\theta, say, Corollary 14.16 implies γ11+θ\gamma\rightarrow\frac{1}{1+\theta}. But in this setting we can say much more, as the next section will show.

14.3.5 Large component sizes in the voter model with new opinions

xxx discuss coalescent, GEM and population genetics.

xxx genetics already implicit in xxx

Fix 0<θ<0<\theta<\infty. take independent random variables (ξi)(\xi_{i}) with distribution

P(ξ>x)=(1-x)θ,  0<x<1P(\xi>x)=(1-x)^{\theta},\ \ 0<x<1

and define

(X1(θ),X2(θ),X3(θ),)=(ξ1,(1-ξ1)ξ2,(1-ξ1)(1-ξ2)ξ3,)(X^{(\theta)}_{1},X^{(\theta)}_{2},X^{(\theta)}_{3},\ldots)=(\xi_{1},(1-\xi_{1% })\xi_{2},(1-\xi_{1})(1-\xi_{2})\xi_{3},\ldots)

so that iXi(θ)=1\sum_{i}X^{(\theta)}_{i}=1.

Proposition 14.17

Consider a sequence of vertex-transitive graphs for which τ2/τ00\tau_{2}/\tau_{0}\rightarrow 0. Consider the stationary distribution 𝐀{\bf A} of the voter model with new opinions, presented in size-biased order. If λτ0θ\lambda\tau_{0}\rightarrow\theta then

(|A1|n,,|Ak|n)d(X1(θ),,Xk(θ)) for all fixed k.\left(\frac{|A_{1}|}{n},\ldots,\frac{|A_{k}|}{n}\right)\ \stackrel{d}{% \rightarrow}\ (X^{(\theta)}_{1},\ldots,X^{(\theta)}_{k})\mbox{ for all fixed }k.

xxx proof

Remark. The same argument goes halfway to proving Open Problem 14.12, by showing

Corollary 14.18

Consider a sequence of vertex-transitive graphs for which τ2/τ00\tau_{2}/\tau_{0}\rightarrow 0. Let C(k)C^{(k)} be the coalescing time for kk walks started at independent uniform positions. Then, for fixed kk, EC(k)τ0(1-k-1)EC^{(k)}\sim\tau_{0}(1-k^{-1}).

xxx argument similar (?) to part of the proof in Cox [104] for the torus.

14.3.6 Number of components in the voter model with new opinions

xxx τc\tau_{c} result