# Critical parameter of the frog model on homogeneous trees with geometric
lifetime

Sandro Gallo  Departamento de Estatística, Universidade Federal de São Carlos
<EMAIL_ADDRESS>and  Caio Pena  Instituto Federal de São Paulo, Campus
Araraquara<EMAIL_ADDRESS>
###### Abstract.

We consider the frog model with geometric lifetime (parameter $1-p$) on
homogeneous trees of dimension $d$. In 2002, [1] proved that there exists a
critical lifetime parameter $p_{c}\in(0,1)$ above which infinitely many frogs
are activated with positive probability, and they gave lower and upper bounds
for $p_{c}$. Since then, the literature on this model focussed on refinements
of the upper bound. In the present paper we improve the bounds for $p_{c}$ _on
both sides_. We also provide a discussion comparing the bounds of the
literature and their proofs. Our proofs are based on coupling.

KEYWORDS: Frog models, Renewal theory, Multi-types branching processes,
Critical parameter.

AMS classification: Primary: 60K35, 05C81, Secondary: 60K05

SG was supported by FAPESP (Auxílio Regular: 2019/23439-4) and CP thanks
financial support of IFSP during the realization of his PhD

##  1\. Introduction

Frog models are simple models for propagation of information (or rumor, or
disease) through a graph: active (informed/ill) particles perform independent
random walks on the graph, activating (informing/infecting) frogs of the
visited vertices. This class of models seems to have been first introduced by
[10] under the name of _egg model_ : particles making independent simple
symmetric random walks on $\mathbb{Z}^{d}$ transform eggs of the visited
vertices into active particles. In our terminology, particles are frogs and
eggs (inactive particles) are inactive frogs.

The literature on frog models has grown very fast over the last two decades,
with variations depending on the lifetime of the frogs, the underlying graph
structure on which the frogs wander around, the type of random walk the frogs
perform, the initial number of frogs per vertex _etc…_ In the present paper we
stand in the line of [1] who considered the case where frogs have geometric
lifetime and make simple symmetric random walks, and we focus specifically on
homogeneous infinite trees.

More precisely, consider the homogeneous tree $\mathbb{T}_{d}$, that is, the
rooted tree in which each vertex has (is connected by edges to) $d+1$
neighbours. One frog is put at each vertex and all but the one of the root
start inactive. Active frogs perform simple symmetric random walks on
$\mathbb{T}_{d}$, for a geometric (parameter $1-p$) number of steps111The
geometric starts at $0$, that is, the probability to make $n\geq 0$ steps is
$(1-p)p^{n}$., activating the inactive frogs of the visited vertices. After
its geometric number of steps, the active frog “dies”: it remains inactive
forever. The process _survives_ if infinitely many frogs are activated.

For any $p\in[0,1]$ we denote the law of the process by $\mathbb{P}_{p}$.
Naturally, if $p=0$ then the frog of the root dies and
$\mathbb{P}_{p}(\text{survival})=0$, while on the other hand, if $p=1$, frogs
won’t die and $\mathbb{P}_{p}(\text{survival})=1$. Moreover, it is clear that
$\mathbb{P}_{p}(\text{survival})$ is non-decreasing in $p$, and we can define
the critical parameter for the model on $\mathbb{T}_{d}$ as

$p_{c}=p_{c}(d):=\inf\\{p\in[0,1]:\mathbb{P}_{p}(\text{survival})>0\\}.$

In the present paper we are interested in obtaining tight bounds for $p_{c}$,
as functions of $d$, so let us list rapidly the results of the literature
concerning this question. In their seminal paper in 2002, [1] proved that

$\frac{d+1}{2d+1}\leq p_{c}\leq\frac{d+1}{2d-2}\,.$ (1)

Three years later, [8] was dedicated to improve the upper bound to

$p_{c}\leq\frac{d+1}{2d}.$

It is only in 2018, with the paper of [5], that a new improvement of the upper
bound was obtained as a consequence of the study of a percolation model on
_oriented_ trees:

$p_{c}\leq\frac{(d+1)[(7d-1)-\sqrt{(7d-1)^{2}-14}]}{d(7d-1)^{2}-7d+2-d(7d-1)\sqrt{(7d-1)^{2}-14}}\,.$

One year after, [9] dedicated to one further improvement of the upper bound,
but the obtained expression is too complicated to be stated here (see
Definition 2.1 and Theorem 2.2 therein).

Notice that the above improvements all refer to the upper bound of $p_{c}$.
The lower bound in display (1), obtained by [1], was not improved so far.

In this paper we prove the following result.

######  Theorem 1.

For any $d\geq 2$,

$\frac{2(d+1)}{\sqrt{4d^{2}+4d-3}+2d+1}\leq
p_{c}(d)\leq\frac{(d+1)({2-\frac{1}{14d^{2}}-4d})(5d-8d^{2})}{(5d-8d^{2})^{2}+d\left({2-\frac{1}{14d^{2}}-4d}\right)^{2}}\,.$
(2)

So, since the definition of the model by [1], two papers were dedicated
exclusively to obtain improvements on the upper bound ([8] gave a simple bound
and [9] gave an improvement, however complicated) while another one [5]
presented, as a consequence of other results, a bound “in the middle”. Here we
get better bounds _on both sides_ : we provide the first improvement of the
lower bound since [1], and get a tighter and simpler upper bound than [9].
There is another motivation behind this seek for tighter bounds, that we now
explain. [3] proved that the critical parameter of the frog model, in general
graphs, is not always a monotonic function of the graph. For homogeneous
trees, the question of whether or not $p_{c}(d)$ is monotonically decreasing
in $d$ remains open. Denote by $l(d)$ (_resp._ $r(d)$) the lower (_resp._
upper) bound of (2). What we can show (using Mathematica) is that $l(d)>r(ad)$
for any $a\geq 1.75$. This implies that $p_{c}(d)>p_{c}(ad)$ for those values
of $a$, meaning for instance that $p_{c}(2)>p_{c}(4)>p_{c}(7)>p_{c}(13)...$. A
proof of monotonicity using this argument needs the bounds to be enhanced, and
we believe the present paper also gives new insights in this direction.

