Stochastic cellular automaton

Short description: Cellular automaton with probabilistic rules

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.

## Contents

* 1 Formal definition
* 2 Examples of stochastic cellular automaton
* 2.1 Majority cellular automaton
* 2.2 Relation to lattice random fields
* 2.3 Cellular Potts model
* 2.4 Non Markovian generalization
* 3 References
* 4 Further reading

## 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 η in a product space E=∏k∈GSk. Here, G is a graph representing the grid of cells (e.g., ℤd), and each Sk is the finite set of possible states for the cell k (e.g., Sk={0,1}).

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

P(dσ|η)=⨂k∈Gpk(dσk|η)

where σ is the next configuration and pk(dσk|η) is a probability distribution on Sk.

Locality is a key requirement, meaning the probability of a cell k changing its state depends only on the states of its neighbors. This is expressed as pk(dσk|η)=pk(dσk|ηVk), where Vk is a finite neighborhood of cell k and ηVk 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. ↑ 1.0 1.1 Vichniac, G. (1984), "Simulating physics with cellular automata", Physica D 10 (1–2): 96–115, doi:10.1016/0167-2789(84)90253-7, Bibcode: 1984PhyD...10...96V .
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, 653, Springer-Verlag, Berlin-New York, ISBN 978-3-540-08450-1
3. ↑ R. L. Dobrushin; V. I. Kri︠u︡kov; A. L. Toom (1978). Stochastic Cellular Systems: Ergodicity, Memory, Morphogenesis. Manchester University Press. ISBN 9780719022067. https://books.google.com/books?id=0Wa7AAAAIAAJ&q=locally+interacting+markov+chains+toom+Dobrushin&pg=PA181.
4. ↑ Fernandez, R.; Louis, P.-Y.; Nardi, F. R. (2018). "Chapter 1: Overview: PCA Models and Issues". Probabilistic Cellular Automata. Springer. doi:10.1007/978-3-319-65558-1_1. ISBN 9783319655581.
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". Probabilistic Cellular Automata. Springer. doi:10.1007/978-3-319-65558-1_18. 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, 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

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Stochastic_cellular_automaton&oldid=3983327"