# Percolation games on rooted regular trees and ergodicity of associated
probabilistic tree automata

Sayar Karmakar, Moumanti Podder, Souvik Roy, Soumyarup Sadhukhan  Sayar
Karmakar, University of Florida, 230 Newell Drive, Gainesville, Florida 32605,
USA.  Moumanti Podder, Indian Institute of Science Education and Research
(IISER) Pune, Dr. Homi Bhabha Road, Pashan, Pune 411008, Maharashtra, India.
Souvik Roy, Indian Statistical Institute, 203 Barrackpore Trunk Road, Kolkata
700108, West Bengal, India.  Soumyarup Sadhukhan, Indian Institute of
Technology, Kalyanpur, Kanpur, Uttar Pradesh 208016, India.
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

We study the _bond percolation game_ and _site percolation game_ on the rooted
tree $T_{d}$ in which each vertex has precisely $d$ children, for $d\geqslant
2$. In the former, each edge of $T_{d}$ is, independently, assigned a label
that reads _trap_ with probability $p$ and _safe_ with probability $1-p$, for
some pre-specified parameter $p\in(0,1)$, whereas in the latter, a similar
random labeling is assigned to the vertices of $T_{d}$. Two players take turns
to make moves, where a move involves relocating a token from where it is
currently situated, say a vertex $u$ of $T_{d}$, to one of the $d$ children of
$u$. A player wins the bond percolation game if she can force her opponent to
move the token along an edge marked a trap, while the site percolation game is
won by a player if she can force her opponent to move the token to a vertex
labeled a trap. We show that in both of these games, the probability of draw
is $0$ if and only if $p\geqslant p_{c}$, where
$p_{c}=1-\frac{(d+1)^{d-1}}{d^{d}}$. We study two _probabilistic tree
automata_ , $B_{p}$ and $N_{p}$, that represent the recurrence relations
arising out of the bond percolation game and the site percolation game
respectively, and we show that each of $B_{p}$ and $N_{p}$ is ergodic if and
only if $p\geqslant p_{c}$.

###### Key words and phrases:

percolation games on rooted trees; two-player combinatorial games;
probabilistic tree automata; ergodicity; probability of draw; weak spatial
mixing; Gibbs measure; phase transition; rooted regular trees; bond
percolation; site percolation

###### 2020 Mathematics Subject Classification:

05C57, 37B15, 37A25, 68Q80

##  1\. Introduction

###  1.1. Overview of the paper

The work accomplished in this paper is the result of our curiosity regarding
_percolation games_ on rooted regular trees. Whereas _percolation_ itself has
been thoroughly researched for decades by both mathematicians and physicists
(see, for instance, [10], [19] and [31]), the notion of percolation games –
more specifically, _node percolation games_ or _site percolation games_ – to
the best of our knowledge, was introduced in [21]. In this paper, we address
both site percolation games and _bond percolation games_ , the latter being
analogous, in some sense, to the former, but with the edges of the graph under
consideration replacing the vertices in their roles in the game.

In [21], each site $(x,y)\in\mathbb{Z}^{2}$ of the $2$-dimensional square
lattice is assigned, independently, a label that reads _trap_ with probability
$p$, _target_ with probability $q$ and _open_ with probability $1-p-q$, where
$p$ and $q$ are pre-fixed parameters such that
$0\leqslant\min\\{p,q\\}\leqslant p+q\leqslant 1$. Two players take turns to
make moves, where a _move_ involves relocating a token from its current
position, say the site $(x,y)$, to one of the sites $(x+1,y)$ and $(x,y+1)$. A
player wins if she either succeeds in moving the token to a site that has been
labeled a target, or forces her opponent in moving the token to a site that
has been labeled a trap. The game continues for as long as the token stays on
open sites, and this may happen indefinitely, thereby leading to a draw. In
[8], a somewhat more complicated version of this game is considered, with a
move being defined as the relocation of the token from its current position
$(x,y)$ to one of $(x+2,y)$, $(x+1,y+1)$ and $(x,y+2)$. In both [21] and [8],
it is shown that the game being studied has probability $0$ of resulting in a
draw whenever $p+q>0$, and this is established by exploiting the connection
that each of these games exhibits with certain judiciously defined
$1$-dimensional _probabilistic cellular automata_ (henceforth abbreviated as
PCA). In fact, this connection allows us to draw conclusions about the
_ergodicity_ of these PCAs as well.

In this paper, we study a special case of the above game on rooted regular
trees. Given $d\in\mathbb{N}$ with $d\geqslant 2$, we denote by $T_{d}$ the
rooted tree, with its root being denoted by $\phi$, in which each vertex has
precisely $d$ children. To each vertex of $T_{d}$, independently, we assign a
label that reads _trap_ with probability $p$ and _safe_ with probability
$1-p$, for a pre-fixed $p\in(0,1)$. Two players take turns to make moves,
where a move involves relocating the token from its current position, say a
vertex $u$, to any one of the $d$ children of $u$. A player wins if she
compels her opponent to move the token to a vertex that has been labeled a
trap. As above, the game may continue indefinitely provided the token never
encounters a vertex labeled a trap, leading to a draw.

We now come to a brief description of the bond percolation game on $T_{d}$.
Each edge of $T_{d}$ is, independently, assigned a label that reads _trap_
with probability $p$ and _safe_ with probability $1-p$, for a pre-fixed
$p\in(0,1)$. A move is defined in the same way as in the above-mentioned site
percolation game played on $T_{d}$. Here, the criterion to win is to force
one’s opponent to move the token _along_ an edge that has been labeled a trap.
The game may result in a draw provided the token traverses _only_ edges that
have been labeled safe.

For each of these games on $T_{d}$, we investigate the probabilities of the
various possible outcomes, i.e. win for the player who moves first, loss for
the player who moves first, and draw for both players. Of particular interest
is the phenomenon of _phase transition_ : we prove the existence of a critical
value $p_{c}$ of $p$ such that for all $p\geqslant p_{c}$, the probability of
either of these games resulting in a draw is $0$, whereas for $p<p_{c}$, the
outcome of draw in each of these games has a strictly positive probability.
The proofs happen by exploiting the connections that these games exhibit with
suitably defined _probabilistic tree automata_ (henceforth abbreviated as
PTA). These connections are born of the recurrence relations deduced from the
games. In the process, we are also able to make assertions regarding
ergodicity, or lack thereof, of these PTAs for various values of $p$ (see
Definition 2.1 and Theorem 3.1).

The main results of this paper, pertaining to the games described above, are
as follows:

######  Theorem 1.1.

For each $p\in(0,1)$, if we let $w_{B,p}$ denote the probability that the
first player wins the bond percolation game that begins at the root $\phi$ of
$T_{d}$, then $p+(1-p)w_{B,p}$ is given by the minimum positive fixed point of
the function

$f_{p}(x)=1-(1-p)[1-(1-p)x^{d}]^{d}.$ (1.1)

The probability that the game results in a draw is strictly positive for all
$p<p_{c}$, and it is $0$ for all $p\geqslant p_{c}$, where

$p_{c}=1-\frac{(d+1)^{d-1}}{d^{d}}.$ (1.2)

######  Theorem 1.2.

For each $p\in(0,1)$, if we let $w_{N,p}$ denote the probability that the
first player wins the node percolation game that begins at the root $\phi$ of
$T_{d}$, then $w_{N,p}$ is given by the minimum positive fixed point of the
function $f_{p}$ as defined in (1.1). The probability that the game results in
a draw is strictly positive for all $p<p_{c}$, and it is $0$ for all
$p\geqslant p_{c}$, where $p_{c}$ is as defined in (1.2).

###  1.2. Brief review of literature

This work bears intimate connections with a diverse array of topics spanning
probability, combinatorics, theoretical computer science and even physics (in
particular, percolation and statistical physics). This is either because of
the objects we study in this paper, or because of the approach we adopt to
analyze said objects. We begin §1.2 with some discussion on percolation games,
as well as some other instances of two-player combinatorial games that they
form a subset of, and the ties that such games often exhibit with cellular
automata or finite-state tree automata (whether deterministic or
probabilistic). The primary motivation for this work stems from [21], in which
a version of the node percolation game was studied on the infinite
$2$-dimensional square lattice (i.e. the graph whose vertex set is
$\mathbb{Z}^{2}$, and in which two vertices $(x_{1},x_{2})$ and
$(y_{1},y_{2})$ are adjacent if and only if $|x_{1}-y_{1}|+|x_{2}-y_{2}|=1$).
Each vertex of the lattice is assigned, independently, a label that reads
_trap_ with probability $p$, _target_ with probability $q$, and _open_ with
the remaining probability $1-p-q$. Two players take turns to make moves, where
a move involves relocating a token from its current location, say $(x,y)$, to
either $(x+1,y)$ or $(x,y+1)$. A player wins if she is either able to move the
token to a vertex labeled a target, or force her opponent to move the token to
a vertex labeled a trap. In [8], the following modification of the above-
mentioned game is considered: a move now involves relocating the token from
where it is currently situated, say $(x,y)$, to any of the vertices $(x+2,y)$,
$(x+1,y+1)$ and $(x,y+2)$. In both [21] and [8], it is shown that the
probability of the event that the game under consideration results in a draw
is $0$ if and only if a _suitably defined_ (via the recurrence relations
arising from the game) $1$-dimensional probabilistic cellular automaton (PCA)
is ergodic. Using the technique of _weight functions_ or _potential functions_
, it is then shown that this PCA is ergodic whenever $p+q>0$. In [9], yet
another modification of the node percolation game is considered, with the
token now being allowed to be moved from $(x,y)$ to one of $(x,y+1)$ and
$(x+1,y+1)$ when $x$ is even, and from $(x,y)$ to one of $(x+1,y+1)$ and
$(x+2,y+1)$ when $x$ is odd. The probability of draw in this game, for various
values of the underlying parameters $p$ and $q$, is explored alongside
ergodicity properties of a $1$-dimensional _generalized_ PCA whose stochastic
update rule captures the recurrence relations arising out of this game. We
mention here that [11] employs the technique of weight functions to come up
with computer-assisted proofs of ergodicity for two classes of PCAs.

For a very broad, general discussion on tree automata, we refer the reader to
[13] and [18], but perhaps more relevant to the definition of PTAs that we
work with (see §2.2) are certain aspects of [29], [23], [20] and [28], among
others. In [29], for instance, _first order logic_ on rooted _Galton-Watson_
(GW) trees is studied using the _Ehrenfeucht-Fraïssé_ (EHR) games – another
example of two-player combinatorial games. For $k\in\mathbb{N}$, the $k$-round
EHR game partitions the space of all locally finite rooted trees into a
_finite_ set $\Sigma_{k}$ of equivalence classes – given _any_
$\sigma\in\Sigma_{k}$, _any_ two rooted trees, $T_{1}$ and $T_{2}$, both of
which belong to $\sigma$, and _any_ first order sentence $A$ of quantifier
depth at most $k$, either $A$ is true on _both_ $T_{1}$ and $T_{2}$, or on
_neither_. If the root $\phi$ of a tree $T$ has children $u_{1},\ldots,u_{r}$,
with $T(u_{i})$ denoting the sub-tree of $T$ that is induced on the subset of
vertices comprising $u_{i}$ and its descendants, then the equivalence class to
which $T$ belongs is given by a deterministic function of the tuple
$\big{(}\min\\{n_{\sigma},k\\}:\sigma\in\Sigma_{k}\big{)}$, where
$n_{\sigma}=\left|\left\\{1\leqslant i\leqslant
r:T(u_{i})\in\sigma\right\\}\right|$. This, then, forms yet another example of
a finite state tree automaton.

In [23], given a deterministic finite state tree automaton $A$, with alphabet
$\mathcal{S}$ (see §2.2 for relevant definitions), a probability distribution
$\nu$, supported on $\mathcal{S}$, is called a _fixed point_ of $A$ if the
following is true: if the children of the root $\phi$ of a GW tree are
assigned i.i.d. $\nu$ states from $\mathcal{S}$, the induced (random) state at
$\phi$ will again have law $\nu$. A map $\iota$ from the space of all locally
finite rooted trees to $\mathcal{S}$ is called an _interpretation_ for $A$ if
the following is true: given any rooted tree $T$, and any vertex $u$ of $T$
with children $u_{1},\ldots,u_{r}$, the state $\iota(T(u))$ is obtained by
applying the automaton $A$ to the tuple
$\big{(}\iota(T(u_{1})),\ldots,\iota(T(u_{r}))\big{)}$. Here, as defined
above, $T(u)$ (respectively $T(u_{i})$, for $1\leqslant i\leqslant r$) denotes
the sub-tree of $T$ induced on the subset of vertices comprising $u$
(respectively $u_{i}$) and its descendants. A fixed point $\nu$ of $A$ is said
to be _interpretable_ if there exists an interpretation $\iota$ for $A$ such
that the law of $\iota(\mathcal{T})$ is $\nu$, where $\mathcal{T}$ denotes the
rooted GW tree. The question of interpretability of a fixed point of a
deterministic finite state tree automaton ties in closely with the notion of
_endogeny_ (see Definition 7 and other relevant parts of § 2.4 of [2]), some
literature on which has been briefly discussed below.

Both [20] and [28] investigate _normal_ and _misère games_ on rooted GW trees.
In [20], a player is allowed to move the token from where it is currently
located, say a vertex $u$, to any child of $u$, whereas in [28], she may move
it from $u$ to any descendant of $u$ that is at a distance at most $k$ away
from $u$, where $k\in\mathbb{N}$ is pre-specified. A player loses the normal
game if she is unable to make a permitted move (which happens when the token
has reached a leaf vertex), whereas a player loses the misére game if her
opponent fails to make a permitted move. The approach outlined in [20] and
[28], namely analyzing the recurrence relations deduced from these games and
seeking their fixed points, is quite similar in flavour to that encountered in
this paper. In fact, the analysis carried out in §6 bears significant
resemblance to that of [20].

Perhaps one of the most seminal works in the literature that relates directly
with the idea of PTAs is [2], which concerns itself with the study of
_recursive distributional equations_. In fact, the set-up introduced in [2] is
a lot broader and more general than the definition (see §2.2) of PTAs
considered in this paper. In [2], a family $(\xi_{i}:i\geqslant 1)$ of jointly
distributed random variables and a family $(X_{i}:i\geqslant 1)$ of
independent and identically distributed random variables are considered, with
the law of each $X_{i}$ being $\mu$. The two families $(\xi_{i}:i\geqslant 1)$
and $(X_{i}:i\geqslant 1)$ are independent of each other. Letting $T(\mu)$
indicate the law of the random variable $g\big{(}(\xi_{i},X_{i}):i\geqslant
1\big{)}$, where $g$ is a function defined on a suitable domain, one of [2]’s
chief goals is to explore the existence and uniqueness of those $\mu$, termed
_fixed points_ , such that $T(\mu)=\mu$. In this context, the _recursive tree
process_ is introduced (see § 2.3 of [2]). Let a vertex $u$ of a rooted tree
have $N$ children (where $N$ could be a random number taking values in
$\\{0,1,2,\ldots;\infty\\}$) that are named $u_{1},u_{2},\ldots,u_{N}$ when
$N$ is finite, and $u_{1},u_{2},u_{3},\ldots$ when $N$ takes the value
$\infty$. Let $X_{i}$ denote the (random) state assigned to the child $u_{i}$,
and let $\xi_{i}$ indicate some random noise associated with $u_{i}$, for
every $i$. Then the (random) state $X$ assigned to the parent vertex $u$ is
given by $g\big{(}(\xi_{i},X_{i}):i\geqslant 1\big{)}$. Further advancements
in the study of recursive distributional equations and recursive tree
processes (as well as the notion of endogeny that we alluded to, earlier) can
be found in [3], [5], [4], [6] etc.

We mention here that recursive distributional equations find numerous
applications, such as in finding _maximal weight partial matchings on random
trees_ (see § 3 of [1]) and _minimal cost perfect matchings_ (see § 5 of [1]),
in the _cavity method_ implemented for _community detection in sparse graphs_
(see, for instance, § 3.3 of [22]), and in establishing _correlation decay_
that subsequently leads to the discovery of the asymptotics for the _log-
partition functions_ in certain statistical physical models (see, for
instance, the discussions in [7]), to name just a few.

It is undeniable that a tremendous motivation for studying percolation games
arises from the classically studied topic of _percolation_ in physics. It is
the presence of players who play _optimally_ and make _adversarial_ moves
against one another, in a bid to win, that sets the former apart from the
latter, and we take this opportunity to draw an important comparison between
the two. It is well-known and relatively straightforward to see that if each
edge of $T_{d}$, independently, is marked _closed_ (this corresponds to the
label _trap_ in our set-up) with probability $p$, and _open_ (this corresponds
to the label _safe_ in our set-up) with probability $1-p$, then for all
$p<1-\frac{1}{d}$, there exists an open path from the root $\phi$ of $T_{d}$
to infinit, i.e.  _percolation happens_. However, the existence of such a path
is _not_ enough to guarantee a positive chance for the bond percolation game
to result in a draw. This is why, we require, as stated in Theorem 1.1,
$p\leqslant p_{c}$ for our game to have a strictly positive probability of
resulting in a draw, where $p_{c}<1-\frac{1}{d}$.

We do not delve too deep into the literature on percolation here, as it is
vast and extensive, but we draw the reader’s attention to [19], to [32]
(emphasising on the connections explored therein between cellular automata and
percolation), and to [26] and [27] (both of which specifically study
percolation on rooted trees, with the former revealing a relation between the
_branching number_ of the tree, the probability with which each edge is left
open, and the probability of existence of an open path from the root to
infinity). While we are on the topic of percolation, we refer to the _Maker-
Breaker percolation games_ (see [14], [15], [17]). To begin with, all edges of
an infinite connected graph are marked _unsafe_. Players _Maker_ and _Breaker_
take turns to make moves, where, in each of her moves, Maker marks $a$ of the
yet-unsafe edges as _safe_ , and in each of her moves, Breaker deletes $b$ of
the yet-unsafe edges from the graph, where $a\in\mathbb{N}$ and
$b\in\mathbb{N}$ are pre-specified. Breaker wins if at any point of time in
the game, the connected component containing a pre-specified vertex of the
graph becomes finite; else Maker wins.

Finally, we come to a brief discussion on how the approach we adopt for
establishing ergodicity of our PTAs (see Definition 2.1, and the arguments
outlined in §5.1, §5.3.1 and §5.3.2 in this regard) is essentially identical
with how _weak spatial mixing_ is defined and proved for models of statistical
mechanics on rooted trees. In particular, we refer the reader to §3.4 of [12],
[24], and Lemma 1.3 (and Equation (3) therein) of [16]. For the definition of
_Gibbs states_ , corresponding to a given model of statistical mechanics, on
an infinite graph, we refer the reader to [30]). From this definition, it
becomes evident that for there to be a _unique Gibbs measure_ for a model of
statistical mechanics defined on $T_{d}$, the effect that _any_ configuration
of _states_ or _spins_ , assigned to the vertices at distance $n$ from the
root $\phi$, on the induced (random) state at $\phi$ must decay as
$n\rightarrow\infty$. This is precisely what (2.3) of Definition 2.1
represents, as well.

