Percolation Games, Probabilistic Cellular Automata, and the Hard-Core Model

Let each site of the square lattice Z² be independently declared closed with probability p, and otherwise open. Consider the following game: a token starts at the origin, and the two players take turns to move it from its current site x to an open site in {x + (0, 1), x + (1, 0)}; if both these sites are closed, then the player to move loses the game. Is there positive probability that the game is drawn with best play – i.e. that neither player can force a win? This is equivalent to the question of ergodicity of a certain elementary one-dimensional probabilistic cellular automaton (PCA), which has been studied in the contexts of enumeration of directed animals, the golden-mean subshift, and the hard-core model. Ergodicity of the PCA has been noted as an open problem by several authors. We prove that the PCA is ergodic for all 0 < p < 1, and correspondingly that the game on Z² has no draws. We establish similar results for a certain misère variant of the game and a PCA associated to it.

On the other hand, we prove that the analogous game does exhibit draws for sufficiently small p on various directed graphs in higher dimensions, including an oriented version of the even sublattice of Z^d in all d ≥ 3. This is proved via a dimension reduction to a hard-core lattice gas in dimension d−1. We show that draws occur whenever the corresponding hard-core model has multiple Gibbs distributions. We conjecture that draws occur also on the standard oriented lattice Z^d for d ≥ 3, but here our method encounters a fundamental obstacle.