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.

References

1. Vichniac, G. (1984), "Simulating physics with cellular automata", Physica D, 10 (1–2): 96–115, Bibcode:1984PhyD...10...96V, doi:10.1016/0167-2789(84)90253-7 .
2. Toom, A. L. (1978), Locally Interacting Systems and their Application in Biology: Proceedings of the School-Seminar on Markov Interaction Processes in Biology, held in Pushchino, March 1976, Lecture Notes in Mathematics, vol. 653, Springer-Verlag, Berlin-New York, ISBN   978-3-540-08450-1, MR   0479791
3. R. L. Dobrushin; V. I. Kri︠u︡kov; A. L. Toom (1978). Stochastic Cellular Systems: Ergodicity, Memory, Morphogenesis. Manchester University Press. ISBN   9780719022067.
4. Fernandez, R.; Louis, P.-Y.; Nardi, F. R. (2018). "Chapter 1: Overview: PCA Models and Issues". In Louis, P.-Y.; Nardi, F. R. (eds.). Probabilistic Cellular Automata. Springer. doi:10.1007/978-3-319-65558-1_1. ISBN   9783319655581. S2CID   64938352.
5. P.-Y. Louis PhD
6. Boas, Sonja E. M.; Jiang, Yi; Merks, Roeland M. H.; Prokopiou, Sotiris A.; Rens, Elisabeth G. (2018). "Chapter 18: Cellular Potts Model: Applications to Vasculogenesis and Angiogenesis". In Louis, P.-Y.; Nardi, F. R. (eds.). Probabilistic Cellular Automata. Springer. doi:10.1007/978-3-319-65558-1_18. hdl:1887/69811. ISBN   9783319655581.

Further reading

• 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