###  1.3. Organization of the paper

This paper has been organized as follows. Formal descriptions of the games
studied in this paper are provided in §2.1, and a general introduction to PTAs
in §2.2. We have devoted §3 to deriving the recurrence relations from the
games, representing them in terms of suitably defined PTAs, and stating
Theorem 3.1 and Theorem 3.2 pertaining to ergodicity properties of these PTAs.
In §4, we describe the intimate connection between the probability of the
outcome of draw in the games we consider, and the ergodicity of the
corresponding PTAs. The main result of §4 is Theorem 4.5 (stated in §4.2).
Four important lemmas concerning stochastic domination are stated in §4.1,
though their proofs are deferred to §8.1 of the Appendix (§8). The second part
of Theorem 3.1 is proved in §5, whereas the first is proved in §6. Finally,
the PTA arising out of the node percolation game is analyzed in §7, including
the proof of Theorem 3.2.

##  2\. The games and tree automata considered, relevant notations and
definitions

###  2.1. A formal introduction to the games

Although we have already introduced the games that we study in this paper in
§1.1, we recall here their salient features. Both the bond percolation game
and the site percolation game are played on the rooted $d$-regular tree
$T_{d}$, there is a parameter $p\in(0,1)$ associated with both of them, and
both involve two players and a token. In each case, $T_{d}$ can be visualized
as a directed graph by endowing each of its edges, that are of the form
$\\{u,v\\}$ with $u$ being the parent of $v$, the direction _from_ $u$
_towards_ $v$ (henceforth indicated by $(u,v)$). At first,

  1. (i)

in case of the bond percolation game, we label each edge of $T_{d}$,
independently, as a trap with probability $p$ and as safe with probability
$1-p$,

  2. (ii)

in case of the site percolation game, we label each vertex of $T_{d}$,
independently, as a trap with probability $p$ and as safe with probability
$1-p$.

Once a realization of this random assignment of labels has been generated, it
is revealed in its entirety to the two players. To begin with, the token rests
at an _initial vertex_ (which could be the root $\phi$ of $T_{d}$), and the
players take turns to move it along the directed edges (as described above) of
$T_{d}$.

  1. (i)

In case of the bond percolation game, a player wins if she is able to force
her opponent to move the token along a directed edge that has been labeled a
trap.

  2. (ii)

In case of the site percolation game, a player wins if she is able to force
her opponent to move the token to a vertex labeled a trap.

A game that continues for eternity is said to result in a draw. We assume both
players to play _optimally_ , i.e. if the game is destined to end in a finite
number of rounds, then the player who wins tries to wrap up the game as
quickly as possible, whereas the player who loses tries to prolong its
duration as much as possible.

###  2.2. A formal introduction to probabilistic tree automata

A _finite state probabilistic tree automaton_ (as mentioned in §1.1, we
abbreviate this as PTA) $A$ defined on $T_{d}$ comprises the following
components:

  1. (i)

a _finite_ set $\mathcal{S}$ of _states_ or _colours_ that we refer to as its
_alphabet_ ,

  2. (ii)

a _stochastic update rule_ , encompassed by the
$|\mathcal{S}|^{d}\times|\mathcal{S}|$-dimensional stochastic matrix
$\vartheta_{A}$, so that if a vertex $u$ in $T_{d}$ has children named
$u_{1},u_{2},\ldots,u_{d}$, and $u_{i}$ has state $a_{i}\in\mathcal{S}$ for
$1\leqslant i\leqslant d$, then the probability of the event that the state of
$u$ is $b\in\mathcal{S}$ is given by the entry
$\vartheta_{A}((a_{1},a_{2},\ldots,a_{d}),b)$ of $\vartheta_{A}$.

Let $L_{n}$ denote the set of all vertices of $T_{d}$ that are in generation
$n$ for $n\in\mathbb{N}_{0}$, where the root $\phi$ is assumed to be in
generation $0$ (i.e. $L_{0}=\\{\phi\\}$). Conditioned on the states of all
vertices in generation $L_{n+1}$, the (random) states assigned to the vertices
in $L_{n}$ under the application of $A$ are independent.

A _configuration_ on $L_{n}$ refers to an assignment
$\sigma:L_{n}\rightarrow\mathcal{S}$ of states to the vertices of $L_{n}$, for
each $n\in\mathbb{N}_{0}$. It is evident that once we fix a configuration on
$L_{n}$, iterative applications of $A$ are only capable of determining /
affecting the (random) states of the vertices in $L_{i}$ for $0\leqslant
i\leqslant n-1$. In fact, it will frequently be the case that we shall fix
$n$, focus on the _level- $n$ truncated tree_ $T_{d}^{n}$ that is the induced
subgraph of $T_{d}$ on the subset of vertices spanning generations
$L_{0},L_{1},\ldots,L_{n}$, carry out our analysis and _then_ let
$n\rightarrow\infty$. In such situations, a configuration on $L_{n}$, which is
the last generation to be included in $T_{d}^{n}$, will be, quite
appropriately, referred to as a _boundary configuration_.

Given a boundary configuration $\sigma:L_{n}\rightarrow\mathcal{S}$ and a
vertex $u$ that is situated in generation $i$ for some $0\leqslant i\leqslant
n-1$, we denote by $A(\sigma,u)$ the random variable indicating the state of
$u$ obtained via iterative applications of $A$, starting from $\sigma$.
Formally speaking, if $u$ is in $L_{n-1}$ and its children are named
$u_{1},u_{2},\ldots,u_{d}$, then $A(\sigma,u)$ is the random variable with the
following probability distribution:

$\operatorname{\mathbf{P}}[A(\sigma,u)=b]=\vartheta_{A}((\sigma(u_{1}),\sigma(u_{2}),\ldots,\sigma(u_{d})),b),\text{
for each }b\in\mathcal{S},$

where $\sigma(u_{i})$ indicates the state that $\sigma$ assigns to the vertex
$u_{i}$ (which is in $L_{n}$) for each $1\leqslant i\leqslant d$. For any
$0\leqslant i\leqslant n-2$, having defined $A(\sigma,w)$ for every vertex $w$
that lies in $L_{j}$ for all $i<j\leqslant n-1$, we define $A(\sigma,v)$, for
every $v\in L_{i}$, as follows. Suppose $v$ has children
$v_{1},v_{2},\ldots,v_{d}$. Then

$\displaystyle\operatorname{\mathbf{P}}\left[A(\sigma,v)=b\big{|}A(\sigma,v_{1})=a_{1},A(\sigma,v_{2})=a_{2},\ldots,A(\sigma,v_{d})=a_{d}\right]=\vartheta_{A}((a_{1},a_{2},\ldots,a_{d}),b),$
(2.1)

for all $b,a_{1},a_{2},\ldots,a_{d}\in\mathcal{S}$. Given a (deterministic)
boundary configuration $\sigma$ on $L_{n}$ for any $n\in\mathbb{N}$, and $u$ a
vertex in $L_{i}$ for any $0\leqslant i\leqslant n-1$, we let
$\mu_{A}(\sigma,u)$ denote the law of the random variable $A(\sigma,u)$. When
$u$ equals the root $\phi$ of $T_{d}$, we abbreviate $\mu_{A}(\sigma,\phi)$ as
simply $\mu_{A}(\sigma)$.

The notations introduced in the previous paragraph can be extended as follows
when, instead of considering a deterministic boundary configuration $\sigma$
on $L_{n}$, we consider a _random_ boundary configuration
$\boldsymbol{\sigma}$ on $L_{n}$, with law $\nu$ supported on
$\mathcal{S}^{d^{n}}$. For any $0\leqslant i\leqslant n-1$ and any vertex $u$
that lies in $L_{i}$, we let $A(\boldsymbol{\sigma},u)$ denote the (random)
state of $u$ obtained by starting from $\boldsymbol{\sigma}$ on $L_{n}$ and
iteratively applying $A$ up the generations of $T_{d}^{n}$. We let
$\mu_{A}(\nu,u)$ denote the law of $A(\boldsymbol{\sigma},u)$. As above, we
abbreviate $\mu_{A}(\nu,\phi)$ as $\mu_{A}(\nu)$.

Recall that, given a measurable space $(\Omega,\mathcal{F})$ and two
probability distributions $\mu_{1}$ and $\mu_{2}$ defined on it, the _total
variation distance_ between $\mu_{1}$ and $\mu_{2}$ is defined as

$\left|\left|\mu_{1}-\mu_{2}\right|\right|_{\operatorname{TV}}=\sup_{S\in\mathcal{F}}\left|\mu_{1}(S)-\mu_{2}(S)\right|.$

When $\Omega$ is countable and $\mathcal{F}$ is its power set, the total
variation metric is related to the $L^{1}$ metric via the following relation:

$\left|\left|\mu_{1}-\mu_{2}\right|\right|_{\operatorname{TV}}=\frac{1}{2}\left|\left|\mu_{1}-\mu_{2}\right|\right|_{L^{1}}=\frac{1}{2}\sum_{\omega\in\Omega}\left|\mu_{1}(\\{\omega\\})-\mu_{2}(\\{\omega\\})\right|.$

Moreover, we have (see, for instance, Proposition 4.7 of [25])

$\left|\left|\mu_{1}-\mu_{2}\right|\right|_{\operatorname{TV}}=\inf\left\\{\operatorname{\mathbf{P}}[X_{1}\neq
X_{2}]:(X_{1},X_{2})\text{ is a coupling of }\mu_{1}\text{ and
}\mu_{2}\right\\},$ (2.2)

where by a coupling $(X_{1},X_{2})$ of $\mu_{1}$ and $\mu_{2}$ we mean a pair
of random variables, $X_{1}$ and $X_{2}$, defined on the same probability
space (with a specified joint distribution), such that $X_{1}$ follows the law
$\mu_{1}$ and $X_{2}$ follows the law $\mu_{2}$.

######  Definition 2.1.

We call a PTA $A$ _ergodic_ if

$\limsup_{n\rightarrow\infty}\sup_{\sigma,\tau:L_{n}\rightarrow\mathcal{S}}\left|\left|\mu_{A}(\sigma)-\mu_{A}(\tau)\right|\right|_{\operatorname{TV}}=0,$
(2.3)

where $\mu_{A}(\sigma)$ and $\mu_{A}(\tau)$, as defined above, indicate the
laws of the random variables $A(\sigma,\phi)$ and $A(\tau,\phi)$ respectively.

A definition as instrumental to this paper as the one above deserves some
discussions about what truly its implications are. Consider _any_ two boundary
configurations $\sigma$ and $\tau$ on $L_{n}$. What the probability
distributions $\mu_{A}(\sigma)$ and $\mu_{A}(\tau)$ of the random variables
$A(\sigma,\phi)$ and $A(\tau,\phi)$ capture are the “effects” of the boundary
configurations $\sigma$ and $\tau$, respectively, on the state of the root
$\phi$ of $T_{d}$, under iterative applications of the PTA $A$. Consequently,
what the total variation distance
$\left|\left|\mu_{A}(\sigma)-\mu_{A}(\tau)\right|\right|_{\operatorname{TV}}$
captures is the difference between these effects, i.e. how differently the
probability distribution of the state of $\phi$ is impacted because of
starting from the boundary configuration $\sigma$ on $L_{n}$ as opposed to
starting from the boundary configuration $\tau$ on $L_{n}$. When (2.3) holds,
it is an indication that the effect _any_ boundary configuration assigned to
$L_{n}$ has on the state of $\phi$ _dwindles_ or _decays_ as $n$ approaches
$\infty$. It is as if, when $n$ is sufficiently large, the PTA $A$, viewed as
a stochastic operator that acts on the states of the vertices of $L_{i}$ for
all $1\leqslant i\leqslant n$, tends to nearly _forget_ the “initial” boundary
configuration on $L_{n}$.

We remark here (see also §1.2) that the phenomenon of ergodicity described
above is reminiscent of the manner in which the property of weak spatial
mixing is defined for any typical model of statistical mechanics studied on
$T_{d}$ (see, for instance, the classical [[12], §3.4] and [24], and the much
more recent [16], all of which adopt approaches similar to what we have
described above to determine if the statistical mechanical models under
consideration possess _unique_ Gibbs measures or not).

##  3\. Recurrence relations from our games and the associated probabilistic
tree automata

For each of the two games we study, we define the following (random) subsets
of vertices of $T_{d}$:

  1. (i)

We indicate by $W$ the subset comprising all those vertices $v$ of $T_{d}$
such that if the game begins with $v$ as the initial vertex, the player who
moves first wins.

  2. (ii)

We indicate by $L$ the subset comprising all those vertices $v$ of $T_{d}$
such that if $v$ is the initial vertex, the player who moves first loses.

  3. (iii)

We indicate by $D$ the subset comprising all those vertices $v$ of $T_{d}$
such that if $v$ is the initial vertex, the game results in a draw.

Henceforth, the _state_ of a vertex $v$ in $T_{d}$ will indicate which of the
above subsets $v$ belongs to under the game we are concerned with. Fixing a
vertex $v$ of $T_{d}$ and letting $v_{1},v_{2},\ldots,v_{d}$ denote its
children, we now explore the recurrence relations that dictate the (random)
state of $v$ given the states of its children.

###  3.1. Recurrence relations for the bond percolation game

Let $v$ be a vertex in $T_{d}$, with children $v_{1},\ldots,v_{d}$ such that
the state of each of $v_{1},\ldots,v_{i}$ is $L$, the state of each of
$v_{i+1},\ldots,v_{i+j}$ is $D$, and the state of each of the remaining
offspring is $W$. Assume that $v$ serves as the initial vertex for a bond
percolation game played between players $P$ and $Q$ in which $P$ plays the
first round.

  1. (i)

If there exists at least one $1\leqslant\ell\leqslant i$ such that the edge
$(v,v_{\ell})$ is safe, then player $P$ relocates the token from $v$ to
$v_{\ell}$. As $v_{\ell}\in L$, a game beginning from $v_{\ell}$ is lost by
the player who plays its first round, which, in this case, is player $Q$.
Thus, in this case, $P$ wins, allowing $v\in W$. Therefore, the probability
that the state of $v$ is $W$, conditioned on the information given above, is
$1-p^{i}$.

  2. (ii)

Suppose $(v,v_{\ell})$ is a trap for every $1\leqslant\ell\leqslant i$, but
there exists some $i+1\leqslant\ell^{\prime}\leqslant i+j$ such that
$(v,v_{\ell})$ is safe. Then $P$ moves the token from $v$ to
$v_{\ell^{\prime}}$, and as $v_{\ell^{\prime}}\in D$, the game beginning at
$v_{\ell^{\prime}}$ results in a draw, thus yielding $v\in D$. Therefore, the
probability that the state of $v$ is $D$, conditioned on the information given
above, is $p^{i}(1-p^{j})$.

  3. (iii)

In all other scenarios, we have $v\in L$.

It is crucial to observe here that the above information can be summarized as
a suitable PTA that we henceforth refer to as $B_{p}$ (to emphasize both upon
the fact that this PTA is derived from recurrence relations arising out of the
_bond_ percolation game and upon its dependence on the parameter $p\in(0,1)$).
The associated alphabet is $\mathcal{S}=\\{W,L,D\\}$, and the stochastic
update rule is captured by the $3^{d}\times 3$-dimensional stochastic matrix
$\vartheta_{B_{p}}$ whose elements are given by

$\vartheta_{B_{p}}((a_{1},a_{2},\ldots,a_{d}),b)=\begin{cases}1-p^{i}&\text{when
}b=W,\\\ p^{i}(1-p^{j})&\text{when }b=D,\\\ p^{i+j}&\text{when
}b=L,\end{cases}$ (3.1)

for all $a_{1},a_{2},\ldots,a_{d}\in\mathcal{S}$ such that
$i=\left|\left\\{1\leqslant\ell\leqslant d:a_{\ell}=L\right\\}\right|$ and
$j=\left|\left\\{1\leqslant\ell\leqslant d:a_{\ell}=D\right\\}\right|$.

This brings us to one of our two main results pertaining to PTAs in this
paper:

######  Theorem 3.1.

Fix $p\in(0,1)$. The PTA $B_{p}$, described in (3.1), is ergodic if and only
if $p\geqslant p_{c}$, where $p_{c}$ is as defined in (1.2).

###  3.2. Recurrence relations for the site percolation game

Once again, we consider a vertex $v$ of $T_{d}$, with children
$v_{1},\ldots,v_{d}$, that serves as our initial vertex for the site
percolation game. We let the state of each of $v_{1},\ldots,v_{i}$ be $L$, the
state of each of $v_{i+1},\ldots,v_{i+j}$ be $D$, and the state of each of the
remaining vertices be $W$. We assume that player $P$ moves first in the game,
followed by player $Q$. The following are the scenarios possible:

  1. (i)

Suppose $v$ itself has been labeled a trap, which happens with probability
$p$. In this case, one may imagine an _unseen_ round that happens _before_ the
_actual_ game begins, during which the token was moved from somewhere else to
$v$ by player $Q$. Since $v$ is a trap, this means that $Q$ immediately lost
to $P$, i.e. the game’s fate was decided even before it truly began. Thus, we
assign the state $W$ to $v$ in this case.

  2. (ii)

Suppose $v$ is safe, and let $i\geqslant 1$. In this case, $P$ moves the token
from $v$ to $v_{\ell}$, for any $1\leqslant\ell\leqslant i$, in the first
round. As $v_{\ell}\in L$, the game that begins at $v_{\ell}$ is lost by the
player who moves first, and in this case, that player is $Q$. Therefore, $P$
wins, allowing $v\in W$.

  3. (iii)

Suppose $v$ is safe, $i=0$ and $j\geqslant 1$. In this case, $P$ moves the
token from $v$ to a $v_{\ell}$, for any $1\leqslant\ell\leqslant j$, in the
first round. As $v_{\ell}\in D$, the game beginning from $v_{\ell}$ results in
a draw, hence leading to $v\in D$.

  4. (iv)

In all other situations, $v\in L$.

Once again, the findings above can be succinctly expressed in the form of a
PTA that we henceforth refer to as $N_{p}$ (to emphasize upon both the fact
that this PTA is derived from recurrence relations arising out of the _node_
percolation game, and its dependence on the parameter $p$). The alphabet
associated with $N_{p}$, as in the case of $B_{p}$ defined in §3.1, is
$\mathcal{S}=\\{W,L,D\\}$, and its stochastic update rule is captured by the
$3^{d}\times 3$-dimensional stochastic matrix $\vartheta_{N_{p}}$ whose
entries are given by

