Stochastic cellular automata or probabilistic cellular automata (PCA) or random cellular automata or locally interacting
Markov chain
In probability theory and statistics, a Markov chain or Markov process is a stochastic process describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally ...
s are an important extension of
cellular automaton
A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessel ...
. Cellular automata are a discrete-time
dynamical system
In mathematics, a dynamical system is a system in which a Function (mathematics), function describes the time dependence of a Point (geometry), point in an ambient space, such as in a parametric curve. Examples include the mathematical models ...
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 Stochastic (; ) is the property of being well-described by a random probability distribution. ''Stochasticity'' and ''randomness'' are technically distinct concepts: the former refers to a modeling approach, while the latter describes phenomena; i ...
one, which means the new entities' states are chosen according to some probability distributions. It is a discrete-time
random dynamical system
In mathematics, a random dynamical system is a dynamical system in which the equations of motion have an element of randomness to them. Random dynamical systems are characterized by a state space ''S'', a set of maps \Gamma from ''S'' into itself t ...
. From the spatial interaction between the entities, despite the simplicity of the updating rules,
complex behaviour
Complex commonly refers to:
* Complexity, the behaviour of a system whose components interact in multiple ways so possible interactions are difficult to describe
** Complex system, a system composed of many components which may interact with each ...
may
emerge like
self-organization
Self-organization, also called spontaneous order in the social sciences, is a process where some form of overall order and disorder, order arises from local interactions between parts of an initially disordered system. The process can be spont ...
. As mathematical object, it may be considered in the framework of
stochastic processes
In probability theory and related fields, a stochastic () or random process is a mathematical object usually defined as a family of random variables in a probability space, where the index of the family often has the interpretation of time. Stoc ...
as an
interacting particle system
In probability theory, an interacting particle system (IPS) is a stochastic process (X(t))_ on some configuration space \Omega= S^G given by a site space, a countably-infinite-order graph G and a local state space, a compact metric space S ...
in discrete-time.
See
for a more detailed introduction.
PCA as Markov stochastic processes
As discrete-time Markov process, PCA are defined on a
product space
In topology and related areas of mathematics, a product space is the Cartesian product of a family of topological spaces equipped with a natural topology called the product topology. This topology differs from another, perhaps more natural-seemi ...
(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
P.-Y. Louis PhD
/ref> for a more detailed introduction following the probability theory's point of view.
Examples of stochastic cellular automaton
Majority cellular automaton
There is a version of the majority cellular automaton with probabilistic updating rules. See the Toom's rule.
Relation to lattice random fields
PCA may be used to simulate the Ising model
The Ising model (or Lenz–Ising model), named after the physicists Ernst Ising and Wilhelm Lenz, is a mathematical models in physics, mathematical model of ferromagnetism in statistical mechanics. The model consists of discrete variables that r ...
of ferromagnetism
Ferromagnetism is a property of certain materials (such as iron) that results in a significant, observable magnetic permeability, and in many cases, a significant magnetic coercivity, allowing the material to form a permanent magnet. Ferromagne ...
in statistical mechanics
In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. Sometimes called statistical physics or statistical thermodynamics, its applicati ...
.[.]
Some categories of models were studied from a statistical mechanics point of view.
Cellular Potts model
There is a strong connection
between probabilistic cellular automata and the cellular Potts model
In computational biology, a Cellular Potts model (CPM, also known as the Glazier-Graner-Hogeweg model) is a computational model of cells and tissues. It is used to simulate individual and collective cell behavior, tissue morphogenesis and cancer de ...
in particular when it is implemented in parallel.
Non Markovian generalization
The Galves–Löcherbach model
The Galves–Löcherbach model (or GL model) is a mathematical model for a biological neural network, network of neurons with intrinsic stochasticity.
In the most general definition, a GL network consists of a countable number of elements (ide ...
is an example of a generalized PCA with a non Markovian aspect.
References
Further reading
*.
*.
*.
*.
*.
*
* {{citation
, last1=Agapie
, first1=A.
, last2=Andreica
, first2=A.
, last3=Giuclea
, first3=M.
, title=Probabilistic Cellular Automata
, journal=Journal of Computational Biology
, year=2014
, volume=21
, issue=9
, pages=699–708
, doi=10.1089/cmb.2014.0074
, pmid=24999557
, pmc=4148062
Cellular automata
Lattice models
Self-organization
Complex systems theory
Spatial processes
Markov models