Probabilistic Cellular Automata, Invariant Measures, and Perfect Sampling
From MaRDI portal
Ergodicity, mixing, rates of mixing (37A25) Dynamical aspects of cellular automata (37B15) Discrete-time Markov processes on general state spaces (60J05) Computational methods in Markov chains (60J22) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Cellular automata (computational aspects) (68Q80)
Abstract: A probabilistic cellular automaton (PCA) can be viewed as a Markov chain. The cells are updated synchronously and independently, according to a distribution depending on a finite neighborhood. We investigate the ergodicity of this Markov chain. A classical cellular automaton is a particular case of PCA. For a 1-dimensional cellular automaton, we prove that ergodicity is equivalent to nilpotency, and is therefore undecidable. We then propose an efficient perfect sampling algorithm for the invariant measure of an ergodic PCA. Our algorithm does not assume any monotonicity property of the local rule. It is based on a bounding process which is shown to be also a PCA. Last, we focus on the PCA Majority, whose asymptotic behavior is unknown, and perform numerical experiments using the perfect sampling procedure.
Recommendations
- 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
- scientific article; zbMATH DE number 176045
- Stationary measures and phase transition for a class of Probabilistic Cellular Automata
- Ergodicity of probabilistic cellular automata: A constructive criterion
- Invariant measures and decay of correlations for a class of ergodic probabilistic cellular automata
- scientific article; zbMATH DE number 32619
- scientific article; zbMATH DE number 218211
- Probabilistic cellular automata with conserved quantities
Cites work
- A non-ergodic probabilistic cellular automaton with a unique invariant measure
- A reader's guide to P. Gacs's ``positive rates paper: ``Reliable cellular automata with self-organization.
- Algorithmical unsolvability of the ergodicity problem for binary cellular automata
- Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata
- Contours, convex sets and cellular automata. IMPA mathematical publications. 23rd Brazilian mathematics colloquium, Rio de Janeiro, Brazil, July 22--27, 2001.
- Directed animals and gas models revisited
- Directed Percolation Arising in Stochastic Cellular Automata Analysis
- Endomorphisms and automorphisms of the shift dynamical system
- Exact sampling from anti‐monotone systems
- Exact sampling with coupled Markov chains and applications to statistical mechanics
- Finite Markov Chains and Algorithmic Applications
- scientific article; zbMATH DE number 953295 (Why is no real title available?)
- scientific article; zbMATH DE number 3892344 (Why is no real title available?)
- Invariant measures and decay of correlations for a class of ergodic probabilistic cellular automata
- Neuropercolation: A Random Cellular Automata Approach to Spatio-temporal Neurodynamics
- New enumerative results on two-dimensional directed animals
- Nilpotency and Limit Sets of Cellular Automata
- On the existence and nonexistence of finitary codings for a class of random fields
- On the Limit Sets of Cellular Automata
- Perfect sampling using bounding chains.
- Probabilistic cellular automata, invariant measures, and perfect sampling
- Reliable cellular automata with self-organization
- Stochastic Cellular Automata Solve the Density Classification Problem with an Arbitrary Precision
- The Nilpotency Problem of One-Dimensional Cellular Automata
Cited in
(27)- Invariant measures for bipermutative cellular automata
- Phase transitions in random mixtures of elementary cellular automata
- Probabilistic cellular automata with memory two: invariant laws and multidirectional reversibility
- Percolation games, probabilistic cellular automata, and the hard-core model
- Ergodicity of some classes of cellular automata subject to noise
- Probabilistic cellular automata, invariant measures, and perfect sampling
- Ergodicity of noisy cellular automata: the coupling method and beyond
- Dynamic aspects of the flip-annihilation process
- scientific article; zbMATH DE number 4090442 (Why is no real title available?)
- scientific article; zbMATH DE number 32619 (Why is no real title available?)
- scientific article; zbMATH DE number 176045 (Why is no real title available?)
- Overview: PCA models and issues
- Around probabilistic cellular automata
- Variable-length analog of Stavskaya process: a new example of misleading simulation
- Probabilistic cellular automata with general alphabets possessing a Markov chain as an invariant distribution
- Coupling from the past for exponentially ergodic one-dimensional probabilistic cellular automata
- Ergodicity of some probabilistic cellular automata with binary alphabet via random walks
- On a class of PCA with size-3 neighborhood and their applications in percolation games
- Kinetically constrained models out of equilibrium
- Block approximations for probabilistic mixtures of elementary cellular automata
- A comprehensive taxonomy of cellular automata
- Ergodicity of the hard-core PCA with a random walk method
- Cellular automata and percolation: an overview of selected connections
- A non-ergodic probabilistic cellular automaton with a unique invariant measure
- Monte Carlo study of infinite-dimensional cellular automata
- Finitary codings for spatial mixing Markov random fields
- Invariant measures and decay of correlations for a class of ergodic probabilistic cellular automata
This page was built for publication: Probabilistic Cellular Automata, Invariant Measures, and Perfect Sampling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5396587)