$\vartheta_{N_{p}}((a_{1},a_{2},\ldots,a_{d}),W)=\begin{cases}1&\text{when
}(a_{1},a_{2},\ldots,a_{d})\in\\{W,L,D\\}^{d}\setminus\\{D,W\\}^{d},\\\
p&\text{when }(a_{1},a_{2},\ldots,a_{d})\in\\{D,W\\}^{d},\end{cases}$ (3.2)
$\vartheta_{N_{p}}((a_{1},a_{2},\ldots,a_{d}),D)=1-p\text{ when
}(a_{1},a_{2},\ldots,a_{d})\in\\{D,W\\}^{d}\setminus\\{(W,W,\ldots,W)\\},$
(3.3)

and

$\vartheta_{N_{p}}((a_{1},a_{2},\ldots,a_{d}),L)=1-p\text{ when
}(a_{1},a_{2},\ldots,a_{d})=(W,W,\ldots W).$ (3.4)

We now state the main result that describes ergodicity properties of the PTA
$N_{p}$:

######  Theorem 3.2.

The PTA $N_{p}$ is ergodic if and only if $p\geqslant p_{c}$, where $p_{c}$ is
as defined in (1.2).

##  4\. The connection between the occurrence of draws and ergodicity of the
corresponding PTA

This section is dedicated to establishing the connection that holds together
the key components of this paper, i.e. the connection between the occurrence
of draws in any of the two games considered in §2.1, and the property of
ergodicity exhibited by the corresponding PTA (as described in §3.1 and §3.2).
Before stating Theorem 4.5 that describes this connection in case of the bond
percolation game (and the analogous Theorem 4.6 that describes this connection
in case of the site percolation game), we state a couple of stochastic
domination lemmas required to prove Theorem 4.5 (respectively, Theorem 4.6),
along with their ramifications.

Consistent with the notations introduced in §2.2, given a vertex $u$ of
$T_{d}$ that is in $L_{i}$ and given a (deterministic) boundary configuration
$\sigma$ on $L_{n}$, with $0\leqslant i\leqslant n-1$, we denote by
$B_{p}(\sigma,u)$ the (random) state of $u$ that is obtained by starting from
$\sigma$ on $L_{n}$ and applying $B_{p}$ iteratively up the generations of
$T_{d}^{n}$ until we reach $L_{i}$. We let $\mu_{B_{p}}(\sigma,u)$ denote the
law of the random variable $B_{p}(\sigma,u)$, and we abbreviate
$\mu_{B_{p}}(\sigma,\phi)$ as simply $\mu_{B_{p}}(\sigma)$. If
$\boldsymbol{\sigma}$ is a random boundary configuration, with law $\nu$, on
$L_{n}$, then we let $B_{p}(\boldsymbol{\sigma},u)$ denote the (random) state
of $u$ obtained by starting from $\boldsymbol{\sigma}$ on $L_{n}$ and applying
$B_{p}$ iteratively up the generations of $T_{d}^{n}$ until we reach $L_{i}$.
We let $\mu_{B_{p}}(\nu,u)$ denote the law of $B_{p}(\boldsymbol{\sigma},u)$,
and we abbreviate $\mu_{B_{p}}(\nu,\phi)$ as simply $\mu_{B_{p}}(\nu)$. When
it comes to the PTA $N_{p}$, the corresponding notations $N_{p}(\sigma,u)$,
$\mu_{N_{p}}(\sigma,u)$ (and the abbreviated $\mu_{N_{p}}(\sigma)$ when $u$ is
the root $\phi$ of $T_{d}$), $N_{p}(\boldsymbol{\sigma},u)$ and
$\mu_{N_{p}}(\nu,u)$ (and the abbreviated $\mu_{N_{p}}(\nu)$ when $u$ is
$\phi$) are similarly defined.

###  4.1. Some stochastic domination lemmas and their implications

Let the root $\phi$ of $T_{d}$ have children $u_{1},\ldots,u_{d}$. We consider
the partial order $W<D>L$ on the alphabet $\mathcal{S}$, and given any two
probability measures, $\nu$ and $\operatorname{\widetilde{\nu}}$, supported on
$\mathcal{S}^{d}$, we write $\nu\leqslant\operatorname{\widetilde{\nu}}$ to
indicate that $\operatorname{\widetilde{\nu}}$ stochastically dominates $\nu$
with respect to the coordinate-wise partial order induced by the partial order
on $\mathcal{S}$ mentioned above (here, the coordinates refer to the states of
the vertices $u_{1},\ldots,u_{d}$).

######  Lemma 4.1.

Suppose $\nu\leqslant\operatorname{\widetilde{\nu}}$ for two probability
measures, $\nu$ and $\operatorname{\widetilde{\nu}}$, supported on
$\mathcal{S}^{d}$. Then
$\mu_{B_{p}}(\nu)\leqslant\mu_{B_{p}}(\operatorname{\widetilde{\nu}})$.

The proof of this lemma is provided in §8.1 of the Appendix (§8). There are
two indispensable uses of Lemma 4.1 in this paper, the first of which is in
showing that whenever the PTA $B_{p}$ is ergodic, the probability that the
corresponding bond percolation game results in a draw is $0$, and the second
is in being able to utilize the fact that the boundary configuration on
$L_{n}$ that maximizes the probability of $D$ as the state of the root $\phi$
under iterative applications of $B_{p}$ is the one that assigns the state $D$
to every vertex of $L_{n}$. The latter fact can be formalized as follows. Let
us denote by $\delta_{D}^{n}$ the boundary configuration that assigns the
state $D$ to each vertex of $L_{n}$, for every $n\in\mathbb{N}$. Then

$\mu_{B_{p}}(\sigma)[D]\leqslant\mu_{B_{p}}\left(\delta_{D}^{n}\right)[D]\text{
for every }\sigma:L_{n}\rightarrow\mathcal{S},\text{ for every
}n\in\mathbb{N},$ (4.1)

where $\mu_{B_{p}}(\sigma)[D]$, $\mu_{B_{p}}(\sigma)[L]$ and
$\mu_{B_{p}}(\sigma)[W]$ denote, respectively, the probabilities of the states
$D$, $L$ and $W$ under the law $\mu_{B_{p}}(\sigma)$.

Suppose $B_{p}$ is ergodic according to Definition 2.1. In keeping with the
notation $\delta_{D}^{n}$, we let $\delta_{L}^{n}$ denote the boundary
configuration on $L_{n}$ that assigns the state $L$ to each vertex of $L_{n}$,
and $\delta_{W}^{n}$ the boundary configuration on $L_{n}$ that assigns the
state $W$ to each vertex of $L_{n}$. From (3.1), it is evident that

$\mu_{B_{p}}\left(\delta_{L}^{n}\right)[D]=\mu_{B_{p}}\left(\delta_{W}^{n}\right)[D],\text{
for every }n\in\mathbb{N}.$

This is because, unless the boundary configuration that we start with assigns
the state $D$ to at least one vertex of $L_{n}$, there can be _no_ vertex in
$L_{i}$, for _any_ $0\leqslant i\leqslant n-1$, which has a positive
probability of being assigned the state $D$. Applying (2.3), we deduce that,
when $B_{p}$ is ergodic,

$\displaystyle\lim_{n\rightarrow\infty}\left|\mu_{B_{p}}\left(\delta_{D}^{n}\right)[D]-\mu_{B_{p}}\left(\delta_{W}^{n}\right)[D]\right|=0\implies\lim_{n\rightarrow\infty}\mu_{B_{p}}\left(\delta_{D}^{n}\right)[D]=0.$
(4.2)

Combining (4.1) and (4.2), we conclude that when $B_{p}$ is ergodic,

$\displaystyle\lim_{n\rightarrow\infty}\max_{\sigma:L_{n}\rightarrow\mathcal{S}}\mu_{B_{p}}(\sigma)[D]=0.$
(4.3)

Another stochastic domination lemma is obtained when we consider the total
order $W\prec D\prec L$ on $\mathcal{S}$. For any two probability measures,
$\nu$ and $\operatorname{\widetilde{\nu}}$, supported on $\mathcal{S}^{d}$, we
let $\nu\preceq\operatorname{\widetilde{\nu}}$ indicate that
$\operatorname{\widetilde{\nu}}$ stochastically dominates $\nu$ with respect
to the coordinate-wise partial order induced by this total order.

######  Lemma 4.2.

Consider probability measures $\nu$ and $\operatorname{\widetilde{\nu}}$,
supported on $\mathcal{S}^{d}$, such that
$\nu\preceq\operatorname{\widetilde{\nu}}$. Then
$\mu_{B_{p}}(\operatorname{\widetilde{\nu}})\preceq\mu_{B_{p}}(\nu)$.

This lemma, too, is proved in §8.1 of the Appendix (§8). Conclusions similar
to those drawn from Lemma 4.1 can be obtained from Lemma 4.2 as well. The
usefulness of Lemma 4.2 lies in the fact that it allows us to, in some sense,
sandwich or squeeze the law $\mu_{B_{p}}(\sigma)$ between the laws
$\mu_{B_{p}}\left(\delta_{W}^{n}\right)$ and
$\mu_{B_{p}}\left(\delta_{L}^{n}\right)$, for _every_ boundary configuration
$\sigma$ on $L_{n}$, for every $n\in\mathbb{N}$, and this, in turn, is helpful
in establishing ergodicity of the PTA $B_{p}$ for suitable values of $p$.

A couple of analogous stochastic domination results are true for the PTA
$N_{p}$, and are stated below, with the proofs postponed to §8.1 of the
Appendix (§8):

######  Lemma 4.3.

Suppose $\nu\leqslant\operatorname{\widetilde{\nu}}$, in the same sense as in
Lemma 4.1, for two probability measures, $\nu$ and
$\operatorname{\widetilde{\nu}}$, supported on $\mathcal{S}^{d}$. Then
$\mu_{N_{p}}(\nu)\leqslant\mu_{N_{p}}(\operatorname{\widetilde{\nu}})$.

######  Lemma 4.4.

Suppose $\nu\preceq\operatorname{\widetilde{\nu}}$, in the same sense as in
Lemma 4.2, for two probability measures, $\nu$ and
$\operatorname{\widetilde{\nu}}$, supported on $\mathcal{S}^{d}$. Then
$\mu_{N_{p}}(\operatorname{\widetilde{\nu}})\preceq\mu_{N_{p}}(\nu)$.

Arguing in the same way as we did after stating Lemma 4.1 and Lemma 4.2, we
conclude that

$\mu_{N_{p}}\left(\delta_{D}^{n}\right)[D]\geqslant\mu_{N_{p}}\left(\sigma\right)[D]\text{
for every }\sigma:L_{n}\rightarrow\mathcal{S},\text{ for every
}n\in\mathbb{N},$ (4.4)

and when $N_{p}$ is ergodic,

$\displaystyle\lim_{n\rightarrow\infty}\sup_{\sigma:L_{n}\rightarrow\mathcal{S}}\mu_{N_{p}}(\sigma)[D]=0.$
(4.5)

###  4.2. How probabilities of draw tie in with ergodicity of the
corresponding PTAs

######  Theorem 4.5.

The probability that the bond percolation game with parameter $p$ results in a
draw is $0$ if and only if $B_{p}$ is ergodic.

We let $\boldsymbol{\omega}$ denote the random assignment of trap / safe
labels to the edges of $T_{d}$ (as described in §2.1). Given a vertex $u$ of
$T_{d}$, we let $\boldsymbol{\omega}(u)$ denote the restriction of
$\boldsymbol{\omega}$ to the edges of $T_{d}(u)$, where $T_{d}(u)$ denotes the
sub-tree of $T_{d}$ induced on the set of vertices comprising $u$ and all its
descendants. For any vertex $u$ in $T_{d}$, we let $X(u)$ denote the (random)
state (in $\mathcal{S}$) of $u$ obtained as a result of $\boldsymbol{\omega}$,
and we set $X=X(\phi)$. Note, crucially, from the way we define the bond
percolation game in §2.1, that $X(u)$ is actually a function of
$\boldsymbol{\omega}(u)$. We let $\mu$ denote the law of $X$.

###### Proof of Theorem 4.5.

Fix any vertex $u$ of $T_{d}$, and let $u_{1},u_{2},\ldots,u_{d}$ denote the
children of $u$. As mentioned above, $X(u_{i})$ is the random state of $u_{i}$
obtained as a result of $\boldsymbol{\omega}(u_{i})$, for each $1\leqslant
i\leqslant d$. By definition of $\boldsymbol{\omega}$ and the fact that each
$T_{d}(u_{i})$ is a copy of $T_{d}$, we deduce that
$\boldsymbol{\omega}(u_{i})$ are independent and identically distributed over
all $1\leqslant i\leqslant d$, and each has the same law as
$\boldsymbol{\omega}$. Consequently, $X(u_{1}),X(u_{2}),\ldots,X(u_{d})$ are
independent and identically distributed, and each has law $\mu$. Since
$\boldsymbol{\omega}(u)$, too, has the same law as $\boldsymbol{\omega}$,
hence $X(u)$ has law $\mu$ as well.

From the recurrence relations described in §3.1, it is immediate that $X(u)$
is obtained by applying $B_{p}$ to $(X(u_{1}),X(u_{2}),\ldots,X(u_{d}))$.
Setting $u$ to be the root $\phi$ of $T_{d}$, this implies that

$X=B_{p}\left(\left(X(u_{1}),X(u_{2}),\ldots,X(u_{d})\right),\phi\right),$

which, in turn, implies that the law $\mu$ of $X$ is the same as
$\mu_{B_{p}}(\nu^{(1)})$, where $\nu^{(1)}$ denotes the joint law of
$(X(u_{1}),X_{2}(u_{2}),\ldots,X(u_{d}))$, given by

$\nu^{(1)}[(a_{1},a_{2},\ldots,a_{d})]=\prod_{i=1}^{d}\mu[a_{i}],\text{ for
all }a_{1},a_{2},\ldots,a_{d}\in\mathcal{S}.$

This allows us to arrive at the following pivotal conclusion: if we assign
i.i.d. $\mu$ random states from $\mathcal{S}$ to the children of the root
$\phi$, then the law of the random state of $\phi$ obtained via an application
of the PTA $B_{p}$ is again $\mu$.

Note that the above idea can be applied iteratively over several generations,
leading to the following conclusion: if we assign i.i.d. $\mu$ random states
from $\mathcal{S}$ to the vertices of $L_{n}$, then the law of the random
state of $\phi$ obtained via iterative applications of $B_{p}$ is again $\mu$.
Formally, letting $\nu^{(n)}$ denote the probability distribution

$\nu^{(n)}\left[\left(a_{1},a_{2},\ldots,a_{d^{n}}\right)\right]=\prod_{i=1}^{d^{n}}\mu[a_{i}],\text{
for all }a_{1},a_{2},\ldots,a_{d^{n}}\in\mathcal{S},$

we conclude that

$\displaystyle\mu_{B_{p}}(\nu^{(n)})\text{ is the same law as }\mu.$

When $B_{p}$ is ergodic, from the above observation and (4.3), we conclude
that

$\mu[D]=\lim_{n\rightarrow\infty}\mu_{B_{p}}(\nu^{(n)})[D]\leqslant\lim_{n\rightarrow\infty}\max_{\sigma:L_{n}\rightarrow\mathcal{S}}\mu_{B_{p}}(\sigma)[D]=0.$
(4.6)

This shows that when $B_{p}$ is ergodic, the probability that the root $\phi$
has state $D$ under $\boldsymbol{\omega}$ is $0$, which means that the bond
percolation game that begins with $\phi$ as the initial vertex _almost never_
results in a draw.

To prove the converse, we assume that the bond percolation game beginning at
the root $\phi$ has probability $0$ of resulting in a draw. Let $\Omega$
denote the set of all realizations of $\boldsymbol{\omega}$ for which the game
starting at $\phi$ does not end in a draw. Then, by our hypothesis, the set
$\\{\text{trap},\text{safe}\\}^{E(T_{d})}\setminus\Omega$, where $E(T_{d})$
denotes the set of all edges of $T_{d}$, is of measure $0$. Furthermore, our
hypothesis guarantees the existence of a random variable $N$, taking values in
$\mathbb{N}$ and _finite almost surely_ , such that the game terminates in
less than $N$ rounds. In fact, for each realization $\omega$ of
$\boldsymbol{\omega}$ that belongs to $\Omega$, the corresponding value
$N(\omega)$ of $N$ is finite.

In addition to (3.1) that captures the recurrence relations for the bond
percolation game taking into account the _random_ assignment
$\boldsymbol{\omega}$, we now consider the following set-up: let $u$ be a
vertex in $T_{d}$, with children $u_{1},\ldots,u_{d}$, and let
$\omega(u,u_{i})$, for $1\leqslant i\leqslant d$, denote deterministic trap /
safe labels assigned to the edges $(u,u_{i})$, for $1\leqslant i\leqslant d$.
We also fix a deterministic assignment $\sigma\in\mathcal{S}^{d}$ of states
from $\mathcal{S}$ to $u_{1},\ldots,u_{d}$. In this situation, the state of
$u$ is decided, according to the rules of the game, as follows:

  1. (i)

If there exists some $1\leqslant i\leqslant d$ with $\omega(u,u_{i})$ safe and
$\sigma(u_{i})=L$, then $u$ is in $W$.

  2. (ii)

If the above does not happen, but there exists some $1\leqslant j\leqslant d$
with $\omega(u,u_{j})$ safe and $\sigma(u_{j})=D$, then $u$ is in $D$.

  3. (iii)

In all other cases, $u$ is in $L$.

For each $\omega$ in $\Omega$, suppose we assign _any_ deterministic
configuration $\sigma\in\mathcal{S}^{d^{N(\omega)}}$ of states from
$\mathcal{S}$ to the vertices of $L_{N(\omega)}$, and now, starting from
$\sigma$, we use $\omega$ and the rules described above to decide the state of
the root $\phi$. Since the fate of the game that begins from $\phi$ is decided
in _less_ than $N(\omega)$ rounds, the configuration $\sigma$ has no effect
whatsoever on the state that $\phi$ should be in. In other words, the state of
$\phi$ is dictated by $\omega$ alone, and is the same irrespective of our
choice of $\sigma$.

Given any $n\in\mathbb{N}$ and any boundary configuration $\sigma$ on $L_{n}$,
recall, from the notation introduced in §2.2, that $B_{p}(\sigma,u)$ denotes
the state of any vertex $u$, with $u\in L_{i}$ for some $0\leqslant i\leqslant
n-1$, obtained by starting from $\sigma$ on $L_{n}$ and applying the PTA
$B_{p}$ iteratively, taking into account the _random_ assignment
$\boldsymbol{\omega}$ of trap / safe labels to the edges of $T_{d}$ (more
precisely, we need only care about the restriction of $\boldsymbol{\omega}$ to
the edges of the truncated tree $T_{d}^{n}$). Therefore, the state of $u$,
obtained by starting from $\sigma$ on $L_{n}$ and iteratively applying the
rules i, ii and iii with a given realization $\omega$ of
$\boldsymbol{\omega}$, is given by $B_{p}(\sigma,u)(\omega)$. On the other
hand, $X(\omega)$ denotes the state of the root $\phi$ dictated by the
assignment $\omega$ alone. Letting $S_{n}$, for every $n\in\mathbb{N}$, denote
the set of all those $\omega$ in $\Omega$ for which $N(\omega)\leqslant n$, by
the argument outlined in the previous paragraph, we have

