Probabilistic cellular automata

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 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 as an interacting particle system in discrete-time.

As discrete-time Markov process, PCA are defined on a product space ${\displaystyle E=\prod _{k\in G}S_{k}}$ (cartesian product) where ${\displaystyle G}$ is a finite or infinite graph, like ${\displaystyle \mathbb {Z} }$ and where ${\displaystyle S_{k}}$ is a finite space, like for instance ${\displaystyle S_{k}=\{-1,+1\}}$ or ${\displaystyle S_{k}=\{0,1\}}$. The transition probability has a product form ${\displaystyle P(d\sigma |\eta )=\otimes _{k\in G}p_{k}(d\sigma _{k}|\eta )}$ where ${\displaystyle \eta \in E}$ and ${\displaystyle p_{k}(d\sigma _{k}|\eta )}$ is a probability distribution on ${\displaystyle S_{k}}$. In general some locality is required ${\displaystyle p_{k}(d\sigma _{k}|\eta )=p_{k}(d\sigma _{k}|\eta _{V_{k}})}$ where ${\displaystyle \eta _{V_{k}}=(\eta _{j})_{j\in V_{k}}}$ with ${\displaystyle {V_{k}}}$ a finite neighbourhood of k. See for a more detailed introduction following the probability theory's point of view.

...
Wikipedia