Percolation games, probabilistic cellular automata, and the hard-core model
Alexander E. Holroyd, Irène Marcovici, Jean Martin · arXiv (Cornell University) · 2015
Let each site of the square lattice $\\mathbb{Z}^2$ be independently assigned one of three states: a \\textit{trap} with probability $p$, a \\textit{target} with probability $q$, and \\textit{open} with probability $1-p-q$, where $0<p+q<1$. Consider the following game: a token starts at the origin, and two players take turns to move, where a move consists of moving the token from its current site $x$ to either $x+(0,1)$ or $x+(1,0)$. A player who moves the token to a trap loses the game immediately, while a player who moves the token to a target wins the game immediately. Is there positive probability that the game is \\emph{drawn} with best play -- i.e.\\ that neither player can force a win? This is equivalent to the question of ergodicity of a certain family of elementary one-dimensional probabilistic cellular automata (PCA). These automata have been studied in the contexts of enumeration of directed lattice animals, the golden-mean subshift, and the hard-core model, and their ergodicity has been noted as an open problem by several authors. We prove that these PCA are ergodic, and correspondingly that the game on $\\mathbb{Z}^2$ has no draws. On the other hand, we prove that certain analogous games \\emph{do} exhibit draws for suitable parameter values on various directed graphs in higher dimensions, including an oriented version of the even sublattice of $\\mathbb{Z}^d$ in all $d\\geq3$. 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 $\\mathbb{Z}^d$ for $d\\geq 3$, but here our method encounters a fundamental obstacle.