$\displaystyle B_{p}(\sigma,\phi)(\omega)=X(\omega)\text{ for every boundary
configuration }\sigma\text{ on }L_{n},\text{ for each }\omega\in S_{n}$
$\displaystyle\implies
B_{p}(\sigma,\phi)\mathbf{1}_{S_{n}}=X\mathbf{1}_{S_{n}}\text{ for every
boundary configuration }\sigma\text{ on }L_{n}$
$\displaystyle\implies\operatorname{\mathbf{P}}\left[B_{p}(\sigma,\phi)\neq
X\right]\leqslant
1-\operatorname{\mathbf{P}}[S_{n}]=\operatorname{\mathbf{P}}[N>n],\text{ for
every boundary configuration }\sigma\text{ on }L_{n}.$ (4.7)

Consequently, for _any_ two boundary configurations $\sigma$ and $\tau$ on
$L_{n}$, we have

$\displaystyle\operatorname{\mathbf{P}}\left[B_{p}(\sigma,\phi)\neq
B_{p}(\tau,\phi)\right]\leqslant\operatorname{\mathbf{P}}\left[B_{p}(\sigma,\phi)\neq
X\right]+\operatorname{\mathbf{P}}\left[B_{p}(\tau,\phi)\neq X\right]\leqslant
2\operatorname{\mathbf{P}}[N>n].$ (4.8)

We emphasize to the reader that in (4.8), when comparing $B_{p}(\sigma,\phi)$
and $B_{p}(\tau,\phi)$, we assume the same underlying assignment of trap /
safe labels to $E(T_{d})$. From (4.8) and the fact that $N$ is finite almost
surely, we conclude that

$\displaystyle\limsup_{n\rightarrow\infty}\sup_{\sigma,\tau:L_{n}\rightarrow\mathcal{S}}\operatorname{\mathbf{P}}\left[B_{p}(\sigma,\phi)\neq
B_{p}(\tau,\phi)\right]\leqslant\limsup_{n\rightarrow\infty}2\operatorname{\mathbf{P}}[N>n]=0,$
(4.9)

so that from (4.9), (2.2) and (2.3), we conclude that $B_{p}$ is indeed
ergodic, as desired. ∎

It is evident that once we prove Theorem 3.1, the second assertion (pertaining
to probabilities of draw in bond percolation games on $T_{d}$) of Theorem 1.1
will follow due to Theorem 4.5. The result analogous to Theorem 4.5 in case of
the site percolation game is as follows:

######  Theorem 4.6.

The probability that the site percolation game with parameter $p$ results in a
draw is $0$ if and only if $N_{p}$ is ergodic.

The proof follows, _mutatis mutandis_ , the argument outlined in the proof of
Theorem 4.5. Once again, once Theorem 3.2 is established, Theorem 1.2 will
follow due to Theorem 4.6.

##  5\. Proof of the second assertion of Theorem 3.1

The proof of Theorem 3.1 comprises four parts. In §5.1, we perform an
analysis, for all values of $p\in(0,1)$, of the effects of the boundary
configuration $\delta_{D}^{n}$ on $L_{n}$ (recall that this assigns the state
$D$ to each vertex of $L_{n}$) on the (random) state of the root $\phi$ of
$T_{d}$ under the PTA $B_{p}$. In §5.2, we show that for all values of $p$
sufficiently small, the PTA $B_{p}$ is non-ergodic. In §5.3, we show that
$B_{p}$ is ergodic for all $p\geqslant p_{c}$, where $p_{c}$ is as defined in
(1.2). Finally, in §5.4, we show that the desired phase transition phenomenon
indeed takes place precisely at $p=p_{c}$, and nowhere else.

###  5.1. Studying the effects of $\delta_{D}^{n}$ on the state of root $\phi$

Recall, from the notations set down in §2.2, that the random state of the root
$\phi$ that is obtained by starting from $\delta_{D}^{n}$ on $L_{n}$ and
iteratively applying $B_{p}$ up the generations until we reach $\phi$ is
$B_{p}(\delta_{D}^{n},\phi)$, and its law is given by
$\mu_{B_{p}}(\delta_{D}^{n})$. For the sake of brevity, let us set
$w_{n}=\mu_{B_{p}}(\delta_{D}^{n})[W]$ (i.e. the probability of $\phi$ being
in $W$ under the law $\mu_{B_{p}}(\delta_{D}^{n})$) and
$\ell_{n}=\mu_{B_{p}}(\delta_{D}^{n})[L]$. Clearly,
$\mu_{B_{p}}(\delta_{D}^{n})[D]=1-w_{n}-\ell_{n}$. We set $w_{0}=\ell_{0}=0$.

To work out the recurrence relations for the sequence
$\\{(w_{n},\ell_{n})\\}_{n\in\mathbb{N}}$, we let $\phi$ have children
$u_{1},u_{2},\ldots,u_{d}$. Recall that $T_{d}(u_{i})$ denotes the sub-tree of
$T_{d}$ induced on all those vertices that are descendants of $u_{i}$
(including $u_{i}$ itself), and that $T_{d}^{n}$ denotes the sub-tree of
$T_{d}$ induced on all those vertices that are in generations
$L_{0},L_{1},\ldots,L_{n}$. Then $T_{d}^{n-1}(u_{i})$ indicates the sub-tree
that is induced on all those vertices that are descendants of $u_{i}$
(including $u_{i}$ itself) and at distance at most $n-1$ away from $u_{i}$.
The random state of $u_{i}$, obtained by starting from $\delta_{D}^{n}$ on
$L_{n}$ and iteratively applying $B_{p}$ up the generations, is given by
$B_{p}(\delta_{D}^{n},u_{i})$, for $1\leqslant i\leqslant d$. It follows
immediately, from how we define PTAs in §2.2 and since $T_{d}^{n}(u_{1})$,
$T_{d}^{n}(u_{2})$, $\ldots$, $T_{d}^{n}(u_{d})$ are copies of a rooted
$d$-regular tree truncated at generation $n-1$, that
$B_{p}(\delta_{D}^{n},u_{1})$, $B_{p}(\delta_{D}^{n},u_{2})$, $\ldots$,
$B_{p}(\delta_{D}^{n},u_{d})$ are i.i.d., and each has law
$\mu_{B_{p}}(\delta_{D}^{n-1})$. Consequently,
$B_{p}(\delta_{D}^{n},u_{i})[W]=w_{n-1}$ and
$B_{p}(\delta_{D}^{n},u_{i})[L]=\ell_{n-1}$, for all $1\leqslant i\leqslant
d$.

Using the stochastic update rule for $B_{p}$ from (3.1), we obtain, for all
$n\in\mathbb{N}$,

$\displaystyle w_{n}$
$\displaystyle=\sum_{i=0}^{d}(1-p^{i})\operatorname{\mathbf{P}}\left[i\text{
vertices out of }u_{1},\ldots,u_{d}\text{ are in }L\right]$
$\displaystyle=\sum_{i=0}^{d}(1-p^{i}){d\choose
i}\ell_{n-1}^{i}(1-\ell_{n-1})^{d-i}$ $\displaystyle=1-\sum_{i=0}^{d}{d\choose
i}(p\ell_{n-1})^{i}(1-\ell_{n-1})^{d-i}=1-\\{1-(1-p)\ell_{n-1}\\}^{d}.$ (5.1)

Next, we have, for all $n\in\mathbb{N}$,

$\displaystyle\ell_{n}$
$\displaystyle=\sum_{i=0}^{d}\sum_{j=0}^{d-i}p^{i+j}\operatorname{\mathbf{P}}\left[i\text{
vertices out of }u_{1},\ldots,u_{d}\text{ are in }L\text{ and }j\text{ are in
}D\right]$ $\displaystyle=\sum_{i=0}^{d}\sum_{j=0}^{d-i}p^{i+j}{d\choose
i}{d-i\choose j}\ell_{n-1}^{i}(1-\ell_{n-1}-w_{n-1})^{j}w_{n-1}^{d-i-j}$
$\displaystyle=\sum_{i,j\in\mathbb{N}_{0}:i+j\leqslant
d}\frac{d!}{i!j!(d-i-j)!}(p\ell_{n-1})^{i}\\{p(1-\ell_{n-1}-w_{n-1})\\}^{j}w_{n-1}^{d-i-j}$
$\displaystyle=[p\ell_{n-1}+p(1-\ell_{n-1}-w_{n-1})+w_{n-1}]^{d}=\\{p+(1-p)w_{n-1}\\}^{d}.$
(5.2)

We may combine (5.1) and (5.2) to obtain, for all $n\in\mathbb{N}$,

$\displaystyle
w_{n+1}=1-\left[1-(1-p)\left\\{p+(1-p)w_{n-1}\right\\}^{d}\right]^{d}.$

In order to simplify the expression above, we set
$w^{\prime}_{n}=p+(1-p)w_{n}$ for all $n\in\mathbb{N}_{0}$, which transforms
the above relation into

$\displaystyle w^{\prime}_{n+1}$
$\displaystyle=p+(1-p)w_{n+1}=p+(1-p)-(1-p)\left[1-(1-p)\left\\{p+(1-p)w_{n-1}\right\\}^{d}\right]^{d}$
$\displaystyle=1-(1-p)\left[1-(1-p){w^{\prime}_{n-1}}^{d}\right]^{d}=f_{p}(w^{\prime}_{n-1}),$
(5.3)

where we set

$f_{p}(x)=1-(1-p)[1-(1-p)x^{d}]^{d},\text{ for }x\in[0,1].$ (5.4)

In the rest of the paper, as far as the PTA $B_{p}$ is concerned, we shall
work with the recurrence relation in (5.3) and the function $f_{p}$ defined in
(5.4).

Recall from above that $w_{0}=0$, so that $w^{\prime}_{0}=p$. Note that
$w_{1}=0$, and hence $w^{\prime}_{1}=p$, as well, because if we consider a
vertex $u$ in $L_{n-1}$ and the boundary configuration $\delta_{D}^{n}$ on
$L_{n}$, then since all the children of $u$ are in state $D$, hence $u$ must
either be in state $D$ or in state $L$ according to (3.1). Since
$w^{\prime}_{0}=w^{\prime}_{1}=p$, the initializing values for the two
subsequences, $\\{w^{\prime}_{2n}\\}_{n\in\mathbb{N}_{0}}$ and
$\\{w^{\prime}_{2n+1}\\}_{n\in\mathbb{N}_{0}}$, are the same. The governing
recurrence relation (5.3) is also the same for the two subsequences.
Consequently, we have

$w^{\prime}_{2n}=w^{\prime}_{2n+1}\text{ for all }n\in\mathbb{N}_{0}.$ (5.5)

####  5.1.1. Convergence of the sequence
$\\{w^{\prime}_{n}\\}_{n\in\mathbb{N}_{0}}$

Our first task is to show that $\lim_{n\rightarrow\infty}w^{\prime}_{n}$
exists, which immediately guarantees, by the transformation introduced above,
that $\lim_{n\rightarrow\infty}w_{n}$ exists as well. Note, also, that because
of (5.5), it suffices for us to show that
$\lim_{n\rightarrow\infty}w^{\prime}_{2n}$ exists, because in that case,
$\lim_{n\rightarrow\infty}w^{\prime}_{2n+1}$ will exist as well, and the two
limits will be equal.

We begin with analyzing the function $f_{p}$ in (5.4):

$\displaystyle f_{p}^{\prime}(x)$
$\displaystyle=(1-p)^{2}d^{2}x^{d-1}[1-(1-p)x^{d}]^{d-1},$ (5.6)

and this is strictly positive for all $x\in(0,1]$, for each $p\in(0,1)$.
Therefore, $f_{p}$ is a strictly increasing function on $[0,1]$ for every
$p\in(0,1)$.

We now claim that $\\{w^{\prime}_{2n}\\}_{n\in\mathbb{N}_{0}}$ forms a
strictly increasing subsequence for every $p\in(0,1)$. We prove this via
induction on the index $n$. Recall from above that $w_{0}=0$, so that
$w^{\prime}_{0}=p$. Therefore, by (5.3), we have, for each $p\in(0,1)$,

$w^{\prime}_{2}=1-(1-p)[1-(1-p)p^{d}]^{d}>1-(1-p)=p=w^{\prime}_{0},$

thus establishing the base case for the induction. Suppose we have shown that
$w^{\prime}_{2n+2}>w^{\prime}_{2n}$ for some $n\in\mathbb{N}_{0}$. Using this
induction hypothesis, the strictly increasing nature of $f_{p}$ from (5.6),
and (5.3), we obtain

$\displaystyle
w^{\prime}_{2n+4}=f_{p}(w^{\prime}_{2n+2})>f_{p}(w^{\prime}_{2n})=w^{\prime}_{2n+2},$

thus completing the inductive argument. Thus,
$\\{w^{\prime}_{2n}\\}_{n\in\mathbb{N}_{0}}$ is shown to form a strictly
increasing subsequence.

Since $w^{\prime}_{2n}$ is bounded above by $1$ for all $n\in\mathbb{N}_{0}$,
the conclusion from the previous paragraph implies that
$\lim_{n\rightarrow\infty}w^{\prime}_{2n}$ exists and is also bounded above by
$1$. Let this limit be $w^{\prime}$. As argued above (using (5.5)), this
proves that the entire sequence $\\{w_{n}\\}_{n\in\mathbb{N}_{0}}$ converges,
and to the same limit $w^{\prime}$.

######  Lemma 5.1.

The limit $w^{\prime}$ of the sequence $\\{w_{n}\\}_{n\in\mathbb{N}_{0}}$ is
the minimum positive fixed point of $f_{p}$.

###### Proof.

Taking the limit of both sides of (5.3) as $n\rightarrow\infty$, and using the
continuity of $f_{p}$, we obtain $w^{\prime}=f_{p}(w^{\prime})$, thus proving
that $w^{\prime}$ is a fixed point of $f_{p}$.

Next, let us note that any non-negative fixed point, say $\gamma$, of $f_{p}$,
must exceed $p$. This is because the strictly increasing nature of $f_{p}$
ensures that $0\leqslant\gamma\implies p=f_{p}(0)\leqslant
f_{p}(\gamma)=\gamma$.

Now, let us consider any non-negative fixed point $\gamma$ of $f_{p}$. We then
have, using (5.3),

$\displaystyle p=w^{\prime}_{0}\leqslant\gamma$ $\displaystyle\implies
w^{\prime}_{2n}=f_{p}^{(n)}(w^{\prime}_{0})\leqslant
f_{p}^{(n)}(\gamma)=\gamma\text{ for each }n\in\mathbb{N},$

where $f_{p}^{(n)}$ indicates the $n$-fold composition of $f_{p}$ with itself.
Taking the limit as $n\rightarrow\infty$, we now obtain
$w^{\prime}\leqslant\gamma$, as desired. ∎

####  5.1.2. A necessary condition for ergodicity of $B_{p}$

From (5.2), taking the limit as $n\rightarrow\infty$, using the fact that
$\lim_{n\rightarrow\infty}w^{\prime}_{n}=w^{\prime}$ exists and using the
continuity of the function $x\mapsto x^{d}$, we conclude that the limit

$\ell^{\prime}=\lim_{n\rightarrow\infty}\ell^{\prime}_{n}=\lim_{n\rightarrow\infty}(1-p){w^{\prime}_{n-1}}^{d}=(1-p)w^{\prime
d}$ (5.7)

exists, where we set $\ell^{\prime}_{n}=(1-p)\ell_{n}$ for each
$n\in\mathbb{N}_{0}$. Next, recall from (4.2) that when $B_{p}$ is ergodic,

$\displaystyle\lim_{n\rightarrow\infty}\mu_{B_{p}}\left(\delta_{D}^{n}\right)[D]=0\Longleftrightarrow\lim_{n\rightarrow\infty}1-\ell_{n}-w_{n}=0\Longleftrightarrow\lim_{n\rightarrow\infty}\ell^{\prime}_{n}+w^{\prime}_{n}=1$
$\displaystyle\Longleftrightarrow w^{\prime}+(1-p)w^{\prime
d}=1\Longleftrightarrow w^{\prime}=g_{p}(w^{\prime}),\text{ where
}g_{p}(x)=1-(1-p)x^{d}.$ (5.8)

It is of utmost importance to note here, from (5.1.2) and (5.4), that
$g_{p}^{(2)}(x)=f_{p}(x)$ for all $x\in[0,1]$ (where $g^{(2)}$ indicates the
composition of $g$ with itself). Next, we note that

$g^{\prime}_{p}(x)=-(1-p)dx^{d-1},\text{ for all }x\in[0,1],$ (5.9)

showing that $g_{p}$ is strictly decreasing on $[0,1]$ for each $p\in(0,1)$.
Moreover, $g_{p}(0)=1$ and $g_{p}(1)=p$, showing that the curve $y=g_{p}(x)$
lies above the line $y=x$ at $x=0$, and below the line $y=x$ at $x=1$.
Therefore, $y=g_{p}(x)$ intersects $y=x$ precisely once in the interval
$(0,1)$, and let this point of intersection be $\alpha_{p}$. Using this fact,
Lemma 5.1 and (5.1.2), we conclude that

$B_{p}\text{ is ergodic only if }w^{\prime}=\alpha_{p},\text{ i.e.\
}\alpha_{p}\text{ is the minimum positive fixed point of }f_{p}=g_{p}^{(2)}.$
(5.10)

######  Lemma 5.2.

The unique fixed point $\alpha_{p}$ of the function of $g_{p}$, in $(0,1)$, is
the minimum positive fixed point of the function $f_{p}$ if and only if
$f_{p}$ has a _unique_ fixed point in $(0,1)$.

###### Proof.

Since $f_{p}=g_{p}^{(2)}$, hence $\alpha_{p}$ must be a fixed point of
$f_{p}$. Suppose, now, that there exists another fixed point $\beta$ of
$f_{p}$ in $(0,1)$, so that we must have $\beta>\alpha_{p}$. Then

$\beta=f_{p}(\beta)=g_{p}^{(2)}(\beta)\implies
g_{p}(\beta)=g_{p}^{(3)}(\beta)=g_{p}^{(2)}(g_{p}(\beta))=f_{p}(g_{p}(\beta)),$

thus showing that $g_{p}(\beta)$ is yet another fixed point of $f_{p}$. Since
$g_{p}$ maps $[0,1]$ to $(0,1]$ (as evident from (5.1.2)), hence
$g_{p}(\beta)\in(0,1]$. Moreover, as $g_{p}$ is strictly decreasing (from
(5.9)) on $[0,1]$, hence

$\beta>\alpha_{p}\implies g_{p}(\beta)<g_{p}(\alpha_{p})=\alpha_{p}.$

