In the mathematical theory of probability, the voter model is an interacting particle system introduced by Richard A. Holley and Thomas M. Liggett in 1975.[1]
One can imagine that there is a "voter" at each point on a connected graph, where the connections indicate that there is some form of interaction between a pair of voters (nodes). The opinions of any given voter on some issue changes at random times under the influence of opinions of his neighbours. A voter's opinion at any given time can take one of two values, labelled 0 and 1. At random times, a random individual is selected and that voter's opinion is changed according to a stochastic rule. Specifically, one of the chosen voter's neighbors is chosen according to a given set of probabilities and that neighbor’s opinion is transferred to the chosen voter.
An alternative interpretation is in terms of spatial conflict. Suppose two nations control the areas (sets of nodes) labelled 0 or 1. A flip from 0 to 1 at a given location indicates an invasion of that site by the other nation.
Note that only one flip happens each time. Problems involving the voter model will often be recast in terms of the dual system of coalescing Markov chains. Frequently, these problems will then be reduced to others involving independent Markov chains.
A voter model is a (continuous time) Markov process
ηt
Zd | |
S=\{0,1\} |
c(x,η)
Zd
c(
)
η
S
η\inS
η(x)
η(.)
ηt(x)
η(.)
t
The dynamic of the process are specified by the collection of transition rates. For voter models, the rate at which there is a flip at
\scriptstylex
c(x,η)
x
c(x,η)=0
x\inZd
η\equiv0
η\equiv1
c(x,η)=c(x,\zeta)
x\inZd
η(y)+\zeta(y)=1
y\inZd
c(x,η)\leqc(x,\zeta)
η\leq\zeta
η(x)=\zeta(x)=0
c(x,η)
\scriptstyleZd
Property (1) says that
η\equiv0
η\equiv1
η\leq\zeta
\forallx,η(x)\leq\zeta(x)
η\leq\zeta
c(x,η)\leqc(x,\zeta)
η(x)=\zeta(x)=0
c(x,η)\geqc(x,\zeta)
η(x)=\zeta(x)=1
The interest in is the limiting behavior of the models. Since the flip rates of a site depends on its neighbours, it is obvious that when all sites take the same value, the whole system stops changing forever. Therefore, a voter model has two trivial extremal stationary distributions, the point-masses
\scriptstyle\delta0
\scriptstyle\delta1
\scriptstyleη\equiv0
\scriptstyleη\equiv1
\scriptstylex,y\inZd
\limt → P[ηt(x) ≠ ηt(y)]=0
It is important to distinguish clustering with the concept of cluster. Clusters are defined to be the connected components of
\scriptstyle\{x:η(x)=0\}
\scriptstyle\{x:η(x)=1\}
This section will be dedicated to one of the basic voter models, the Linear Voter Model.
If
\scriptstylep(
\scriptstyle)
\scriptstyleZd
p(x,y)\geq0 and\sumyp(x,y)=1
\scriptstyleη
c(x,η)=\left\{ \begin{array}{l} \sumyp(x,y)η(y) forall η(x)=0\\ \sumyp(x,y)(1-η(y)) forall η(x)=1\\ \end{array}\right.
Or if
\scriptstyleηx
\scriptstylex
η → ηx atrate\sumy:η(y) ≠ η(x)p(x,y).
A process of coalescing random walks
\scriptstyleAt\subsetZd
\scriptstyleAt
\scriptstylet
\scriptstyleAt
\scriptstyleZd
\scriptstylep(
\scriptstyle)
\scriptstylep(
\scriptstyle)
The concept of Duality is essential for analysing the behavior of the voter models. The linear voter models satisfy a very useful form of duality, known as coalescing duality, which is:
η(η | |
P | |
t\equiv |
1
A(η(A | |
onA)=P | |
t)\equiv |
1),
\scriptstyleη\in
Zd | |
\{0,1\} |
\scriptstyleηt
\scriptstyleA=\{x\inZd,η(x)=1\}\subsetZd
\scriptstyleAt
Let
\scriptstylep(x,y)
\scriptstyleZd
\scriptstylep(x,y)=p(0,x-y)
\scriptstyle\forallη\in
Zd | |
S=\{0,1\} |
Pη[ηt(x) ≠ ηt(y)]=P[η(Xt) ≠ η(Yt)]
\scriptstyleXt
\scriptstyleYt
\scriptstyleZd
\scriptstyleX0=x
\scriptstyleY0=y
\scriptstyleη(Xt)
\scriptstylet
\scriptstyleXt
\scriptstyleYt
\scriptstyleX(t)-Y(t)
\scriptstyleX(t)-Y(t)
\scriptstyled\leq2
\scriptstyleXt
\scriptstyleYt
Pη[ηt(x) ≠ ηt(y)]=P[η(Xt) ≠ η(Yt)]\leqP[Xt ≠ Yt] → 0 as t\to0
On the other hand, when
d\geq3
\scriptstyled\geq3
\scriptstyleX(t)-Y(t)
\scriptstylex ≠ y
\limt → inftyP[ηt(x) ≠ ηt(y)]=C\limt → inftyP[Xt ≠ Yt]>0
C
If
\scriptstyle\tilde{X}(t)=X(t)-Y(t)
Theorem 2.1
The linear voter model
\scriptstyleηt
\scriptstyle\tilde{X}t
\scriptstyle\tilde{X}t
\scriptstyled=1
\scriptstyle\sumx|x|p(0,x)\leinfty
\scriptstyled=2
\scriptstyle\sumx|x|2p(0,x)\leinfty
\scriptstyled\geq3
Remarks: To contrast this with the behavior of the threshold voter models that will be discussed in next section, note that whether the linear voter model clusters or coexists depends almost exclusively on the dimension of the set of sites, rather than on the size of the range of interaction.
Theorem 2.2Suppose
\scriptstyle\mu
\scriptstyle
Zd | |
S=\{0,1\} |
\scriptstyle\tilde{X}t
\scriptstyle\muS(t) ⇒ \rho\delta1+(1-\rho)\delta0 as t\toinfty
\scriptstyle\tilde{X}t
\scriptstyle\muS(t) ⇒ \mu\rho
where
\scriptstyle\muS(t)
\scriptstyleηt
\scriptstyle ⇒
\scriptstyle\mu\rho
\scriptstyle\rho=\mu(\{η:η(x)=1\})
One of the interesting special cases of the linear voter model, known as the basic linear voter model, is that for state space
\scriptstyle
Zd | |
\{0,1\} |
p(x,y)=\begin{cases} 1/2d&if|x-y|=1andη(x) ≠ η(y)\\[8pt] 0&otherwise \end{cases}
ηt(x)\to1-ηt(x) atrate (2d)-1|\{y:|y-x|=1,ηt(y) ≠ ηt(x)\}|
\scriptstyled\leq2
\scriptstyled\geq3
\scriptstyleZd
\scriptstyled\leq2
\scriptstyled\geq3
For the special case with
\scriptstyled=1
\scriptstyleS=Z1
\scriptstylep(x,x+1)=p(x,x-1)=
1 | |
2 |
\scriptstylex
\scriptstyle\muS(t) ⇒ \rho\delta1+(1-\rho)\delta0
As mentioned before, clusters of an
\scriptstyleη
\scriptstyle\{x:η(x)=0\}
\scriptstyle\{x:η(x)=1\}
\scriptstyleη
C(η)=\limn → infty
2n | |
numberofclustersin[-n,n] |
Proposition 2.3
Suppose the voter model is with initial distribution
\scriptstyle\mu
\scriptstyle\mu
P\left(C(η)= | 1 |
P[ηt(0) ≠ ηt(1)] |
\right)=1.
Define the occupation time functionals of the basic linear voter model as:
t | |
T | |
0 |
\rho | |
η | |
s(x)ds. |
Theorem 2.4
Assume that for all site x and time t,
\scriptstyleP(ηt(x)=1)=\rho
\scriptstylet → infty
\scriptstyle
x/t → | |
T | |
t |
\rho
\scriptstyled\geq2
proof
By Chebyshev's inequality and the Borel–Cantelli lemma, there is the equation below:
P\left( | \rho |
r |
\leq\liminft → infty
Tt | |
t |
\leq\lim\supt → infty
Tt | |
t |
\leq\rhor\right)=1; \forallr>1
\scriptstyler\searrow1
This section concentrates on a kind of non-linear voter model, known as the threshold voter model. To define it, let
\scriptstylel{N}
\scriptstyle0\inZd
\scriptstyleZd
\scriptstyleRd
\scriptstylel{N}
\scriptstyleZd
\scriptstylel{N}
\scriptstyle(1,0,0,...,0),...,(0,...,0,1)
\scriptstyleT
\scriptstylel{N}
\scriptstyleT
c(x,η)=\left\{ \begin{array}{l} 1 if |\{y\inx+l{N}:η(y) ≠ η(x)\}|\geqT\\ 0 otherwise\\ \end{array}\right.
Simply put, the transition rate of site
\scriptstylex
\scriptstylex
For example, if
\scriptstyled=1
\scriptstylel{N}=\{-1,0,1\}
\scriptstyleT=2
\scriptstyle...1 1 0 0 1 1 0 0...
If a threshold voter model does not fixate, the process should be expected to will coexist for small threshold and cluster for large threshold, where large and small are interpreted as being relative to the size of the neighbourhood,
\scriptstyle|l{N}|
\scriptstyleT>
|l{N | |
|-1}{2} |
\scriptstyled=1
\scriptstyleT=
|l{N | |
|-1}{2} |
\scriptstyleT=\theta|l{N}|
\scriptstyle\theta
\scriptstyle\theta<
1 | |
4 |
\scriptstyle|l{N}|
Here are two theorems corresponding to properties (1) and (2).
Theorem 3.1
If
\scriptstyleT>
|l{N | |
|-1}{2} |
Theorem 3.2
The threshold voter model in one dimension (
\scriptstyled=1
\scriptstylel{N}=\{-T,...,T\},T\geq1
proof
The idea of the proof is to construct two sequences of random times
\scriptstyleUn
\scriptstyleVn
\scriptstylen\geq1
\scriptstyle0=V0<U1<V1<U2<V2<...
\scriptstyle\{Uk+1-Vk,k\geq0\}
\scriptstyleE(Uk+1-Vk)<infty
\scriptstyle\{Vk-Uk,k\geq1\}
\scriptstyleE(Vk-Uk)=infty
\scriptstyle\{ηt(.)
\scriptstyle\{-T,...,T\}\}
\scriptstylet\in
infty | |
\cup | |
k=1 |
[Uk,Vk]
Once this construction is made, it will follow from renewal theory that
P(A)\geqP(t\in
infty | |
\cup | |
k=1 |
[Uk,Vk])\to1 as t\toinfty
\scriptstyle\limt → P(ηt(1) ≠ ηt(0))=0
Remarks: (a) Threshold models in higher dimensions do not necessarily cluster if
\scriptstyleT=
|l{N | |
|-1}{2} |
\scriptstyled=2,T=2
\scriptstylel{N}=\{(0,0),(0,1),(1,0),(0,-1),(-1,0)\}
\scriptstyleη
\scriptstylei,j
η(4i,j)=η(4i+1,j)=1, η(4i+2,j)=η(4i+3,j)=0
(b) Under the assumption of Theorem 3.2, the process does not fixate. To see this, consider the initial configuration
\scriptstyle...000111...
Property 3 indicates that the threshold voter model is quite different from the linear voter model, in that coexistence occurs even in one dimension, provided that the neighbourhood is not too small. The threshold model has a drift toward the "local minority", which is not present in the linear case.
Most proofs of coexistence for threshold voter models are based on comparisons with hybrid model known as the threshold contact process with parameter
\scriptstyleλ>0
\scriptstyle
Zd | |
[0,1] |
c(x,η)=\left\{ \begin{array}{l} λ if η(x)=0 and|\{y\inx+l{N}:η(y)=1\}|\geqT;\\ 1 if η(x)=1;\\ 0 otherwise \end{array}\right.
Proposition 3.3
For any
\scriptstyled,l{N}
\scriptstyleT
\scriptstyleλ=1
The case that
\scriptstyleT=1
In particular, there is interest in a kind of Threshold T=1 model with
\scriptstylec(x,η)
c(x,η)=\left\{ \begin{array}{l} 1 ifexistsone y with |x-y|\leqN and η(x) ≠ η(y)\\ 0 otherwise\\ \end{array}\right.
\scriptstyleN
\scriptstylel{N}
\scriptstyleN
\scriptstylel{N}1=\{-2,-1,0,1,2\}
\scriptstyleN1=2
\scriptstylel{N}2=\{(0,0),(0,1),(1,0),(0,-1),(-1,0)\}
\scriptstyleN2=1
By Theorem 3.2, the model with
\scriptstyled=1
\scriptstylel{N}=\{-1,0,1\}
\scriptstyled
\scriptstylel{N}
Theorem 3.4
Suppose that
\scriptstyleN\geq1
\scriptstyle(N,d) ≠ (1,1)
\scriptstyleZd
\scriptstyleN
The proof of this theorem is given in a paper named "Coexistence in threshold voter models" by Thomas M. Liggett.