Search Results for “voter model”

Source: Voter model

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.

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.

Definition

voter

model

voter

= Clustering and coexistence

voter

model

The linear voter model

= Model description

= Limiting behaviors of linear voter models

= A special linear voter model

The threshold voter model

= Model description

= Limiting behaviors of threshold voter model

,

{

U

k
+
1

−

V

k

,
k
≥
0
}

{\displaystyle \scriptstyle \{U_{k+1}-V_{k},k\geq 0\}}

are i.i.d.with

E

(

U

k
+
1

−

V

k

)
<
∞

{\displaystyle \scriptstyle \mathrm {E} (U_{k+1}-V_{k})<\infty }

,

{

V

k

−

U

k

,
k
≥
1
}

{\displaystyle \scriptstyle \{V_{k}-U_{k},k\geq 1\}}

are i.i.d.with

E

(

V

k

−

U

k

)
=
∞

{\displaystyle \scriptstyle \mathrm {E} (V_{k}-U_{k})=\infty }

,
the random variables in (b) and (c) are independent of each other,
event A=

{

η

t

(
.
)

{\displaystyle \scriptstyle \{\eta _{t}(.)}

is constant on

{
−
T
,
…
,
T
}
}

{\displaystyle \scriptstyle \{-T,\dots ,T\}\}}

, and event A holds for every

t
∈

∪

k
=
1

∞

[

U

k

,

V

k

]

{\displaystyle \scriptstyle t\in \cup _{k=1}^{\infty }[U_{k},V_{k}]}

.
Once this construction is made, it will follow from renewal theory that

P
(
A
)
≥
P
(
t
∈

∪

k
=
1

∞

[

U

k

,

V

k

]
)
→
1

as

t
→
∞

{\displaystyle P(A)\geq P(t\in \cup _{k=1}^{\infty }[U_{k},V_{k}])\to 1\quad {\text{as}}\quad t\to \infty }

Hence,

lim

t
→
∞

P
(

η

t

(
1
)
≠

η

t

(
0
)
)
=
0

{\displaystyle \scriptstyle \lim _{t\rightarrow \infty }P(\eta _{t}(1)\neq \eta _{t}(0))=0}

, so that the process clusters.
Remarks: (a) Threshold models in higher dimensions do not necessarily cluster if

T
=

|

N

|

−
1

2

{\displaystyle \scriptstyle T={\frac {|{\mathcal {N}}|-1}{2}}}

. For example, take

d
=
2
,
T
=
2

{\displaystyle \scriptstyle d=2,T=2}

and

N

=
{
(
0
,
0
)
,
(
0
,
1
)
,
(
1
,
0
)
,
(
0
,
−
1
)
,
(
−
1
,
0
)
}

{\displaystyle \scriptstyle {\mathcal {N}}=\{(0,0),(0,1),(1,0),(0,-1),(-1,0)\}}

. If

η

{\displaystyle \scriptstyle \eta }

is constant on alternating vertical infinite strips, that is for all

i
,
j

{\displaystyle \scriptstyle i,j}

:

η
(
4
i
,
j
)
=
η
(
4
i
+
1
,
j
)
=
1
,

η
(
4
i
+
2
,
j
)
=
η
(
4
i
+
3
,
j
)
=
0

{\displaystyle \eta (4i,j)=\eta (4i+1,j)=1,\quad \eta (4i+2,j)=\eta (4i+3,j)=0}

then no transition ever occur, and the process fixates.
(b) Under the assumption of Theorem 3.2, the process does not fixate. To see this, consider the initial configuration

…
000111
…

{\displaystyle \scriptstyle \dots 000111\dots }

, in which infinitely many zeros are followed by infinitely many ones. Then only the zero and one at the boundary can flip, so that the configuration will always look the same except that the boundary will move like a simple symmetric random walk. The fact that this random walk is recurrent implies that every site flips infinitely often.
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

λ
>
0

{\displaystyle \scriptstyle \lambda >0}

. This is the process on

[
0
,
1

]

Z

d

{\displaystyle \scriptstyle [0,1]^{Z^{d}}}

with flip rates:

c
(
x
,
η
)
=

{

λ

if

η
(
x
)
=
0

and

|

{
y
∈
x
+

N

:
η
(
y
)
=
1
}

|

≥
T
;

1

if

η
(
x
)
=
1
;

0

otherwise

{\displaystyle c(x,\eta )=\left\{{\begin{array}{l}\lambda \quad {\text{if}}\quad \eta (x)=0\quad {\text{and}}|\{y\in x+{\mathcal {N}}:\eta (y)=1\}|\geq T;\\1\quad {\text{if}}\quad \eta (x)=1;\\0\quad {\text{otherwise}}\end{array}}\right.}

Proposition 3.3
For any

d
,

N

{\displaystyle \scriptstyle d,{\mathcal {N}}}

and

T

{\displaystyle \scriptstyle T}

, if the threshold contact process with

λ
=
1

{\displaystyle \scriptstyle \lambda =1}

has a nontrivial invariant measure, then the threshold voter model coexists.

= Model with threshold T = 1

=
The case that

T
=
1

{\displaystyle \scriptstyle T=1}

is of particular interest because it is the only case in which it is known exactly which models coexist and which models cluster.
In particular, there is interest in a kind of Threshold T=1 model with

c
(
x
,
η
)

{\displaystyle \scriptstyle c(x,\eta )}

that is given by:

c
(
x
,
η
)
=

{

1

if exists one

y

with

|

x
−
y

|

≤
N

and

η
(
x
)
≠
η
(
y
)

0

otherwise

{\displaystyle c(x,\eta )=\left\{{\begin{array}{l}1\quad {\text{if exists one}}\quad y\quad {\text{with}}\quad |x-y|\leq N\quad {\text{and}}\quad \eta (x)\neq \eta (y)\\0\quad {\text{otherwise}}\\\end{array}}\right.}

N

{\displaystyle \scriptstyle N}

can be interpreted as the radius of the neighbourhood

N

{\displaystyle \scriptstyle {\mathcal {N}}}

;

N

{\displaystyle \scriptstyle N}

determines the size of the neighbourhood (i.e., if

N

1

=
{
−
2
,
−
1
,
0
,
1
,
2
}

{\displaystyle \scriptstyle {\mathcal {N}}_{1}=\{-2,-1,0,1,2\}}

, then

N

1

=
2

{\displaystyle \scriptstyle N_{1}=2}

; while for

N

2

=
{
(
0
,
0
)
,
(
0
,
1
)
,
(
1
,
0
)
,
(
0
,
−
1
)
,
(
−
1
,
0
)
}

{\displaystyle \scriptstyle {\mathcal {N}}_{2}=\{(0,0),(0,1),(1,0),(0,-1),(-1,0)\}}

, the corresponding

N

2

=
1

{\displaystyle \scriptstyle N_{2}=1}

).
By Theorem 3.2, the model with

d
=
1

{\displaystyle \scriptstyle d=1}

and

N

=
{
−
1
,
0
,
1
}

{\displaystyle \scriptstyle {\mathcal {N}}=\{-1,0,1\}}

clusters. The following theorem indicates that for all other choices of

d

{\displaystyle \scriptstyle d}

and

N

{\displaystyle \scriptstyle {\mathcal {N}}}

, the model coexists.
Theorem 3.4
Suppose that

N
≥
1

{\displaystyle \scriptstyle N\geq 1}

, but

(
N
,
d
)
≠
(
1
,
1
)

{\displaystyle \scriptstyle (N,d)\neq (1,1)}

. Then the threshold model on

Z

d

{\displaystyle \scriptstyle Z^{d}}

with parameter

N

{\displaystyle \scriptstyle N}

coexists.
The proof of this theorem is given in a paper named "Coexistence in threshold voter models" by Thomas M. Liggett.