On a class of PCA with size-3 neighborhood and their applications in percolation games

Abstract

Different versions of percolation games on Z(2), with parameters p and q that indicate, respectively, the probability with which a site in Z(2) is labeled a trap and the probability with which it is labeled a target, are shown to have probability 0 of culminating in draws when p + q > 0. We show that, for fixed p and q, the probability of draw in each of these games is 0 if and only if a certain 1-dimensional probabilistic cellular automaton (PCA) F-p,F-q with a size-3 neighborhood is ergodic. This allows us to conclude that F-p,F-q is ergodic whenever p + q > 0, thereby rigorously establishing ergodicity for a considerable class of PCAs that tie in closely with important topics such as the enumeration of directed animals, broadcasting of information on directed infinite lattices, examining reliability of computations against the presence of noise etc. The key to our proof is the technique of weight functions. We include extensive discussions on game theoretic PCAs to which this technique may be applicable to establish ergodicity, and on percolation games to which this technique may be applicable to explore the 'regimes' (depending on the underlying parameter(s), such as (p, q) in our case) in which the probabilities of draw are 0.