This yields a fixed point of $f_{p}$ which is strictly positive and less than
$\alpha_{p}$. Therefore, in such a situation, $\alpha_{p}$ can no longer be
the minimum positive fixed point of $f_{p}$. This concludes the proof of this
lemma. ∎

###  5.2. Showing that $B_{p}$ is non-ergodic when $p$ is sufficiently small

From the conclusions drawn in §5.1.2, it suffices to show that for $p$
sufficiently small, the minimum positive fixed point $w^{\prime}$ of $f_{p}$
cannot equal the unique fixed point $\alpha_{p}$ of $g_{p}$. From the
definition of $g_{p}$ in (5.1.2), we have

$\alpha_{p}+(1-p)\alpha_{p}^{d}=1\implies\alpha_{p}+(1-p)\alpha_{p}>1\implies\alpha_{p}>\frac{1}{2-p},$

using the inequality $0<\alpha_{p}<1\implies\alpha_{p}>\alpha_{p}^{d}$ as
$d\in\mathbb{N}$ and $d\geqslant 2$. If we can show that the minimum positive
fixed point of $f_{p}$ is less than $\frac{1}{2-p}$ for all $p$ sufficiently
small, our goal would be accomplished.

Note that $f_{p}(0)=p>0$, so that the curve $y=f_{p}(x)$ lies above the line
$y=x$ at $x=0$. If we can show that the curve $y=f_{p}(x)$ lies beneath the
line $y=x$ at $x=\frac{1}{2-p}$, i.e.

$f_{p}\left(\frac{1}{2-p}\right)<\frac{1}{2-p}\text{ for all }p\text{
sufficiently small},$ (5.11)

then, because of the continuity of $f_{p}$ and the intermediate value theorem,
there must exist some fixed point of $f_{p}$ in the interval
$\left(0,\frac{1}{2-p}\right)$.

Note that (5.11) boils down to showing, for all $p$ sufficiently small,

$\displaystyle
1-(1-p)\left[1-(1-p)\cdot\left(\frac{1}{2-p}\right)^{d}\right]^{d}<\frac{1}{2-p}$
$\displaystyle\Longleftrightarrow
1-\frac{1}{2-p}<(1-p)\left[1-\frac{1-p}{(2-p)^{d}}\right]^{d}$
$\displaystyle\Longleftrightarrow\frac{1}{2-p}<\left[1-\frac{(2-p)-1}{(2-p)^{d}}\right]^{d}=\left[1-\frac{1}{(2-p)^{d-1}}+\frac{1}{(2-p)^{d}}\right]^{d}.$
(5.12)

Defining the function $h_{d}(x)=\left[1-x^{d-1}+x^{d}\right]^{d}-x$, for
$x\in\left(\frac{1}{2},1\right)$, we see that (5.12) is proved if we can show
that $h_{d}(x)>0$ for all $x$ sufficiently close to $\frac{1}{2}$. Note that
the continuity of the function $h_{d}$ guarantees that it suffices to show
that $h_{d}\left(\frac{1}{2}\right)>0$, i.e.

$\displaystyle\left[1-\frac{1}{2^{d}}\right]^{d}=\left[1-\frac{1}{2^{d-1}}+\frac{1}{2^{d}}\right]^{d}>\frac{1}{2}\text{
for all }d\in\mathbb{N},d\geqslant 2$
$\displaystyle\Longleftrightarrow\frac{1}{2^{d}}+\frac{1}{2^{1/d}}<1\text{ for
all }d\in\mathbb{N},d\geqslant 2.$ (5.13)

We now define the function

$h(x)=\frac{1}{2^{x}}+\frac{1}{2^{1/x}}=e^{-x\ln 2}+e^{-\frac{\ln
2}{x}},\text{ for }x\geqslant 2.$ (5.14)

Differentiating this function with respect to $x$ yields

$\displaystyle h^{\prime}(x)$ $\displaystyle=-\ln 2e^{-x\ln 2}+\frac{\ln
2}{x^{2}}e^{-\frac{\ln 2}{x}}=\ln 2\left[\frac{2^{-1/x}}{x^{2}}-2^{-x}\right]$
(5.15)

and this is strictly positive if and only if

$\displaystyle\frac{2^{-1/x}}{x^{2}}>2^{-x}\Longleftrightarrow
2^{x-\frac{1}{x}}>x^{2}\Longleftrightarrow\left(x-\frac{1}{x}\right)\ln 2>2\ln
x.$ (5.16)

We now consider the function

$r(x)=\left(x-\frac{1}{x}\right)\ln 2-2\ln x,\text{ for }x\geqslant 2.$ (5.17)

Differentiating this function with respect to $x$ yields

$\displaystyle r^{\prime}(x)$ $\displaystyle=\left(1+\frac{1}{x^{2}}\right)\ln
2-\frac{2}{x}=\ln 2-\frac{2}{x}+\frac{\ln 2}{x^{2}}>0\text{ for all
}x\geqslant 2,$

since $2/x\leqslant 1$ whereas $\ln 2>1$. Consequently, $r(x)$ is strictly
increasing for $x\geqslant 2$. Moreover, $r(5)\approx 0.108$. Thus, we
conclude that $r(x)>0$ for all $x\geqslant 5$, so that from (5.17), we
conclude that the inequality in (5.16) holds for all $x\geqslant 5$.

From the relationship between (5.15) and (5.16), using the above conclusion,
we obtain $h^{\prime}(x)>0$ for all $x\geqslant 5$, so that $h(x)$ is strictly
increasing for $x\geqslant 5$. Note, from (5.14), that

$\lim_{x\rightarrow\infty}h(x)=\lim_{x\rightarrow\infty}\frac{1}{2^{x}}+\frac{1}{2^{1/x}}=1.$

These two properties of the function $h$ together ensure that $h(x)<1$ for all
$x\geqslant 5$, i.e. that (5.2) holds for all $d\geqslant 5$.

Finally, we note that $h(2)\approx 0.957$, $h(3)\approx 0.918$ and
$h(4)\approx 0.903$, thus establishing (5.2) holds for all $d\geqslant 2$, as
needed. From (5.2), (5.12), (5.11) and the discussion surrounding (5.11), we
see that our objective for §5.2 has been accomplished. In other words, we have
shown that for all $p$ sufficiently small, the minimum positive fixed point
$w^{\prime}$ of $f_{p}$ is strictly less than the unique fixed point
$\alpha_{p}$ of $g_{p}$, and therefore, by (5.10), $B_{p}$ is not ergodic for
such values of $p$.

###  5.3. Showing that $B_{p}$ is ergodic when $p\geqslant p_{c}$

The argument in §5.3 comprises two parts.

  1. (i)

The first part, addressed in §5.3.1, ensures that (4.3) holds, i.e.

$\lim_{n\rightarrow\infty}\max_{\sigma:L_{n}\rightarrow\mathcal{S}}\mu_{B_{p}}(\sigma)[D]=0,\text{
for all }p\geqslant p_{c},$

where $p_{c}$ is as defined in (1.2), and recall that the alphabet
$\mathcal{S}=\\{W,D,L\\}$ for our PTAs. In other words, the probability that
the root $\phi$ gets assigned the state $D$, starting from _any_ boundary
configuration on $L_{n}$ and iteratively applying $B_{p}$ up the generations,
converges to $0$ as $n\rightarrow\infty$. This is verified by showing that the
function $f_{p}$ has a unique fixed point in $(0,1)$, and then using Lemma
5.2, Lemma 5.1, (5.1.2) and finally, (4.1).

  2. (ii)

The second part, addressed in §5.3.2, ensures that the probability that the
root $\phi$ is assigned the state $W$ (likewise, the state $L$), starting from
_any_ boundary configuration on $L_{n}$ and iteratively applying $B_{p}$ up
the generations, converges, as $n\rightarrow\infty$, to a limit that has no
dependence on the boundary configuration we begin with. The key tool to verify
this is Lemma 4.2.

####  5.3.1. The limiting probability of state $D$ at the root, starting from
any boundary configuration on $L_{n}$, as $n\rightarrow\infty$

We begin by recalling that $f_{p}(0)=p>0$, so that $y=f_{p}(x)$ lies above the
line $y=x$ at $x=0$. Consequently, the first time that they intersect, the
curve $y=f_{p}(x)$ must be traveling from _above_ $y=x$ to _beneath_ $y=x$,
thus implying that the slope of $y=f_{p}(x)$ at the minimum positive fixed
point $w^{\prime}$ (recall Lemma 5.1) must be less than or equal to the slope
of $y=x$, which is $1$.

Suppose, now, the function $f_{p}$ has multiple fixed points in $(0,1)$. Let
$\beta$ be a fixed point of $f_{p}$ with $w^{\prime}<\beta<1$, such that no
fixed point of $f_{p}$ lies in the sub-interval $(w^{\prime},\beta)$. From the
previous paragraph, it is evident, then, that the curve $y=f_{p}(x)$ lies
beneath the line $y=x$ throughout the sub-interval $(w^{\prime},\beta)$, and
it starts traveling from _beneath_ $y=x$ to _above_ $y=x$ at $x=\beta$.
Consequently, the slope of $y=f_{p}(x)$ at $x=\beta$ must be at least as large
as the slope of $y=x$, which is $1$.

From the above discussion, it is evident that if the slope $f^{\prime}_{p}(x)$
of $y=f_{p}(x)$ remains bounded above by $1$ throughout the interval $[0,1]$,
then $f_{p}$ cannot have multiple fixed points in $[0,1]$ (it is important to
note here that $f_{p}(x)$ is a polynomial of degree $d^{2}$, where $d\geqslant
2$, and its graph does not coincide with the line $y=x$ for _any_ non-
degenerate sub-interval of $[0,1]$).

Our goal, now, is to show that $f^{\prime}_{p}(x)$ remains bounded above by
$1$ for all $x\in[0,1]$, for each $p\geqslant p_{c}$, where $p_{c}$ is as
defined in (1.2). We consider the function $t(x)=x-(1-p)x^{d+1}$, for
$x\in[0,1]$. Then

$\displaystyle t^{\prime}(x)=1-(1-p)(d+1)x^{d}>0\Longleftrightarrow
x<(1-p)^{-1/d}(d+1)^{-1/d}.$

This tells us that the function $t(x)$ is strictly increasing for $0\leqslant
x\leqslant(1-p)^{-1/d}(d+1)^{-1/d}$ and strictly decreasing for
$(1-p)^{-1/d}(d+1)^{-1/d}\leqslant x\leqslant 1$. Consequently, the maximum of
$t(x)$, for $x\in[0,1]$, is attained at $(1-p)^{-1/d}(d+1)^{-1/d}$, and this
maximum value is given by

$\max\\{t(x):x\in[0,1]\\}=t\left((1-p)^{-1/d}(d+1)^{-1/d}\right)=(1-p)^{-1/d}(d+1)^{-\frac{d+1}{d}}d.$

Substituting the above in (5.6), we see that

$\displaystyle f^{\prime}_{p}(x)$
$\displaystyle\leqslant\max\left\\{f^{\prime}_{p}(x):x\in[0,1]\right\\}=(1-p)^{2}d^{2}\left[(1-p)^{-1/d}(d+1)^{-\frac{d+1}{d}}d\right]^{d-1}$
$\displaystyle=(1-p)^{\frac{d+1}{d}}d^{d+1}(d+1)^{-\frac{(d+1)(d-1)}{d}}=\left[(1-p)^{\frac{1}{d}}d(d+1)^{-\frac{d-1}{d}}\right]^{d+1},$

and this is less than or equal to $1$ if and only if we have

$\displaystyle(1-p)^{\frac{1}{d}}d(d+1)^{-\frac{d-1}{d}}\leqslant
1\Longleftrightarrow(1-p)\leqslant d^{-d}(d+1)^{d-1}\Longleftrightarrow
p\geqslant 1-\frac{(d+1)^{d-1}}{d^{d}},$

thus showing, from (1.2), that we have $f^{\prime}_{p}(x)\leqslant 1$ for all
$x\in[0,1]$, for every $p\geqslant p_{c}$. Consequently, via the argument
above, we conclude that $f_{p}$ has a unique fixed point in $(0,1)$. This
conclusion, via Lemma 5.2, Lemma 5.1 and (5.1.2), leads to
$\lim_{n\rightarrow\infty}\mu_{B_{p}}\left(\delta_{D}^{n}\right)[D]=0$. This,
in turn, by (4.1), yields
$\lim_{n\rightarrow\infty}\max_{\sigma:L_{n}\rightarrow\mathcal{S}}\mu_{B_{p}}(\sigma)[D]=0$,
thus satisfying (4.3).

####  5.3.2. The limiting probabilities of states $W$ and $L$ at the root,
starting from any boundary configuration on $L_{n}$, as $n\rightarrow\infty$

Recall that $\delta_{W}^{n}$ denotes the boundary configuration that assigns
the state $W$ to each vertex of $L_{n}$, and $\delta_{L}^{n}$ the boundary
configuration that assigns the state $L$ to each vertex of $L_{n}$. If we now
consider _any_ boundary configuration $\sigma$ on $L_{n}$, then we have
$\delta_{W}^{n}\preceq\sigma\preceq\delta_{L}^{n}$, where $\preceq$ indicates
the coordinate-wise partial order induced by the total order $W\prec D\prec
L$.

From Lemma 4.2 and the above observation, we conclude that

$\displaystyle\mu_{B_{p}}(\delta_{W}^{n})\preceq\mu_{B_{p}}(\sigma)\preceq\mu_{B_{p}}(\delta_{L}^{n})\text{
when }n\text{ is even},$
$\displaystyle\mu_{B_{p}}(\delta_{L}^{n})\preceq\mu_{B_{p}}(\sigma)\preceq\mu_{B_{p}}(\delta_{W}^{n})\text{
when }n\text{ is odd}.$

This, in turn, yields the following set of inequalities:

$\displaystyle\begin{split}&\mu_{B_{p}}(\delta_{W}^{n})[L]\leqslant\mu_{B_{p}}(\sigma)[L]\leqslant\mu_{B_{p}}(\delta_{L}^{n})[L]\text{
when }n\text{ is even},\\\
&\mu_{B_{p}}(\delta_{L}^{n})[L]\leqslant\mu_{B_{p}}(\sigma)[L]\leqslant\mu_{B_{p}}(\delta_{W}^{n})[L]\text{
when }n\text{ is odd};\end{split}$
$\displaystyle\begin{split}&\mu_{B_{p}}(\delta_{L}^{n})[W]\leqslant\mu_{B_{p}}(\sigma)[W]\leqslant\mu_{B_{p}}(\delta_{W}^{n})[W]\text{
when }n\text{ is even},\\\
&\mu_{B_{p}}(\delta_{W}^{n})[W]\leqslant\mu_{B_{p}}(\sigma)[W]\leqslant\mu_{B_{p}}(\delta_{L}^{n})[W]\text{
when }n\text{ is odd}.\end{split}$

Recall from §2.2 the relation between the total variation metric and the
$L_{1}$ metric on the space of measures defined on a countable set endowed
with its power set as the $\sigma$-field. From the above inequalities and
(4.1), we have

$\displaystyle\sup_{\sigma,\tau:L_{n}\rightarrow\mathcal{S}}\left|\left|\mu_{A}(\sigma)-\mu_{A}(\tau)\right|\right|_{\operatorname{TV}}$
$\displaystyle\leqslant\frac{1}{2}\sup_{\sigma,\tau:L_{n}\rightarrow\mathcal{S}}\left|\mu_{A}(\sigma)[L]-\mu_{A}(\tau)[L]\right|+\frac{1}{2}\sup_{\sigma,\tau:L_{n}\rightarrow\mathcal{S}}\left|\mu_{A}(\sigma)[W]-\mu_{A}(\tau)[W]\right|$
$\displaystyle+\frac{1}{2}\sup_{\sigma,\tau:L_{n}\rightarrow\mathcal{S}}\left|\mu_{A}(\sigma)[D]-\mu_{A}(\tau)[D]\right|$
$\displaystyle=\frac{1}{2}\left|\mu_{B_{p}}(\delta_{L}^{n})[L]-\mu_{B_{p}}(\delta_{W}^{n})[L]\right|+\frac{1}{2}\left|\mu_{B_{p}}(\delta_{W}^{n})[W]-\mu_{B_{p}}(\delta_{L}^{n})[W]\right|$
$\displaystyle+\sup_{\sigma:L_{n}\rightarrow\mathcal{S}}\left|\mu_{A}(\sigma)[D]\right|$
$\displaystyle=\frac{1}{2}\left|\mu_{B_{p}}(\delta_{L}^{n})[L]-\mu_{B_{p}}(\delta_{W}^{n})[L]\right|+\frac{1}{2}\left|\mu_{B_{p}}(\delta_{W}^{n})[W]-\mu_{B_{p}}(\delta_{L}^{n})[W]\right|$
$\displaystyle+\mu_{B_{p}}(\delta_{D}^{n})[D].$ (5.18)

From §5.3.1, the last of the above three summands approaches $0$ in the limit
as $n\rightarrow\infty$, when $p\geqslant p_{c}$. Consequently, if we can
show, for $p\geqslant p_{c}$, that

$\lim_{n\rightarrow\infty}\mu_{B_{p}}(\delta_{W}^{n})[W]\text{ and
}\lim_{n\rightarrow\infty}\mu_{B_{p}}(\delta_{L}^{n})[W]\text{ exist and are
equal},$ (5.19)

then, noting that
$\mu_{B_{p}}(\delta_{W}^{n})[L]=1-\mu_{B_{p}}(\delta_{W}^{n})[W]$ and
$\mu_{B_{p}}(\delta_{L}^{n})[L]=1-\mu_{B_{p}}(\delta_{L}^{n})[W]$, and taking
the limit supremum of the expression on each side of (5.18) as
$n\rightarrow\infty$, we conclude that (2.3) holds, and hence $B_{p}$ is
ergodic for $p\geqslant p_{c}$.

Let us begin the proof of (5.19) by noting that a vertex that has _all_ its
children in state $W$ must itself be in state $L$ with probability $1$, as
guaranteed by (3.1). Consequently, for every $n\in\mathbb{N}$ with $n\geqslant
2$, the law $\mu_{B_{p}}(\delta_{W}^{n})$ is the same as
$\mu_{B_{p}}(\delta_{L}^{n-1})$. Therefore, we have
$\mu_{B_{p}}(\delta_{W}^{n})[W]=\mu_{B_{p}}(\delta_{L}^{n-1})[W]$ for every
$n\in\mathbb{N}$ with $n\geqslant 2$. Thus, (5.19) is proved if we simply show
that the limit

$\lim_{n\rightarrow\infty}\mu_{B_{p}}(\delta_{L}^{n})[W]\text{ exists,}$
(5.20)

since this guarantees that
$\lim_{n\rightarrow\infty}\mu_{B_{p}}(\delta_{W}^{n})[W]$ exists as well, and
equals the limit in (5.20).

