Abstract
We make a 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. We make an exact analysis by using the theory of Markov processes. This can be done for small problems only. For larger problems we approximate the distribution by products of marginal distributions of low order. The approximation use new developments in efficient computation of probabilities based on factorizations of the distribution. We investigate the popular voter model. We show that for one dimension the bifurcation at α = 1/3 is an artifact of the mean-field approximation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
U. N. Bhat Elements of Applied Stochastic Processes. Wiley, New York, 1984.
U. Diekmann, R. Law, and J. Metz (eds.). The Geometry of Ecological Interactions. Cambridge University Press, Cambridge, 2000.
R. Durret. http://www.math.cornell.edu/~durrett/survey/survhome.html
H.A. Gutowitz and J.D. Victor and B.W. Knight. Local structure theory for cellular automata. Physica D, 28D:18–48, 1987.
H.A. Gutowitz and J.D. Victor. Local structure theory in more than one dimension. Complex Systems, 1:57–67, 1987.
D. R Heyman and D. P. OLeary. Overcoming instability in computing the fundamental matrix for a Markov chain. SIAM J. Matrix Analysis and Applications, 19:534–540, 1998.
A. Ilachinski Cellular Automata A Discrete Universe. World Scientific, Singapore, 2001
M.I. Jordan. Learning in Graphical Models. MIT Press, Cambrigde, 1999
S. L. Lauritzen. Graphical Models. Oxford: Clarendom Press, 1996.
H. Muhlenbein. Darwin’s continent cycle theory and its simulation by the Prisoner’s Dilemma. Complex Systems, 5:459–478, 1991.
Heinz Muhlenbein, Thilo Mahnig, and Alberto Ochoa. Schemata, distributions and graphical models in evolutionary optimization. Journal of Heuristics, 5(2):213–247, 1999.
H. Muhlenbein and Th. Mahnig. Evolutionary algorithms: From recombination to search distributions. In L. Kallel, B. Naudts, and A. Rogers, editors, Theoretical Aspects of Evolutionary Computing, Natural Computing, pages 137–176. Springer Verlag, Berlin, 2000.
Heinz Muhlenbein and Thilo Mahnig. Evolutionary optimization and the estimation of search distributions Journal of Approx. Reason., to appear, 2002.
N. A. Oomes. Emerging markets and persistent inequality in a nonlinear voter model. In D. Griffeath and C. Moore, editors, New Constructions in Cellular Automata, pages 207–229, Oxford University Press, Oxford, 2002.
M. Opper and D. Saad, editors. Advanced Mean Field Methods, MIT Press, Cambridge, 2001.
S. Wolfram. Cellular Automata and Complexity. Addison-Wesley, Reading, 1994.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mühlenbein, H., Höns, R. (2002). Stochastic Analysis of Cellular Automata and the Voter Model. In: Bandini, S., Chopard, B., Tomassini, M. (eds) Cellular Automata. ACRI 2002. Lecture Notes in Computer Science, vol 2493. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45830-1_9
Download citation
DOI: https://doi.org/10.1007/3-540-45830-1_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44304-9
Online ISBN: 978-3-540-45830-2
eBook Packages: Springer Book Archive