Probabilistic cellular automata and random fields with i.i.d. directions
Mairesse, Jean ; Marcovici, Irène
Annales de l'I.H.P. Probabilités et statistiques, Tome 50 (2014), p. 455-475 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

Considérons le modèle le plus simple d’automates cellulaires probabilistes (ACP) de dimension 1. Les cellules sont indexées par les entiers relatifs, l’alphabet est {0,1}, et toutes les cellules évoluent de manière synchrone. Le nouveau contenu d’une cellule est choisi aléatoirement, indépendamment des autres, selon une distribution dépendant seulement du contenu de la cellule et de sa voisine de droite. On connaît des conditions nécessaires et suffisantes portant sur les quatre paramètres d’un tel ACP pour qu’il ait la mesure produit de Bernoulli comme mesure invariante. Nous étudions les propriétés du champ aléatoire formé par le diagramme espace-temps obtenu lorsqu’on itère l’ACP à partir de sa mesure invariante de Bernoulli. Il s’agit d’un champ aléatoire non trivial, présentant de très faibles dépendances et de jolies propriétés combinatoires. En particulier, les lignes horizontales mais aussi les lignes selon les autres directions sont constituées de variables aléatoires i.i.d. Nous étudions l’extension de ces résultats à des mesures invariantes de forme markovienne, ainsi qu’aux ACP ayant des alphabets et des voisinages plus grands.

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.

Publié le : 2014-01-01
DOI : https://doi.org/10.1214/12-AIHP530
Classification:  37B15,  60J05,  60G60 
@article{AIHPB_2014__50_2_455_0,
     author = {Mairesse, Jean and Marcovici, Ir\`ene},
     title = {Probabilistic cellular automata and random fields with i.i.d. directions},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     volume = {50},
     year = {2014},
     pages = {455-475},
     doi = {10.1214/12-AIHP530},
     mrnumber = {3189079},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIHPB_2014__50_2_455_0}
}

Mairesse, Jean; Marcovici, Irène. Probabilistic cellular automata and random fields with i.i.d. directions. Annales de l'I.H.P. Probabilités et statistiques, Tome 50 (2014) pp. 455-475. doi : 10.1214/12-AIHP530. http://gdmltest.u-ga.fr/item/AIHPB_2014__50_2_455_0/

[1] Y. Belyaev, Y. Gromak and V. Malyshev. Invariant random Boolean fields. Mat. Zametki 6 (1969) 555-566 (in Russian). | MR 258113 | Zbl 0201.18605

[2] M. Bousquet-Mélou. New enumerative results on two-dimensional directed animals. Discrete Math. 180 (1998) 73-106. | MR 1603701 | Zbl 0974.05002

[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. | MR 2853437 | Zbl 1230.68148

[4] D. Dhar. Exact solution of a directed-site animals-enumeration problem in three dimensions. Phys. Rev. Lett. 51(10) (1983) 853-856. | MR 721768

[5] P. Gács. Reliable cellular automata with self-organization. J. Statist. Phys. 103(1-2) (2001) 45-267. | MR 1828729 | Zbl 0973.68158

[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. | MR 1017739 | Zbl 0683.68045

[7] G. Hedlund. Endomorphisms and automorphisms of the shift dynamical system. Math. Systems Theory 3 (1969) 320-375. | MR 259881 | Zbl 0182.56901

[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. | MR 2877007

[9] Y. Le Borgne and J.-F. Marckert. Directed animals and gas models revisited. Electron. J. Combin. 14(1) (2007) R71. | MR 2365970 | Zbl 1157.82332

[10] J. Lebowitz, C. Maes and E. Speer. Statistical mechanics of probabilistic cellular automata. J. Statist. Phys. 59(1-2) (1990) 117-170. | MR 1049965 | Zbl 1083.82522

[11] J.-F. Marckert. Directed animals, quadratic and rewriting systems. Electron. J. Combin. 19(3) (2012) P45. | MR 2988867 | Zbl 1253.05082

[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. | MR 599548 | Zbl 0441.68053

[13] A. Toom. Algorithmical unsolvability of the ergodicity problem for binary cellular automata. Markov Process. Related Fields 6(4) (2000) 569-577. | MR 1805094 | Zbl 0973.68160

[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] N. Vasilyev. Bernoulli and Markov stationary measures in discrete local interactions. In Developments in Statistics, Vol. 1 99-112. Academic Press, New York, 1978. | MR 505437 | Zbl 0403.60096

[16] A. Verhagen. An exactly soluble case of the triangular Ising model in a magnetic field. J. Statist. Phys. 15(3) (1976) 219-231. | MR 428999