×

zbMATH — the first resource for mathematics

Ergodicity of some classes of cellular automata subject to noise. (English) Zbl 07055679
Summary: Cellular automata (CA) are dynamical systems on symbolic configurations on the lattice. They are also used as models of massively parallel computers. As dynamical systems, one would like to understand the effect of small random perturbations on the dynamics of CA. As models of computation, they can be used to study the reliability of computation against noise.We consider various families of CA (nilpotent, permutive, gliders, CA with a spreading symbol, surjective, algebraic) and prove that they are highly unstable against noise, meaning that they forget their initial conditions under slightest positive noise. This is manifested as the ergodicity of the resulting probabilistic CA. The proofs involve a collection of different techniques (couplings, entropy, Fourier analysis), depending on the dynamical properties of the underlying deterministic CA and the type of noise.
MSC:
60K35 Interacting random processes; statistical mechanics type models; percolation theory
60J05 Discrete-time Markov processes on general state spaces
37B15 Dynamical aspects of cellular automata
37A50 Dynamical systems and their relations with probability theory and stochastic processes
PDF BibTeX XML Cite
Full Text: DOI Euclid arXiv
References:
[1] A. Adamatzky (ed.), Cellular automata, Encyclopedia of Complexity and Systems Science, Springer, 2009.
[2] V. Belitsky and P. A. Ferrari, Ballistic annihilation and deterministic surface growth, Journal of Statistical Physics 80 (1995), 517-543. · Zbl 1081.60553
[3] V. Belitsky and P. A. Ferrari, Invariant measures and convergence properties for cellular automaton 184 and related processes, Journal of Statistical Physics 118 (2005), no. 3-4, 589-623. · Zbl 1126.37301
[4] J. van den Berg and J. E. Steif, On the existence and nonexistence of finitary codings for a class of random fields, The Annals of Probability 27 (1999), no. 3, 1501-1522. · Zbl 0968.60091
[5] M. Bramson and C. Neuhauser, Survival of one-dimensional cellular automata under random perturbations, The Annals of Probability 22 (1994), no. 1, 244-263. · Zbl 0793.60107
[6] A. Bušić, J. Mairesse, and I. Marcovici, Probabilistic cellular automata, invariant measures, and perfect sampling, Advances in Applied Probability 45 (2013), no. 4, 960-980. · Zbl 1327.37008
[7] T. Ceccherini-Silberstein and M. Coornaert, Cellular automata and groups, Springer, 2010. · Zbl 1218.37004
[8] P. Chassaing and J. Mairesse, A non-ergodic probabilistic cellular automaton with a unique invariant measure, Stochastic Processes and their Applications 121 (2010), no. 11, 2474-2487. · Zbl 1237.60076
[9] B. Chopard and M. Droz, Cellular automata modeling of physical systems, Cambridge University Press, 1998. · Zbl 0973.82033
[10] C. F. Coletti and P. Tisseur, Invariant measures and decay of correlations for a class of ergodic probabilistic cellular automata, Journal of Statistical Physics 140 (2010), 103-121. · Zbl 1196.37024
[11] T. M. Cover and J. A. Thomas, Elements of information theory, Wiley, 1991. · Zbl 0762.94001
[12] P. Dai Pra, P.-Y. Louis, and S. Rœlly, Stationary measures and phase transition for a class of probabilistic cellular automata, ESAIM: Probability and Statistics 6 (2002), 89-104. · Zbl 1003.60090
[13] M. Denker, C. Grillenberger, and K. Sigmund, Ergodic theory on compact spaces, Springer-Verlag, 1976. · Zbl 0328.28008
[14] R. Durrett, Oriented percolation in two dimensions, The Annals of Probability 12 (1984), no. 4, 999-1040. · Zbl 0567.60095
[15] R. Durrett, Lecture notes on particle systems and percolation, Wadsworth & Brooks/Cole, 1988. · Zbl 0659.60129
[16] P. Ferrari, Ergodicity for a class of probabilistic cellular automata, Revista de Matemáticas Aplicadas 12 (1991), 93-102. · Zbl 0743.68100
[17] P. A. Ferrari, A. Maass, S. Martinez, and P. Ney, Cesàro mean distribution of group automata starting from measures with summable decay, Ergodic Theory and Dynamical Systems 20 (2000), no. 6, 1657-1670. · Zbl 0992.37011
[18] R. Fisch, The one-dimensional cyclic cellular automaton: a system with deterministic dynamics that emulates an interacting particle system with stochastic dynamics, Journal of Theoretical Probabilities 3 (1990), no. 2, 311-338. · Zbl 0701.60105
[19] P. Gács, Reliable computation with cellular automata, Journal of Computer and System Sciences 32 (1986), no. 1, 15-78. · Zbl 0621.68038
[20] P. Gács, Reliable cellular automata with self-organization, Journal of Statistical Physics 103 (2001), no. 1-2, 45-267. · Zbl 0973.68158
[21] M. Garzon, Models of massive parallelism, Springer, 1995. · Zbl 0844.68041
[22] H.-O. Georgii, Gibbs measures and phase transitions, De Gruyter, 1988. · Zbl 0657.60122
[23] S. Goldstein, R. Kuik, J. L. Lebowitz, and C. Maes, From PCA’s to equilibrium systems and back, Communications in Mathematical Physics 125 (1989), 71-79. · Zbl 0683.68045
[24] L. Gray, The behavior of processes with statistical mechanical properties, Percolation Theory and Ergodic Theory of Infinite Particle Systems (H. Kesten, ed.), The IMA Volumes in Mathematics and Its Applications, vol. 8, Springer, 1987, pp. 131-167.
[25] P. Guillon and G. Richard, Nilpotency and limit sets of cellular automata, Proceedings of the 33rd International Symposium (MFCS 2008), LNCS, vol. 5162, Springer, 2008, pp. 375-386. · Zbl 1173.68572
[26] B. Hellouin de Menibus and M. Sablik, Self-organisation in cellular automata with coalescent particles: qualitative and quantitative approaches, Journal of Statistical Physics 167 (2017), no. 5, 1180-1220. · Zbl 1423.37016
[27] B. Hellouin de Menibus and M. Sablik, Characterization of sets of limit measures of a cellular automaton iterated on a random configuration, Ergodic Theory and Dynamical Systems 38 (2018), no. 2, 601-650. · Zbl 1407.37016
[28] B. Hellouin de Menibus, V. Salo, and G. Theyssier, Characterizing asymptotic randomization in abelian cellular automata, Ergodic Theory and Dynamical Systems (To appear).
[29] R. Holley, Free energy in a Markovian model of a lattice spin system, Communications in Mathematical Physics 23 (1971), no. 2, 87-99. · Zbl 0241.60096
[30] A. E. Holroyd, I. Marcovici, and J. B. Martin, Percolation games, probabilistic cellular automata, and the hard-core model, Probability Theory and Related Fields (To appear). · Zbl 1418.91100
[31] J.-F. Marckert J. Casse, Markovianity of the invariant distribution of probabilistic cellular automata on the line, Stochastic Processes and their Applications 125 (2015), no. 9, 3458-3483. · Zbl 1371.37016
[32] B. Jahnel and C. Külske, A class of non-ergodic probabilistic cellular automata with unique invariant measure and quasi-periodic orbit, Stochastic Processes and their Applications 125 (2015), no. 6, 2427-2450. · Zbl 1315.82005
[33] J. Kari, The nilpotency problem of one-dimensional cellular automata, SIAM Journal on Computing 21 (1992), no. 3, 571-586. · Zbl 0761.68067
[34] J. Kari, Theory of cellular automata: A survey, Theoretical Computer Science 334 (2005), 3-33. · Zbl 1080.68070
[35] J. Kari and S. Taati, Statistical mechanics of surjective cellular automata, Journal of Statistical Physics 160 (2015), no. 5, 1198-1243. · Zbl 1360.37044
[36] O. Kozlov and N. Vasilyev, Reversible Markov chains with local interaction, Multicomponent Random Systems (R. L. Dobrushin and Ya. G. Sinai, eds.), Marcel Dekker, 1980, pp. 451-469. · Zbl 0444.60099
[37] P. Kůrka, Cellular automata with vanishing particles, Fundamenta Informaticae 58 (2003), no. 3-4, 203-221. · Zbl 1111.68521
[38] P. Kůrka, Topological and symbolic dynamics, Cours Spécialisés, vol. 11, Société Mathématique de France, 2003. · Zbl 1038.37011
[39] J. K. Lebowitz, C. Maes, and E. R. Speer, Statistical mechanics of probabilistic cellular automata, Journal of Statistical Physics 59 (1990), no. 1-2, 117-170. · Zbl 1083.82522
[40] T. M. Liggett, Interacting particle systems, Springer, 1985. · Zbl 0559.60078
[41] D. A. Lind, Applications of ergodic theory and sofic systems to cellular automata, Physica D. Nonlinear Phenomena 10 (1984), no. 1-2, 36-44. · Zbl 0562.68038
[42] T. Lindvall, Lectures on the coupling method, Dover, 2002. · Zbl 1013.60001
[43] P.-Y. Louis, Ergodicity of PCA: Equivalence between spatial and temporal mixing conditions, Electronic Communications in Probability 9 (2004), 119-131. · Zbl 1059.60098
[44] P.-Y. Louis and F. R. Nardi (eds.), Probabilistic cellular automata: Theory, applications and future perspectives, Springer, 2018. · Zbl 1401.68010
[45] C. Maes and S. B. Shlosman, Ergodicity of probabilistic cellular automata: A constructive criterion, Communications in Mathematical Physics 135 (1991), no. 2, 233-251. · Zbl 0717.68073
[46] J. Mairesse and I. Marcovici, Around probabilistic cellular automata, Theoretical Computer Science 559 (2014), 42-72. · Zbl 1360.68615
[47] J. Mairesse and I. Marcovici, Probabilistic cellular automata and random fields with i.i.d. directions, Annales de l’Institut Henri Poincaré, Probabilités et Statistiques 50 (2014), no. 2, 455-475. · Zbl 1359.37027
[48] C. E. M. Pearce and F. K. Fletcher, Oriented site percolation, phase transitions and probability bounds, Journal of Inequalities in Pure and Applied Mathematics 6 (2005), no. 5, 135. · Zbl 1087.60075
[49] O. Penrose, Foundations of statistical mechanics: A deductive treatment, Pergamon, 1970. · Zbl 0193.27801
[50] M. Pivato and R. Yassawi, Limit measures for affine cellular automata, Ergodic Theory and Dynamical Systems 22 (2002), no. 4, 1269-1287. · Zbl 1082.37017
[51] J. G. Propp and D. B. Wilson, Exact sampling with coupled Markov chains and applications to statistical mechanics, Random Structures and Algorithms 9 (1996), no. 1-2, 223-252. · Zbl 0859.60067
[52] G. Rozenberg, T. Bäck, and J. N. Kok (eds.), Handbook of natural computing, vol. 1, Springer, 2012. · Zbl 1248.68001
[53] Th. W. Ruijgrok and E. G. D. Cohen, Deterministic lattice gas models, Physics Letters A 133 (1988), no. 7-8, 415-418.
[54] V. Salo, On nilpotency and asymptotic nilpotency of cellular automata, Electronic Proceedings in Theoretical Computer Science 90 (2012), 86-96.
[55] J. E. Steif, \( \bar{d} \)-Convergence to equilibrium and space-time Bernoulicity for spin systems in the \(m<\varepsilon\) case, Ergodic Theory and Dynamical Systems 11 (1991), no. 3, 547-575.
[56] T. Toffoli and N. Margolus, Cellular automata machines, MIT Press, 1987. · Zbl 0655.68055
[57] A. Toom, Stable and attractive trajectories in multicomponent systems, Multicomponent Random Systems (R. L. Dobrushin and Ya. G. Sinai, eds.), Marcel Dekker, 1980, pp. 549-575. · Zbl 0441.68053
[58] A. L. Toom, N. B. Vasilyev, O. N. Stavskaya, L. G. Mityushin, G. L. Kuryumov, and S. A. Pirogov, Discrete local Markov systems, Stochastic cellular systems: ergodicity, memory, morphogenesis (R. L. Dobrushin, V. I. Kryukov, and A. L. Toom, eds.), Manchester University Press, 1990.
[59] N. B. Vasilyev, Bernoulli and Markov stationary measures in discrete local interactions, Locally Interacting Systems and Their Application in Biology (R. L. Dobrushin, V. I. Kryukov, and A. L. Toom, eds.), Springer, 1978, pp. 99-112.
[60] S. Wolfram (ed.), Theory and applications of cellular automata, World Scientific, 1986. · Zbl 0609.68043
[61] S. Wolfram (ed.), A new kind of science, Wolfram Media, 2002. · Zbl 1022.68084
[62] H. Yaguchi, Application of entropy analysis to discrete-time interacting particle systems on the one-dimensional lattice, Hiroshima Mathematical Journal 30 (2000), no. 1, 137-165. · Zbl 0951.60098
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.