Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Stochastic cellular automaton
Summary
Stochastic cellular automata or probabilistic cellular automata (PCA) or random cellular automata or locally interacting Markov chains are an important extension of cellular automaton. Cellular automata are a discrete-time dynamical system of interacting entities, whose state is discrete.
The state of the collection of entities is updated at each discrete time according to some simple homogeneous rule. All entities' states are updated in parallel or synchronously. Stochastic Cellular Automata are CA whose updating rule is a stochastic one, which means the new entities' states are chosen according to some probability distributions. It is a discrete-time random dynamical system. From the spatial interaction between the entities, despite the simplicity of the updating rules, complex behaviour may emerge like self-organization. As mathematical object, it may be considered in the framework of stochastic processes as an interacting particle system in discrete-time.
See
for a more detailed introduction.
As discrete-time Markov process, PCA are defined on a product space (cartesian product) where
is a finite or infinite graph, like and where is a finite space, like for instance
or . The transition probability has a product form
where
and is a probability distribution on .
In general some locality is required where
with a finite neighbourhood of k. See for a more detailed introduction following the probability theory's point of view.
There is a version of the majority cellular automaton with probabilistic updating rules. See the Toom's rule.
PCA may be used to simulate the Ising model of ferromagnetism in statistical mechanics.
Some categories of models were studied from a statistical mechanics point of view.
There is a strong connection
between probabilistic cellular automata and the cellular Potts model in particular when it is implemented in parallel.
The Galves-Löcherbach model is an example of a generalized PCA with a non Markovian aspect.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.