Let $q_{n}=\mu_{B_{p}}(\delta_{L}^{n})[W]$, and we set $q_{0}=0$. We also keep
in mind that $\mu_{B_{p}}(\delta_{L}^{n})[D]=0$ for every $n$. Adopting an
argument similar to that used in §5.1 to arrive at (5.1) and (5.2), we note
that if the root $\phi$ has children $u_{1},\ldots,u_{d}$, then the (random)
states of these children, starting from $\delta_{L}^{n}$ on $L_{n}$, are
distributed as i.i.d. $\mu_{B_{p}}(\delta_{L}^{n-1})$. Therefore, for each
$n\in\mathbb{N}$, using (3.1), we have,

$\displaystyle q_{n}$
$\displaystyle=\sum_{i=0}^{d}(1-p^{i})\operatorname{\mathbf{P}}\left[i\text{
vertices out of }u_{1},\ldots,u_{d}\text{ are in state }L\right]$
$\displaystyle=1-\sum_{i=0}^{d}p^{i}{d\choose
i}(1-q_{n-1})^{i}q_{n-1}^{d-i}=1-[p+(1-p)q_{n-1}]^{d}.$ (5.21)

Letting $q^{\prime}_{n}=p+(1-p)q_{n}$ for each $n\in\mathbb{N}$, the above
equation gets transformed as follows:

$\displaystyle
p+(1-p)q_{n}=p+(1-p)-(1-p)[p+(1-p)q_{n-1}]^{d}\Longleftrightarrow
q^{\prime}_{n}=1-(1-p){q^{\prime}_{n-1}}^{d}=g_{p}(q^{\prime}_{n-1}),$ (5.22)

where $g_{p}$ is as defined in (5.1.2). Iterating the recurrence in (5.22), we
obtain
$q^{\prime}_{n+1}=g_{p}^{(2)}(q^{\prime}_{n-1})=f_{p}(q^{\prime}_{n-1})$ for
all $n\in\mathbb{N}$, with $f_{p}$ as defined in (5.4).

It would seem, at this point, that the proof of the fact that the limit
$q^{\prime}=\lim_{n\rightarrow\infty}q^{\prime}_{n}$ exists goes through
_exactly_ the same as we argue the existence of the limit
$w^{\prime}=\lim_{n\rightarrow\infty}w^{\prime}_{n}$ from (5.3) onward, but
that is not _quite_ the case. We need to make use of the fact that $p\geqslant
p_{c}$, and hence the function $f_{p}$ has a _unique_ fixed point, which is
the same as the fixed point $\alpha_{p}$ of $g_{p}$, in $[0,1]$.

Notice that $q_{0}=0$, so that the argument for showing that
$\lim_{n\rightarrow\infty}q^{\prime}_{2n}$ exists and equals the minimum
positive fixed point $w^{\prime}$ of $f_{p}$, goes through verbatim as the
argument, outlined in §5.1.1, for showing that
$\lim_{n\rightarrow\infty}w^{\prime}_{2n}$ exists and equals $w^{\prime}$, the
minimum positive fixed point of $f_{p}$. We now apply (5.22) to obtain
$q^{\prime}_{2n+1}=g_{p}(q^{\prime}_{2n})$, so that upon taking the limits of
both sides as $n\rightarrow\infty$ and using the fact that $g_{p}$ is a
continuous function, we obtain

$\lim_{n\rightarrow\infty}q^{\prime}_{2n+1}=\lim_{n\rightarrow\infty}g_{p}(q^{\prime}_{2n})=g_{p}(w^{\prime}).$

Note that, had $f_{p}$ not had a unique fixed point in $[0,1]$, $w^{\prime}$
and $g_{p}(w^{\prime})$ would, respectively, be the smallest and the largest
positive fixed points of $f_{p}$ in $[0,1]$ (see the proof of Lemma 5.2). In
that case, $w^{\prime}\neq g_{p}(w^{\prime})$, so that the subsequences
$\\{q^{\prime}_{2n}\\}_{n\in\mathbb{N}_{0}}$ and
$\\{q^{\prime}_{2n+1}\\}_{n\in\mathbb{N}_{0}}$ would converge to two different
limits. Since we consider $p\geqslant p_{c}$, however, the function $f_{p}$
has, indeed, a unique fixed point in $[0,1]$, which is the fixed point
$\alpha_{p}$ of $g_{p}$, and this is why both $w^{\prime}$ and
$g_{p}(w^{\prime})$ equals $\alpha_{p}$. This completes the proof of the fact
that $q^{\prime}=\lim_{n\rightarrow\infty}q^{\prime}_{n}$ exists and equals
$\alpha_{p}$. This implies that
$\lim_{n\rightarrow\infty}q_{n}=p+(1-p)q^{\prime}$ exists as well, thus
proving (5.20).

###  5.4. Proving that the phase transition happens at $p=p_{c}$

The principal idea guiding the argument in §5.4 is as follows:

  1. (i)

We show that, for every $p\in(0,1)$, there exists $x_{p}\in(0,1)$ such that
the function $f_{p}$ defined in (5.4) is strictly convex on $[0,x_{p})$ and
strictly concave on $(x_{p},1]$. Thus, there can be at most two points of
intersection between the curve $y=f_{p}(x)$ and the line $y=x$ inside the sub-
interval $[0,x_{p}]$, and at most two again in the sub-interval $[x_{p},1]$.
Hence, there are at most four fixed points of $f_{p}$ inside $[0,1]$.

  2. (ii)

From the proof of Lemma 5.2, for any fixed point $\beta$ of $f_{p}$, we
conclude that  (a) either $\beta$ equals the fixed point $\alpha_{p}$ of
$g_{p}$,  (b) or else, $g_{p}(\beta)$ is _another_ fixed point of $f_{p}$, so
that $\beta$ and $g_{p}(\beta)$ yield a pair of fixed points of $f_{p}$.  This
allows us to conclude that $f_{p}$ must _always_ have an _odd_ number of fixed
point in $[0,1]$, irrespective of the value of $p$. Moreover, the proof of
Lemma 5.2 reveals that for every fixed point $\beta$ of $f_{p}$ in $[0,1]$
with $\beta\neq\alpha_{p}$, we either have $\beta<\alpha_{p}<g_{p}(\beta)$ or
$g_{p}(\beta)<\alpha_{p}<\beta$. Therefore, whenever there are multiple, and
hence an odd number of, fixed points of $f_{p}$ in $[0,1]$, the fixed point in
the middle is going to be $\alpha_{p}$.

  3. (iii)

Utilizing the conclusions drawn above, we see that $f_{p}$ either has a single
fixed point or precisely three fixed points. From §5.2 and §5.3, it is evident
that there exists some $p_{0}\in(0,1)$ such that $f_{p}$ has three fixed
points in $[0,1]$ when $p<p_{0}$, and $f_{p}$ has a unique fixed point in
$[0,1]$ when $p\geqslant p_{c}$, with $p_{c}$ as defined in (1.2), and
$p_{0}\leqslant p_{c}$, evidently.

  4. (iv)

Consequently, there must exist some $p_{1}$ with $p_{0}\leqslant
p_{1}\leqslant p_{c}$, and associated with it, a $p^{\prime}_{1}$ with
$p_{1}<p^{\prime}_{1}\leqslant 1$, such that $f_{p}$ has precisely three fixed
points in $[0,1]$ for $p<p_{1}$, and a unique fixed point in $[0,1]$ for
$p_{1}<p\leqslant p^{\prime}_{1}$.

We now examine what happens at $p_{1}$. From the argument outlined so far, we
know that $f_{p}$ cannot have precisely two fixed points in $[0,1]$ for
$p=p_{1}$. We show that, in fact, as $p$ approaches $p_{1}$ from the left
(i.e. through values less than $p_{1}$), the smallest and the largest fixed
points come closer and closer to the fixed point in the middle (which is
$\alpha_{p}$, as argued in (ii)), and eventually, the three coincide at
$p=p_{1}$. This, in turn, aids us in showing that $p_{1}$, in fact, equals
$p_{c}$.

Having outlined what we intend to show, we are now ready to embark on working
out the details involved. Note that there is no further need to justify (ii),
(iii) and the first paragraph of (iv).

####  5.4.1. Convexity / concavity properties of $f_{p}$

From (5.6), we obtain

$\displaystyle f^{\prime\prime}_{p}(x)$
$\displaystyle=(1-p)^{2}d^{2}(d-1)\left[x\left\\{1-(1-p)x^{d}\right\\}\right]^{d-2}\left[1-(1-p)(d+1)x^{d}\right],$

so that

$\displaystyle f^{\prime\prime}_{p}(x)>0\Longleftrightarrow x<x_{p},\text{
where }x_{p}=(1-p)^{-1/d}(d+1)^{-1/d}.$ (5.23)

This tells us that $f_{p}$ is strictly convex on $[0,x_{p})$ and strictly
concave on $(x_{p},1]$, as claimed above in (i).

####  5.4.2. Analyzing the behaviour of the fixed points around $p_{1}$, where
$p_{1}$ is as in (iv)

The objective in §5.4.2 is to understand the positions of the smallest and
largest fixed points of $f_{p}$ in $[0,1]$ (whenever $f_{p}$ does not have a
unique fixed point in $[0,1]$) relative to $x_{p}$ (recall from (ii) and (iii)
that whenever $f_{p}$ does not have a unique fixed point in $[0,1]$, it has
precisely three fixed points in $[0,1]$, the middle one of which is
$\alpha_{p}$).

We begin by finding the value of $\alpha_{p}$ at $p=p_{c}$. From (5.1.2),
(1.2) and (5.23), we obtain

$\displaystyle
g_{p_{c}}(x_{p_{c}})=1-(1-p_{c})\left\\{(1-p_{c})^{-1/d}(d+1)^{-1/d}\right\\}^{d}=\frac{d}{d+1},$

whereas

$\displaystyle
x_{p_{c}}=(1-p_{c})^{-1/d}(d+1)^{-1/d}=\frac{(d+1)^{-\frac{d-1}{d}}}{d^{-1}}\cdot(d+1)^{-1/d}=\frac{d}{d+1},$

thus showing that $g_{p_{c}}(x_{p_{c}})=x_{p_{c}}$, so that
$\alpha_{p_{c}}=x_{p_{c}}$ is the unique fixed point of $g_{p}$ in $[0,1]$.
Moreover, in §5.3, we have proved that $B_{p}$ is ergodic for $p\geqslant
p_{c}$ and hence for $p=p_{c}$, so that Lemma 5.2 tells us that $f_{p_{c}}$
has a unique fixed point, which is $\alpha_{p_{c}}=x_{p_{c}}$.

Having made the observations above regarding $p=p_{c}$, we now focus on
$p\in(0,1)\setminus\\{p_{c}\\}$ – henceforth, for the sake of brevity, we
simply denote this subset of values of $p$ by the phrase $p\neq p_{c}$.

Since $f_{p}(0)=p>0$ (since $p\in(0,1)$) and Lemma 8.1, stated and proved in
§8.2 of the Appendix (§8), tells us that $f_{p}(x_{p})<x_{p}$ for every $p\neq
p_{c}$, we conclude that there exists at least one point of intersection
inside the interval $(0,x_{p})$ between the curve $y=f_{p}(x)$ and the line
$y=x$, for every $p\neq p_{c}$. Since $f_{p}$ is strictly convex on
$[0,x_{p})$ and $f_{p}(x_{p})<x_{p}$ whereas $f_{p}(0)>0$, there is actually
_precisely one_ point of intersection in the interval $(0,x_{p})$ between
$y=f_{p}(x)$ and $y=x$.

The above paragraph leads to the following conclusions:

  1. (i)

when $f_{p}$ has a unique fixed point, $\alpha_{p}$, in $[0,1]$, we have
$\alpha_{p}\in(0,x_{p})$,

  2. (ii)

the smallest positive fixed point of $f_{p}$ lies in the sub-interval
$(0,x_{p})$, for every $p\neq p_{c}$,

  3. (iii)

_no other_ fixed point of $f_{p}$ lies in the sub-interval $(0,x_{p})$, which
means that when $f_{p}$ has three fixed points, both $\alpha_{p}$ and the
largest fixed point of $f_{p}$ (in $[0,1]$) belong to the sub-interval
$(x_{p},1)$.

In what follows, we denote by $\alpha_{1,p}$ the smallest positive fixed
point, and $\alpha_{2,p}$ the largest positive fixed point, of $f_{p}$ in
$[0,1]$, when $f_{p}$ has multiple fixed points in $[0,1]$. The above
conclusions reveal that, in this case,

$\alpha_{1,p}<x_{p}<\alpha_{p}<\alpha_{2,p}.$ (5.24)

Our next task is to understand how the distances $x_{p}-\alpha_{1,p}$ and
$\alpha_{2,p}-x_{p}$ vary as the number of fixed points of $f_{p}$ in $[0,1]$
vary with the parameter $p$. To begin with, we ensure that these differences
are continuous functions of $p$. From (5.23), it is clear that $x_{p}$ is a
continuous function of $p$. We now ensure, using the implicit function
theorem, that both $\alpha_{1,p}$ and $\alpha_{2,p}$ are differentiable with
respect to $p$, and hence are also continuous functions of $p$.

For the sake of this paragraph, we consider only those values of $p$ for which
$f_{p}$ has three fixed points in $[0,1]$. Recall from (5.4) the definition of
$f_{p}$. We rewrite this as a function of two variables, as follows:

$f(p,x)=1-(1-p)[1-(1-p)x^{d}]^{d},\text{ for }(p,x)\in(0,1)\times[0,1].$

Then $f(p,\alpha_{1,p})=f(p,\alpha_{2,p})=0$. Note that (already known from
(5.6))

$\frac{\partial}{\partial
x}f(p,x)=(1-p)^{2}d^{2}x^{d-1}[1-(1-p)x^{d}]^{d-1}\neq 0\text{ at
}x=\alpha_{1,p}\text{ and }x=\alpha_{2,p},$

so that for each such $p$, by the implicit function theorem, there exist open
subsets $U_{1,p}$ and $U_{2,p}$ of $(0,1)\times[0,1]$, and open sets $W_{1,p}$
and $W_{2,p}$ of $(0,1)$ such that

  1. (i)

$\alpha_{1,p}\in W_{1,p}$ and $\alpha_{2,p}\in W_{2,p}$,

  2. (ii)

$(p,\alpha_{1,p})\in U_{1,p}$ and $(p,\alpha_{2,p})\in U_{2,p}$,

  3. (iii)

for every $p^{\prime}\in W_{1,p}$, there exists a unique
$\gamma_{1}(p^{\prime})$, with $(p^{\prime},\gamma_{1}(p^{\prime}))\in
W_{1,p}$, such that $f\left(p^{\prime},\gamma_{1}(p^{\prime})\right)=0$ and
$\gamma_{1}(p^{\prime})$ is a continuously differentiable function of
$p^{\prime}$ in $W_{1,p}$,

  4. (iv)

for every $p^{\prime}\in W_{2,p}$, there exists a unique
$\gamma_{2}(p^{\prime})$, with $(p^{\prime},\gamma_{2}(p^{\prime}))\in
W_{2,p}$, such that $f\left(p^{\prime},\gamma_{2}(p^{\prime})\right)=0$ and
$\gamma_{2}(p^{\prime})$ is a continuously differentiable function of
$p^{\prime}$ in $W_{2,p}$.

Clearly, $\gamma_{1}(p^{\prime})=\alpha_{1,p^{\prime}}$ for each
$p^{\prime}\in W_{1,p}$, and $\gamma_{2}(p^{\prime})=\alpha_{2,p^{\prime}}$
for each $p^{\prime}\in W_{2,p}$. This establishes the desired
differentiability, and hence continuity, of the functions $\alpha_{1,p}$ and
$\alpha_{2,p}$ with respect to $p$.

Let us now come back to the argument that we began in (iv). It is clear, from
how we have defined $p_{1}$ in (iv), that $x_{p}-\alpha_{1,p}$ and
$\alpha_{2,p}-x_{p}$ are both strictly positive for $p<p_{1}$, whereas for
$p_{1}<p\leqslant p^{\prime}_{1}$, there is a unique fixed point $\alpha_{p}$
of $f_{p}$, lying inside the sub-interval $(0,x_{p})$. By the continuity
properties established above, this can only happen if

$\alpha_{2,p}-x_{p}\rightarrow 0\text{ as }p\rightarrow p_{1}\text{ from the
left}.$ (5.25)

Due to (5.24), the above automatically ensures that $\alpha_{p}-x_{p}$ also
approaches $0$ as $p\rightarrow p_{1}$ from the left.

We now claim that we must also have

$x_{p}-\alpha_{1,p}\rightarrow 0\text{ as }p\rightarrow p_{1}\text{ from the
left}.$ (5.26)

We prove this via an argument that leads to a contradiction. So, suppose that
the above does not happen. Using the continuity properties established above,
we then know that $x_{p}-\alpha_{1,p}$ approaches
$c:=x_{p_{1}}-\alpha_{1,p_{1}}>0$ as $p\rightarrow p_{1}$ from the left.
Combining this with (5.25), we see that at $p=p_{1}$, there are precisely two
distinct fixed points of $f_{p}$ – one of which is at $x_{p_{1}}$ itself, and
the other at $\alpha_{1,p_{1}}$. This contradicts our finding in (ii).
Consequently, our supposition must be erroneous, and we conclude that (5.26)
does hold.

Now, (5.25) and (5.26) together lead to the conclusion that at $p=p_{1}$, the
function $f_{p}$ has a unique fixed point, which is $x_{p_{1}}$ itself.
Therefore, $x_{p_{1}}=\alpha_{p_{1}}$. Using this conclusion, the definition
of $g_{p}$ from (5.1.2), the expression for $x_{p}$ from (5.23), and (1.2), we
obtain

$\displaystyle
1-(1-p_{1})\left\\{(1-p_{1})^{-1/d}(d+1)^{-1/d}\right\\}^{d}=(1-p_{1})^{-1/d}(d+1)^{-1/d}$
$\displaystyle\Longleftrightarrow\frac{d}{d+1}=(1-p_{1})^{-1/d}(d+1)^{-1/d}\Longleftrightarrow
p_{1}=1-\frac{(d+1)^{d-1}}{d^{d}}=p_{c}.$

This, along with what we have found in §5.3, allows us to conclude that

  1. (i)

the function $f_{p}$ has three fixed points in $[0,1]$ for all $0<p<p_{c}$,

  2. (ii)

and it has a unique fixed point in $[0,1]$ for all $p_{c}\leqslant p<1$.

Consequently, again taking into account what we have established in §5.3 and
using Lemma 5.2, we conclude that the PTA $B_{p}$ is ergodic if and only if
$p\geqslant p_{c}$, provided $p\in(0,1)$. This completes the proof of Theorem
3.1.

##  6\. Proof of the first assertion of Theorem 1.1

