Stochastic cellular automaton

<h2 id="pca-as-markov-stochastic-processes">PCA as Markov stochastic processes</h2>
<p>As discrete-time Markov process, PCA are defined on a <a href="/facts/Product_space/0hg02IaX">product space</a> 
  
    
      
        E
        =
        
          ∏
          
            k
            ∈
            G
          
        
        
          S
          
            k
          
        
      
    
    {\displaystyle E=\prod _{k\in G}S_{k}}
  
 (cartesian product) where 
  
    
      
        G
      
    
    {\displaystyle G}

is a finite or infinite graph, like 
  
    
      
        
          Z
        
      
    
    {\displaystyle \mathbb {Z} }
  
 and where 
  
    
      
        
          S
          
            k
          
        
      
    
    {\displaystyle S_{k}}
  
 is a finite space, like for instance

S
          
            k
          
        
        =
        {
        −
        1
        ,
        +
        1
        }
      
    
    {\displaystyle S_{k}=\{-1,+1\}}
  
 or 
  
    
      
        
          S
          
            k
          
        
        =
        {
        0
        ,
        1
        }
      
    
    {\displaystyle S_{k}=\{0,1\}}
  
. The transition probability has a product form

P
        (
        d
        σ
        
          |
        
        η
        )
        =
        
          ⊗
          
            k
            ∈
            G
          
        
        
          p
          
            k
          
        
        (
        d
        
          σ
          
            k
          
        
        
          |
        
        η
        )
      
    
    {\displaystyle P(d\sigma |\eta )=\otimes _{k\in G}p_{k}(d\sigma _{k}|\eta )}
  
 where

η
        ∈
        E
      
    
    {\displaystyle \eta \in E}
  
 and 
  
    
      
        
          p
          
            k
          
        
        (
        d
        
          σ
          
            k
          
        
        
          |
        
        η
        )
      
    
    {\displaystyle p_{k}(d\sigma _{k}|\eta )}
  
 is a probability distribution on 
  
    
      
        
          S
          
            k
          
        
      
    
    {\displaystyle S_{k}}
  
.
In general some locality is required 
  
    
      
        
          p
          
            k
          
        
        (
        d
        
          σ
          
            k
          
        
        
          |
        
        η
        )
        =
        
          p
          
            k
          
        
        (
        d
        
          σ
          
            k
          
        
        
          |
        
        
          η
          
            
              V
              
                k
              
            
          
        
        )
      
    
    {\displaystyle p_{k}(d\sigma _{k}|\eta )=p_{k}(d\sigma _{k}|\eta _{V_{k}})}
  
 where

η
          
            
              V
              
                k
              
            
          
        
        =
        (
        
          η
          
            j
          
        
        
          )
          
            j
            ∈
            
              V
              
                k
              
            
          
        
      
    
    {\displaystyle \eta _{V_{k}}=(\eta _{j})_{j\in V_{k}}}
  
  with 
  
    
      
        
          
            V
            
              k
            
          
        
      
    
    {\displaystyle {V_{k}}}
  
 a finite neighbourhood of k. See <a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> for a more detailed introduction following the probability theory's point of view.
</p>
<h2 id="examples-of-stochastic-cellular-automaton">Examples of stochastic cellular automaton</h2>
<h3>Majority cellular automaton</h3>
<p>There is a version of the <a href="/facts/Majority_problem_(cellular_automaton)/jvAH2tRQ">majority cellular automaton</a> with probabilistic updating rules. See the <a href="/facts/Toom%2527s_rule/d6yPlV5j">Toom's rule</a>.
</p>
<h3>Relation to lattice random fields</h3>
<p>PCA may be used to simulate the <a href="/facts/Ising_model/lvBpj2h1">Ising model</a> of <a href="/facts/Ferromagnetism/fH3HFnSl">ferromagnetism</a> in <a href="/facts/Statistical_mechanics/6zMsNYYG">statistical mechanics</a>.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
Some categories of models were studied from a statistical mechanics point of view.
</p>
<h3>Cellular Potts model</h3>
<p>There is a strong connection<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a>
between probabilistic cellular automata and the <a href="/facts/Cellular_Potts_model/HymsL8za">cellular Potts model</a> in particular when it is implemented in parallel.
</p>
<h3>Non Markovian generalization</h3>
<p>The <a href="/facts/Galves%25E2%2580%2593L%25C3%25B6cherbach_model/qq5rrtFI">Galves–Löcherbach model</a> is an example of a generalized PCA with a non Markovian aspect.
</p>

