Abstract
Probabilistic cellular automata (PCA) represent a class of discrete-time Markov chains where cells update synchronously and independently based on local neighborhoods. This paper investigates the fundamental property of ergodicity in these systems. We demonstrate that for one-dimensional cellular automata, ergodicity is equivalent to nilpotency, rendering the property undecidable. To address the challenge of simulating these systems, we introduce a "perfect sampling" algorithm based on an "Envelope PCA" (EPCA) bounding process. This method allows for the efficient generation of samples from the invariant measure without requiring monotonicity. Numerical experiments on the Majority PCA reveal evidence of phase transitions, highlighting the utility of our sampling approach.
Introduction
Probabilistic Cellular Automata (PCA) are widely used to model complex dynamical systems, ranging from biological networks to physical processes. A central question in the study of PCA is ergodicity: does the system eventually settle into a unique stable statistical distribution (an invariant measure) regardless of its initial state? While deterministic cellular automata (DCA) are well-understood in some contexts, the introduction of noise in PCA complicates both theoretical analysis and practical simulation.
Theoretical Boundaries: Ergodicity and Undecidability
A major contribution of this work is the formal linkage between ergodicity and nilpotency in one-dimensional systems. In the context of DCA, a system is nilpotent if it eventually reaches a fixed "all-zero" state from any configuration. We prove that for 1D systems, ergodicity is equivalent to nilpotency.
Because nilpotency has been previously proven to be undecidable—meaning no general algorithm can determine if a given rule set is nilpotent—our result implies that ergodicity in 1D PCA is also mathematically undecidable. This establishes a fundamental limit on our ability to predict the long-term stability of these systems through automated analysis of their local rules.
The Envelope PCA and Perfect Sampling
To study ergodic systems that are analytically intractable, researchers rely on simulation. However, standard Markov Chain Monte Carlo (MCMC) methods suffer from "burn-in" issues, where it is unclear if the simulation has reached equilibrium.
We propose a "perfect sampling" algorithm based on Coupling-from-the-Past (CFTP). To make CFTP computationally feasible for non-monotonic systems like the Majority PCA, we introduce the Envelope PCA (EPCA). The EPCA operates on an expanded state space {0, 1, ?}, where ? denotes an unknown state. By simulating the EPCA, we can bound the set of all possible trajectories of the original PCA. When the ? symbols disappear, the system has "coupled," and the resulting state is a guaranteed sample from the invariant measure.
Numerical Experiments and Phase Transitions
We applied the EPCA algorithm to the Majority PCA, a model where cells update to the majority state of their neighbors with some probability of error $\alpha$. This model is particularly interesting because it lacks the monotonicity property required by many other sampling techniques.
Our experiments provide numerical evidence for a phase transition. As shown in the figures above, varying the parameter $\alpha$ leads to qualitatively different long-term behaviors. At lower noise levels (e.g., $\alpha = 0.5$), the system may exhibit sparse, branching structures reminiscent of directed percolation. At higher noise levels (e.g., $\alpha = 0.6$), the system reaches a dense, disordered equilibrium. Our sampling tool allows for precise investigation of the critical values where these transitions occur, supporting conjectures about the existence of multiple invariant measures in certain parameter regimes.
Conclusion
This research clarifies the theoretical landscape of PCA by proving the undecidability of ergodicity in 1D and provides a robust algorithmic framework for perfect sampling. The Envelope PCA bypasses the need for monotonicity, opening the door for the rigorous study of a broader class of stochastic dynamical systems. Future work will continue to explore the "Positive Rates Conjecture" and the limits of the EPCA's efficiency in higher dimensions.
Summary updated