Solution of the multistate voter model and application to strong neutrals in the naming game

We consider the voter model with $M$ states initially in the system. Using generating functions, we pose the spectral problem for the Markov transition matrix and solve for all eigenvalues and eigenvectors exactly. With this solution, we can find all future probability probability distributions, the expected time for the system to condense from $M$ states to $M-1$ states, the moments of consensus time, the expected local times, and the expected number of states over time. Furthermore, when the initial distribution is uniform, such as when $M=N$, we can find simplified expressions for these quantities. In particular, we show that the mean and variance of consensus time for $M=N$ are $\frac{1}{N}{(N-1)}^2$ and $\frac{1}{3}({\pi }^2-9){(N-1)}^2$, respectively. We verify these claims by simulation of the model on complete and Erdős-Rényi graphs and show that the results also hold on these sparse networks.

Figure 1

Simulation of the voter model for $N=100$ and $M=50$ on complete and Erdős-Rényi networks $G(N,1/3)$ plotted with $p$. For each $p$, the simulation is averaged over 1000 runs. Since $\eta$ is bounded, Eq. (34) predicts a linear relationship with $p$ with a slope of $ln\left(100\right)-ln\left(2\right)\approx 3.912$. The best fit line for the data is given, which has slope 3.951. Furthermore, the data for these sparse networks accurately follow the complete graph paradigm.

Figure 2

Simulation of the voter model on complete and Erdős-Rényi networks $G(N,1/3)$ plotted with $lnN$. Data are averaged over 2000 runs with $p=2$ and $M=20$. For the complete graph, Eq. (34) predicts a linear relationship between the second moment and $lnN$ with a slope of 2. The best fit line for the data on the complete graph is given, which has a slope of $2.094$. Data for these sparse networks are also accurately predicted by complete graph results.

Figure 3

Example of expected local times for $N=30$ and $M=3$. The initial condition is $n_1\left(0\right)=n_2\left(0\right)=10$. Most of the time is spent on the boundary where one of the states had been eliminated. Each macrostate on the boundary has nearly equal local time.

Figure 4

Data for the number of states in the system over time plotted for the voter model on the complete graph and Erdős-Rényi networks $G(N,1/3)$. In each case, we take $N=100$ and $M=100$ and average the results over 1000 runs. The exact solution given by Eq. (56) is also plotted. This numerically suggests that the complete graph paradigm accurately describes the dynamics on these sparse networks.

Figure 5

Simulation data for the second moment of consensus time $T_2$ with $N=100$ over $30000$ runs. The exact solution given in Eq. (59) is given as the solid curve. In addition, the upper bound found by applying Eq. (36) to Eq. (58) is plotted as the dashed line. The upper bound overestimates the data by a factor of $1.107007$ at most.