For my VIGRE REU project, I wrote a Java applet to simulate the non-linear voter model. This is a stochastic cellular automaton that works as follows: One is given a lattice or graph whose vertices are called cells or sites. Each site x has a set of neighbor sites (including the site itself) which are said to be near x and which may influence the state of the site x which is either On or Off. Uniformly, a site x is chosen at random and it state is updated according to the following rule. One counts the number of On sites near the chosen site. Call this count(x). The site then turns (or stays) On with probability f(count(x)), where f is a predetermined function whose parameters we modify. One then repeats this process by picking another site, updating, and so on. This generates a sequence of configurations that is reminiscent of diffusion.
The function f is usually chosen to be increasing so that a site is more and more likely to be on if more and more of it's neighboring sites are on. Also, f is chosen so that the system is symmetric under color change, meaning that if we invert the state of each cell, apply the update process, and invert the system again, we should get the same result (probabilistically) as if we simply updated the system.
Mathematically, it is convenient to choose the integer lattice on the plane (Z x Z) and define a sites neighbor's as those lattice points directly north, east, south, and west of the given site. However, for the purposes of simulation it is only possible consider a finite number of sites, so one chooses the integer lattice "wrapped around" every m steps in the x direction and every n steps in the y direction. This is mathematically just Zm x Zn with the same neighborhood relationship as before. Under this choice, f is a function from {0,1,2,3,4,5} to [0,1]. Because of the symmetry condition stated above, f must have the property that f(5 - count(x)) = 1 - f(count(x)) for any value of count(x). Thus the values of f(0),f(1) and f(2) determine the function f. It is usually assumed that f(0) = 0 so that a site will not turn on or off unless it has a neighbor of similar preference. This leaves us with f(1) and f(2), which we will call alpha and beta respectively. The java applet below allows one to input these values and watch how they affect the evolution of the system. Remember, patience is a virtue. My thanks go to Davar Khoshnevisan, my advisor for this project, and to the NSF VIGRE program.
Start the applet here:
