Percolation games

James Martin, University of Oxford
Fine Hall 214

In-Person Talk 

Joint work with Alexander Holroyd and Irène Marcovici. Let each site of the square lattice Z^2 be declared "closed" with probability p, independently for different sites. 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. 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>0, and correspondingly that the game on Z^2 has no draws.

On the other hand, we prove that for p sufficiently small, the analogous game does exhibit draws on various directed graphs in dimension d at least 3. This is proved via analysis of a hard-core lattice gas in dimension d−1: draws can 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 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) and on random trees.