Let each site of the square lattice Z2 be declared "closed" with probability p, a "target" with probability q, and "open" with probability 1−p−q, where 0 <= p <= p+q <= 1. Different sites are independent.
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 a site in {x+(0,1),x+(1,0)}. A player moving to a closed site loses immediately. A player moving to a target site wins immediately. Otherwise, the game continues.
Is there positive probability that the game is drawn with best play - i.e. that neither player can force a win? We show that this question is equivalent to the question of ergodicity of a certain elementary one-dimensional probabilistic cellular automaton (PCA). We prove that the PCA is ergodic whenever p+q>0, and correspondingly that the game on Z2 has no draws.
On the other hand, we prove that for q=0 and p sufficiently small, the analogous game does exhibit draws on various directed graphs in dimension d at least 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 Zd for d at least 3, but here our method encounters a fundamental obstacle.
If time permits, I will also mention similar games on undirected lattices, where there are a few related results but also many open questions.
This is joint work with Alexander Holroyd and Irene Marcovici.