As asserted earlier, now that we have proved both Theorem 3.1 and 4.6, the
second assertion of Theorem 1.1 follows immediately. We are yet to prove,
however, the first assertion of Theorem 1.1. To this end, in addition to the
subsets $W$, $L$ and $D$ defined at the very start of §3, we define the
subsets $W_{n}$, $L_{n}$ and $D_{n}$, for each $n\in\mathbb{N}$, as follows. A
vertex $u$ of $T_{d}$ belongs to $W_{n}$ if the bond percolation game starting
at $u$ is won by the player who moves first, in less than $n$ rounds; $u$ is
in $L_{n}$ if the bond percolation game starting at $u$ is lost by the player
who moves first, in less than $n$ rounds; $u$ is in $D_{n}$ if the bond
percolation game starting at $u$ lasts for at least $n$ rounds. We set
$W_{0}=L_{0}=\emptyset$.

It is evident from the definitions above that $W_{n-1}\subset W_{n}$ and
$L_{n-1}\subset L_{n}$ for all $n\in\mathbb{N}$. Moreover, Lemma 8.2 ensures
that $W_{n}\uparrow W$ and $L_{n}\uparrow L$ as $n\rightarrow\infty$ (the
conclusion drawn from which is that if one of the two players can win a bond
percolation game, then they can guarantee to do so in a finite number of
rounds that can be determined in advance). If we let $w_{p}$ and $\ell_{p}$
denote the probabilities of $\phi$ being in $W$ and $L$ respectively, and
$w^{(n)}$ and $\ell^{(n)}$ the probabilities of $\phi$ being in $W_{n}$ and
$L_{n}$ respectively for every $n\in\mathbb{N}_{0}$, then the above implies
that $w^{(n)}\rightarrow w_{p}$ and $\ell^{(n)}\rightarrow\ell_{p}$ as
$n\rightarrow\infty$.

We now deduce the recurrence relations governing the sequences
$\\{w^{(n)}\\}_{n}$ and $\\{\ell^{(n)}\\}_{n}$. For $\phi$ to be in $W_{n}$,
it must have at least one child $u$ with $u\in L_{n-1}$ and $(\phi,u)$ a safe
edge. Thus

$\displaystyle w^{(n)}=\sum_{i=0}^{d}(1-p^{i}){d\choose
i}\left(\ell^{(n-1)}\right)^{i}\left(1-\ell^{(n)}\right)^{d-i}=1-\left[1-(1-p)\ell^{(n-1)}\right]^{d}.$
(6.1)

On the other hand, for $\phi$ to be in $L_{n}$,

  1. (i)

no child $u$ of $\phi$ can be such that $u\notin W$ and $(\phi,u)$ is safe,
because then the first player would either win or force the outcome to be a
draw,

  2. (ii)

no child $u$ of $\phi$ can be such that $u\in W\setminus W_{n-1}$ and
$(\phi,u)$ is safe, because then the first player, playing optimally, would
move the token to such a $u$, making sure that the game lasts at least $n$
rounds.

Thus, for every child $u$ of $\phi$ that is not in $W_{n-1}$, the edge
$(\phi,u)$ must be a trap. Thus

$\displaystyle\ell^{(n)}$ $\displaystyle=\sum_{i=0}^{d}p^{d-i}{d\choose
i}\left(w^{(n-1)}\right)^{i}\left(1-w^{(n-1)}\right)^{d-i}=\left[p+(1-p)w^{(n-1)}\right]^{d}.$
(6.2)

Notice the resemblance (6.1) and (6.2) bear with (5.1) and (5.2) – this is to
be expected since the stochastic update rule for $B_{p}$ is derived from the
recurrence relations arising out of the bond percolation game.

Setting ${w^{\prime}}^{(n)}=p+(1-p)w^{(n)}$, we deduce, just as we derived
(5.3), that ${w^{\prime}}^{(n+1)}=f_{p}({w^{\prime}}^{(n-1)})$, for
$n\in\mathbb{N}$, where $f_{p}$ is as defined in (5.4). Since $w^{(0)}=0$ and
hence ${w^{\prime}}^{(0)}=p$, we argue the same way as in §5.1.1, and Lemma
5.1, that $\lim_{n\rightarrow\infty}{w^{\prime}}^{(n)}$, which must equal
$p+(1-p)w_{p}$, exists and equals the minimum positive fixed point of $f_{p}$,
as claimed in Theorem 1.1.

##  7\. Analysis of the PTA $N_{p}$ arising out of the node percolation game

Recall from §3.2 the definition of the PTA $N_{p}$ representing the recurrence
relations arising out of the node percolation game. From Theorem 4.6, we know
that the node percolation game with the underlying parameter $p$ has
probability $0$ of resulting in a draw if and only if $N_{p}$ is ergodic, and
therefore, to establish Theorem 1.2, it suffices to prove Theorem 3.2. The
proof of Theorem 3.2 is nearly identical to that of Theorem 3.1, but in §7, we
accomplish two objectives:

  1. (i)

point out precisely where the argument for proving Theorem 3.2 differs from
the argument for proving Theorem 3.1;

  2. (ii)

justify why there is such a similarity in the analysis, by establishing a
connection between the bond percolation game and the node percolation game.

###  7.1. Outlining the proof of Theorem 3.2

As in §5.1, we consider the law $\mu_{N_{p}}(\delta_{D}^{n})$ of the (random)
state of the root $\phi$ of $T_{d}$ obtained by starting from the boundary
configuration $\delta_{D}^{n}$ on $L_{n}$ and applying $N_{p}$ iteratively up
the generations. We let $\beta_{n}=\mu_{N_{p}}(\delta_{D}^{n})[W]$ and
$\gamma_{n}=\mu_{N_{p}}(\delta_{D}^{n})[L]$, for each $n\in\mathbb{N}$, and we
set $\beta_{0}=\gamma_{0}=0$. The children $u_{1},\ldots,u_{d}$ of $\phi$ have
i.i.d. states governed by the common law $\mu_{N_{p}}(\delta_{D}^{n-1})$.
Using (3.2), (3.3) and (3.4), we have

$\displaystyle\beta_{n}=1-(1-\gamma_{n-1})^{d}+p(1-\gamma_{n-1})^{d}=1-(1-p)(1-\gamma_{n-1})^{d},$
(7.1)

and

$\displaystyle\gamma_{n}=(1-p)\beta_{n-1}^{d}.$ (7.2)

Combining (7.1) and (7.2), and using (5.4), we obtain

$\beta_{n+1}=1-(1-p)\left[1-(1-p)\beta_{n-1}^{d}\right]^{d}=f_{p}(\beta_{n-1}),$
(7.3)

Immediately, utilizing the analysis carried out in §5.1.1, we conclude that
the limit $\beta:=\lim_{n\rightarrow\infty}\beta_{n}$ exists and equals the
minimum positive fixed point of $f_{p}$.

Moreover, we note, from the conclusion drawn above and (7.2), that
$\gamma:=\lim_{n\rightarrow\infty}\gamma_{n}=(1-p)\beta^{d}$, so that the
limiting probability of the event that the root gets assigned the state $D$
under $\mu_{N_{p}}(\delta_{D}^{n})$ as $n\rightarrow\infty$ (which we are
interested in on account of (4.2) and (4.1), as a criterion for checking
ergodicity) is $0$ if and only if

$\beta+\gamma=1\Longleftrightarrow\beta=1-(1-p)\beta^{d}\Longleftrightarrow\beta=g_{p}(\beta),$
(7.4)

where $g_{p}$ is as defined in (5.1.2). Once again, we are back to nearly the
same criterion as (5.10), i.e. that $N_{p}$ is ergodic only if
$\beta=\alpha_{p}$, the unique fixed point of $g_{p}$ in $(0,1)$. It is now
straightforward to see that the analysis becomes identical to that carried out
in §5.1.2, §5.2, §5.3 and §5.4.

###  7.2. Establishing a connection between bond percolation games and node
percolation games

Modifying slightly the notation in §6, we let $w_{B,p}$ denote the probability
that the bond percolation game starting at the root $\phi$ is won by the first
player, and we let $w_{N,p}$ denote the probability that the node percolation
game starting at the root $\phi$ is won by the first player. Proceeding the
same way as in §6, with the recurrence relations now resembling (7.1) and
(7.2), we conclude that $w_{N,p}$ is the minimum positive fixed point of
$f_{p}$. From §6, we know that $p+(1-p)w_{B,p}$ is the minimum positive fixed
point of $f_{p}$. These together imply that $w_{N,p}=p+(1-p)w_{B,p}$, and this
equality is explained by the connection detailed below.

Fix an assignment $\omega$ of trap / safe labels to the _vertices_ of $T_{d}$.
For every vertex $v$ of $T_{d}$ except its root $\phi$, consider the directed
edge $(u,v)$ that connects the parent $u$ of $v$ to $v$. We now obtain an
assignment $\omega^{\prime}$ of trap / safe labels to the _edges_ of $T_{d}$
as follows:

  1. (i)

if $v$ has been marked a trap under $\omega$, we label the edge $(u,v)$ as a
trap under $\omega^{\prime}$,

  2. (ii)

if $v$ has been marked safe under $\omega$, we label the edge $(u,v)$ as safe
under $\omega^{\prime}$.

Likewise, given an assignment $\omega^{\prime}$ of trap / safe labels to the
_edges_ of $T_{d}$, the procedure above yields an assignment $\omega$ of trap
/ safe labels to the _vertices_ of $T_{d}\setminus\\{\phi\\}$.

Forgetting for an instant the label assigned to $\phi$ under $\omega$, we
immediately see the following: moving the token along an edge $(u,v)$ marked
as a trap under $\omega^{\prime}$, in the bond percolation game, is equivalent
to moving the token from $u$ to the vertex $v$ marked as a trap under
$\omega$, in the node percolation game. Likewise, moving the token along an
edge $(u,v)$ marked safe under $\omega^{\prime}$, in the bond percolation
game, is equivalent to moving the token from $u$ to the vertex $v$ marked safe
under $\omega$, in the node percolation game. Consequently:

  1. (i)

If $\omega^{\prime}$ is such that the bond percolation game starting at the
root $\phi$ is won by the first player, then the node percolation game
starting at $\phi$ is also won by the first player under $\omega$, as long as
$\phi$ has been marked safe under $\omega$. The probability of $\phi$ being
marked safe is $1-p$, whereas the probability of the event that the bond
percolation game starting at the root $\phi$ is won by the first player is
$w_{B,p}$.

  2. (ii)

The other possibility is that $\phi$ has been marked a trap under $\omega$, in
which case the first player wins immediately. The probability that $\phi$ is
marked a trap is $p$.

This concludes the explanation as to why $w_{N,p}$ equals $p+(1-p)w_{B,p}$.

##  8\. Appendix

###  8.1. Proofs of the lemmas concerning stochastic domination, from §4.1

###### Proof of Lemma 4.1.

Let us fix two (deterministic) assignments $\sigma$ and
$\operatorname{\widetilde{\sigma}}$ of states from $\mathcal{S}$ to the
children $u_{1},u_{2},\ldots,u_{d}$ of a vertex $u$ in $T_{d}$, such that
$\sigma(u_{i})\leqslant\operatorname{\widetilde{\sigma}}(u_{i})$ for each
$1\leqslant i\leqslant d$, according to the partial order $W<D>L$ on
$\mathcal{S}$. We also fix a (deterministic) assignment $\omega$ of trap /
safe labels to the edges $(u,u_{1}),\ldots,(u,u_{d})$.

Without loss of generality, we assume that
$\operatorname{\widetilde{\sigma}}(u_{\ell})=D$ for all
$1\leqslant\ell\leqslant k$, for some $1\leqslant k\leqslant d$. Suppose
$\sigma(u_{\ell})=D$ for all $1\leqslant\ell\leqslant j$ where $0\leqslant
j\leqslant k$. Further, we have
$\sigma(u_{\ell})=\operatorname{\widetilde{\sigma}}(u_{\ell})\in\\{W,L\\}$ for
all $k+1\leqslant\ell\leqslant d$. Finally, we assume that there exists some
$j\leqslant i\leqslant k$ such that $\sigma(u_{\ell})=L$ for all
$j+1\leqslant\ell\leqslant i$ and $\sigma(u_{\ell})=W$ for all
$i+1\leqslant\ell\leqslant k$. The only interesting case is where $j<k$, and
that is what we focus on.

We consider all the possible scenarios, below:

  1. (i)

Suppose there exists some $k+1\leqslant\ell\leqslant d$ such that
$(u,u_{\ell})$ is safe under $\omega$, and
$\sigma(u_{\ell})=\operatorname{\widetilde{\sigma}}(u_{\ell})=L$. In this
case, we have $B_{p}(\sigma,u)=B_{p}(\operatorname{\widetilde{\sigma}},u)=W$.

  2. (ii)

Suppose the above does not happen, but there exists some $\ell$, with
$j+1\leqslant\ell\leqslant i$, such that $(u,u_{\ell})$ is safe under
$\omega$. In this case, we have $B_{p}(\sigma,u)=W$ whereas
$B_{p}(\operatorname{\widetilde{\sigma}},u)=D$.

  3. (iii)

Suppose neither of the two possibilities mentioned above transpires, but there
exists some $1\leqslant\ell\leqslant j$ such that $(u,u_{\ell})$ is safe under
$\omega$. In this case, we have
$B_{p}(\sigma,u)=B_{p}(\operatorname{\widetilde{\sigma}},u)=D$.

  4. (iv)

Suppose none of the three possibilities above transpires, but there exists
some $i+1\leqslant\ell\leqslant k$ such that $(u,u_{\ell})$ is safe under
$\omega$. In this case, we have $B_{p}(\sigma,u)=L$ whereas
$B_{p}(\operatorname{\widetilde{\sigma}},u)=D$.

  5. (v)

If none of the four possibilities mentioned above transpires, then we have
$B_{p}(\sigma,u)=B_{p}(\operatorname{\widetilde{\sigma}},u)=L$.

The observations above reveal that $B_{p}(\sigma,u)$ is stochastically
dominated by $B_{p}(\operatorname{\widetilde{\sigma}},u)$ when we implement
the same assignment $\omega$ of trap / safe labels to the edges
$(u,u_{1}),\ldots,(u,u_{d})$ in both cases.

Given probability measures $\nu$ and $\operatorname{\widetilde{\nu}}$ as
stated in Lemma 4.1, we let $\sigma$ and $\operatorname{\widetilde{\sigma}}$
denote _coupled_ random assignments of states to $u_{1},\ldots,u_{d}$ such
that $\sigma$ follows $\nu$, $\operatorname{\widetilde{\sigma}}$ follows
$\operatorname{\widetilde{\nu}}$ and
$\sigma(u_{i})\leqslant\operatorname{\widetilde{\sigma}}(u_{i})$ for each
$1\leqslant i\leqslant d$ almost surely, then apply the conclusion drawn above
to complete the proof. ∎

###### Proof of Lemma 4.2.

As in the proof of Lemma 4.1, we fix assignments $\sigma$ and
$\operatorname{\widetilde{\sigma}}$ of states from $\mathcal{S}$ to the
children $u_{1},\ldots,u_{d}$ of $u$ such that
$\sigma(u_{\ell})\preceq\operatorname{\widetilde{\sigma}}(u_{\ell})$, for each
$1\leqslant\ell\leqslant d$, according to the total order $W\prec D\prec L$ on
$\mathcal{S}$. In fact, without loss of generality, we assume that

$\displaystyle\sigma(u_{\ell})=W\text{ for }1\leqslant\ell\leqslant
i,\sigma(u_{\ell})=D\text{ for }i+1\leqslant\ell\leqslant j\text{ and
}\sigma(u_{\ell})=L\text{ for }j+1\leqslant\ell\leqslant d,$

whereas

$\displaystyle\operatorname{\widetilde{\sigma}}(u_{\ell})=W\text{ for
}1\leqslant\ell\leqslant
i_{1},\operatorname{\widetilde{\sigma}}(u_{\ell})=D\text{ for
}i_{1}+1\leqslant\ell\leqslant
i_{2},\operatorname{\widetilde{\sigma}}(u_{\ell})=L\text{ for
}i_{2}+1\leqslant\ell\leqslant i,$
$\displaystyle\operatorname{\widetilde{\sigma}}(u_{\ell})=D\text{ for
}i+1\leqslant\ell\leqslant
j_{1},\operatorname{\widetilde{\sigma}}(u_{\ell})=L\text{ for
}j_{1}+1\leqslant\ell\leqslant
j,\operatorname{\widetilde{\sigma}}(u_{\ell})=L\text{ for
}j+1\leqslant\ell\leqslant d.$

The illustration in Figure 1 is intended to help the reader visualize.

Figure 1. Comparing the assignments $\sigma$ and
$\operatorname{\widetilde{\sigma}}$ in the proofs of Lemmas 4.2 and 4.4

We also fix an assignment $\omega$ of trap / safe labels to the edges
$(u,u_{1}),\ldots,(u,u_{d})$.

The following situations can arise:

  1. (i)

If there exists some $k$, with $j+1\leqslant k\leqslant d$, such that
$(u,u_{k})$ is safe under $\omega$, then
$B_{p}(\sigma,u)=B_{p}(\operatorname{\widetilde{\sigma}},u)=W$.

  2. (ii)

If $(u,u_{\ell})$ is a trap for every $j+1\leqslant\ell\leqslant d$ but there
exists some $k$, with $j_{1}+1\leqslant k\leqslant j$, such that $(u,u_{k})$
is safe under $\omega$, then $B_{p}(\sigma,u)=D$ whereas
$B_{p}(\operatorname{\widetilde{\sigma}},u)=W$.

  3. (iii)

If $(u,u_{\ell})$ is a trap for every $j_{1}+1\leqslant\ell\leqslant d$, but
there exists some $k_{1}$ with $i_{2}+1\leqslant k_{1}\leqslant i$ and some
$k_{2}$ with $i+1\leqslant k_{2}\leqslant j_{1}$ such that $(u,u_{k_{1}})$ and
$(u,u_{k_{2}})$ are both safe under $\omega$, then $B_{p}(\sigma,u)=D$ whereas
$B_{p}(\operatorname{\widetilde{\sigma}},u)=W$.

  4. (iv)

If $(u,u_{\ell})$ is a trap for every $j_{1}+1\leqslant\ell\leqslant d$ and
$i_{2}+1\leqslant\ell\leqslant i$, but there exists some $k$ with
$i+1\leqslant k\leqslant j$ such that $(u,u_{k})$ is safe under $\omega$, then
$B_{p}(\sigma,u)=B_{p}(\operatorname{\widetilde{\sigma}},u)=D$.

  5. (v)

If $(u,u_{\ell})$ is a trap for every $i+1\leqslant\ell\leqslant d$, but there
exists some $k$ with $i_{2}+1\leqslant k\leqslant i$ such that $(u,u_{k})$ is
safe under $\omega$, then $B_{p}(\sigma,u)=L$ whereas
$B_{p}(\operatorname{\widetilde{\sigma}},u)=W$.

  6. (vi)

