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.

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 }${\displaystyle \eta } in a product space ${\displaystyle E=\prod _{k\in G}S_{k}}${\displaystyle E=\prod _{k\in G}S_{k}}. Here, ${\displaystyle G}${\displaystyle G} is a graph representing the grid of cells (e.g., ${\displaystyle \mathbb {Z} ^{d}}${\displaystyle \mathbb {Z} ^{d}}), and each ${\displaystyle S_{k}}${\displaystyle S_{k}} is the finite set of possible states for the cell ${\displaystyle k}${\displaystyle k} (e.g., ${\displaystyle S_{k}=\{0,1\}}${\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 )}${\displaystyle P(d\sigma |\eta )=\bigotimes _{k\in G}p_{k}(d\sigma _{k}|\eta )}

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

Locality is a key requirement, meaning the probability of a cell ${\displaystyle k}${\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}})}${\displaystyle p_{k}(d\sigma _{k}|\eta )=p_{k}(d\sigma _{k}|\eta _{V_{k}})}, where ${\displaystyle V_{k}}${\displaystyle V_{k}} is a finite neighborhood of cell ${\displaystyle k}${\displaystyle k} and ${\displaystyle \eta _{V_{k}}}${\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.

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.^[1] Some categories of models were studied from a statistical mechanics point of view.

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

• Almeida, R. M.; Macau, E. E. N. (2010), "Stochastic cellular automata model for wildland fire spread dynamics", 9th Brazilian Conference on Dynamics, Control and their Applications, June 7–11, 2010, vol. 285, p. 012038, doi:10.1088/1742-6596/285/1/012038 .
• Clarke, K. C.; Hoppen, S. (1997), "A self-modifying cellular automaton model of historical urbanization in the San Francisco Bay area" (PDF), Environment and Planning B: Planning and Design, 24 (2): 247–261, Bibcode:1997EnPlB..24..247C, doi:10.1068/b240247, S2CID 40847078 .
• Mahajan, Meena Bhaskar (1992), Studies in language classes defined by different types of time-varying cellular automata, Ph.D. dissertation, Indian Institute of Technology Madras .
• Nishio, Hidenosuke; Kobuchi, Youichi (1975), "Fault tolerant cellular spaces", Journal of Computer and System Sciences , 11 (2): 150–170, doi:10.1016/s0022-0000(75)80065-1 , MR 0389442 .
• Smith, Alvy Ray III (1972), "Real-time language recognition by one-dimensional cellular automata", Journal of Computer and System Sciences , 6 (3): 233–253, doi:10.1016/S0022-0000(72)80004-7 , MR 0309383 .
• Louis, P.-Y.; Nardi, F. R., eds. (2018). Probabilistic Cellular Automata. Emergence, Complexity and Computation. Vol. 27. Springer. doi:10.1007/978-3-319-65558-1. hdl:2158/1090564. ISBN 9783319655581.
• Agapie, A.; Andreica, A.; Giuclea, M. (2014), "Probabilistic Cellular Automata", Journal of Computational Biology, 21 (9): 699–708, doi:10.1089/cmb.2014.0074, PMC 4148062 , PMID 24999557

• Cellular automata
• Lattice models
• Self-organization
• Complex systems theory
• Spatial processes
• Markov models
• Stochastic processes
• Models of computation

• Articles with short description
• Short description is different from Wikidata
• Wikipedia articles that are too technical from June 2013
• All articles that are too technical