We perform a rigorous stochastic analysis of both deterministic and stochastic cellular automata. The theory uses a mesoscopic view, i.e. it works with probabilities instead of individual configurations used in micro-simulations. An exact stochastic analysis can be done using the theory of Markov processes. But this analysis is restricted to small problems only. For larger problems we compute the distribution using a factorization into marginals. These marginals are then approximated by the given marginals of low order with iterative proportional fitting using the maximum entropy principle. This method has been developed in probabilistic logic. Our method leads to a set of difference equations which have to be iterated numerically. We use the exact methods as well as our approximations to investigate the popular nonlinear voter model (NLVM). We show that the "phase transitions" regarded in recent papers are artifacts of the mean-field approximation. They do not show up in the real automata. There exist many mathematical peculiarities of the NLVM which raise doubts concerning the suitability of the model. As an alternative we propose the Exponential Voter Model which depends on a single parameter only, the inverse "temperature" β. Our proposed method to perform a stochastic analysis is not restricted to cellular automata, but can be applied to more general discrete stochastic systems.
['Heinz Mühlenbein', 'Robin Höns']
STOCHASTIC ANALYSIS OF CELLULAR AUTOMATA WITH APPLICATION TO THE VOTER MODEL