voter model coexists on the graph with two clusters
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, for one of the chosen voter's neighbors is chosen[clarification needed] according to a given set of probabilities and that individual'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[clarification needed] of coalescing[clarification needed]Markov chains. Frequently, these problems will then be reduced to others involving independent Markov chains.
A voter model is a (continuous time) Markov process with state space and transition rates function , where is a d-dimensional integer lattice, and •,• is assumed to be nonnegative, uniformly bounded and continuous as a function of in the product topology on . Each component is called a configuration. To make it clear that stands for the value of a site x in configuration ; while means the value of a site x in configuration at time .
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 from 0 to 1 or vice versa is given by a function of site . It has the following properties:
for every if or if
for every if for all
is invariant under shifts in
Property (1) says that and are fixed points for the evolution. (2) indicates that the evolution is unchanged by interchanging the roles of 0's and 1's. In property (3), means , and implies if , and implies if .
What we are interested in is the limiting behavior of the models. Since the flip rates of a site depends 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 and on or respectively, which represent consensus. The main question we will discuss is whether or not there are others, which would then represent coexistence of different opinions in equilibrium. We say that coexistence occurs if there is a stationary distribution that concentrates on configurations with infinitely many 0's and 1's. On the other hand, if for all and all initial configurations, we have:
we will say that clustering occurs.
It is important to distinguish clustering with the concept of cluster. Clusters are defined to be the connected components of or .
This section will be dedicated to one of the basic voter models, the Linear Voter Model.
Let •,• be the transition probabilities for an irreducible random walk on ,and we have:
Then in Linear voter model, the transition rates are linear functions of :
Or if we use to indicate that a flip happens at site , the transition rates are simply:
We define a process of coalescing random walks as follows. Here denotes the set of sites occupied by these random walks at time . To define , consider several (continuous time) random walks on with unit exponential holding times and transition probabilities •,•, and take them to be independent until two of them meet. At that time, the two that meet coalesce into one particle, which continues to move like a random walk with transition probabilities •,• .
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:
where is the initial configuration of and is the initial state of the coalescing random walks .
Let be the transition probabilities for an irreducible random walk on and , then the duality relation for such linear voter models says that
where and are (continuous time) random walks on with , , and is the position taken by the random walk at time . and forms a coalescing random walks described at the end of section 2.1. is a symmetrized random walk. If is recurrent and , and will hit eventually with probability 1, and hence
Therefore, the process clusters.
On the other hand, when , the system coexists. It is because for , is transient, thus there is a positive probability that the random walks never hit, and hence for
for some constant corresponding to the initial distribution.
Now let be a symmetrized random walk, we have the following theorems:
The linear voter model clusters if is recurrent, and coexists if is transient. In particular,
the process clusters if and , or if and ;
the process coexists if .
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.
In this section, we will concentrate on a kind of non-linear voter models, known as the threshold voter model.
To define it, let be a neighbourhood of that is obtained by intersecting with any compact, convex, symmetric set in ; in other word, is assumed to be a finite set that is symmetric with respect to all reflections and irreducible (i.e. the group it generates is )We will always assume that contains all the unit vectors . For a positive integer , the threshold voter model with neighbourhood and threshold is the one with rate function:
Simply put, the transition rate of site is 1 if the number of sites that do not take the same value is larger or equal to the threshold T. Otherwise, site stays at the current status and will not flip.
For example, if , and , then the configuration is an absorbing state or a trap for the process.
If a threshold voter model does not fixate, we should expect that the process 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, . The intuition is that having a small threshold makes it easy for flips to occur, so it is likely that there will be a lot of both 0's and 1's around at all times. The following are three major results:
If , then the process fixates in the sense that each site flips only finitely often.
If and , then the process clusters.
If with sufficiently small() and sufficiently large, then the process coexists.
Here are two theorems corresponding to properties (1) and (2).
If , then the process fixates.
The threshold voter model in one dimension () with , clusters.
The idea of the proof is to construct two sequences of random times , for with the following properties:
are i.i.d.with ,
are i.i.d.with ,
the random variables in (b) and (c) are independent of each other,
event A= is constant on , and event A holds for every .
Once this construction is made, it will follow from renewal theory that
Hence,, so that the process clusters.
Remarks: (a) Threshold models in higher dimensions do not necessarily cluster if . For example, take and . If is constant on alternating vertical infinite strips,that is for all :
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 , 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 . This is the process on with flip rates:
For any and , if the threshold contact process with has a nontrivial invariant measure, then the threshold voter model coexists.