Ergodicity of some classes of cellular automata subject to noise

DOI10.1214/19-EJP297zbMATH Open1466.37013arXiv1712.05500OpenAlexW3101089153MaRDI QIDQ2631867FDOQ2631867

Authors: Irène Marcovici, Mathieu Sablik, Siamak Taati 

Publication date: 16 May 2019

Published in: Electronic Journal of Probability (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1712.05500

Recommendations

• Ergodicity of noisy cellular automata: the coupling method and beyond
• scientific article; zbMATH DE number 32619
• scientific article
• Ergodicity of probabilistic cellular automata: A constructive criterion
• The ergodic theory of cellular automata
• Ergodicity of some probabilistic cellular automata with binary alphabet via random walks
• On the dynamics of stochastic elementary cellular automata
• Ergodic properties of certain surjective cellular automata
• On ergodic one-dimensional cellular automata
• Rigidity results in cellular automata theory: probabilistic and ergodic theory approach

zbMATH Keywords

noiseergodicitycellular automatacouplingentropy methodFourier analysisprobabilistic cellular automata

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Discrete-time Markov processes on general state spaces (60J05) Entropy and other invariants, isomorphism, classification in ergodic theory (37A35) Dynamical aspects of cellular automata (37B15)

Cites Work

• Title not available (Why is that?)
• Statistical mechanics of probabilistic cellular automata.
• Ergodic theory on compact spaces
• Theory of cellular automata: a survey
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Handbook of Natural Computing
• Title not available (Why is that?)
• Title not available (Why is that?)
• Limit measures for affine cellular automata
• Title not available (Why is that?)
• Statistical mechanics of surjective cellular automata
• Oriented percolation in two dimensions
• Title not available (Why is that?)
• The Nilpotency Problem of One-Dimensional Cellular Automata
• Gibbs measures and phase transitions
• Title not available (Why is that?)
• Exact sampling with coupled Markov chains and applications to statistical mechanics
• Cellular Automata Modeling of Physical Systems
• Cellular automata and groups
• Ergodicity of PCA: equivalence between spatial and temporal mixing conditions
• From PCA's to equilibrium systems and back
• Stationary measures and phase transition for a class of Probabilistic Cellular Automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reliable cellular automata with self-organization
• Ballistic annihilation and deterministic surface growth.
• On the existence and nonexistence of finitary codings for a class of random fields
• Ergodicity of probabilistic cellular automata: A constructive criterion
• Cesàro mean distribution of group automata starting from measures with summable decay
• Title not available (Why is that?)
• Title not available (Why is that?)
• Invariant measures and convergence properties for cellular automaton 184 and related processes
• Title not available (Why is that?)
• Reliable computation with cellular automata
• Probabilistic cellular automata and random fields with i.i.d. directions
• Free energy in a Markovian model of a lattice spin system
• Nilpotency and Limit Sets of Cellular Automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Around probabilistic cellular automata
• On Nilpotency and Asymptotic Nilpotency of Cellular Automata
• Probabilistic Cellular Automata, Invariant Measures, and Perfect Sampling
• A non-ergodic probabilistic cellular automaton with a unique invariant measure
• Markovianity of the invariant distribution of probabilistic cellular automata on the line
• A class of non-ergodic probabilistic cellular automata with unique invariant measure and quasi-periodic orbit
• Title not available (Why is that?)
• The one-dimensional cyclic cellular automaton: A system with deterministic dynamics that emulates an interacting particle system with stochastic dynamics
• Invariant measures and decay of correlations for a class of ergodic probabilistic cellular automata
• Probabilistic cellular automata. Theory, applications and future perspectives
• Title not available (Why is that?)
• Characterization of sets of limit measures of a cellular automaton iterated on a random configuration
• Survival of one-dimensional cellular automata under random perturbations
• Application of entropy analysis to discrete-time interacting particle systems on the one-dimensional lattice
• -Convergence to equilibrium and space—time bernoullicity for spin systems in the M < ε case
• Percolation games, probabilistic cellular automata, and the hard-core model
• Characterizing asymptotic randomization in abelian cellular automata
• Self-organisation in cellular automata with coalescent particles: qualitative and quantitative approaches

Cited In (15)

• The Gacs-Kurdyumov-Levin automaton revisited
• Simply modified GKL density classifiers that reach consensus faster
• Coupling from the past for exponentially ergodic one-dimensional probabilistic cellular automata
• Cold dynamics in cellular automata: a tutorial
• Transfer matrix analysis of one-dimensional majority cellular automata with thermal noise
• Locality of the interaction affects dynamics in probabilistic cellular automata
• Stable multi-level monotonic eroders
• Title not available (Why is that?)
• On a class of PCA with size-3 neighborhood and their applications in percolation games
• The ergodic theory of cellular automata
• Bootstrap percolation, probabilistic cellular automata and sharpness
• A nonlinear eroder in presence of one-sided noise
• Ergodicity of noisy cellular automata: the coupling method and beyond
• Title not available (Why is that?)
• Ergodicity of some probabilistic cellular automata with binary alphabet via random walks

This page was built for publication: Ergodicity of some classes of cellular automata subject to noise

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2631867)