Probabilistic cellular automata and random fields with i.i.d. directions

Jean Mairesse; Irène Marcovici

Annales de l'I.H.P. Probabilités et statistiques (2014)

  • Volume: 50, Issue: 2, page 455-475
  • ISSN: 0246-0203

Abstract

top
Let us consider the simplest model of one-dimensional probabilistic cellular automata (PCA). The cells are indexed by the integers, the alphabet is { 0 , 1 } , and all the cells evolve synchronously. The new content of a cell is randomly chosen, independently of the others, according to a distribution depending only on the content of the cell itself and of its right neighbor. There are necessary and sufficient conditions on the four parameters of such a PCA to have a Bernoulli product invariant measure. We study the properties of the random field given by the space–time diagram obtained when iterating the PCA starting from its Bernoulli product invariant measure. It is a non-trivial random field with very weak dependences and nice combinatorial properties. In particular, not only the horizontal lines but also the lines in any other direction consist of i.i.d. random variables. We study extensions of the results to Markovian invariant measures, and to PCA with larger alphabets and neighborhoods.

How to cite

top

Mairesse, Jean, and Marcovici, Irène. "Probabilistic cellular automata and random fields with i.i.d. directions." Annales de l'I.H.P. Probabilités et statistiques 50.2 (2014): 455-475. <http://eudml.org/doc/272015>.

@article{Mairesse2014,
abstract = {Let us consider the simplest model of one-dimensional probabilistic cellular automata (PCA). The cells are indexed by the integers, the alphabet is $\lbrace 0,1\rbrace $, and all the cells evolve synchronously. The new content of a cell is randomly chosen, independently of the others, according to a distribution depending only on the content of the cell itself and of its right neighbor. There are necessary and sufficient conditions on the four parameters of such a PCA to have a Bernoulli product invariant measure. We study the properties of the random field given by the space–time diagram obtained when iterating the PCA starting from its Bernoulli product invariant measure. It is a non-trivial random field with very weak dependences and nice combinatorial properties. In particular, not only the horizontal lines but also the lines in any other direction consist of i.i.d. random variables. We study extensions of the results to Markovian invariant measures, and to PCA with larger alphabets and neighborhoods.},
author = {Mairesse, Jean, Marcovici, Irène},
journal = {Annales de l'I.H.P. Probabilités et statistiques},
keywords = {probabilistic cellular automata; product-form invariant measures; random fields},
language = {eng},
number = {2},
pages = {455-475},
publisher = {Gauthier-Villars},
title = {Probabilistic cellular automata and random fields with i.i.d. directions},
url = {http://eudml.org/doc/272015},
volume = {50},
year = {2014},
}

TY - JOUR
AU - Mairesse, Jean
AU - Marcovici, Irène
TI - Probabilistic cellular automata and random fields with i.i.d. directions
JO - Annales de l'I.H.P. Probabilités et statistiques
PY - 2014
PB - Gauthier-Villars
VL - 50
IS - 2
SP - 455
EP - 475
AB - Let us consider the simplest model of one-dimensional probabilistic cellular automata (PCA). The cells are indexed by the integers, the alphabet is $\lbrace 0,1\rbrace $, and all the cells evolve synchronously. The new content of a cell is randomly chosen, independently of the others, according to a distribution depending only on the content of the cell itself and of its right neighbor. There are necessary and sufficient conditions on the four parameters of such a PCA to have a Bernoulli product invariant measure. We study the properties of the random field given by the space–time diagram obtained when iterating the PCA starting from its Bernoulli product invariant measure. It is a non-trivial random field with very weak dependences and nice combinatorial properties. In particular, not only the horizontal lines but also the lines in any other direction consist of i.i.d. random variables. We study extensions of the results to Markovian invariant measures, and to PCA with larger alphabets and neighborhoods.
LA - eng
KW - probabilistic cellular automata; product-form invariant measures; random fields
UR - http://eudml.org/doc/272015
ER -

References

top
  1. [1] Y. Belyaev, Y. Gromak and V. Malyshev. Invariant random Boolean fields. Mat. Zametki 6 (1969) 555–566 (in Russian). Zbl0201.18605MR258113
  2. [2] M. Bousquet-Mélou. New enumerative results on two-dimensional directed animals. Discrete Math.180 (1998) 73–106. Zbl0974.05002MR1603701
  3. [3] A. Bušić, J. Mairesse and I. Marcovici. Probabilistic cellular automata, invariant measures, and perfect sampling. In 28th International Symposium on Theoretical Aspects of Computer Science 296–307. Schloss Dagsthul. Leibniz-Zent. Inform., Wadern, 2011. Zbl1230.68148MR2853437
  4. [4] D. Dhar. Exact solution of a directed-site animals-enumeration problem in three dimensions. Phys. Rev. Lett. 51(10) (1983) 853–856. MR721768
  5. [5] P. Gács. Reliable cellular automata with self-organization. J. Statist. Phys. 103(1–2) (2001) 45–267. Zbl0973.68158MR1828729
  6. [6] S. Goldstein, R. Kuik, J. Lebowitz and C. Maes. From PCAs to equilibrium systems and back. Comm. Math. Phys. 125(1) (1989) 71–79. Zbl0683.68045MR1017739
  7. [7] G. Hedlund. Endomorphisms and automorphisms of the shift dynamical system. Math. Systems Theory3 (1969) 320–375. Zbl0182.56901MR259881
  8. [8] J. Kari and S. Taati. Conservation laws and invariant measures in surjective cellular automata. In Automata 2011, DMTCS Proceedings 113–122. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2012. Zbl1323.37011MR2877007
  9. [9] Y. Le Borgne and J.-F. Marckert. Directed animals and gas models revisited. Electron. J. Combin. 14(1) (2007) R71. Zbl1157.82332MR2365970
  10. [10] J. Lebowitz, C. Maes and E. Speer. Statistical mechanics of probabilistic cellular automata. J. Statist. Phys. 59(1–2) (1990) 117–170. Zbl1083.82522MR1049965
  11. [11] J.-F. Marckert. Directed animals, quadratic and rewriting systems. Electron. J. Combin. 19(3) (2012) P45. Zbl1253.05082MR2988867
  12. [12] A. Toom. Stable and attractive trajectories in multicomponent systems. In Multicomponent Random Systems 549–575. Adv. Probab. Related Topics 6. Dekker, New York, 1980. Zbl0441.68053MR599548
  13. [13] A. Toom. Algorithmical unsolvability of the ergodicity problem for binary cellular automata. Markov Process. Related Fields 6(4) (2000) 569–577. Zbl0973.68160MR1805094
  14. [14] A. Toom, N. Vasilyev, O. Stavskaya, L. Mityushin, G. Kurdyumov and S. Pirogov. Discrete local Markov systems. In Stochastic Cellular Systems: Ergodicity, Memory, Morphogenesis. R. Dobrushin, V. Kryukov and A. Toom (Eds). Manchester Univ. Press, Manchester, 1990. 
  15. [15] N. Vasilyev. Bernoulli and Markov stationary measures in discrete local interactions. In Developments in Statistics, Vol. 1 99–112. Academic Press, New York, 1978. Zbl0403.60096MR505437
  16. [16] A. Verhagen. An exactly soluble case of the triangular Ising model in a magnetic field. J. Statist. Phys. 15(3) (1976) 219–231. MR428999

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.