STOCHASTIC ANALYSIS OF CELLULAR AUTOMATA WITH APPLICATION TO THE VOTER MODEL

Heinz Mühlenbein () and Robin Höns ()
Additional contact information
Heinz Mühlenbein: Fraunhofer Institute for Autonomous Intelligent Systems, D-53754 Sankt Augustin, Germany
Robin Höns: Fraunhofer Institute for Autonomous Intelligent Systems, D-53754 Sankt Augustin, Germany

Advances in Complex Systems (ACS), 2002, vol. 05, issue 02n03, 301-337

Abstract: We perform a rigorous stochastic analysis of both deterministic and stochastic cellular automata. The theory uses amesoscopic 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 afactorizationinto marginals. These marginals are then approximated by the given marginals of low order withiterative proportional fittingusing themaximum entropy principle. This method has been developed in probabilistic logic. Our method leads to a set ofdifference equationswhich have to be iterated numerically. We use the exact methods as well as our approximations to investigate the popularnonlinear 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 theExponential Voter Modelwhich 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.

Keywords: Stochastic cellular automata; marginal distribution; approximation of distributions; factorization of distributions; junction tree; iterative proportional fitting; maximum entropy; probabilistic logic; nonlinear voter model (search for similar items in EconPapers)
Date: 2002
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0219525902000596
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:acsxxx:v:05:y:2002:i:02n03:n:s0219525902000596

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0219525902000596

Access Statistics for this article

Advances in Complex Systems (ACS) is currently edited by Frank Schweitzer

More articles in Advances in Complex Systems (ACS) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().