If $(u,u_{\ell})$ is a trap for every $i_{2}+1\leqslant\ell\leqslant d$, but
there exists $k$ with $i_{1}+1\leqslant k\leqslant i_{2}$ such that
$(u,u_{k})$ is safe under $\omega$, then $B_{p}(\sigma,u)=L$ whereas
$B_{p}(\operatorname{\widetilde{\sigma}},u)=D$.

  7. (vii)

Finally, if $(u,u_{\ell})$ is a trap for every $i_{1}+1\leqslant\ell\leqslant
d$, then $B_{p}(\sigma,u)=B_{p}(\operatorname{\widetilde{\sigma}},u)=L$.

The observations above reveal that
$B_{p}(\operatorname{\widetilde{\sigma}},u)$ is stochastically dominated by
$B_{p}(\sigma,u)$ when we implement the same assignment $\omega$ of trap /
safe labels to the edges $(u,u_{1}),\ldots,(u,u_{d})$ in both cases. The rest
of the proof follows the same way as the proof of Lemma 4.1. ∎

###### Proof of Lemma 4.3.

The argument is along the same lines as the proof of Lemma 4.1. We fix
assignments $\sigma$ and $\operatorname{\widetilde{\sigma}}$ of states to the
children $u_{1},\ldots,u_{d}$ of $u$ such that
$\sigma(u_{i})\leqslant\operatorname{\widetilde{\sigma}}(u_{i})$ for each
$1\leqslant i\leqslant d$, according to the partial order $W<D>L$, and an
assignment $\omega$ of trap / safe labels to $u$ (i.e. $\omega$ simply
dictates if $u$ is a trap or not). Let
$\sigma(u_{\ell})=\operatorname{\widetilde{\sigma}}(u_{\ell})=L$ for all
$1\leqslant\ell\leqslant i$, let
$\sigma(u_{\ell})=\operatorname{\widetilde{\sigma}}(u_{\ell})=W$ for all
$i+1\leqslant\ell\leqslant j$, and let
$\operatorname{\widetilde{\sigma}}(u_{\ell})=D$ for all
$j+1\leqslant\ell\leqslant d$ (with $j\leqslant d-1$). We have the following
possibilities:

  1. (i)

If $u$ is a trap under $\omega$, then
$N_{p}(\sigma,u)=N_{p}(\operatorname{\widetilde{\sigma}},u)=W$.

  2. (ii)

If $u$ is safe, and $i\geqslant 1$, then
$N_{p}(\sigma,u)=N_{p}(\operatorname{\widetilde{\sigma}},u)=W$.

  3. (iii)

If $u$ is safe, $i=0$ and there exists at least one $j+1\leqslant\ell\leqslant
d$ such that $\sigma(u_{\ell})=L$. In this case, we have $N_{p}(\sigma,u)=W$
whereas $N_{p}(\operatorname{\widetilde{\sigma}},u)=D$.

  4. (iv)

Suppose $u$ is safe, there exists _no_ $1\leqslant\ell\leqslant d$ such that
$\sigma(u_{\ell})=L$ (which automatically means that there exists no
$1\leqslant\ell\leqslant d$ such that
$\operatorname{\widetilde{\sigma}}(u_{\ell})=L$, as well), and there exists
some $j+1\leqslant k\leqslant d$ such that $\sigma(u_{k})=D$. In this case,
$N_{p}(\sigma,u)=N_{p}(\operatorname{\widetilde{\sigma}},u)=D$.

  5. (v)

Suppose $u$ is safe, there exists _no_ $1\leqslant\ell\leqslant d$ such that
$\sigma(u_{\ell})=L$, there exists _no_ $j+1\leqslant\ell\leqslant d$ such
that $\sigma(u_{\ell})=D$. In this case, we have $N_{p}(\sigma,u)=L$ whereas
$N_{p}(\operatorname{\widetilde{\sigma}},u)=D$.

The above cases reveal that $N_{p}(\sigma,u)$ is stochastically dominated by
$N_{p}(\operatorname{\widetilde{\sigma}},u)$ when we apply the same assignment
$\omega$ of trap / safe labels to $u$. We now draw our desired conclusion the
same was as in the proof of Lemma 4.1. ∎

###### Proof of Lemma 4.4.

As in the proof of Lemma 4.2, we fix assignments $\sigma$ and
$\operatorname{\widetilde{\sigma}}$ of states from $\mathcal{S}$ to the
children $u_{1},\ldots,u_{d}$ of $u$ as illustrated in Figure 1. We also fix
the label $\omega$ indicating whether $u$ is a trap or not. We now consider
the following possibilities:

  1. (i)

If $u$ is a trap under $\omega$, then
$N_{p}(\sigma,u)=N_{p}(\operatorname{\widetilde{\sigma}},u)=W$.

  2. (ii)

If $u$ is safe under $\omega$ and $d>j$, then
$N_{p}(\sigma,u)=N_{p}(\operatorname{\widetilde{\sigma}},u)=W$.

  3. (iii)

If $u$ is safe under $\omega$, $d=j$ but $j-j_{1}=d-j_{1}\geqslant 1$, then
$N_{p}(\sigma,u)=D$ whereas $N_{p}(\operatorname{\widetilde{\sigma}},u)=W$.

  4. (iv)

If $u$ is safe under $\omega$ and $d=j_{1}$, but $j_{1}>i$ and $i>i_{2}$, then
$N_{p}(\sigma,u)=D$ whereas $N_{p}(\operatorname{\widetilde{\sigma}},u)=W$.

  5. (v)

If $u$ is safe under $\omega$, $d=j_{1}$ and $i=i_{2}$ but $j_{1}>i$, we have
$N_{p}(\sigma,u)=N_{p}(\operatorname{\widetilde{\sigma}},u)=D$.

  6. (vi)

If $u$ is safe under $\omega$ and $d=i$ but $i>i_{2}$, then
$N_{p}(\sigma,u)=L$ whereas $N_{p}(\operatorname{\widetilde{\sigma}},u)=W$.

  7. (vii)

If $u$ is safe under $\omega$ and $d=i_{2}$ but $i_{2}>i_{1}$, we have
$N_{p}(\sigma,u)=L$ whereas $N_{p}(\operatorname{\widetilde{\sigma}},u)=D$.

  8. (viii)

In all other cases, we have
$N_{p}(\sigma,u)=N_{p}(\operatorname{\widetilde{\sigma}},u)=L$.

The above cases reveal that $N_{p}(\sigma,u)$ is stochastically dominated by
$N_{p}(\operatorname{\widetilde{\sigma}},u)$ when we apply the same assignment
$\omega$ of trap / safe labels to $u$. We now draw our desired conclusion the
same was as in the proof of Lemma 4.1. ∎

###  8.2. Proofs of various claims made in §5.4

We begin with the following lemma:

######  Lemma 8.1.

For every $p\in(0,1)\setminus\\{p_{c}\\}$, we have $f_{p}(x_{p})<x_{p}$, for
$x_{p}$ as defined in (5.23) and $p_{c}$ as defined in (1.2). We have
$f_{p}(x_{p})=x_{p}$ at $p=p_{c}$.

###### Proof.

From (5.4) and (5.23), we get

$\displaystyle f_{p}(x_{p})$ $\displaystyle=1-\frac{(1-p)d^{d}}{(d+1)^{d}}.$

Let us consider the function

$a_{1}(p)=\frac{(1-p)d^{d}}{(d+1)^{d}}+(1-p)^{-1/d}(d+1)^{-1/d},\text{ for
}p\in(0,1).$

Then

$\displaystyle
a^{\prime}_{1}(p)=-\frac{d^{d}}{(d+1)^{d}}+\frac{1}{d}(1-p)^{-\frac{d+1}{d}}(d+1)^{-1/d}$

and this is strictly positive if and only if (using (1.2))

$\displaystyle\frac{1}{d}(1-p)^{-\frac{d+1}{d}}(d+1)^{-1/d}>\frac{d^{d}}{(d+1)^{d}}\Longleftrightarrow\frac{(d+1)^{d-1/d}}{d^{d+1}}>(1-p)^{\frac{d+1}{d}}$
$\displaystyle\Longleftrightarrow\frac{(d+1)^{\frac{(d-1)(d+1)}{d}}}{d^{d+1}}>(1-p)^{\frac{d+1}{d}}\Longleftrightarrow
p>1-\frac{(d+1)^{d-1}}{d^{d}}=p_{c}.$

Therefore, $a_{1}(p)$ is strictly decreasing for $0<p\leqslant p_{c}$ and
strictly increasing for $p_{c}<p<1$, so that its minimum value is attained at
$p=p_{c}$, and this minima equals

$a_{1}(p_{c})=\frac{(d+1)^{d-1}}{d^{d}}\cdot\frac{d^{d}}{(d+1)^{d}}+\frac{d}{(d+1)^{\frac{d-1}{d}}}\cdot(d+1)^{-1/d}=1.$

Consequently, $a_{1}(p)\geqslant 1$ for all $p\in(0,1)$, thus leading to
$f_{p}(x_{p})\leqslant x_{p}$ for all $p\in(0,1)$. In fact, the strict
inequality $f_{p}(x_{p})<x_{p}$ holds for all $p\neq p_{c}$. ∎

###  8.3. Proof of a compactness result from §6

Recall from §3 the definitions of $W$, $L$ and $D$, and from §6 the
definitions of $W_{n}$, $L_{n}$ and $D_{n}$ for $n\in\mathbb{N}_{0}$. Let
$\widetilde{W}=W\setminus\bigcup_{n=1}^{\infty}W_{n}$ and
$\widetilde{L}=W\setminus\bigcup_{n=1}^{\infty}L_{n}$. We state and prove a
lemma very similar to Proposition 7 of [20].

######  Lemma 8.2.

The sets $\widetilde{W}$ and $\widetilde{L}$ are both empty.

###### Proof.

Consider a vertex $u$ of $T_{d}$, with children $u_{1},u_{2},\ldots,u_{d}$.
For $u$ to be in $\widetilde{W}$, there must, first and foremost, be some
$u_{\ell}\in L$ with $(u,u_{\ell})$ a safe edge. If such a $u_{\ell}$ is in
$L_{n}$ for some $n\in\mathbb{N}$, then the first player, assumed to play
optimally, can move the token from $u$ to $u_{\ell}$, and thereby win the game
in less than $n+1$ rounds. In that case, $u$ would be in $W_{n+1}$, not in
$\widetilde{W}$. Thus, $u\in\widetilde{W}$ if and only if there exists some
$u_{\ell}$ in $\widetilde{L}$ with $(u,u_{\ell})$ safe, but no
$u_{\ell^{\prime}}$ such that simultaneously $u_{\ell^{\prime}}\in L_{n}$ for
some $n\in\mathbb{N}$ and $(u,u_{\ell^{\prime}})$ is safe. Also, in such a
case, the first player moves the token from $u$ to such a $u_{\ell}$.

For $u$ to be in $\widetilde{L}$, note that for every child
$u_{\ell^{\prime}}$ of $u$ with $(u,u_{\ell^{\prime}})$ safe, we must have
$u_{\ell^{\prime}}\in W$. If every such $u_{\ell^{\prime}}$ belongs to $W_{n}$
for some $n\in\mathbb{N}$, then the first player would be forced to lose the
game in less than $n+1$ rounds, and $u$ would be in $L_{n+1}$, not
$\widetilde{L}$. Thus, out of all $u_{\ell^{\prime}}$ for which
$(u,u_{\ell^{\prime}})$ is safe, there exists at least one $u_{\ell}$ that
belongs to $\widetilde{W}$. Again, under the assumption of optimal play, the
first player would move the token from $u$ to such a $u_{\ell}$.

The above reveals to us a pattern: for the root $\phi$ of $T_{d}$ to be in
$\widetilde{W}$, it must have at least one child, say $v_{1}$, that is in
$\widetilde{L}$, with $(\phi,v_{1})$ a safe edge, and to which the first
player moves the token. This, in turn, implies that $v_{1}$ has at least one
child $v_{2}$ that is in $\widetilde{W}$, with $(v_{1},v_{2})$ a safe edge, to
which the second player move the token, and so on we continue. We see that the
game continues indefinitely, as neither of the players is ever forced to move
the token along a trap edge. Consequently, this game results in a draw,
contradicting our supposition that $\phi\in\widetilde{W}$. Thus,
$\widetilde{W}=\emptyset$, and consequently, so is $\widetilde{L}$. ∎

## References

  * Aldous and Steele [2004] David Aldous and J Michael Steele.  The objective method: probabilistic combinatorial optimization and local weak convergence.  _Probability on discrete structures_ , pages 1–72, 2004.
  * Aldous and Bandyopadhyay [2005] David J Aldous and Antar Bandyopadhyay.  A survey of max-type recursive distributional equations.  _Annals of Applied Probability_ , 15(2):1047–1110, 2005.
  * Bandyopadhyay [2002] Antar Bandyopadhyay.  Bivariate uniqueness in the logistic recursive distributional equation.  2002\.
  * Bandyopadhyay [2004] Antar Bandyopadhyay.  Bivariate uniqueness and endogeny for the logistic recursive distributional equation.  _arXiv preprint math/0401389_ , 2004.
  * Bandyopadhyay [2006] Antar Bandyopadhyay.  A necessary and sufficient condition for the tail-triviality of a recursive tree process.  _Sankhyā: The Indian Journal of Statistics_ , pages 1–23, 2006\.
  * Bandyopadhyay [2011] Antar Bandyopadhyay.  Endogeny for the logistic recursive distributional equation.  _Zeitschrift für Analysis und ihre Anwendungen_ , 30(2):237–251, 2011.
  * Bandyopadhyay and Gamarnik [2008] Antar Bandyopadhyay and David Gamarnik.  Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models.  _Random Structures & Algorithms_, 33(4):452–479, 2008.
  * Bhasin et al. [2022a] Dhruv Bhasin, Sayar Karmakar, Moumanti Podder, and Souvik Roy.  On a class of probabilistic cellular automata with size-$3$ neighbourhood and their applications in percolation games.  _arXiv preprint arXiv:2208.11670_ , 2022a.
  * Bhasin et al. [2022b] Dhruv Bhasin, Sayar Karmakar, Moumanti Podder, and Souvik Roy.  Ergodicity of a generalized probabilistic cellular automaton with parity-based neighbourhoods.  _arXiv preprint arXiv:2212.01753_ , 2022b.
  * Bollobás and Riordan [2006] Béla Bollobás and Oliver Riordan.  _Percolation_.  Cambridge University Press, 2006.
  * Bresler et al. [2022] Guy Bresler, Chenghao Guo, and Yury Polyanskiy.  Linear programs with polynomial coefficients and applications to 1d cellular automata.  _arXiv preprint arXiv:2204.06357_ , 2022.
  * Brightwell and Winkler [2002] Graham R Brightwell and Peter Winkler.  Random colorings of a cayley tree.  _Contemporary combinatorics_ , 10:247–276, 2002.
  * Comon et al. [2008] Hubert Comon, Max Dauchet, Rémi Gilleron, Florent Jacquemard, Denis Lugiez, Christof Löding, Sophie Tison, and Marc Tommasi.  Tree automata techniques and applications, 2008.
  * Day and Falgas-Ravry [2021a] A Nicholas Day and Victor Falgas-Ravry.  Maker–breaker percolation games i: crossing grids.  _Combinatorics, Probability and Computing_ , 30(2):200–227, 2021a.
  * Day and Falgas-Ravry [2021b] A Nicholas Day and Victor Falgas-Ravry.  Maker-breaker percolation games ii: Escaping to infinity.  _Journal of Combinatorial Theory, Series B_ , 151:482–508, 2021b.
  * de Boer et al. [2023] David de Boer, Pjotr Buys, and Guus Regts.  Uniqueness of the gibbs measure for the 4-state anti-ferromagnetic potts model on the regular tree.  _Combinatorics, Probability and Computing_ , 32(1):158–182, 2023.
  * Dvořák et al. [2021] Vojtěch Dvořák, Adva Mond, and Victor Souza.  The maker-breaker percolation game on the square lattice.  _arXiv preprint arXiv:2105.12864_ , 2021.
  * Gécseg and Steinby [1984] Ferenc Gécseg and Magnus Steinby.  _Tree automata_ , volume 416.  Akadémiai Kiadó Budapest, 1984.
  * Grimmett [1999] Geoffrey Grimmett.  _What is percolation?_ Springer, 1999.
  * Holroyd and Martin [2021] Alexander E Holroyd and James B Martin.  Galton–watson games.  _Random Structures & Algorithms_, 59(4):495–521, 2021.
  * Holroyd et al. [2019] Alexander E Holroyd, Irène Marcovici, and James B Martin.  Percolation games, probabilistic cellular automata, and the hard-core model.  _Probability Theory and Related Fields_ , 174(3):1187–1217, 2019.
  * Javanmard et al. [2016] Adel Javanmard, Andrea Montanari, and Federico Ricci-Tersenghi.  Phase transitions in semidefinite relaxations.  _Proceedings of the National Academy of Sciences_ , 113(16):E2218–E2223, 2016.
  * Johnson et al. [2020] Tobias Johnson, Moumanti Podder, and Fiona Skerman.  Random tree recursions: Which fixed points correspond to tangible sets of trees?  _Random Structures & Algorithms_, 56(3):796–837, 2020.
  * Jonasson [2002] Johan Jonasson.  Uniqueness of uniform random colorings of regular trees.  _Statistics & Probability Letters_, 57(3):243–248, 2002.
  * Levin and Peres [2017] David A Levin and Yuval Peres.  _Markov chains and mixing times_ , volume 107.  American Mathematical Soc., 2017.
  * Lyons [1990] Russell Lyons.  Random walks and percolation on trees.  _The annals of Probability_ , 18(3):931–958, 1990\.
  * Lyons [1992] Russell Lyons.  Random walks, capacity and percolation on trees.  _The Annals of Probability_ , pages 2043–2088, 1992.
  * Podder and Bhasin [2022] Moumanti Podder and Dhruv Bhasin.  Combinatorial games on galton-watson trees involving several-generation-jump moves.  _arXiv preprint arXiv:2205.02124_ , 2022.
  * Podder and Spencer [2017] Moumanti Podder and Joel Spencer.  Galton-watson probability contraction.  _Electronic Communications in Probability_ , 22:1–16, 2017\.
  * Simon [2014] Barry Simon.  _The Statistical Mechanics of Lattice Gases, Volume I_ , volume 260\.  Princeton University Press, 2014.
  * Stauffer and Aharony [2018] Dietrich Stauffer and Ammon Aharony.  _Introduction to percolation theory_.  Taylor & Francis, 2018.
  * Toom [2001] André Toom.  Contours, convex sets, and cellular automata.  In _Text of a course at the 23-th Colloquium of Brazilian mathematicians. Translated from English into Portugues by Andréa Vanessa Rocha and Pedro Ferreira de Lima. IMPA, Rio de Janeiro_ , 2001.