Simulation of the Nonlinear Voter Model

Lagniappe #9

Simulation of the Nonlinear Voter Model

adapted from Local Frequency Dependence and Global Coexistence

© J. Molofsky, R. Durrett, S. Levin, J. Dushoff and D. Griffeath, 1997

Nearly three years ago, in our December 12, 1994 recipe, we described an interesting instance of phase separation within a simple two-parameter class of probabilistic cellular automata known as the Nonlinear Voter Model. What follows is an account of our extensive simulation of those systems over the entire range of parameter values, in order to obtain a good approximation to the phase portrait. These findings will be summarized in a forthcoming article by the above-mentioned authors.

Let us investigate the various types of system behavior which can arise in the Nonlinear Voter Model for different choices of the parameters p₁ and p₂. In light of mean-field analysis, which ignores spatial interactions, we should anticipate a similarly complex phase portrait, but the extent of commonality is hard to predict. Unfortunately, except in the linear voter model case (.2,.4), the exact symmetry of our automata places them beyond the reach of currently available techniques for rigorous mathematical analysis. Thus we resort to Monte Carlo simulation in order to compare and contrast the phase portrait of the spatial model with that of its non-spatial counterpart.

The mean-field portrait suggests that evidence of ergodicity, clustering, and phase separation may be most easily discernible with parameters on the bottom edge, { (p₁,0) ; 0 < p₁ < 1 ) }. In order to test for qualitatively different spatial behaviors, we use our WinCA modeling software to check how readily each species is able to invade the other's terrain. Our experiments take place on a 640 by 480 array, with type 0 (white) initially on the left half, type 1 (black) on the right half, and with a mixed boundary condition which wraps the top edge to the bottom but disables interaction between the left and right edges. This setup effectively emulates large-scale interface dynamics of the infinite system. We also analyze more conventional simulations, starting from random initial configurations with a given density in (0,1), and with wrap-around at each edge. As it turns out, we encounter three distinct scenarios by varying p₁, with p₂ = 0.

If p₁ = .35, or for any larger value of the parameter, each species invades the other's territory at a linear rate, and between the two wave fronts the system rapidly reaches an equilibrium with density .5. Fig. 1 shows this process after 1000 updates.

Fig1. The (.35,0) model from a vertical interface after 1000 updates

Starting from any random distribution, the simulation appears to converge quickly to the same symmetric equilibrium with short length-scale. This, then, is the ergodic case. One should note that our probabilistic automata, when restricted to a finite array, are finite Markov chains with only the trivial states all 0's and all 1's as traps. Therefore, strictly speaking, nontrivial invariant distributions do not exist for the finite systems. We are observing a metastable steady state which will persist for eons, but eventually break down. Only in the infinite system should we expect to obtain a true stochastic equilibrium with this or any other choice of parameters.

For p₁ = .27 or smaller, on the other hand, neither species is able to make significant headway into the other's domain. Rather, the interface stays tight, as seen in Fig. 2 after 5000 updates.

Fig.2 The (.27,0) model from a vertical interface after 5000 updates

Starting from a symmetric random distribution, this standoff allows solid regions of either type to consolidate. Pockets of one species which are completely surrounded by the other gradually disappear, by a kind of curvature-driven surface tension. In our finite simulation the species which acquires more territory by chance eventually takes over the entire array. In the infinite system both 0's and 1's persist, by symmetry, but after a sufficiently long time any prescribed region will be overwhelmingly likely to consist of a single species. This is the clustering regime. From random initial distributions with any density other than .5 the consolidation process favors the predominant type, so that after a long time, in all likelihood, that type will take over the finite system, or cover a prescribed window of the infinite system.

The plot thickens when we investigate p₁ = .31, in which case each species is able to invade, but only as a minority faction. Waves of mixed population advance steadily (at about half the speed of the ergodic instance above), as shown in Fig. 3 after 2000 updates.

Fig.3 The (.31,0) model from a vertical interface after 2000 updates

Now, however, there is evidently a low-density equilibrium emerging on the left, and a high density equilibrium on the right. For instance, sample averages over moderate-sized windows within the low-density region average about .2 and rarely exceed .25, whereas corresponding averages within the high-density region average about .8 and are rarely lower than .75. This, then, is phase separation. The corresponding dynamics started from symmetric randomness create ever larger patches of the two nontrivial equilibria over time, with interfaces between the patches evolving by surface tension; Fig.4 shows that process at time 5000.

