Percolation games, probabilistic cellular automata, and the hard-core\n model

Abstract

Let each site of the square lattice $\\mathbb{Z}^2$ be independently assigned\none of three states: a \\textit{trap} with probability $p$, a \\textit{target}\nwith probability $q$, and \\textit{open} with probability $1-p-q$, where\n$0<p+q<1$. Consider the following game: a token starts at the origin, and two\nplayers take turns to move, where a move consists of moving the token from its\ncurrent site $x$ to either $x+(0,1)$ or $x+(1,0)$. A player who moves the token\nto a trap loses the game immediately, while a player who moves the token to a\ntarget wins the game immediately. Is there positive probability that the game\nis \\emph{drawn} with best play -- i.e.\\ that neither player can force a win?\nThis is equivalent to the question of ergodicity of a certain family of\nelementary one-dimensional probabilistic cellular automata (PCA). These\nautomata have been studied in the contexts of enumeration of directed lattice\nanimals, the golden-mean subshift, and the hard-core model, and their\nergodicity has been noted as an open problem by several authors. We prove that\nthese PCA are ergodic, and correspondingly that the game on $\\mathbb{Z}^2$ has\nno draws.\n On the other hand, we prove that certain analogous games \\emph{do} exhibit\ndraws for suitable parameter values on various directed graphs in higher\ndimensions, including an oriented version of the even sublattice of\n$\\mathbb{Z}^d$ in all $d\\geq3$. This is proved via a dimension reduction to a\nhard-core lattice gas in dimension $d-1$. We show that draws occur whenever the\ncorresponding hard-core model has multiple Gibbs distributions. We conjecture\nthat draws occur also on the standard oriented lattice $\\mathbb{Z}^d$ for\n$d\\geq 3$, but here our method encounters a fundamental obstacle.\n