×

zbMATH — the first resource for mathematics

Markovianity of the invariant distribution of probabilistic cellular automata on the line. (English) Zbl 1371.37016
Summary: We revisit the problem of finding the conditions under which synchronous probabilistic cellular automata indexed by the line \(\mathbb{Z}\), or the periodic line \(\mathbb{Z} / n \mathbb{Z}\), depending on 2 neighbours, admit as invariant distribution the law of a space-indexed Markov chain. Our advances concern PCA defined on a finite alphabet, where most of existing results concern size 2 alphabet.
A part of the paper is also devoted to the comparison of different structures (\(\mathbb{Z}\), \(\mathbb{Z} / n \mathbb{Z}\), and also some structures constituted with two consecutive lines of the space-time diagram) with respect to the property to possess a Markovian invariant distribution.

MSC:
37B15 Dynamical aspects of cellular automata
60K35 Interacting random processes; statistical mechanics type models; percolation theory
60J22 Computational methods in Markov chains
37A25 Ergodicity, mixing, rates of mixing
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Albenque, M., A note on the enumeration of directed animals via gas considerations, Ann. Appl. Probab., 14, 5, 1860-1879, (2009) · Zbl 1194.60056
[2] Bagnoli, F., Cellular automata · Zbl 0940.68503
[3] Beliaev, Y. K.; Gromak, Y. I.; Malyshev, V. A., Invariant random Boolean fields, Math. Notes Acad. Sci. USSR, 6, 5, 792-799, (1969)
[4] Bousquet-Mélou, M., New enumerative results on two-dimensional directed animals, Discrete Math., 180, 1, 73-106, (1998) · Zbl 0974.05002
[5] Chassaing, P.; Mairesse, J., A non-ergodic probabilistic cellular automaton with a unique invariant measure, Stochastic Process. Appl., 121, 11, 2474-2487, (2011) · Zbl 1237.60076
[6] Chopard, B.; Dupis, A.; Masselot, A.; Luthi, P., Cellular automata and lattice Boltzmann techniques: an approach to model and simulate complex systems, Adv. Complex Syst., 5, 2, 103-246, (2002) · Zbl 1090.82030
[7] Dai Pra, P., Space-time large deviations for interacting particle systems, (1992), Rutgers Univ., (Ph.D. thesis) · Zbl 0797.60028
[8] P. Dai Pra, P. Louis, S. Roelly, Stationary measures and phase transition for a class of probabilistic cellular automata, Preprint, WIAS, 2001. URL http://books.google.fr/books?id=H9ExHAAACAAJ. · Zbl 1003.60090
[9] Dhar, D., Equivalence of the two-dimensional directed-site animal problem to baxter’s hard-square lattice-gas model, Phys. Rev. Lett., 49, 14, 959-962, (1982)
[10] Dhar, D., The directed animals and related problems, (Field Theory, Quantum Gravity and Strings (Meudon/Paris, 1984/1985), Lect. Notes Phys., vol. 246, (1986), Springer Berlin), 368-372
[11] Ganguly, N.; Sikdar, B.; Deutsch, A.; Canright, G.; Chaudhuri, P. P., A survey on cellular automata, tech. rep, (2003), Centre for High Performance Computing, Dresden University of Technology
[12] Gács, P., Reliable cellular automata with self-organization, J. Stat. Phys., 103, 90-99, (1998)
[13] Georgii, H., (Gibbs Measures and Phase Transitions, De Gruyter Studies in Maths, (2011), De Gruyter), URL http://books.google.fr/books?id=3vMCnvMH-hkC
[14] Kari, J., Theory of cellular automata: a survey, Theoret. Comput. Sci., 334, 1-3, 3-33, (2005) · Zbl 1080.68070
[15] Le Borgne, Y.; Marckert, J., Directed animals and gas models revisited, J. Combin., 14, 4, R71, (2007) · Zbl 1157.82332
[16] Lebowitz, J. L.; Maes, C.; Speer, E. R., Statistical mechanics of probabilistic cellular automata, J. Stat. Phys., 59, 1-2, 117-170, (1990) · Zbl 1083.82522
[17] Liggett, T., (Interacting Particle Systems, Classics in Mathematics, (1985), Springer), URL http://books.google.fr/books?id=I3aNPR1FursC · Zbl 0559.60078
[18] Louis, P., Automates cellulaires probabilistes : mesures stationnaires, mesures de Gibbs associées et ergodicité, (2002), Université Lille 1, (Ph.D. thesis)
[19] Mairesse, J.; Marcovici, I., Around probabilistic cellular automaton, Theoret. Comput. Sci., 559, 42-72, (2014) · Zbl 1360.68615
[20] Mairesse, J.; Marcovici, I., Probabilistic cellular automata and random fields with iid directions, Ann. Inst. Henri Poincaré Probab. Stat., 50, 2, 455-475, (2014) · Zbl 1359.37027
[21] Marckert, J., Directed animals, quadratic and rewriting systems, Electron. J. Combin., 19, 3, P45, (2012) · Zbl 1253.05082
[22] Marcovici, I., Automates cellulaires probabilistes et mesures spécifiques sur des espaces symboliques, (2013), Université Paris Diderot, (Ph.D. thesis)
[23] Toom, A.; Vasilyev, N.; Stavskaya, O.; Mityushin, L.; Kurdyumov, G.; Pirogov, S., (Dobrushin, R. L.; Kryukov, V. I.; Toom, A. L., Stochastic Cellular Systems: Ergodicity, Memory, Morphogenesis (Part: Discrete Local Markov systems, 1-182), (1990), Manchester University Press Manchester)
[24] Vasilyev, N., Bernoulli and Markov stationary measures in discrete local interactions, (Locally Interacting Systems and Their Application in Biology, (1978), Springer), 99-112 · Zbl 0403.60096
[25] Verhagen, A., An exactly soluble case of the triangular Ising model in a magnetic field, J. Stat. Phys., 15, 3, 219-231, (1976)
[26] Wolfram, S., (Cellular Automata and Complexity: Collected Papers, Advanced Book Program, (1994), Addison-Wesley Publishing Company), URL http://books.google.de/books?id=8u1EDgvtVhEC
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.