Further related literature will be provided in Section 4. We will also take
the opportunity to discuss further the monotonicity issue, and clarify the
relation between the upper bounds of the literature and their respective
proofs. As we will explain there, no significant improvement on the upper
bound can be achieved using our method of proof, meaning that a different
approach has to be developed to prove monotonicity by comparisons of lower and
upper bounds.

The paper is organized as follows: we prove the lower bound in Section 2, we
prove the upper bound in Section 3, and we conclude with a discussion in
Section 4.

##  2\. Proof of the lower bound

The idea of the proof is to look at the frog model as a branching process, and
to couple it with a two-type branching process (TTBP) in such a way that the
latter dominates the former. This TTBP is defined in Subsection 2.1. In
Subsection 2.2, we give the alternative construction of the frog model as a
branching process, which we call _frog model branching process_ (FMBP). We
prove the lower bound of Theorem 1 in Subsection 2.3, by constructing the
coupling between the TTBP and the FMBP.

###  2.1. A two-type branching process

Consider a two-type branching process in which, at each time step, exactly one
particle is chosen, dies, and gives birth to a random number of individuals of
each type, independently of everything else. For $a=1,2$, we denote by
$p_{a}(i,j)$ the probability that a particle of type $a$ generates $i$
particles of type 1 and $j$ particles of type 2:

$\displaystyle p_{1}(0,0)=1-p,\,\,p_{1}(1,0)$
$\displaystyle=0,\,\,p_{1}(2,0)=\frac{pd}{d+1},\,\,p_{1}(0,1)=\frac{p}{d+1}.$
(3) $\displaystyle
p_{2}(0,0)=1-p,\,\,p_{2}(1,0)=\dfrac{p}{d+1},\,\,p_{2}(2,0)=\dfrac{p(d-1)}{d+1},\,\,p_{2}(0,1)=\dfrac{p}{d+1}.$
(4)

With regard to the question of survival, this TTBP behaves as the two-type
Galton-Watson process with the same offspring distribution given by $p_{1}$
and $p_{2}$ as above. And it is well-known that a multi-types Galton-Watson
process has probability zero to survive if, and only if, the largest
eigenvalue of first moment matrix is smaller or equal to $1$ (see [2] for
instance). Simple calculations show that this matrix is

$M=\left(\begin{array}[]{cc}\frac{2dp}{d+1}&\frac{p}{d+1}\\\
\frac{(2d-1)p}{d+1}&\frac{p}{d+1}\end{array}\right)$

and has largest eigenvalue

$\rho_{M}=\frac{\left(\sqrt{4d^{2}+4d-3}+2d+1\right)p}{2(d+1)}.$

In other words, if

$p\leq\frac{2(d+1)}{\sqrt{4d^{2}+4d-3}+2d+1},$

then the TTBP defined above will generate finitely many individuals with
probability $1$.

###  2.2. The frog model as a branching process

To compare to the above TTBP, we define the following modification in the
dynamics of the frog model, which does not alter its survival probability.

  1. (1)

We consider the frog model in a way that frogs move one at a time, and at each
time, the frog which is chosen to make the step is arbitrary. That is, the
frog of the origin makes a move (with probability $p$), activating the
sleeping frog of the visited site. Then, we choose whichever frog between the
activated ones, to make a move (move which is done with probability $p$ too)
while the others stay frozen (don’t move) and active, and can be chosen to
make a move in a future time step. This procedure slows down the process in
the sense that it propagates slower on the tree, but since the random walks of
each activated frog are independent, this doesn’t change anything in terms of
survival.

  2. (2)

For further comparison with a two-type branching process, we will interpret
“moves” differently. At each step, instead of saying that the chosen frog
moves to a neighboring site, we will think that it dies out, and with
probability $p$ gives birth to frogs at one neighboring site: one frog if the
chosen neighboring site has been already visited, and two frogs otherwise.

  3. (3)

For any $t\geq 0$, we denote by $\mathcal{T}_{t}\subset\mathbb{T}_{d}$ the set
of visited sites at time $t$. Notice that
$\mathcal{T}_{t}\subseteq\mathcal{T}_{t+1},t\geq 0$.

  4. (4)

We consider the model starting from the random time $K=\inf\\{t\geq
0:|\mathcal{T}_{t}|=d+3\\}$ where $|\cdot|$ denotes the cardinal of the set.
This guarantees that at least one frog at distance $2$ of the root has been
activated (see next point). Notice that $K=\infty$ has a positive probability
of occurring.

  5. (5)

At each time step $t$, frogs which are at the tip of $\mathcal{T}_{t}$
(meaning that they have $d$ unvisited neighboring sites) are classified as
Type $1$, and the other frogs are classified as Type 2. Observe that, since we
consider times $t\geq K$, at least one neighboring site of a Type 2 frog is
surrounded by at least two already visited sites. This means that any
activated frog in the system can be classified as either type 1 or type 2.

Notice that, if a frog, when it births, is of type 1, depending on the
position of its vertex $v$ with respect to the evolving set
$\mathcal{T}_{t},t\geq 1$, it may transform into type 2 (notice the difference
in the preceding sentence between “transform” and “give birth to”). However,
the inverse cannot occur, a frog which births of type 2 cannot, with time
passing, transform into a type 1 frog.

