Stochastic cellular automata or probabilistic cellular automata (PCA) or random cellular automata or locally interacting

Markov chain A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happe ...

s are an important extension of cellular automaton. 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. Examples include the mathematical models that describe the swinging of a ...

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 (, ) refers to the property of being well described by a random probability distribution. Although stochasticity and randomness are distinct in that the former refers to a modeling approach and the latter refers to phenomena themselv ...

one, which means the new entities' states are chosen according to some probability distributions. It is a discrete-time

random dynamical system In the mathematical field of dynamical systems, 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 ma ...

. From the spatial interaction between the entities, despite the simplicity of the updating rules, complex behaviour may

emerge Emerge may refer to: * '' Emerge: The Best of Neocolours'', the fourth album of Neocolours * Emerge Desktop, a Desktop shell replacement for Microsoft Windows * ''Emerge'' (magazine), a defunct news magazine * Emerge Stimulation Drink, a drink s ...

self-organization Self-organization, also called spontaneous order in the social sciences, is a process where some form of overall order arises from local interactions between parts of an initially disordered system. The process can be spontaneous when suffi ...

. 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. Stochastic processes are widely used as mathematical models of systems and phenomena that appe ...

as an interacting particle system 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

E=\prod_ S_k

(cartesian product) where

G

is a finite or infinite graph, like

\mathbb Z

and where

S_k

is a finite space, like for instance

S_k=\

S_k=\

. The transition probability has a product form

P(d\sigma ,  \eta) = \otimes_ p_k(d\sigma_k ,  \eta)

where

\eta \in E

and

p_k(d\sigma_k ,  \eta)

is a probability distribution on

S_k

. In general some locality is required

p_k(d\sigma_k ,  \eta)=p_k(d\sigma_k ,  \eta_)

where

\eta_=(\eta_j)_

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 Toom's rule is a 2-dimensional cellular automaton model created by Andrei Toom Andrei Leonovich Toom (in Russian: Андрей Леонович Тоом), also known as André Toom, (1942 Tashkent, Soviet Union - 2022 Queens, New York City) was ...

Relation to lattice random fields

PCA may be used to simulate the Ising model of ferromagnetism in

statistical mechanics In physics, statistical mechanics is a mathematical framework that applies statistical methods and probability theory to large assemblies of microscopic entities. It does not assume or postulate any natural laws, but explains the macroscopic be ...

.. 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 particular when it is implemented in parallel.

Non Markovian generalization

The Galves-Löcherbach model is an example of a generalized PCA with a non Markovian aspect.