<h2 id="further-reading">Further reading</h2>
<ul><li>Almeida, R. M.; Macau, E. E. N. (2010), "Stochastic cellular automata model for wildland fire spread dynamics", <i>9th Brazilian Conference on Dynamics, Control and their Applications, June 7–11, 2010</i>, vol. 285, p. 012038, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1088%2F1742-6596%2F285%2F1%2F012038">10.1088/1742-6596/285/1/012038</a>.</li>
<li>Clarke, K. C.; Hoppen, S. (1997), <a href="http://www.geog.ucsb.edu/~kclarke/Papers/clarkehoppengaydos.pdf">"A self-modifying cellular automaton model of historical urbanization in the San Francisco Bay area"</a> (PDF), <i>Environment and Planning B: Planning and Design</i>, 24 (2): 247–261, <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/1997EnPlB..24..247C">1997EnPlB..24..247C</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1068%2Fb240247">10.1068/b240247</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:40847078">40847078</a>.</li>
<li><a href="/facts/Meena_Mahajan/wg2GfBEc">Mahajan, Meena Bhaskar</a> (1992), <a href="http://www.imsc.res.in/~meena/papers/thesis.ps.gz"><i>Studies in language classes defined by different types of time-varying cellular automata</i></a>, Ph.D. dissertation, <a href="/facts/Indian_Institute_of_Technology_Madras/LC6q9DdR">Indian Institute of Technology Madras</a>.</li>
<li>Nishio, Hidenosuke; Kobuchi, Youichi (1975), "Fault tolerant cellular spaces", <i><a href="/facts/Journal_of_Computer_and_System_Sciences/cNek9ego">Journal of Computer and System Sciences</a></i>, 11 (2): 150–170, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fs0022-0000%2875%2980065-1">10.1016/s0022-0000(75)80065-1</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0389442">0389442</a>.</li>
<li><a href="/facts/Alvy_Ray_Smith/Q9CXUXv5">Smith, Alvy Ray III</a> (1972), "Real-time language recognition by one-dimensional cellular automata", <i><a href="/facts/Journal_of_Computer_and_System_Sciences/cNek9ego">Journal of Computer and System Sciences</a></i>, 6 (3): 233–253, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2FS0022-0000%2872%2980004-7">10.1016/S0022-0000(72)80004-7</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0309383">0309383</a>.</li>
<li>Louis, P.-Y.; Nardi, F. R., eds. (2018). <i>Probabilistic Cellular Automata</i>. Emergence, Complexity and Computation. Vol. 27. Springer. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-319-65558-1">10.1007/978-3-319-65558-1</a>. <a href="/facts/Hdl_(identifier)/rdebSxmC">hdl</a>:<a href="https://hdl.handle.net/2158%2F1090564">2158/1090564</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 9783319655581.</li>
<li>Agapie, A.; Andreica, A.; Giuclea, M. (2014), "Probabilistic Cellular Automata", <i>Journal of Computational Biology</i>, 21 (9): 699–708, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1089%2Fcmb.2014.0074">10.1089/cmb.2014.0074</a>, <a href="/facts/PMC_(identifier)/dX1zMt71">PMC</a> <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4148062">4148062</a>, <a href="/facts/PMID_(identifier)/JlHAvMHt">PMID</a> <a href="https://pubmed.ncbi.nlm.nih.gov/24999557">24999557</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>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 <a href="978-3-540-08450-1" target="_blank">978-3-540-08450-1</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>R. L. Dobrushin; V. I. Kri︠u︡kov; A. L. Toom (1978). Stochastic Cellular Systems: Ergodicity, Memory, Morphogenesis. Manchester University Press. ISBN 9780719022067. <a href="9780719022067" target="_blank">9780719022067</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>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. <a href="9783319655581" target="_blank">9783319655581</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>P.-Y. Louis PhD <a href="https://tel.archives-ouvertes.fr/tel-00002203v1" target="_blank">https://tel.archives-ouvertes.fr/tel-00002203v1</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>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. <a href="/wiki/Bibcode_(identifier)" target="_blank">/wiki/Bibcode_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>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. <a href="9783319655581" target="_blank">9783319655581</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
</ol>

Stochastic cellular automaton open-in-new

Stochastic cellular automaton