Fix $t\geq K$ and $\mathcal{T}_{t}=T$. Denote by $p_{v}(i,j|T)$ the offspring
distribution of the frog located at $v$ inside $T$ which has been chosen to
make a move, where $i$ and $j$ are respectively the numbers of offsprings of
types 1 and 2. For any $v$, the distribution $p_{v}$ lives on
$\\{(0,0),(1,0),(0,1),(2,0)\\}$. The location of $v$ inside
$\mathcal{T}_{t}=T$ specifies the type 1 or 2 of the frog:

  * •

Suppose it has type 1. Then, independently of $v$ and $T$

$\displaystyle
p_{v}(0,0|T)=1-p\,,\,\,p_{v}(1,0|T)=0\,,\,\,p_{v}(2,0|T)=\frac{pd}{d+1}\,,\,\,p_{v}(0,1|T)=\frac{p}{d+1}.$
(5)

  * •

Suppose it has type 2. Then, there exist two integers (which depend on the
location of $v$ in $T$) $a,b$, with $a\geq 1$ and $a+b\geq 2$, such that

$\displaystyle
p_{v}(0,0|T)=1-p\,,\,\,\,p_{v}(1,0|T)=\frac{pb}{d+1}\,,\,\,\,p_{v}(2,0|T)=p-p\frac{a+b}{d+1}\,,\,\,\,p_{v}(0,1|T)=\frac{pa}{d+1}.$
(6)

###  2.3. Proof of the lower bound

We are now ready to prove our lower bound.

###### Proof of the lower bound of Theorem 1.

Let $N_{t}^{FM,i},i=1,2$ (_resp._ $N_{t}^{TT,i},i=1,2$) count the number of
active particles of type $i$ in the system at time $t$ in the FMBP (_resp._ in
the TTBP).

Since we are only interested in bounding the critical parameter of the frog
model, instead of starting from $\mathcal{T}_{0}=\\{o\\}$ we can start the
frog model from any of the configurations satisfying $|\mathcal{T}_{0}|=d+3$.
So let us start from any vectors $(N_{0}^{FM,1},N_{0}^{FM,2})$ having positive
probability to be produced in the FM with $|\mathcal{T}_{0}|=d+3$, and put
$(N_{0}^{TT,1},N_{0}^{TT,2})=(N_{0}^{FM,1},N_{0}^{FM,2})$. If we can couple
these processes in such a way that, for any $t\geq 0$, $N_{t}^{TT,1}\geq
N_{t}^{FM,1}$ and $N_{t}^{TT,1}+N_{t}^{TT,2}\geq N_{t}^{FM,1}+N_{t}^{FM,2}$,
then, in particular, the total number of particles in the TTBP is at least as
large as the total number of activated frogs in the FMBP, at each time step.
Together with what we said in Subsection 2.1, if

$p\leq\frac{2(d+1)}{\sqrt{4d^{2}+4d-3}+2d+1},$

then the FMBP would not survive with probability $1$, which would conclude the
proof of the theorem.

So it only remains to prove that we can couple these processes in such a way
that, for any $t\geq 0$, $N_{t}^{TT,1}\geq N_{t}^{FM,1}$ and
$N_{t}^{TT,1}+N_{t}^{TT,2}\geq N_{t}^{FM,1}+N_{t}^{FM,2}$. The inequalities
are satisfied at $t=0$ by definition. We assume the inequalities are satisfied
at time $t$, and we now want to prove that they are still satisfied at time
$t+1$. To couple the processes at $t+1$, we need to couple the probability
distributions $p_{1},p_{2}$ and $p_{v}(\cdot|T)$. We do this using a random
variable $U_{t+1}$ uniformly distributed in $[0,1]$ (independent of
everything) and several partitions of $[0,1]$. First, partitions
$\mathcal{P}_{1},\mathcal{P}_{2}$ to construct $p_{1},p_{2}$:

$\displaystyle\mathcal{P}_{1}$
$\displaystyle=\\{I_{1}^{0,1},I_{1}^{2,0},I_{1}^{0,0}\\}$
$\displaystyle\mathcal{P}_{2}$
$\displaystyle=\\{I_{2}^{0,1},I_{2}^{1,0},I_{2}^{2,0},I_{2}^{0,0}\\}$

where

