Stochastic cellular automaton

This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (June 2013) (Learn how and when to remove this template message)

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 }$ 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{\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 )=\underset{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.

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, 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", Environment and Planning B: Planning and Design 24 (2): 247–261, doi:10.1068/b240247, Bibcode: 1997EnPlB..24..247C, http://www.geog.ucsb.edu/~kclarke/Papers/clarkehoppengaydos.pdf .
• Studies in language classes defined by different types of time-varying cellular automata, Ph.D. dissertation, Indian Institute of Technology Madras, 1992, http://www.imsc.res.in/~meena/papers/thesis.ps.gz .
• 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 .
• "Real-time language recognition by one-dimensional cellular automata", Journal of Computer and System Sciences 6 (3): 233–253, 1972, doi:10.1016/S0022-0000(72)80004-7 .
• Probabilistic Cellular Automata. Emergence, Complexity and Computation. 27. Springer. 2018. doi:10.1007/978-3-319-65558-1. 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, PMID 24999557 

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/Stochastic cellular automaton. Read more