2015/03/18 by Alexander E. Holroyd, Holroyd, Alexander E., Irène Marcovici +3 · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #Cellular Automata and Applications #Stochastic processes and statistical mechanics #Theoretical and Computational Physics
paper · pdf · doi:10.48550/arxiv.1503.05614
Let each site of the square lattice \ℤ2 be independently assigned\none of three states: a \trap with probability p, a \target\nwith probability q, and \open with probability 1-p-q, where\n0<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 \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 \ℤ2 has\nno draws.\n On the other hand, we prove that certain analogous games \do exhibit\ndraws for suitable parameter values on various directed graphs in higher\ndimensions, including an oriented version of the even sublattice of\n\ℤd in all d\≥3. 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 \ℤd for\nd\≥ 3, but here our method encounters a fundamental obstacle.\n