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

DOI10.1007/S00440-018-0881-6MaRDI QIDQ2312690zbMATH OpenOpenAlexWikidataFDO

Authors A. E. Holroyd, Irène Marcovici, James Martin

Publication date 17 July 2019

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.05614

zbMATH Keywords

combinatorial gameergodicityhard-core modelpercolationprobabilistic cellular automaton

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Dynamical aspects of cellular automata (37B15) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Cellular automata (computational aspects) (68Q80) 2-person games (91A05) Games involving graphs (91A43)

Abstract: Let each site of the square lattice $mathbb{Z}^2$ be independently assigned one of three states: a extit{trap} with probability $p$, a extit{target} with probability $q$, and extit{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 $dgeq3$. 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 $dgeq3$, but here our method encounters a fundamental obstacle.

Recommendations

• Trapping games on random boards
• Percolation and the complexity of games
• scientific article; zbMATH DE number 1944403
• Maker–Breaker percolation games I: crossing grids
• Maker-breaker percolation games. II: Escaping to infinity

Cites work

• A reader's guide to P. Gacs's ``positive rates paper: ``Reliable cellular automata with self-organization.
• An ergodic theorem for interacting systems with attractive interactions
• Around probabilistic cellular automata
• Directed animals and gas models revisited
• Dual processes and their application to infinite interacting systems
• Galton–Watson games
• scientific article; zbMATH DE number 3694341 (Why is no real title available?)
• scientific article; zbMATH DE number 3626404 (Why is no real title available?)
• scientific article; zbMATH DE number 1224949 (Why is no real title available?)
• scientific article; zbMATH DE number 1568491 (Why is no real title available?)
• scientific article; zbMATH DE number 3319095 (Why is no real title available?)
• New enumerative results on two-dimensional directed animals
• On Phase Transition in the Hard-Core Model on ${\mathbb Z}^d$
• Percolation and disorder-resistance in cellular automata
• Phase coexistence and slow mixing for the hard-core model on \(\mathbb Z^{2}\)
• Probabilistic cellular automata and random fields with i.i.d. directions
• Probabilistic Cellular Automata, Invariant Measures, and Perfect Sampling
• Random majority percolation
• Reliable cellular automata with self-organization
• Survival of discrete time growth models, with applications to oriented percolation
• The positive rates problem for attractive nearest neighbor spin systems on ?
• Trapping games on random boards
• Uniform sampling of subshifts of finite type on grids and trees

Cited in

(16)

• Maker-breaker percolation games. II: Escaping to infinity
• Probabilistic cellular automata with memory two: invariant laws and multidirectional reversibility
• Search for an immobile hider on a stochastic network
• Ergodicity of some classes of cellular automata subject to noise
• The geodesic transversal problem on some networks
• Friendly frogs, stable marriage, and the magic of invariance
• Maker–Breaker percolation games I: crossing grids
• Trapping games on random boards
• Galton–Watson games
• Ergodicity of some probabilistic cellular automata with binary alphabet via random walks
• On a class of PCA with size-3 neighborhood and their applications in percolation games
• Combinatorial games on Galton-Watson trees involving several-generation-jump moves
• A comprehensive taxonomy of cellular automata
• Ergodicity of the hard-core PCA with a random walk method
• Cellular automata and percolation: an overview of selected connections
• Random zero-sum dynamic games on infinite directed graphs

This page was built for publication: Percolation games, probabilistic cellular automata, and the hard-core model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2312690)