Phase transition in percolation games on rooted Galton-Watson trees

Abstract

We study the bond percolation game and the site percolation game on the rooted Galton-Watson tree $T_{\chi }$ with offspring distribution $\chi$. We obtain the probabilities of win, loss and draw for each player in terms of the fixed points of functions that involve the probability generating function $G$ of $\chi$, and the parameters $p$ and $q$. Here, $p$ is the probability with which each edge (respectively vertex) of $T_{\chi }$ is labeled a trap in the bond (respectively site) percolation game, and $q$ is the probability with which each edge (respectively vertex) of $T_{\chi }$ is labeled a target in the bond (respectively site) percolation game. We obtain a necessary and sufficient condition for the probability of draw to be $0$ in each game, and we examine how this condition simplifies to yield very precise phase transition results when $\chi$ is Binomial$(d,\pi )$, Poisson$(\lambda )$, or Negative Binomial$(r,\pi )$, or when $\chi$ is supported on $\{0,d\}$ for some $d\in \mathbb{N}$, $d⩾2$. It is fascinating to note that, while all other specific classes of offspring distributions we consider in this paper exhibit phase transition phenomena as the parameter-pair $(p,q)$ varies, the probability that the bond percolation game results in a draw remains $0$ for all values of $(p,q)$ when $\chi$ is Geometric$(\pi )$, for all $0<\pi ⩽1$. By establishing a connection between these games and certain finite state probabilistic tree automata on rooted $d$-regular trees, we obtain a precise description of the regime (in terms of $p$, $q$ and $d$) in which these automata exhibit ergodicity or weak spatial mixing.

Much more general results that now include the previously stated results as special cases