Fig.4 The (.31,0) model from symmetric randomness after 5000 updates

From any other density in (0,1), the evolution apparently converges to the nontrivial steady state with a higher density of the initially prevalent species. To summarize, the phase point (.31,0) corresponds to a system in which all 0's and all 1's are unstable, yet there are two distinct stable mixed equilibria dominated by 0's and 1's, respectively.

Our initial experiments indicate convincingly that the bottom edge of the spatial phase diagram agrees qualitatively with that of the mean-field model, exhibiting ergodicity, clustering, and phase separation, though this last phenomenon would seem to be rather rare. The next order of business is to obtain a good empirical estimate of the complete spatial phase portrait - in particular, searching for evidence of multiple outcome and periodic phases. To this end, we have enlisted the aid of CAM8, our dedicated cellular automaton machine from MIT capable of simulating nonlinear voter models on 512 by 512 arrays at several hundred updates per second. The ability to generate images such as Figs.1-4 in less than 10 seconds, and to tweak parameters on the fly, provides an extremely efficient interactive visualization environment for the study of our competition models. We conclude this discussion by summarizing our findings based on extensive, detailed simulation of the entire (p₁,p₂) parameter space using both WinCA and CAM8.

Motivated by the mean-field portrait, we have investigated barely ergodic systems for a large sampling of values of p₂, especially for p₂ between .25 and 1, starting from random distributions with very small density (e.g., .01). In multiple outcome cases one would expect convergence to all 0's from sufficiently small initial densities. In every instance, however, small isolated configurations such as dyads tend to nucleate linearly growing patches of the symmetric equilibrium. Evidently, in contrast to the mean-field model, there is no multiple outcome regime for the spatial model.

To our surprise, careful inspection of a minuscule neighborhood of the upper right corner of phase space does reveal a fourth regime for the spatial model corresponding to the mean-field periodic case. For instance, starting from symmetric randomness on a 320 by 240 array with wrap around edges, parameter choices p₁ = p₂ = .998 lead to the highly clustered configuration of Fig.5 after 5000 updates.

Fig.5 The (.998,.998) model from symmetric randomness after 5000 updates

What's going on here? The system is best viewed as a perturbation of the deterministic cellular automaton at (1,0), which is locally periodic, meaning that the sequence of values at each site repeats from some time on, but the sequences at different sites can have different patterns and lengths. That rule subjected to very occasional random errors self-organizes into quasi-periodic configurations dominated by horizontal and vertical clusters of period 2 stripes. Over time stochastic fluctuations prevent fixation and, provided the error is small enough, aligned clusters apparently grow to arbitrarily large length scale. This phase admits two totally aligned steady states, of horizontal and vertical stripes, respectively. Starting from any random configuration with density in (0,1), the dynamics converge to symmetric mixture of the two aligned states. For cases in which the errors occur more than a few times in a thousand, however, the alignment process breaks down and ergodicity prevails. (A similar but more robust phenomenon takes place in the opposite corner of the square: rule (0,0), a.k.a. deterministic majority vote, is locally periodic with fixation at most sites, whereas any small or moderate random perturbation of (0,0) clusters.)

Finally, the results of our extensive CAM8 simulation are summarized in the estimated phase diagram of Fig.6. Note that the phase boundary between clustering and ergodicity runs from about (.024,1) at the top edge, down through the linear voter point (.2,.4), before a bifurcation encloses the tiny phase separation region which comprises less than 0.25% of the square.

Fig.6 Estimation of the phase portrait for the spatial model

A particularly subtle issue is whether the boundary bifurcation occurs at (.2,.4), as in the mean-field model, or for a smaller value of p₂. In spite of the mathematical plausibility of the former alternative, our simulation data would seem to indicate the latter. As we move away from the lower edge, the discernible width of the phase separation region decreases at a rate which precludes any detectable instances of this phase with p₂ > .3, say. Assuming the boundaries vary smoothly, it is hard to see how this "triangle" could extend all the way to the linear voter point.