[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/stochastic-cellular-automaton-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en\/wiki24\/stochastic-cellular-automaton-wikipedia\/","headline":"Stochastic cellular automaton – Wikipedia","name":"Stochastic cellular automaton – Wikipedia","description":"before-content-x4 From Wikipedia, the free encyclopedia after-content-x4 Cellular automaton with probabilistic rules Stochastic cellular automata or probabilistic cellular automata (PCA)","datePublished":"2015-09-12","dateModified":"2015-09-12","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en\/wiki24\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/af7086e41950c4fda2f04eb064603b64da1a5c4e","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/af7086e41950c4fda2f04eb064603b64da1a5c4e","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/en\/wiki24\/stochastic-cellular-automaton-wikipedia\/","wordCount":4595,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4From Wikipedia, the free encyclopedia       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Cellular automaton with probabilistic rulesStochastic cellular automata or probabilistic cellular automata (PCA) or random cellular automata or locally interacting Markov chains[1][2] are an important extension of cellular automaton. Cellular automata are a discrete-time dynamical system of interacting entities, whose state is discrete.       (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4The state of the collection of entities is updated at each discrete time according to some simple homogeneous rule. All entities’ states are updated in parallel or synchronously. Stochastic Cellular Automata are CA whose updating rule is a stochastic one, which means the new entities’ states are chosen according to some probability distributions. It is a discrete-time random dynamical system. From the spatial interaction between the entities, despite the simplicity of the updating rules, complex behaviour may emerge like self-organization. As mathematical object, it may be considered in the framework of stochastic processes as an interacting particle system in discrete-time.See [3]for a more detailed introduction.Table of ContentsPCA as Markov stochastic processes[edit]Examples of stochastic cellular automaton[edit]Majority cellular automaton[edit]Relation to lattice random fields[edit]Cellular Potts model[edit]Non Markovian generalization[edit]References[edit]Further reading[edit]PCA as Markov stochastic processes[edit]As discrete-time Markov process, PCA are defined on a product space        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4E=\u220fk\u2208GSk{displaystyle E=prod _{kin G}S_{k}} (cartesian product) where G{displaystyle G}is a finite or infinite graph, like Z{displaystyle mathbb {Z} } and where Sk{displaystyle S_{k}} is a finite space, like for instanceSk={\u22121,+1}{displaystyle S_{k}={-1,+1}} or Sk={0,1}{displaystyle S_{k}={0,1}}. The transition probability has a product formP(d\u03c3|\u03b7)=\u2297k\u2208Gpk(d\u03c3k|\u03b7){displaystyle P(dsigma |eta )=otimes _{kin G}p_{k}(dsigma _{k}|eta )} where\u03b7\u2208E{displaystyle eta in E} and pk(d\u03c3k|\u03b7){displaystyle p_{k}(dsigma _{k}|eta )} is a probability distribution on Sk{displaystyle S_{k}}.In general some locality is required pk(d\u03c3k|\u03b7)=pk(d\u03c3k|\u03b7Vk){displaystyle p_{k}(dsigma _{k}|eta )=p_{k}(dsigma _{k}|eta _{V_{k}})} where\u03b7Vk=(\u03b7j)j\u2208Vk{displaystyle eta _{V_{k}}=(eta _{j})_{jin V_{k}}}  with Vk{displaystyle {V_{k}}} a finite neighbourhood of k. See [4] for a more detailed introduction following the probability theory’s point of view.Examples of stochastic cellular automaton[edit]Majority cellular automaton[edit]There is a version of the majority cellular automaton with probabilistic updating rules. See the Toom’s rule.Relation to lattice random fields[edit]PCA may be used to simulate the Ising model of ferromagnetism in statistical mechanics.[5]Some categories of models were studied from a statistical mechanics point of view.Cellular Potts model[edit]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[edit]The Galves-L\u00f6cherbach model is an example of a generalized PCA with a non Markovian aspect.References[edit]^ 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.\u00a0653, Springer-Verlag, Berlin-New York, ISBN\u00a0978-3-540-08450-1, MR\u00a00479791^ R. L. Dobrushin; V. I. Kri\ufe20u\ufe21kov; A. L. Toom (1978). Stochastic Cellular Systems: Ergodicity, Memory, Morphogenesis. ISBN\u00a09780719022067.^ 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\u00a09783319655581. S2CID\u00a064938352.^ P.-Y. Louis PhD^ Vichniac, G. (1984), “Simulating physics with cellular automata”, Physica D, 10 (1\u20132): 96\u2013115, Bibcode:1984PhyD…10…96V, doi:10.1016\/0167-2789(84)90253-7.^ 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\u00a09783319655581.Further reading[edit]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\u201311, 2010, 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\u2013261, doi:10.1068\/b240247, S2CID\u00a040847078.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\u2013170, doi:10.1016\/s0022-0000(75)80065-1, MR\u00a00389442.Smith, Alvy Ray, III (1972), “Real-time language recognition by one-dimensional cellular automata”, Journal of Computer and System Sciences, 6 (3): 233\u2013253, doi:10.1016\/S0022-0000(72)80004-7, MR\u00a00309383.Louis, P.-Y.; Nardi, F. R., eds. (2018). Probabilistic Cellular Automata. Emergence, Complexity and Computation. Vol.\u00a027. Springer. doi:10.1007\/978-3-319-65558-1. hdl:2158\/1090564. ISBN\u00a09783319655581.Agapie, A.; Andreica, A.; Giuclea, M. (2014), “Probabilistic Cellular Automata”, Journal of Computational Biology, 21 (9): 699\u2013708, doi:10.1089\/cmb.2014.0074, PMC\u00a04148062, PMID\u00a024999557     (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/stochastic-cellular-automaton-wikipedia\/#breadcrumbitem","name":"Stochastic cellular automaton – Wikipedia"}}]}]