Information Technology Reference
In-Depth Information
Stochastic Analysis of Cellular Automata and the Voter
Model
Heinz M uhlenbein and Robin H ons
FhG-AiS D-53754 Sankt Augustin
Abstract.
We make a stochastic analysis of both deterministic and stochastic
cellular automata. The theory uses a mesoscopic view, i.e. it works with proba-
bilities 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 de-
velopments 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
isan artifact of the mean-field approxima-
tion.
=1
=
3
1
Introduction
Complex cellular automata are usually analyzed by micro-simulations. A myr-
iad of runs are made with different initial conditions. Then some general pat-
terns are sought for describing the results of the runs. The computer outputs
show realizations of complex spatio-temporal stochastic processes. They can be
a valuable aid in intuitively defining and characterizing the processes involved
and can lead to the discovery of new and interesting phenomena. But one should
not infer too much from a few realizations of a stochastic process: it is not the
behavior of each individual cell that matters, since the stochasticity will ensure
that all realizations are different at least in detail. It is the gross properties of the
stochastic process that are likely to be of interest in the long run.
As a first step to solve these problems we propose the
mesoscopic view
.We
follow here the approach used in statistical physics. There a
microscopic view,
a
mesoscopic view,
and a
macroscopic view
are distinguished. In the microscopic
view a large state space of configurations is defined, together with state transi-
tions by interactions of the elementary units. The mesoscopic view works with
stochastic processes. Instead of clearly defined configurations
it uses prob-
ability distributions
on the configuration space. This approach has two
advantages: first, it allows a very soft specification of systems, and second, the
processes can be modeled with uncertainty. In the macroscopic view differential
equations of macroscopic variables are derived. The macroscopic variables can
be seen as expectations
x
(t)
p(
x
;t)
.
