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, for one of the chosen voter's neighbors is chosen 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 of coalescing Markov chains. Frequently, these problems will then be reduced to others involving independent Markov chains. Definition. A voter model is a (continuous time) Markov process formula_1 with state space formula_2 and transition rates function formula_3, where formula_4 is a d-dimensional integer lattice, and formula_5•,•formula_6 is assumed to be nonnegative, uniformly bounded and continuous as a function of formula_7 in the product topology on formula_8. Each component formula_9 is called a configuration. To make it clear that formula_10 stands for the value of a site x  in configuration formula_11; while formula_12 means the value of a site x in configuration formula_11 at time formula_14. 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 formula_15 from 0 to 1 or vice versa is given by a function formula_16 of site formula_17. It has the following properties: Property (1) says that formula_31 and formula_32 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), formula_27 means  formula_34, and formula_35 implies formula_26 if formula_28, and implies formula_38 if formula_39. Clustering and coexistence. The interest 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 formula_40 and formula_41 on formula_42 or formula_43 respectively, which represent consensus. The main question to be discussed is whether or not there are others, which would then represent coexistence of different opinions in equilibrium. It  is said 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 formula_44 and all initial configurations, then It is said that clustering occurs. It is important to distinguish clustering with the concept of cluster. Clusters are defined to be the connected components of formula_46 or formula_47. The linear voter model. Model description. This section will be dedicated to one of the basic voter models, the Linear Voter Model. If formula_48•,•formula_49 be the transition probabilities for an irreducible random walk on formula_30, then : Then in Linear voter model, the transition rates are linear functions of formula_52: Or if formula_54 indicates that a flip happens at formula_55, then transition rates are simply: A process of coalescing random walks formula_57 is defined as follows. Here formula_58 denotes the set of sites occupied by these random walks at time formula_59. To define formula_60, consider several (continuous time) random walks on formula_30 with unit exponential holding times and transition probabilities formula_48•,•formula_63, 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 formula_48•,•formula_63 . 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 formula_67 is the initial configuration of formula_68 and formula_69 is the initial state of the coalescing random walks formula_58. Limiting behaviors of linear voter models. Let formula_71 be the transition probabilities for an irreducible random walk on formula_30 and formula_73, then the duality relation for such linear voter models says that formula_74 where formula_76 and formula_77 are (continuous time) random  walks on formula_30 with formula_79, formula_80, and formula_81 is the position taken by the random walk at time formula_59. formula_76 and formula_77 forms a coalescing random walks described at the end of section 2.1. formula_85 is a symmetrized random walk. If formula_85 is recurrent and formula_87, formula_76 and formula_77 will hit eventually with probability 1, and hence Therefore, the process clusters. On the other hand, when formula_91, the system coexists. It is because for formula_92, formula_85 is transient, thus there is a positive probability that the random walks never hit, and hence for formula_94 for some constant formula_96 corresponding to  the initial distribution. If formula_97 be a symmetrized random walk, then there are the following theorems: Theorem 2.1 The linear voter model formula_68 clusters if formula_99 is recurrent, and coexists if formula_99 is transient. In particular, 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.2 Suppose formula_106 is any translation spatially ergodic and invariant probability measure on  the state space formula_107, then where formula_112 is the distribution of formula_68; formula_114 means weak convergence, formula_115 is a nontrivial extremal invariant measure and formula_116. A special linear voter model. One of the interesting special cases of the linear voter model, known as the basic linear voter model, is that for state space formula_117: So that In this case, the process clusters if formula_87, while coexists if formula_92. This dichotomy is closely related to the fact that simple random walk on formula_30 is recurrent if formula_123 and transient if formula_92. Clusters in one dimension "d" = 1. For the special  case with formula_101, formula_126 and formula_127 for each formula_15. From Theorem 2.2, formula_129, thus clustering occurs in this case. The aim of this section is to give a more precise description of this clustering. As mentioned before, clusters of an formula_52 are defined to be the connected components of formula_131 or formula_132. The mean cluster size for formula_52 is defined to be: provided the limit exists. Proposition 2.3 Suppose the voter model is with initial distribution formula_106 and formula_106 is a translation invariant probability measure, then Occupation time. Define the occupation time functionals of the basic linear voter model as : Theorem 2.4 Assume that for all site x and time t, formula_139, then as formula_140, formula_141 almost surely if formula_142 proof By Chebyshev's inequality and the Borel–Cantelli lemma, there is the equation below: The theorem follows when letting formula_144. The threshold voter model. Model description. This section, concentrates on a kind of non-linear voter models, known as the "threshold voter model". To define it, let formula_145 be a neighbourhood of formula_146 that is obtained by intersecting formula_30 with any compact, convex, symmetric set in formula_148; in other word, formula_145 is assumed to be a finite set that  is symmetric with respect to all reflections and irreducible (i.e. the group it generates is formula_30). It can always be assumed that formula_145 contains all the unit vectors formula_152. For a positive integer formula_153, the threshold voter model with neighbourhood formula_145 and threshold formula_153 is the one with rate function: Simply put, the transition rate of site formula_15 is 1 if the number of sites that do not take the same value is larger or equal to the threshold T. Otherwise, site formula_15 stays at the current status and will not flip. For example, if formula_101, formula_160 and formula_161, then  the configuration formula_162 is an absorbing state or a trap for the process. Limiting behaviors of threshold voter model. 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, formula_163. 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: Here are two theorems corresponding to properties (1) and (2). Theorem 3.1 If formula_164, then the process fixates. Theorem 3.2 The threshold voter model in one dimension (formula_101) with formula_173, clusters. proof The idea of the proof is to construct two sequences of random times formula_174, formula_175 for formula_176 with the following properties: Once this construction is made, it will follow from renewal theory that Hence,formula_186, so that the process clusters. Remarks: (a) Threshold models in higher dimensions do not necessarily cluster if formula_166. For example, take formula_188 and formula_189. If formula_52 is constant on alternating vertical infinite  strips, that is for all formula_191: 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 formula_193, 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 formula_194. This is the process on formula_195 with flip rates: Proposition 3.3 For any formula_197 and formula_153, if the threshold contact process with formula_199 has a nontrivial invariant measure, then the threshold voter model  coexists. Model with threshold "T" = 1. The case that formula_200 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 formula_201 that is given by: formula_203 can be interpreted as the radius of the neighbourhood formula_145; formula_203 determines the size of the neighbourhood (i.e., if formula_206, then formula_207; while for formula_208, the corresponding formula_209). By Theorem 3.2, the model with formula_101 and formula_160 clusters. The following theorem indicates that for all other choices  of formula_212 and formula_145, the model coexists. Theorem 3.4 Suppose that formula_214, but formula_215. Then the threshold model on formula_30 with parameter formula_203 coexists. The proof of this theorem is given in a paper named "Coexistence in threshold voter models" by Thomas M. Liggett.