Stochastic cellular automaton

A stochastic cellular automaton (SCA), also known as a probabilistic cellular automaton (PCA), is a type of computational model. It consists of a grid of cells, where each cell has a particular state (e.g., "on" or "off"). The states of all cells evolve in discrete time steps according to a set of rules.

Unlike a standard cellular automaton where the rules are deterministic (fixed), the rules in a stochastic cellular automaton are probabilistic. This means a cell's next state is determined by chance, according to a set of probabilities that depend on the states of neighboring cells.^[1]

Despite the simple, local, and random nature of the rules, these models can produce complex global patterns through processes like emergence and self-organization. They are used to model a wide variety of real-world phenomena where randomness is a factor, such as the spread of forest fires, the dynamics of disease epidemics, or the simulation of ferromagnetism in physics (see Ising model).

As a mathematical object, a stochastic cellular automaton is a discrete-time random dynamical system. It is often analyzed within the frameworks of interacting particle systems and Markov chains, where it may be called a system of locally interacting Markov chains.^[2][3] See ^[4] for a more detailed introduction.

Formal definition

From the perspective of probability theory, a stochastic cellular automaton is a discrete-time Markov process. The configuration of all cells at a given time is a state ${\displaystyle \eta }$ in a product space ${\displaystyle E=\prod _{k\in G}S_{k}}$. Here, ${\displaystyle G}$ is a graph representing the grid of cells (e.g., ${\displaystyle \mathbb {Z} ^{d}}$), and each ${\displaystyle S_{k}}$ is the finite set of possible states for the cell ${\displaystyle k}$ (e.g., ${\displaystyle S_{k}=\{0,1\}}$).

The transition probability, which defines the dynamics, has a product form:

${\displaystyle P(d\sigma |\eta )=\bigotimes _{k\in G}p_{k}(d\sigma _{k}|\eta )}$

where ${\displaystyle \sigma }$ is the next configuration and ${\displaystyle p_{k}(d\sigma _{k}|\eta )}$ is a probability distribution on ${\displaystyle S_{k}}$.

Locality is a key requirement, meaning the probability of a cell ${\displaystyle k}$ changing its state depends only on the states of its neighbors. This is expressed as ${\displaystyle p_{k}(d\sigma _{k}|\eta )=p_{k}(d\sigma _{k}|\eta _{V_{k}})}$, where ${\displaystyle V_{k}}$ is a finite neighborhood of cell ${\displaystyle k}$ and ${\displaystyle \eta _{V_{k}}}$ are the states of the cells in that neighborhood. See ^[5] for a more detailed introduction from this 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 of ferromagnetism in statistical mechanics.^[1] Some categories of models were studied from a statistical mechanics point of view.

Cellular Potts model

There is a strong connection^[6] 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.