Probabilistic cellular automata and random fields with i.i.d. directions

Mairesse, Jean, Ana BušićHAL 2012 · DOI · arXiv

This paper explores a fascinating intersection of probability theory and computer science: how simple, local rules in a Probabilistic Cellular Automaton (PCA) can generate global structures with paradoxical properties. Specifically, the authors identify a class of PCA whose "history" (space-time diagram) looks like pure, independent noise along any straight line you choose to draw through it, even though the system as a whole is highly correlated.

TL;DR

The authors characterize a specific class of one-dimensional probabilistic cellular automata that possess Bernoulli product invariant measures. They prove that the resulting space-time diagrams form a unique type of random field where every straight line—regardless of its angle—consists of independent and identically distributed (i.i.d.) random variables, despite the field itself being globally dependent.

What Problem Does This Paper Address?

Probabilistic Cellular Automata (PCA) are discrete-time dynamical systems where a grid of cells updates synchronously based on local, stochastic rules. While they are used to model everything from biological growth to traffic flow, they are notoriously difficult to analyze. Finding the "steady state" (invariant measure) of a PCA is often an intractable problem.

The authors focus on the simplest non-trivial case: a 1D PCA with a binary alphabet ({0, 1}) where each cell's next state depends only on itself and its right neighbor. The core challenge is twofold:

  1. Determining the exact conditions under which the steady state of the system is "simple" (i.e., a Bernoulli product measure where every cell is independent).
  2. Understanding the correlation structure of the "space-time diagram"—the 2D map showing the evolution of the system over time.

Methods

The paper relies on rigorous mathematical proofs and combinatorial analysis. Key methodological contributions include:

  • Marginal Probability Formulas: The authors derive explicit recursive formulas to describe the probability of seeing specific patterns in the PCA’s output.
  • Transversal PCA: A novel conceptual tool where the authors show that a space-time diagram generated by a PCA moving "down" (through time) can sometimes be viewed as being generated by a different PCA moving "sideways" (across space).
  • Algebraic Characterization: They identify necessary and sufficient algebraic conditions on the four transition parameters of the PCA to ensure a Bernoulli invariant measure.
  • Incremental Construction: They provide a step-by-step algorithm to build these complex random fields from a single starting point using local independence and PCA rules.

Datasets

Not applicable. This is a theoretical mathematics paper; no empirical datasets were used. The "data" consists of the mathematical structures and space-time diagrams generated by the defined PCA rules.

Key Insights and Ideas

  • The "i.i.d. Directions" Phenomenon: The most striking insight is the existence of non-trivial random fields where every line is i.i.d. Usually, if a horizontal line is i.i.d., the act of updating the cells to the next time step introduces correlations. The authors find the "sweet spot" where these correlations exist globally but vanish along any linear trajectory.
  • Pairwise Independence vs. Global Dependence: In these specific diagrams, any two cells are independent. However, groups of three cells (specifically those forming equilateral triangles pointing up) are dependent. This is a spatial version of the classic probability puzzle where variables are pairwise independent but not mutually independent.
  • Symmetry and Rotation: For certain parameters, the space-time diagram is statistically invariant under rotations of $2\pi/3$. This symmetry allows the researchers to use "transversal" PCA to prove properties that would be difficult to see from a standard time-evolution perspective.
  • Markovian Extensions: The authors show that these results aren't just limited to the simplest cases; they extend the logic to Markovian measures (where cells have local dependencies) and larger neighborhoods.

Key Results

  • Theorem 3.2: Provides the exact necessary and sufficient conditions on PCA parameters to have a Bernoulli product invariant measure.
  • Proposition 4.4: Proves that if a PCA satisfies two specific conditions, every line in its stationary space-time diagram consists of i.i.d. variables.
  • Theorem 5.3: Establishes the conditions for a PCA to have a Markovian invariant measure, providing a new, simpler proof for a result that had been previously explored in more complex contexts.
  • Theorem 5.6: Generalizes the invariance conditions to PCA with any finite alphabet and any finite neighborhood size.

Limitations and Future Work

The authors acknowledge that the "i.i.d. directions" property is quite fragile; it only exists when the PCA parameters are tuned to a specific codimension-1 subspace of the parameter space.

The paper leaves open several intriguing questions:

  • General Distributions: For PCA parameters that don't satisfy these conditions, can we still find an explicit description of the invariant measure?
  • Statistical Physics Links: There is a known but not fully mapped connection between these PCA and "directed animals" in percolation theory. The authors suggest that explicitly determining invariant measures for broader classes of PCA could solve long-standing problems in lattice statistics, such as computing site-percolation thresholds.

Summary updated

Abstract

Let us consider the simplest model of one-dimensional probabilistic cellular automata (PCA). The cells are indexed by the integers, the alphabet is {0, 1}, and all the cells evolve synchronously. The new content of a cell is randomly chosen, independently of the others, according to a distribution depending only on the content of the cell itself and of its right neighbor. There are necessary and sufficient conditions on the four parameters of such a PCA to have a Bernoulli product invariant measure. We study the properties of the random field given by the space-time diagram obtained when iterating the PCA starting from its Bernoulli product invariant measure. It is a non-trivial random field with very weak dependences and nice combinatorial properties. In particular, not only the horizontal lines but also the lines in any other direction consist in i.i.d. random variables. We study extensions of the results to Markovian invariant measures, and to PCA with larger alphabets and neighborhoods.
BibTeX
@inproceedings{jean2012probabilistic,
  author = {Mairesse, Jean and Ana Bušić},
  title = {{Probabilistic cellular automata and random fields with i.i.d. directions}},
  booktitle = {HAL},
  year = {2012},
  doi = {10.48550/arxiv.1207.5917},
}
Figure