Probabilistic cellular automata, invariant measures, and perfect sampling

Ana Busic, Jean Mairesse, Irène Marcovici

Probabilistic Cellular Automata (PCA) are discrete-time dynamical systems where cells on a lattice update synchronously and independently according to local stochastic rules. This paper investigates the long-term behavior of these systems, specifically focusing on ergodicity—the property where a system eventually "forgets" its initial state and converges to a unique invariant measure (equilibrium).

The Decidability of Ergodicity

A fundamental question in the study of PCA is whether one can algorithmically determine if a given system is ergodic. For Deterministic Cellular Automata (DCA), ergodicity is closely linked to nilpotency, a state where the system eventually collapses into a single configuration regardless of the input.

The authors provide a significant theoretical result: for 1-dimensional cellular automata, ergodicity is equivalent to nilpotency. Since nilpotency is known to be undecidable (no general algorithm can determine it for all cases), it follows that ergodicity is also undecidable. This "No-Go" theorem implies that there is no magic formula to classify the long-term behavior of all 1D PCA; they must be analyzed on a case-by-case basis.

Perfect Sampling via Envelope PCA

To study ergodic systems practically, researchers often need to sample from their invariant measures. Traditional Markov Chain Monte Carlo (MCMC) methods provide only approximations and suffer from "burn-in" bias. To overcome this, the authors introduce the Envelope PCA (EPCA), an algorithm based on a technique called Coupling From The Past (CFTP).

The EPCA extends the system's state space by adding an "uncertainty" symbol, ?. By starting a simulation where every cell is initially ?, the algorithm tracks the "envelope" of all possible configurations. As the local rules are applied, some ? symbols resolve into concrete states. When the last ? disappears, the system has coupled, providing a perfect sample—a configuration drawn exactly from the invariant measure with no bias. Crucially, the EPCA does not require the local rules to be monotonic, a common limitation in previous sampling algorithms.

Numerical Experiments: The Majority PCA

The authors applied their perfect sampling tool to the Majority PCA, a model where cells tend to adopt the state of the majority of their neighbors but with some noise. A long-standing conjecture suggests a phase transition in this model based on the probability $\alpha$ of following the majority rule.

Space-time diagrams of the Majority PCA for (a) $\alpha = 0.5$ and (b) $\alpha = 0.6$.

Using the EPCA, the authors provided numerical evidence for this transition. They observed that when $\alpha$ is high (above $\approx 0.45$), the system exhibits multiple invariant measures. The space-time diagrams in Figure 1 illustrate the qualitative change in system behavior as $\alpha$ increases, showing how the "blue" state becomes more persistent and structured as the noise decreases.

Conclusion

This work bridges theoretical computer science and statistical physics. By proving the undecidability of ergodicity in 1D and providing a robust perfect sampling algorithm, the authors offer both a warning about the limits of general theory and a powerful tool for specific numerical investigation. Future work remains in extending these results to higher dimensions and exploring the famous "Positive Rates Conjecture."

Summary updated

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.
BibTeX
@inproceedings{busic2013probabilistic,
  author = {Ana Busic and Jean Mairesse and Irène Marcovici},
  title = {{Probabilistic cellular automata, invariant measures, and perfect sampling}},
  booktitle = {Advances},
  year = {2013},
  doi = {10.1017/s0001867800006728},
}
Figure