$I_{1}^{0,1}=\left[0,\frac{p}{d+1}\right[\,\,,\,\,\,I_{1}^{2,0}=\left[\frac{p}{d+1},p\right[\,\,,\,\,\,I^{0,0}=[p,1]$

and

$I_{2}^{0,1}=\left[0,\frac{p}{d+1}\right[\,\,,\,\,\,I_{2}^{1,0}=\left[\frac{p}{d+1},\frac{2p}{d+1}\right[\,\,,\,\,\,I_{2}^{2,0}=\left[\frac{2p}{d+1},p\right[\,\,,\,\,\,I_{2}^{0,0}=[p,1]\,.$

We refer to Figure 1 for a pictorial representation of these partitions.

Observe that

$P(U_{t+1}\in I_{1}^{i,j})=p_{1}(i,j)\,\,\,\,\text{and}\,\,\,\,P(U_{t+1}\in
I_{2}^{i,j})=p_{2}(i,j).$

Now, for moving frogs of type 1 in the FMBP, no matter what is the pair
$(v,T)$, we can use the partition $\mathcal{P}_{1}$ since for such frogs
$p_{v}(\cdot|T)=p_{1}$.

According to (6), for moving frogs of type 2 we use the partition (recall that
$a\geq 1$ and $a+b\geq 2$)

$\mathcal{P}_{(a,b)}=\\{I_{(a,b)}^{0,1},I_{(a,b)}^{1,0},I_{(a,b)}^{2,0},I_{(a,b)}^{0,0}\\}$

where

$I_{(a,b)}^{0,1}=\left[0,\frac{ap}{d+1}\right[\,\,,\,\,\,I_{(a,b)}^{1,0}=\left[\frac{ap}{d+1},\frac{(a+b)p}{d+1}\right[\,\,,\,\,\,I_{(a,b)}^{2,0}=\left[\frac{(a+b)p}{d+1},p\right[\,\,,\,\,\,I_{(a,b)}^{0,0}=[p,1]\,.$

Observe that, for any $a,b$ and $i,j$, we have

$P(U_{t+1}\in I_{(a,b)}^{i,j})=p_{v}(i,j|T)\,.$

Figure 1. Pictorial representation of the partitions
$\mathcal{P}_{1},\mathcal{P}_{2}$ and $\mathcal{P}_{(a,b)}$, when $d=4,a=2$
and $b=1$.

The coupling is now performed updating both processes at time $t+1$ using the
same uniform $U_{t+1}$. We can now establish the recursion from $t$ to $t+1$,
recalling that the recursion hypothesis is $N_{t}^{TT,1}\geq N_{t}^{FM,1}$ and
$N_{t}^{TT,1}+N_{t}^{TT,2}\geq N_{t}^{FM,1}+N_{t}^{FM,2}$:

  1. (1)

If the chosen frog for the next move of the FMBP is of type 1, then a particle
of type 1 of the TTBP is chosen to give birth to its offspring. Since
$N_{t}^{TT,1}\geq N_{t}^{FM,1}$, this choice is always possible. In this case,
according to our coupling, the two chosen particles (one in each process) give
birth the the same offspring, and thus the inequalities are maintained.

  2. (2)

Suppose now that the chosen frog is of type 2, then, either a type 2 particle
of the branching process is chosen to give birth to its offspring, or, if
there is none, a type 1 particle is chosen.

According to the location $v$ in $T$ of the chosen frog of type 2, a pair
$(a,b)$ of integers is associated, as explained before. For any fixed pair
$(a,b)$, we have the following possibilities:

    1. (a)

The particle of the TTBP is also a type 2 particle: then

       * •

if $U_{t+1}\leq\frac{p}{d+1}$, then one particle of type 2 is created in each
process so that the inequalities are maintained;

       * •

if $U_{t+1}\geq p$, then the chosen particle dies in each process so that the
inequalities are maintained;

       * •

if $U_{t+1}\in\left[\frac{p}{d+1},\frac{ap}{d+1}\right]$ (and therefore $a\geq
2$ since otherwise this interval half open to the right is empty) the
branching process produces two type 1 particles while the frog model produces
one type 2 particle, and therefore the inequalities are maintained

       * •

if $U_{t+1}\in I_{(a,b)}^{1,0}$ then either one (if $a=1$) or two (if $a\geq
2$) type 1 particles are created in the branching process, while the frog
model creates one type 1 particle, thus the inequalities are maintained;

       * •

if $U_{t+1}\in I_{(a,b)}^{2,0}$ then two type 1 particles are created in both
processes and the inequalities are maintained.

    2. (b)

There is no more type 2 particles in the TTBP, and we have to choose a type 1
particle. In this case, the reasoning is the same as above, observing moreover
that, necessarily, $N^{TT,1}_{t}\geq N^{FM,1}_{t}+1$.

Thus, in any case, we have $N_{t+1}^{TT,1}\geq N_{t+1}^{FM,1}$ and
$N_{t+1}^{TT,1}+N_{t+1}^{TT,2}\geq N_{t+1}^{FM,1}+N_{t+1}^{FM,2}$,
establishing the recursion.

The proof of the lower bound of Theorem 1 is concluded.

##  3\. Proof of the upper bound

We will proceed in three steps. In a first step of the proof, we explain the
comparison of the frog model with its oriented version. This part of the proof
is common to [8], [9] and [5]. In the second step, we state Theorem 2, a very
nice result which identify the critical parameter of the oriented version with
the root of a power series. Notice that, although this result was already
proved in [5] (see Theorem 1 therein), will partially prove it in order to
give support to our discussion in Section 4. Based on this theorem, the two
last steps are dedicated to obtain bounds for the critical parameter of the
oriented version, and these steps only rely on calculus. This is done by first
finding finite degree polynomials (of degree 6 and degree 5) which approximate
the power series from below and from above, and next, finding root
approximations for these polynomials.

Let us now give some notation. We denote by $d(v,v^{\prime})$ the distance
between any two vertices of $v,v^{\prime}$ of $\mathbb{T}_{d}$, defined as the
number of edges of the unique path connecting them. We write $v\leq
v^{\prime}$ if $v$ is one of the vertices on the path between the root $o$ and
$v^{\prime}$, and we naturally write $v<v^{\prime}$ if $v\leq v^{\prime}$ and
$v\neq v^{\prime}$.

###  3.1. Step one: oriented version of the frog model

Consider the following modification of the frog model, that we call _oriented
frog model_ : when a frog, initially at vertex $v\in\mathbb{T}_{d}$ is
activated and makes its random walk, it only activates the frogs of vertices
$v^{\prime}$ such that $v^{\prime}>v$.

It is obvious that, if this oriented model survives, then the original model
survives as well. So if we find an upper bound for the critical parameter
$\hat{p}_{c}$ of the oriented model, it will also be an upper bound for the
critical parameter of the original model.

Our objective in the remaining of the proof will be to find tight upper and
lower bounds for $\hat{p}_{c}$. Notice that even though the lower bound on
$\hat{p}_{c}$ is not necessary to get our upper bound for $p_{c}$, we will
partially provide it to show that the upper bound of $\hat{p}_{c}$ is already
very accurate as an estimate of $\hat{p}_{c}$ (see the discussion in Section
4).

###  3.2. Step two: $\hat{p}_{c}$ as the root of a power series

For any vertices $v^{\prime},v$, we denote by $\\{v\rightarrow v^{\prime}\\}$
the event that the frog at $v$, if it were active, would visit $v^{\prime}$
during his random walk. Lemma 2.1 of [8] states that for any $v,v^{\prime}$
such that $d(v,v^{\prime})=n\geq 1$,

$\mathbb{P}_{p}(v{\rightarrow}v^{\prime})=r^{n}$ (7)

where

$r=r(p,d):=\dfrac{d+1-\sqrt{(d+1)^{2}-4dp^{2}}}{2dp},$ (8)

a fact which will have importance later on. Notice in particular that, writing
$r_{c}=r(\hat{p}_{c},d)$, we can now focus on $r_{c}$ directly since $r$ is a
continuous bijection on $[0,1]$.

The objective of the present step is to prove the following very nice theorem
which gives the critical parameter as root of a power series. It is proved,
indirectly, in [5], so we include its proof here for the sake of completeness.

######  Theorem 2.

$\sum_{k\geq
1}d^{k}r(\hat{p}_{c},d)^{k}\prod_{i=1}^{k-1}(1-r(\hat{p}_{c},d)^{i})=1.$

###### Proof.

We denote by $\\{v\stackrel{{\scriptstyle c}}{{\rightarrow}}v^{\prime}\\}$ the
event that either $\\{v\rightarrow v^{\prime}\\}$, or there exist $k\geq 1$
and a sequence of vertices $v_{1},\ldots,v_{k}$ such that
$v=:v_{0}<v_{1}<\ldots<v_{k}<v_{k+1}:=v^{\prime}$ such that
$\cap_{i=0}^{k}\\{v_{i}\rightarrow v_{i+1}\\}$. In words,
$\\{v\stackrel{{\scriptstyle c}}{{\rightarrow}}v^{\prime}\\}$ means that $v$
has started a chain of activation of frogs which in particular activates
$v^{\prime}$. By symmetry, we can use
$u_{n}=u_{n}(r,d):=\mathbb{P}_{p}(o\stackrel{{\scriptstyle
c}}{{\rightarrow}}v)$ for any $v$ such that $d(o,v)=n$.

On the one hand we have

$\mathbb{P}_{p}(\cup_{v:d(o,v)=n}\\{o\stackrel{{\scriptstyle
c}}{{\rightarrow}}v\\})\searrow\mathbb{P}_{p}(\text{survival of the oriented
model}).$

Thus

$\mathbb{P}_{p}(\cup_{v:d(o,v)=n}\\{o\stackrel{{\scriptstyle
c}}{{\rightarrow}}v\\})\leq d^{n}\mathbb{P}_{p}(o\stackrel{{\scriptstyle
c}}{{\rightarrow}}v)=:d^{n}u_{n}.$

In other words,

$d^{n}u_{n}\rightarrow 0\Rightarrow\mathbb{P}_{p}(\text{survival of the
oriented model})=0.$ (9)

On the other hand, the expected number of vertices at distance $n$ of the root
which have been visited by frogs is, also by symmetry

$\sum_{v:d(o,v)=n}\mathbb{P}_{p}(o\stackrel{{\scriptstyle
c}}{{\rightarrow}}v)=d^{n}u_{n}.$

Fix some $N\geq 1$ and consider the following process, obtained from the
oriented model _via_ the following recursive procedure:

  * •

At each vertex of level $N$ which has been visited (at time $N$, since the
process is oriented), we keep only one activated frog.

  * •

Each frog activated at level $iN,i\geq 1$ is started, and at each vertex of
level $(i+1)N$ which has been visited, we keep only one activated frog.

Observe first that this modified process is dominated by the oriented process,
since at each step $i\geq 1$ of the recursive procedure we only keep 1
activated frog at the visited vertices at distance $iN$ of the root. Moreover,
the frog we keep at $iN$, given it has reached this level, can be substituted
by a new active frog, because of the loss of memory property of the geometric
distribution (7). It follows that the number of visited vertices at level
$iN,i\geq 1$ of this modified process has the same distribution as the number
of individuals at the $i^{\text{th}}$ generation in a Galton-Watson tree with
expected offspring $d^{N}u_{N}$. If $d^{N}u_{N}>1$, the Galton-Watson has
positive probability to survive, and thus so does the oriented model. In other
words

$\exists N\geq 1:d^{N}u_{N}>1\Rightarrow\mathbb{P}_{p}(\text{survival of the
oriented model})>0.$ (10)

To continue, we need to study $u_{n}=\mathbb{P}_{p}(o\stackrel{{\scriptstyle
c}}{{\rightarrow}}v)$ and its limiting properties, and it is precisely in that
study that [5] differs from [8] and [9] (see Section 4 for a discussion).
Indeed, [5] used a result of [4] implying that $u_{n}$ is the probability that
an undelayed renewal sequence, with inter-renewal distribution
$f_{k}=r^{k}\prod_{i=1}^{k-1}(1-r^{i}),k\geq 1$, has a renewal at time $n$.
This allows them to conclude, using renewal theory (see Section 4 in [5]) that
$u_{\infty}(r,d):=\lim u_{n}^{1/n}$ exists, is continuous in $r$, and it
satisfies the equality

$\sum_{k\geq 1}r^{k}u_{\infty}^{-k}\prod_{i=1}^{k-1}(1-r^{i})=1.$ (11)

Together with (9) and (10), the existence of $u_{\infty}(r,d)$ gives us

$\displaystyle u_{\infty}>1/d$
$\displaystyle\Rightarrow\mathbb{P}_{p}(\text{survival of the oriented
model})>0$ $\displaystyle u_{\infty}<1/d$
$\displaystyle\Rightarrow\mathbb{P}_{p}(\text{survival of the oriented
model})=0.$

The continuity of $u_{\infty}(r,d)$ allows us conclude that $r_{c}$ satisfies

$u_{\infty}(r_{c},d)=\frac{1}{d}.$ (12)

Putting (12) together with (11) concludes the proof of the theorem.

###  3.3. Third step: bounds for $\hat{p}_{c}$ as zeros of polynomials

Using (8) and and Theorem 2, the way to proceed now is to find
$\underline{r}=\underline{r}(d)$ and $\overline{r}=\overline{r}(d)$ such that

$\underline{r}\leq r_{c}\leq\overline{r}$ (13)

which yields

$\frac{(d+1)\underline{r}}{1+d\underline{r}^{2}}\leq\hat{p}_{c}\leq\frac{(d+1)\overline{r}}{1+d\overline{r}^{2}}.$
(14)

A first characterization that we will give of $\underline{r}$ and
$\overline{r}$ is as zeros of polynomials.

######  Proposition 3.

Let $\underline{r}$ (_resp._ $\overline{r}$), denote the unique root of the
polynomial $L(r):=-d^{3}r^{6}+d^{3}r^{5}+d^{2}r^{3}-2dr+1$ (_resp._ of the
polynomial $U(r):=d^{3}r^{5}+d^{2}r^{3}-2dr+1$) in $r\in(0,1/d)$. Then

$\underline{r}\leq r_{c}\leq\overline{r}.$

###### Proof.

We have the inequalities for any $k\geq 3$

$1-r-r^{2}<(1-r-r^{2}+r^{k}\leq)\prod_{i=1}^{k-1}\left(1-r^{i}\right)\leq(1-r)(1-r^{2})$
(15)

where the lower bound between parenthesis follows by recursion and the two
others are trivial. Inequalities (15) imply that

$f_{\text{inf}}(r)\leq\sum_{k\geq 1}d^{k}r^{k}\prod_{i=1}^{k-1}(1-r^{i})\leq
f_{\text{sup}}(r)$

with

$f_{\text{inf}}(r)=dr+d^{2}(1-r)r^{2}+(1-r-r^{2})\left(-\frac{d^{3}r^{3}}{dr-1}\right)$

and

$f_{\text{sup}}(r)=dr+d^{2}(1-r)r^{2}+(1-r)(1-r^{2})\left(-\frac{d^{3}r^{3}}{dr-1}\right).$

With Theorem 2 we conclude that

$f_{\text{inf}}(r_{c})\leq 1\leq f_{\text{sup}}(r_{c}).$

With some further algebra, we notice that

$\displaystyle f_{\text{inf}}(r_{c})\leq 1$ $\displaystyle\Leftrightarrow
d^{3}r_{c}^{5}+d^{2}r_{c}^{3}-2dr_{c}+1\geq 0$ $\displaystyle
f_{\text{sup}}(r_{c})\geq 1$
$\displaystyle\Leftrightarrow-d^{3}r_{c}^{6}+d^{3}r_{c}^{5}+d^{2}r_{c}^{3}-2dr+1\leq
0.$

But since both polynomials are decreasing on $(0,1/d)$, then we conclude that
the root $\underline{r}$ of $L(r)=-d^{3}r^{6}+d^{3}r^{5}+d^{2}r^{3}-2dr+1$ and
the root $\overline{r}$ of $U(r)=d^{3}r^{5}+d^{2}r^{3}-2dr+1$ will satisfy

$\underline{r}\leq r_{c}\leq\overline{r}$

as stated by the lemma.

###  3.4. Fourth (last) step: explicit bounds for $\hat{p}_{c}$ as functions
of $d$

In principle, we could simply seek for the exact expression of the zeros
stated in Proposition 3. However, this leads to very complicated expressions.
So we will do one further step to get approximations of $\overline{r}$ and
$\underline{r}$.

######  Lemma 4.

For $d\geq 2$

$\underline{r}(d)\geq
r_{L}:=\frac{5-8d-16d^{2}+64d^{3}}{12d-20d^{2}-48d^{3}+128d^{4}}$

and

$\overline{r}(d)\leq r_{U}:=\frac{2-\frac{1}{14d^{2}}-4d}{5d-8d^{2}}.$

Putting Display (14), Proposition 3 and Lemma 4 together, we get explicit
lower and upper bounds for $\hat{p}_{c}$ as function of $d$. In conjunction
with Step 1, this in particular proves the upper bound given in Theorem 1.

##  4\. Discussion on the bounds and their proofs

###  4.1. Further literature on related models

Under the name “frog model”, a vast literature as been developed in recent
years. Here we highlight two other papers focussing on trees. The first one,
[6], considers the speed of the spread and the final proportion of activated
frogs, on finite trees and with frogs having a.s. finite lifetime (not
necessarily starting with one sleeping frog _per_ site). Although the
situation and problem are slightly different than us here, the paper also
gives a nice account of the recent literature for general frog models. The
second one, much more related to our, is [7], which proves transience and
recurrence of the frog model on infinite trees when the frogs have infinite
lifetime (and starting with one sleeping frog _per_ site). In this paper, the
authors use a similar argument as the one used here to get the upper bound,
designing a multi-type branching process which dominates the frog model of
interest. We will come back to this in Section 4.3 when we will discuss lower
bounds.

###  4.2. The upper bounds and their proofs

Our objective here is to compare the upper bounds of the literature, as well
as their proofs. Specifically, we have to compare the works of [8], [5] and
[9], and the present work.

As already mentioned, the proofs of these works have Step 1 in common: they
consider the oriented version of the frog model. The main difference is in
Step 2. [8] used the fact that, finding a solution, in $p$, for
$d^{k}u_{k}(p,d)=1$ inside the interval $(0,1/d)$, yields an upper bound for
$p_{c}$. This is the content of Theorem 3.1 therein, and it is a fact which
can also be concluded from (10) above. The problem is that this yields a bound
which depends on $k$, and as they observe, it is not obvious whether this
sequence of upper bounds is decreasing, so they cannot make the limiting
procedure at this step. Instead, they consider a sequence $v_{k}\leq u_{k}$,
and work on the asymptotic of the sequence of solutions of $d^{k}v_{k}$ as
function of $r$, or, equivalently, of $p$ (see Lemmas 4.1, 4.2 and 4.3
therein). It is interesting how this approach differs from ours, on a
mathematical ground. Formally, what [8] obtained is that (see Display (4.2)
therein)

$u_{k}=r^{k}\prod_{i=1}^{k-1}(1-r^{i})+\sum_{j=1}^{k-1}r^{k-j}u_{j}\prod_{l=1}^{k-j-1}(1-r^{l}).$
(16)

At this point what they decided to do, instead of studying the asymptotic
behavior in $k$, is to take

$v_{k}=r^{k}\prod_{i=1}^{k-1}(1-r)+\sum_{i=1}^{k-1}r^{k-j}u_{j}\prod_{l=1}^{k-j-1}(1-r)=r^{k}(1-r)^{k-1}+\sum_{i=1}^{k-1}r^{k-j}u_{j}(1-r)^{k-j-1}$

which clearly satisfies $v_{k}\leq u_{k}$. Observe that this amounts simply to
substitute $r^{i}$ and $r^{l}$ by $r$ into the products of (16). They can then
work asymptotically with the solutions of $d^{k}v_{k}=1$ and conclude their
bound $r_{c}\leq 1-\sqrt{{(d-1)}/{d}}$, which is actually the solution of
$dr(2-r)=1$ for $r\in(0,1/d)$. It was also remarked by [8] that substituting
the $r^{i}$ and $r^{l}$ by $r^{2}$ for any $k\geq 2$ would naturally yield
tighter, yet more complicated bounds for $r_{c}$. Indeed, they state that
$r_{c}$ would be the root $\bar{r}_{U}$ of
$\bar{U}(r):=dr^{4}-d(d+1)r^{3}+2dr-1$ in $(0,1/d)$. It is precisely what [9]
used, yielding yet another refinement of the bound, although very complicated
(see Definition 2.1 and Theorem 2.2 therein).

On the contrary, what we do (and what was done by [5]) in Step 2 is that we
directly work asymptotically on (16) using renewal theory, and this yields
Theorem 2. In particular, notice that the bounds of [8] and [9] are direct
consequences of Theorem 2 as well: indeed, substituting, in the products,
$r^{i}$ and $r^{l}$ by $r$, yields the polynomial $dr(2-r)=1$ used by [8], and
substituting by $r^{i}$ and $r^{l}$ by $r^{2}$ (for $i,l\geq 2$) yields the
polynomial $\bar{U}(r):=dr^{4}-d(d+1)r^{3}+2dr-1$ used by [9].

Clearly our upper bound (2) is simpler than the one of [9]. In order to see
that it is also tighter, it is enough to notice (we did this using
Mathematica) that $\bar{U}(r_{U})<0$ and that $\bar{U}$ is monotonically
increasing on $(0,1/d)$ (see Lemma 4 for the definition of $r_{U}$).

###  4.3. The lower bounds and their proofs

The original lower bound of [1] was based on a simple coupling with a one-type
branching process in which each particle could have 0 offsprings with
probability $1-p$, 1 offspring with probability $p/(d+1)$ (for frogs coming
back) and 2 offsprings with probability $pd/(d+1)$. In other words, their
coupling took into account the fact that, except for the frog initially at the
root, an active frog necessarily is surrounded by at least one neighbouring
site. What we noticed in the present paper is that after a certain number of
steps (almost-surely finite), any activated frog which is not at the tip of
the visited cluster has at least two visited neighbouring sites. In order to
take this into account, we needed to consider a two-type branching process.

The frog model can be seen as an “infinite types” branching process, and it is
naturally possible to improve further our reasoning. The idea would be to
compare the frog model with branching processes having more and more types.
For instance, a simple modification of the multi-type branching process used
by [7] in the proof of their Proposition 19 could be used as well in our
setting. This amounts essentially in adding types corresponding to keeping
track of two simultaneously activated particles. Doing so, we are able, for
instance, to prove that $p_{c}(2)<p_{c}(3)$, but it is impossible to get
explicit expression holding for any $d$ based on so much types. More
generally, we tried such method up to a certain level, and obtained slightly
tighter lower bounds with very involved expressions, and we preferred to keep
it simple at the cost of precision.

###  4.4. Concluding remark

Tighter bounds on $\hat{p}_{c}$ can be obtained from Theorem 2, this is a
matter of root approximation for the power series of Theorem 2. However, as
pointed by Table 1, such improvements would be almost insignificant compared
to the distance to the lower bounds of $p_{c}$ since we are limited by the
lower bound on $\hat{p}_{c}$, already very close to the upper bound. For this
reason we mentioned in Introduction that further works should either improve
the lower bound or find another approach (different from the comparison with
the oriented version of the frog model) to get upper bounds for $p_{c}$.

Table 1. Lower bound (LB) and upper bound (UB) of $p_{c}$ from Theorem 1 and lower bound on $\hat{p}_{c}$ from Lemma 4. d | LB on $p_{c}$ | LB on $\hat{p}_{c}$ | UB on $\hat{p}_{c}$ and $p_{c}$
---|---|---|---
2 | 0.6261364 | 0.7103674 | 0.7137989
3 | 0.5835921 | 0.6419859 | 0.6428580
4 | 0.5625890 | 0.6071563 | 0.6074957
5 | 0.5500385 | 0.5860557 | 0.5862210
6 | 0.5416859 | 0.5719015 | 0.5719940
7 | 0.5357250 | 0.5617475 | 0.5618043
8 | 0.5312564 | 0.5541074 | 0.5541448
9 | 0.5277818 | 0.5481503 | 0.5481761
10 | 0.5250027 | 0.5433751 | 0.5433937
20 | 0.5125001 | 0.5217793 | 0.5217815
50 | 0.5050000 | 0.5087345 | 0.5087346
100 | 0.5025000 | 0.5043711 | 0.5043711

##  5\. Appendix: Root approximations

As promised, we now prove Lemma 4.

###### Proof.

For the lower bound, we use the Newton-Raphson method for root approximation
of $L(r)=-r^{3}r^{6}+d^{3}r^{5}+d^{2}r^{3}-2dr+1$. The second derivative of
$L(r)$ is positive for all $r\in(0,1/d)$, so $L(r)$ is convex on this
interval. Thus, the approximation calculated from the Newton-Raphson method
will be smaller than the root $\underline{r}$. Recall that the Newton-Raphson
iterative method is started from some value $t_{0}$ and for any $n\geq 1$

$\displaystyle t_{n}$ $\displaystyle=$ $\displaystyle
t_{n-1}-\frac{L(t_{n-1})}{L^{\prime}(t_{n-1})}.$

Starting with $t_{0}=0$ and iterating two time, we get after some algebraic
manipulations

$t_{2}=\frac{5-8d-16d^{2}+64d^{3}}{12d-20d^{2}-48d^{3}+128d^{4}}.$

This concludes the proof of the lower bound.

For the upper bound, the proof of the Newton-Raphson method is much longer so
we will proceed simply proving that $r_{U}\geq\bar{r}$, which is faster. We
proceed in two steps: we first show that the polynomial $U$ is monotonically
decreasing in $r$ around the root of interest, and secondly, that $U(r_{U})<0$
for any $d\geq 2$.

For the first step, notice that

$U^{\prime}(r)<0\Leftrightarrow 5d^{2}r^{4}+3dr^{2}-2<0,$

This is equivalent to $r<\sqrt{{1}/{(5d)}}$. It only remains to get sure that
$r_{U}<\sqrt{{1}/{(5d)}}$. To see this, we come back to the proof of
Proposition 3, and notice that

$(1-r)^{k-1}\leq\prod_{i=1}^{k-1}\left(1-r^{i}\right)$

leads to an intermediary polynomial $f_{\text{inf}}(r)\leq
dr(2-r)\leq\sum_{k\geq 1}d^{k}r^{k}\prod_{i=1}^{k-1}(1-r^{i})$. Thus
$dr_{U}(2-r_{U})\leq 1$, meaning that indeed $r_{U}\leq 1-\sqrt{{(d-1)}/{d}}$
which is strictly smaller than $\sqrt{{1}/{(5d)}}$ for any $d\geq 2$.

To prove the second step, we used Mathematica to write $U(r_{U}(d))<0$ as

$-\frac{1}{537824\,d^{12}(8d-5)^{5}}\bar{U}(d)<0$

where

$\displaystyle\bar{U}(d)$
$\displaystyle=211441664\,d^{14}-801511424\,d^{13}+988904672\,d^{12}-496642048\,d^{11}$
$\displaystyle+72342816\,d^{10}+14993216\,d^{9}-2579360\,d^{8}-918064\,d^{7}$
$\displaystyle+203840\,d^{6}+26460\,d^{5}-7840\,d^{4}-280\,d^{3}+140\,d^{2}-1.$

We are done if we prove that $\bar{U}(d)>0$ for any $d\geq 2$. Using Cauchy
bounds, we know that the largest root of this polynomial is smaller or equal
to (for $i=0,\ldots,14$ we write $a_{i}$ for the coefficient of order $i$)

$m:=1+\max\left\\{\left|\frac{a_{13}}{a_{14}}\right|,\ldots,\left|\frac{a_{0}}{a_{14}}\right|\right\\}=1+\frac{988904672}{211441664}<6.$

The proof is concluded noticing that for $d=2,\ldots,6$, $\bar{U}(d)>0$.

## References

  * [1] Oswaldo Alves, Fabio Machado, and Serguei Popov.  Phase transition for the frog model.  Electron. J. Probab., 7:21 pp., 2002.
  * [2] Krishna B Athreya and Peter E Ney.  Branching processes.  Courier Corporation, 2004.
  * [3] L. R. Fontes, F. P. Machado, and A. Sarkar.  The critical probability for the frog model is not a monotonic function of the graph.  J. Appl. Probab., 41(1):292–298, 2004.
  * [4] Sandro Gallo, L. Garcia, Nancy, Valdivino V. Junior, and Pablo M. Rodríguez.  Rumor processes on $\mathbb{N}$ and discrete renewal processes.  J. Stat. Phys., 155(3):591–602, 2014.
  * [5] Sandro Gallo and Pablo M Rodriguez.  Frog models on trees through renewal theory.  Journal of Applied Probability, 55(3):887–899, 2018.
  * [6] Jonathan Hermon.  Frogs on trees?  Electronic Journal of Probability, 23:1–40, 2018.
  * [7] Christopher Hoffman, Tobias Johnson, and Matthew Junge.  Recurrence and transience for the frog model on trees.  The Annals of Probability, 45(5):2826–2854, 2017.
  * [8] Élcio Lebensztayn, Fábio P. Machado, and Serguei Popov.  An improved upper bound for the critical probability of the frog model on homogeneous trees.  J. Stat. Phys., 119(1-2):331–345, 2005.
  * [9] Elcio Lebensztayn and Jaime Utria.  A new upper bound for the critical probability of the frog model on homogeneous trees.  Journal of Statistical Physics, 176(1):169–179, 2019.
  * [10] András Telcs and Nicholas C Wormald.  Branching and tree indexed random walks on fractals.  Journal of applied probability, 36(4):999–1011, 1999.