# Speed of Random Walks in Dirichlet Environment on a Galton-Watson Tree

Dongjian Qian  Yang Xiao

###### Abstract

This paper deals with a transient random walk in Dirichlet environment, or
equivalently a linearly edge reinforced random walk, on a Galton-Watson tree.
We compute the stationary distribution of the environment seen from the
particle of an edge reinforced random walk. We obtain a formula for the speed
and give a necessary and sufficient condition for the walk to have a positive
speed under some moment conditions on the offspring distribution of the tree.

[label 1]organization=School of Mathematical Sciences,addressline=Fudan
University, city=Shanghai, country=People’s Republic of China

##  1 Introduction

An edge reinforced random walk (ERRW) is a non-Markov process that tends to
favor previously visited edges, first introduced by Coppersmith and Diaconis
[7]. Let $G=(V,E)$ be an oriented graph and $(\alpha_{e})_{e\in E}$ a set of
positive deterministic weights. For two adjacent points $x,y\in V$, we denote
by $(x,y)$ the edge from $x$ to $y$. An oriented edge $e$ is thus written as
$e:=(\underline{e},\overline{e})$, where $\underline{e}$ and $\overline{e}$
are the tail and head of $e$ respectively. We define the ERRW $(X_{n})_{n\geq
0}$ on $G$ with transition probabilities

$\mathbf{P}(X_{n+1}=y|X_{1},\cdots,X_{n})=\frac{\alpha_{(X_{n},y)}+N^{X}_{(X_{n},y)}(n)}{\sum_{\underline{e}=X_{n}}\alpha_{e}+N^{X}_{e}(n)}\textbf{1}_{\\{(X_{n},y)\in
E\\}},$ (1)

where $N_{e}^{X}(n):=\\#\\{1\leq k\leq n:(X_{k-1},X_{k})=e\\}$. In words, if
the process is at a vertex $x$ at time $n$, it will choose for its next step
some neighbour $y$ with probability proportional to
$\alpha_{(x,y)}+N^{X}_{(x,y)}(n)$.

By means of Polya’s urns, it is well-known that this process can be
represented as a mixture of Markov chains called Random Walk in Dirichlet
Environment (RWDE), a special case of random walk in random environment.
Specifically, independently at each vertex $x$, pick a random vector with
positive entries
$(\eta_{e})_{\underline{e}=x}=(\eta(\underline{e},\overline{e}))_{\underline{e}=x}$
which satisfies $\sum_{\underline{e}=x}\eta_{e}=1$. The joint law of
$(\eta_{e})_{\underline{e}=x}$ is taken to be the Dirichlet distribution with
parameters $(\alpha_{e})_{\underline{e}=x}$, i.e. it has density

$\frac{\Gamma(\sum_{\underline{e}=x}\alpha_{e})}{\prod_{\underline{e}=x}\Gamma(\alpha_{e})}\prod_{\underline{e}=x}(y_{e}^{\alpha_{e}-1}\textbf{1}_{\\{0<y_{e}<1\\}})\textbf{1}_{\\{\sum_{\underline{e}=x}y_{e}=1\\}}.$

We call $(\eta_{e})_{e\in E}$ a Dirichlet environment, and denote its
distribution by ${\rm DE}(\cdot)$. Given the environment $(\eta_{e})_{e\in
E}$, we define the RWDE $(X_{n})_{n\geq 0}$ as the Markov chain on $G$ with
transition probabilities

${{\rm P}}^{\eta}(X_{n+1}=y|X_{n}=x)=\eta(x,y),\qquad(x,y)\in E.$

We write ${\rm P}^{\eta}_{x}(\cdot)$ for the quenched measure ${\rm
P}^{\eta}(\cdot|X_{0}=x)$. The connection between ERRW and RWDE is as follows:
the RWDE $(X_{n})_{n\geq 0}$ under the annealed measure
$\mathbf{P}(\cdot):=\int{{\rm P}}^{\eta}(\cdot){\rm DE}(\mathrm{d}\eta)$ is an
ERRW.

In the article, we focus on the case where $G$ is a super-critical Galton-
Watson tree $\mathbb{T}$ with some offspring distribution $(p_{n})_{n\geq 0}$,
and hence $m:=\sum_{n\geq 0}np_{n}>1$. We consider it as an oriented graph
where each edge has two directions (from parent to child and child to parent).
We write $\rho$ for the root, and $xi,1\leq i\leq\nu(x)$, resp. $x_{*}$, for
the children, resp. the parent, of a vertex $x$. Often, we will artificially
add a parent $\rho_{*}$ to the root $\rho$, and we will call the new tree
$\mathbb{T}_{*}$. Since we are interested in the transient case, we will
preferably work on the event $\mathcal{S}$ that $\mathbb{T}_{*}$ is infinite.

Fix two positive numbers $\alpha_{p},\alpha_{c}$. We study the ERRW
$(X_{n})_{n\geq 0}$ on the tree $\mathbb{T}_{*}$ named
$(\alpha_{p},\alpha_{c})$-ERRW where the weights $(\alpha_{e})_{e\in E}$ are
given by $\alpha_{(x,x_{*})}=\alpha_{p}$ and $\alpha_{(x_{*},x)}=\alpha_{c}$,
$x\in\mathbb{T}$, with $X_{0}=\rho$. It is a generalization of the model given
in [17]. Similar to the $\lambda$-biased random walk (see, for example, [14]),
the $(\alpha_{p},\alpha_{c})$-ERRW introduces an asymmetry between moving up
or down in the tree. By the connection mentioned above, $(X_{n})_{n\geq 0}$
can be identified with an $(\alpha_{p},\alpha_{c})$-RWDE on $\mathbb{T}_{*}$.
We denote by $\mathbb{P}(\cdot)$ the annealed distribution of $(X_{n})_{n\geq
0}$ when we also average over the tree $\mathbb{T}_{*}$, and by $\mathbb{E}$
the associated expectation. To sum up, the walk $(X_{n})_{n\geq 0}$ can be
studied under three levels of randomness: under ${\rm P}^{\eta}$ (both the
tree $\mathbb{T}_{*}$ and the environment $(\eta_{e})_{e\in E}$ are fixed, the
walk is a Markov chain), under $\mathbf{P}$ (the tree $\mathbb{T}_{*}$ is
fixed and the walk is an $(\alpha_{p},\alpha_{c})$-ERRW on $\mathbb{T}_{*}$),
and under $\mathbb{P}$ where we average over everything. We point out that
what we defined is a directed ERRW on a tree, which corresponds, in the
setting of [17], to an undirected ERRW with weights
$(2\alpha_{p}-1,2\alpha_{c})$.

Let $(A_{i},1\leq i\leq\nu)$ have the distribution under $\mathbb{P}$ of

$\left(\frac{\eta(\rho,\rho
1)}{\eta(\rho,\rho_{*})},\cdots,\frac{\eta(\rho,\rho\nu(\rho))}{\eta(\rho,\rho_{*})}\right).$
(2)

From Lyons and Pemantle [12], we know that the walk $(X_{n})_{n\geq 0}$ is
transient $\mathbb{P}(\cdot|\mathcal{S})$-a.s. if and only if

$\inf_{t\in[0,1]}\mathbb{E}\left[\sum_{i=1}^{\nu}A_{i}^{t}\right]>1,$ (3)

which is specified in Proposition 2.6 in our case. Let $|x|$ be the generation
of the vertex $x$ and set $|\rho_{*}|:=-1$. Under
$\mathbb{P}(\cdot|\mathcal{S})$, the quantity

$v:=\lim_{n\to\infty}|X_{n}|/n$

is called speed of the random walk $(X_{n})_{n\geq 0}$. This limit exists
$\mathbb{P}(\cdot|\mathcal{S})$-a.s. indeed and is deterministic by [9].

Assuming that the offspring distribution has high enough moments, our first
result gives a necessary and sufficient condition for the speed $v$ to be
positive, so that the walk drifts towards infinity linearly. As far as we
know, the only available result was in the case $\alpha_{p}=1$,
$\alpha_{c}=1/2$ on a $d$-regular tree, $d\geq 2$ [1] (see also [6]). Note
that the ratios $(A_{i})_{1\leq i\leq\nu}$ in Dirichlet environment are not
bounded from above and below, so the general criteria for random walks in
random environment on Galton–Watson trees put forward in [1] cannot be
applied. Let $f(s):=\sum_{n\geq 0}s^{n}p_{n}$ denote the generating function
of the offspring distribution and $q$ the smallest root of $f(s)=s$ in
$[0,1]$, i.e. $q$ is the extinction probability $1-\mathbb{P}(\mathcal{S})$ of
the Galton–Watson tree. We introduce

$\displaystyle d:=\min\\{n\geq
1:p_{n}>0\\},\,r:=\sup\\{k:\mathbb{E}[A^{-k}]f^{\prime}(q)<1\\},$

where $A$ is a generic random variable distributed as $A_{1}$ conditioned on
$\nu\geq 1$.

######  Theorem 1.1.

Suppose that $m\in(1,\infty)$, that the $(\alpha_{p},\alpha_{c})$-ERRW
$(X_{n})_{n\geq 0}$ is transient, i.e. (3) holds, and that

$\mathbb{E}[\nu^{d\alpha_{c}+3+\alpha_{p}}]<\infty.$ (4)

The speed $v$ is positive if and only if:

  * 1.

$2r-\alpha_{c}+\alpha_{p}-1>0$ when $p_{0}=0,p_{1}>0$;

  * 2.

$(2d-1)\alpha_{c}+\alpha_{p}-1>0$ when $p_{0}=0,p_{1}=0$;

  * 3.

$r-\alpha_{c}+\alpha_{p}-1>0$ when $p_{0}>0$.

The second case is reminiscent of a criterion for positive speed given in [19]
in the case of the lattice $\mathbb{Z}^{k},k\geq 3$ in which the role of the
parameter $\kappa$ there would be played by the quantity
$2(\alpha_{p}+d\alpha_{c})-(\alpha_{p}+\alpha_{c})=(2d-1)\alpha_{c}+\alpha_{p}$.
The third case is equivalent to $(\alpha_{p}-1)/\alpha_{c}>f^{\prime}(q)$.
Taking $(\alpha_{p},\alpha_{c})=(\lambda\alpha,\alpha)$ and (informally)
making $\alpha$ go to $+\infty$, it boils down to $\lambda>f^{\prime}(q)$,
which agrees with the result of Lyons, Pemantle, and Peres [14] in the case of
$\lambda$-biased random walk.

Figure 1: We have $m=2$ for these graphs. Gray areas are where
$(\alpha_{p},\alpha_{c})$-ERRW has positive speed, while dashed areas are
where the transient walk has zero speed. The remaining areas correspond to the
region of recurrence. The first picture shows the effect of long pipe traps,
which only depends on $p_{1}$. (Note that in this case $f^{\prime}(q)=p_{1}$.)
The effect of traps is weak when $p_{0}=p_{1}=0$, as is shown in the second
graph. Finally, we can see from the third one that traps from leaves have a
stronger effect than traps from pipes.

We actually obtain a necessary and sufficient condition (without condition
(4)) for the positivity of the speed in terms of the conductance of the tree.
Recall that we can view $(X_{n})_{n}$ as a RWDE. Let $\tau_{x}:=\inf\\{n\geq
0:X_{n}=x\\}$ denote the hitting time of $x$ with $\inf\emptyset=\infty$. For
$x\in\mathbb{T}$, let

$\beta(x):={{\rm P}}_{x}^{\eta}(\tau_{x_{*}}=\infty),$ (5)

which is a functional of the tree $\mathbb{T}_{*}$ and the environment
$(\eta_{e})_{e}$. The random variable $\beta(\rho)$ is the so-called
conductance of the tree $\mathbb{T}_{*}$. Since $(X_{n})_{n\geq 0}$ is
supposed to be transient, $\beta(\rho)>0$ a.s. conditioned on $\mathbb{T}_{*}$
being infinite.

Define $\Phi:\mathbb{N}\rightarrow\mathbb{R}^{+}$ as

$\Phi(k):=\frac{\Gamma(\alpha_{p})\Gamma(\alpha_{c}+k+1)}{\Gamma(\alpha_{c}+1)\Gamma(\alpha_{p}+k)}.$
(6)

Our necessary and sufficient condition for the positivity of the speed reads
as follows.

######  Theorem 1.2.

Suppose that $m\in(1,\infty)$ and that the $(\alpha_{p},\alpha_{c})$-ERRW
$(X_{n})_{n\geq 0}$ is transient i.e. (3) holds. The speed $v$ is positive if
and only if

$\mathscr{C}:=\sum_{k\geq
0}\Phi(k)\mathbb{E}\left[\frac{(1-\beta(\rho))^{k+1}}{\eta(\rho,\rho^{*})}\right]\mathbb{E}\left[\beta(\rho)(1-\beta(\rho))^{k}\right]<\infty.$
(7)

Our next result is a formula for the speed $v$ of $(X_{n})_{n\geq 0}$. In the
standard case of $\lambda$-biased random walk on a Galton-Watson tree
conditioned on non-extinction, Lyons, Pemantle, and Peres find an explicit
speed formula when $\lambda=1$ [13] with the help of an invariant measure.
Note that the walk is a simple random walk in this case. For general bias
$\lambda$, [2] gives a formula for the speed in terms of the conductance of a
tree. We give a general formula for the speed of the
$(\alpha_{p},\alpha_{c})$-ERRW $(X_{n})_{n}$ which, as in [2], involves the
conductance $\beta(\rho)$.

For sake of concision, we let $\beta$ be a generic random variable with
distribution $\beta(\rho)$. Recall the definition of $(A_{i})_{1\leq
i\leq\nu}$ in (2) and let $\beta_{0},\beta_{1},\cdots$ be i.i.d. random
variables distributed as $\beta$, and independent of $(A_{i})_{1\leq
i\leq\nu}$. We introduce the hypergeometric function (see [3] for example)
${}_{2}F_{1}(1,\alpha_{c}+1;\alpha_{p};x):[0,1)\rightarrow\mathbb{R}^{+}$:

$_{2}F_{1}(1,\alpha_{c}+1;\alpha_{p};x):=\sum_{k\geq
0}\Phi(k)x^{k},\,x\in[0,1).$ (8)

We simply write $F(x)$ when there is no confusion.

######  Theorem 1.3.

Suppose that $m\in(1,\infty)$, that the $(\alpha_{p},\alpha_{c})$-ERRW
$(X_{n})_{n\geq 0}$ is transient i.e. (3) holds, and that (3.3) holds. Then
the speed $v$ is positive and can be expressed as

$\begin{split}&\mathbb{E}\left[\frac{\beta_{0}(\sum_{i=1}^{\nu}A_{i}+1)}{1+\sum_{i=1}^{\nu}A_{i}\beta_{i}}\times
F\left(\frac{1-\beta_{0}}{1+\sum_{i=1}^{\nu}A_{i}\beta_{i}}\right)\right]^{-1}\mathbb{E}\left[\frac{\beta_{0}(\sum_{i=1}^{\nu}A_{i}-1)}{1+\sum_{i=1}^{\nu}A_{i}\beta_{i}}\times
F\left(\frac{1-\beta_{0}}{1+\sum_{i=1}^{\nu}A_{i}\beta_{i}}\right)\right].\end{split}$
(9)

######  Corollary 1.4.

When $\alpha_{p}=\alpha_{c}=\alpha>0$, if (3) and (3.3) hold, the speed
formula reduces to

$\frac{\mathbb{E}\left[\beta_{0}{(\sum_{i=1}^{\nu}A_{i}-1)((1-\beta_{0})\alpha^{-1}+\beta_{0}+\sum_{i=1}^{\nu}A_{i}\beta_{i})}{(\beta_{0}+\sum_{i=1}^{\nu}A_{i}\beta_{i})^{-2}}\right]}{\mathbb{E}\left[\beta_{0}(\sum_{i=1}^{\nu}A_{i}+1){((1-\beta_{0})\alpha^{-1}+\beta_{0}+\sum_{i=1}^{\nu}A_{i}\beta_{i})}{(\beta_{0}+\sum_{i=1}^{\nu}A_{i}\beta_{i})^{-2}}\right]}.$
(10)

When $\alpha_{p}=1$, $\alpha_{c}=1/2$ and (3) holds, it reduces to

$\frac{\mathbb{E}\left[\beta_{0}(\sum_{i=1}^{\nu}A_{i}-1)\sqrt{1+\sum_{i=1}^{\nu}A_{i}\beta_{i}}(\beta_{0}+\sum_{i=1}^{\nu}A_{i}\beta_{i})^{-3/2}\right]}{\mathbb{E}\left[\beta_{0}(\sum_{i=1}^{\nu}A_{i}+1)\sqrt{1+\sum_{i=1}^{\nu}A_{i}\beta_{i}}(\beta_{0}+\sum_{i=1}^{\nu}A_{i}\beta_{i})^{-3/2}\right]}.$
(11)

The main tool of our paper is the invariant measure of the environment seen
from a particle, which is standard in the theory of random walks in random
environment. Using arguments from ergodic theory, this
invariantinvariantinvariant measure describes the asymptotic distribution of
the environment seen from the particle. The stationary measures have been
investigated in several models, like random walk in random environment (RWRE)
on $\mathbb{Z}$, see [5] for example; simple random walks on a Galton-Watson
tree in [13]; $\lambda$-biased random walks on a Galton-Watson tree in [2],
[11]; null recurrent biased random walks or RWRE on a Galton-Watson tree in
[18], [8]; continuous-time biased random walks on a Galton-Watson tree in [4];
RWDE on $\mathbb{Z}^{k},k\geq 3$ in [19], etc.

In this article, we give an expression of the invariant distribution of the
environment seen from $(X)_{n\geq 0}$. To do so, we need the concept of double
trees marked with a distinguished path. In words, double trees consist of the
gluing of two trees, the tree $\mathbb{T}^{+}_{*}$ standing for the subtree
rooted at the particle, and the tree $\mathbb{T}^{-}_{*}$ standing for the
part of the tree located below the particle. The distinguished path $\gamma$
represents the history of the walk up to the current time.

Let us give the stationary measure for the environment seen from the particle.
We first sample two independent Galton-Watson trees
$\mathbb{T}^{-}_{*},\mathbb{T}^{+}_{*}$, with the
$(\alpha_{p},\alpha_{c})$-initial weights. Then we create the double tree
$\mathbb{T}^{-}\rightleftharpoons\mathbb{T}^{+}$ by connecting the roots of
$\mathbb{T}^{-}_{*},\mathbb{T}^{+}_{*}$, denoted by $\rho^{-},\rho^{+}$
respectively (see Figure 2). In other words, we let
$\rho^{-}_{*}:=\rho^{+},\rho^{+}_{*}:=\rho^{-}$. We require that
$\alpha_{(\rho^{-},\rho^{+})}=\alpha_{(\rho^{+},\rho^{-})}=\alpha_{p}$ and the
other weights are the same as those on the original trees. We call
$e_{\rho}:=(\rho^{-},\rho^{+})$ the root edge.

Figure 2: A double tree with $(\alpha_{p},\alpha_{c})$-initial weights. We use
purple and green colors to distinguish $\mathbb{T}^{-}$ and $\mathbb{T}^{+}$.
One can see that the double tree weights are locally the same as those on a
Galton-Watson tree.

The double tree is a weighted directed graph, so we can define a Dirichlet
environment on it (see Figure 2). Let $Y=(Y_{n})_{n\geq 0}$ and
$X=(X_{n})_{n\geq 0}$ be two random walks on the double tree starting from
$\rho^{+}$ and $\rho^{-}$ respectively which are conditionally independent
given the Dirichlet environment (see Figure 3). We stress that, after
averaging over the Dirichlet environment, $Y$ and $X$ are not independent
anymore. Let $Rev((X_{n})_{n\geq 0})$ be the time-reverse of the path of
$(X_{n})_{n\geq 0}$, which is therefore indexed by $\mathbb{Z}_{-}$.

For $k\geq 0$, we concatenate the reversed path $Rev((X_{n})_{n\geq 0})$ with
the finite path $(Y_{l})_{0\leq n\leq k}$ and denote it by $Rev((X_{n})_{n\geq
0})\ast(Y_{n})_{0\leq n\leq k}$. Since $X$ is transient, this path ‘comes’
from the boundary of the tree $\mathbb{T}^{-}$ . Let
$\tau^{X}_{x}:=\inf\\{n>0,X_{n}=x\\}$ be the hitting time of a vertex $x$ on
the double tree for $X$. We call $\mu_{ER}^{(k)}$ the distribution of the
double tree with marked path

$\displaystyle\left(\mathbb{T}^{-}\rightleftharpoons\mathbb{T}^{+},Rev((X_{n})_{n\geq
0})\ast(Y_{n})_{0\leq n\leq k}\right).$

We define the distribution $\mu_{ER}$ on the space of double trees with marked
path by

$\displaystyle\mu_{ER}(\cdot)=\sum_{k=1}^{\infty}\Phi(N^{Y}_{e_{\rho}}(k))\textbf{1}_{\\{\tau^{X}_{\rho^{+}}=\infty,Y_{k}=\rho^{+}\\}}\mu_{ER}^{(k)}(\cdot)$
(12)

where the definition of the function $\Phi:\mathbb{N}\rightarrow\mathbb{R}$ is
given in (6). It defines an invariant measure for the environment seen from
the particle for the $(\alpha_{p},\alpha_{c})$-ERRW (See Corollary 3.10).

Figure 3: Two random walks $X$ and $Y$ on the double tree with weights in
Figure 2. After sampling the double tree and Dirichlet environment, we sample
$(X_{n})_{n\geq 0},(Y_{n})_{n\geq 0}$ independently. We use blue color to
indicate that we need to reverse the path of $(X_{n})_{n\geq 0}$.

The article is arranged as follows. In Section 2, we talk about regeneration
structure and give some properties of RWDE, especially RWDE on a Galton-Watson
tree. In Section 3, we extend the path reversal argument of [2] to our case
and characterize the environment seen from a particle when it is far away from
the root. We also prove Theorem 1.2 in this section and give the invariant
measure. In Section 4, we prove Theorem 1.3 and give the method of computing
(10) and (11). We also deduce the criteria for positive speed and prove
Theorem 1.1.
Acknowledgements: We would like to thank Elie Aïdékon for offering the
question and many important discussions.

##  2 Preliminaries

###  2.1 Facts about Regeneration Time

For a random walk $(X_{n})_{n\geq 0}$ on a Galton-Watson tree starting from
$\rho$, we call $\theta$ a fresh epoch if $X_{\theta}\not=X_{n}$ for all
$n<\theta$ and a regeneration epoch if additionally, $X_{\theta-1}\not=X_{n}$
for all $n\geq\theta$. More specifically, let $\theta_{0}:=0,\Theta_{0}:=0$.
For $k\geq 1$, let

$\theta_{k}:=\inf\\{n>\theta_{k-1}:X_{n}\not=X_{j},\forall 0\leq j<n\\}$

be the $k$-th fresh epoch, and

$\Theta_{k}:=\inf\\{n>\Theta_{k-1}:n\in\\{\theta_{i},i\geq
1\\},X_{j}\not=(X_{n})_{*},\forall j\geq n\\}$ (13)

be the $k$-th regeneration epoch. In [14, Section 3], properties of these
random times for biased random walk are given and these facts can be enhanced
to the proposition below.

######  Proposition 2.1.

For any transient random walk in random environment on a Galton-Watson tree
given non-extinction, there are infinitely many regeneration epochs a.s.
Moreover $\\{\Theta_{k+1}-\Theta_{k}\\}_{k\geq 1}$ are i.i.d. as are the
increments $\\{|X_{\Theta_{k+1}}|-|X_{\Theta_{k}}|\\}_{k\geq 1}$.

We omit the proof of the proposition since it is similar to the one in [14].

Let $\mathbb{E}_{\rho}[\cdot]=\mathbb{E}[\cdot|X_{0}=\rho]$. As proved in [9],
the speed of random walk in random environment is a.s. the deterministic
constant

$\displaystyle\dfrac{\mathbb{E}_{\rho}[|X_{\Theta_{2}}|-|X_{\Theta_{1}}||\mathcal{S}]}{\mathbb{E}_{\rho}[\Theta_{2}-\Theta_{1}|\mathcal{S}]},$
(14)

where the numerator
$\mathbb{E}_{\rho}[|X_{\Theta_{2}}|-|X_{\Theta_{1}}||\mathcal{S}]$ is always
finite. Therefore, the speed is positive if and only if
$\mathbb{E}_{\rho}[\Theta_{2}-\Theta_{1}|\mathcal{S}]<\infty$. We sum up these
results as a fact.

######  Fact 2.2.

For a transient RWRE $(X_{n})_{n\geq 0}$ on a Galton-Watson tree, the
following statements are equivalent:

  1. 1.

$\lim_{n\to\infty}|X_{n}|/n$ is deterministic and positive;

  2. 2.

$\mathbb{E}_{\rho}[\Theta_{2}-\Theta_{1}|\mathcal{S}]<\infty$.

In particular, the speed is deterministic for RWDE, and we deduce that the
speed of ERRW is identical to that of RWDE.

###  2.2 Facts about RWDE

This section covers some basic properties of Dirichlet environment. See [20]
for a more thorough review.

Let $p$ be a fixed positive integer and $(\alpha_{1},\cdots,\alpha_{p})$ be
positive real numbers. We say that the random vector
$D(\alpha_{1}\cdots\alpha_{p}):=(D_{1},\cdots,D_{p})$ has Dirichlet
distribution with parameter $(\alpha_{1},\cdots,\alpha_{p})$ if it has density

$\frac{\Gamma(\sum_{j=1}^{p}\alpha_{j})}{\prod_{j=1}^{p}\Gamma(\alpha_{j})}\prod_{j=1}^{p}(x_{j}^{\alpha_{j}-1}\textbf{1}_{\\{0<x_{j}<1\\}})\textbf{1}_{\\{\sum
x_{j}=1\\}}.$ (15)

We denote by $Gamma(\alpha,r)$ the gamma distribution with parameters $\alpha$
and $r$ whose density is

$\displaystyle\frac{r^{\alpha}}{\Gamma(\alpha)}x^{\alpha-1}e^{-rx}\textbf{1}_{\\{x\geq
0\\}}.$

By computation, we have the following lemma.

######  Lemma 2.3.

If $\Gamma_{i}\sim Gamma(\alpha_{i},1),1\leq i\leq p$ are mutually independent
random variables, then $(\Gamma_{i}/\sum_{j=1}^{p}\Gamma_{j})_{1\leq i\leq
p}\sim D(\alpha_{1}\cdots\alpha_{p})$. Besides, for $\alpha_{j}+s_{j}>0,1\leq
j\leq p$,

${{\mathbf{E}}}\left[\prod_{j=1}^{p}(D_{j})^{s_{j}}\right]=\frac{\Gamma(\sum_{j=1}^{p}\alpha_{j})}{\prod_{j=1}^{p}\Gamma(\alpha_{j})}\frac{\prod_{j=1}^{p}\Gamma(\alpha_{j}+s_{j})}{\Gamma(\sum_{j=1}^{p}\alpha_{j}+\sum_{j=1}^{p}s_{j})}.$

As in the beginning of the introduction, let $G=(V,E)$ be an oriented graph
and $(\alpha_{e})_{e\in E}$ a set of positive deterministic weights. Recall
that (1) defines an ERRW on $G$, a self-interacting model without the Markov
property, under the measure $\mathbf{P}$. For a path $\gamma$ and an edge $e$,
we denote by $N_{e}(\gamma)$ the local time of $e$ in $\gamma$ which is the
number of times that $e$ appears in $\gamma$.

######  Lemma 2.4.

For a path $\gamma$ with length $n$ (i.e. with $n$ edges) on $G$,

$\mathbf{P}((X_{k})_{0\leq k\leq n}=\gamma)=\prod_{y\in
V}\frac{\Gamma(\sum_{\underline{e}=y}\alpha_{e})}{\Gamma(\sum_{\underline{e}=y}\alpha_{e}+N_{e}(\gamma))}\prod_{e\in
E}\frac{\Gamma(\alpha_{e}+N_{e}(\gamma))}{\Gamma(\alpha_{e})}.$ (16)

The right-hand side of (16) is well-defined by multiplying terms of all
vertices and edges on the whole graph instead of just those in $\gamma$, since
for $e\notin\gamma$, $N_{e}(\gamma)=0$.

Next, we consider two paths on $G$. Let $\alpha+N(\gamma)$ denote the weights
$(\alpha_{e}+N_{e}(\gamma))_{e\in E}$. When the graph $G$ and weights
$(\alpha_{e})_{e\in E}$ are fixed, we define ${\rm DE}^{G}(\cdot|\alpha)$
(resp. $\mathbf{E}_{DE}^{G}(\cdot|\alpha)$) as the probability measure (resp.
expectation) corresponding to the Dirichlet environment on $G$ with weights
$(\alpha_{e})_{e\in E}$. Sometimes we write $\mathbf{E}_{DE}(\cdot|\alpha)$
(resp. $\mathbf{E}_{DE}^{G}(\cdot)$) when the graph (resp. weights) is clear
from the context.

######  Lemma 2.5.

Let $G=(V,E)$ be an arbitrary graph. For two paths $\gamma_{1},\gamma_{2}$ on
$G$ with weight $(\alpha_{e})_{e\in E}$, we have

$\mathbf{E}_{DE}[{{\rm P}}^{\eta}(\gamma_{1}){{\rm
P}}^{\eta}(\gamma_{2})|\alpha]=\mathbf{P}(\gamma_{2}|\alpha+N(\gamma_{1}))\mathbf{P}(\gamma_{1}|\alpha)=\mathbf{P}(\gamma_{1}|\alpha+N(\gamma_{2}))\mathbf{P}(\gamma_{2}|\alpha).$

###### Proof.

We only need to prove the first equality.

$\begin{split}&\mathbf{E}_{DE}[{{\rm P}}^{\eta}(\gamma_{1}){{\rm
P}}^{\eta}(\gamma_{2})|\alpha]=\mathbf{E}_{DE}\left[\prod_{e\in
E}\eta_{e}^{N_{e}(\gamma_{1})+N_{e}(\gamma_{2})}\right]\\\ &=\prod_{y\in
V}\frac{\Gamma(\sum_{\underline{e}=y}\alpha_{e})}{\Gamma(\sum_{\underline{e}=y}\alpha_{e}+N_{e}(\gamma_{1})+N_{e}(\gamma_{2}))}\prod_{e\in
E}\frac{\Gamma(\alpha_{e}+N_{e}(\gamma_{1})+N_{e}(\gamma_{2}))}{\Gamma(\alpha_{e})}\\\
&={\mathbf{P}}(\gamma_{1}|\alpha)\prod_{y\in
V}\frac{\Gamma(\sum_{\underline{e}=y}\alpha_{e}+N_{e}(\gamma_{1}))}{\Gamma(\sum_{\underline{e}=y}\alpha_{e}+N_{e}(\gamma_{1})+N_{e}(\gamma_{2}))}\prod_{e\in
E}\frac{\Gamma(\alpha_{e}+N_{e}(\gamma_{1})+N_{e}(\gamma_{2}))}{\Gamma(\alpha_{e}+N_{e}(\gamma_{1}))}\\\
&={\mathbf{P}}(\gamma_{2}|\alpha+N(\gamma_{1})){\mathbf{P}}(\gamma_{1}|\alpha).\end{split}$

∎

Lemma 2.5 shows that, in the same environment, the information one walk gives
to the other is visualized as edge local times added to the weights after
averaging the environment.

For completeness, we give a specific account of conditions on transience of
RWDE on a Galton-Watson tree. Recall that $A_{i},1\leq i\leq\nu$ are,
according to (2), ratios of Dirichlet random variables. Lyons and Pemantle
[12] show that a random walk in random environment is transient if and only if
$\inf_{t\in[0,1]}\mathbb{E}[\sum_{i=1}^{\nu}A_{i}^{t}]>1$, that is in our case

$\inf_{t\in[0,1\wedge\alpha_{p}]}\frac{\Gamma(\alpha_{p}-t)\Gamma(\alpha_{c}+t)}{\Gamma(\alpha_{c})\Gamma(\alpha_{p})}>\frac{1}{m}.$
(17)

By taking the logarithm derivative with respect to $t$ on the left-hand side,
we get $-\psi(\alpha_{p}-t)+\psi(\alpha_{c}+t)$, where
$\psi:=\Gamma^{\prime}/\Gamma$ is a strictly increasing function named digamma
function. Hence the minimum is attained at
$t=0\vee\frac{\alpha_{p}-\alpha_{c}}{2}\wedge 1$. We consider three cases:
$\alpha_{p}\leq\alpha_{c}$, $\alpha_{p}\geq\alpha_{c}+2$ and
$\alpha_{p}\in(\alpha_{c},\alpha_{c}+2)$ separately.

  * 1.

When $\alpha_{p}\leq\alpha_{c}$, the minimum is reached at $0$ and RWDE is
always transient.

  * 2.

When $\alpha_{p}\geq\alpha_{c}+2$, the minimum is reached at $1$, so RWDE is
transient if and only if $\alpha_{p}<m\alpha_{c}+1$. In this case,
$\alpha_{c}\leq\frac{1}{m-1}$ always implies recurrence.

  * 3.

Finally let us focus on the last case
$\alpha_{p}\in(\alpha_{c},\alpha_{c}+2)$, where the minimum is reached at
$\frac{\alpha_{p}-\alpha_{c}}{2}$. We plug $t=\frac{\alpha_{p}-\alpha_{c}}{2}$
into (17) with $\alpha_{c}$ fixed, obtaining a function $g(\alpha_{p})$. By
taking the logarithm derivative of $g(\alpha_{p})$ with respect to
$\alpha_{p}$, we have

$\frac{\mathrm{d}}{\mathrm{d}\alpha_{p}}\log
g(\alpha_{p})=\frac{\mathrm{d}}{\mathrm{d}\alpha_{p}}\log\left(\frac{\Gamma(\frac{\alpha_{p}+\alpha_{c}}{2})^{2}}{\Gamma(\alpha_{p})\Gamma(\alpha_{c})}\right)=\psi\left(\frac{\alpha_{p}+\alpha_{c}}{2}\right)-\psi(\alpha_{p})\leq
0.$

At once we see that the minimum of $g(\alpha_{p})$ for all
$\alpha_{p}\in[\alpha_{c},\alpha_{c}+2]$ is reached at
$\alpha_{p}=\alpha_{c}+2$. We take $\alpha_{p}=\alpha_{c}+2$ and then
$g(\alpha_{p})=g(\alpha_{c}+2)>\frac{1}{m}$ becomes
$\alpha_{c}>\frac{1}{m-1}$. Therefore, when
$\frac{1}{m-1}<\alpha_{c}<\alpha_{p}<\alpha_{c}+2$, the walk is always
transient. When $\alpha_{c}\leq\frac{1}{m-1}$ there will be a critical point
$\phi_{0}(\alpha_{c})$ such that $g(\phi_{0}(\alpha_{c}))=\frac{1}{m}$. The
function $g(\alpha_{p})$ is decreasing with respect to $\alpha_{p}$, so the
walk is transient only when $\alpha_{p}<\phi_{0}(\alpha_{c})$.

In summary, we have the following proposition.

######  Proposition 2.6.

Let $(X_{n})_{n\geq 0}$ be a random walk in an
$(\alpha_{p},\alpha_{c})$-Dirichlet environment on a Galton-Watson tree
conditioned on non-extinction.

  * (a)

When $\alpha_{c}>\frac{1}{m-1}$, if $\alpha_{p}<m\alpha_{c}+1$ then RWDE is
transient and otherwise recurrent;

  * (b)

when $\alpha_{c}\leq\frac{1}{m-1}$, if $\alpha_{p}<\phi_{0}(\alpha_{c})$ then
RWDE is transient and otherwise recurrent, where
$\phi_{0}(\alpha_{c})\in(\alpha_{c},\alpha_{c}+2]$ satisfies

$\frac{\Gamma(\frac{\phi_{0}(\alpha_{c})+\alpha_{c}}{2})^{2}}{\Gamma(\phi_{0}(\alpha_{c}))\Gamma(\alpha_{c})}=\frac{1}{m}.$

##  3 Asymptotic distribution of the environment seen from the particle

###  3.1 Trees, Paths and Weights

Following Neveu [16], let $\mathcal{U}:=\\{\rho\\}\cup\bigcup_{n\geq
1}(\mathbb{N}^{+})^{n}$ denote the set of words and $\rho$ serves as an empty
word. If $u\neq\rho$, we denote by $u_{*}$ the parent of $u$, which is the
word $\rho i_{1}i_{2}\dots i_{n-1}$ if $u=\rho i_{1}i_{2}\dots i_{n}$. We
define $T$ as a subset of $\mathcal{U}$ s.t.

  * 1.

$\rho\in T$,

  * 2.

if $x\in T\backslash\\{\rho\\}$, then $x_{*}\in T$,

  * 3.

if $x=\rho i_{1}\cdots i_{n}\in T\backslash\\{\rho\\}$, then any word $\rho
i_{1}\cdots i_{n-1}j$ with $j\leq i_{n}$ belongs to $T$.

Given $x,y\in\mathcal{U}$, we write $x\preceq y$ if $x=y$ or
$y=xj_{1}j_{2}\cdots j_{n}$ i.e. $x$ is an ancestor of $y$. Set $x\prec y$ if
$x\preceq y$ and $x\not=y$. We create a new tree called $T_{*}$ by adding a
vertex $\rho_{*}$ to $T$ as the parent of $\rho$. For all $x\in T$,
$\rho_{*}\prec\rho\preceq x$.

Then we define a double tree $T^{-}\rightleftharpoons T^{+}$ introduced in [2,
Section 2.2]. Intuitively, we first pick two trees $T^{-}$ and $T^{+}$ with
root $\rho^{-}$ and $\rho^{+}$, and then artificially connect $\rho^{-}$ and
$\rho^{+}$. See Figure 2. We use the double tree to study the environment seen
from the particle. Suppose a transient random walk starts from the root $\rho$
and moves on the tree $T$. After a fairly long time, the walk would be far
away from the root, and the tree seen from the current location looks like a
double tree $T^{-}\rightleftharpoons T^{+}$. The starting point of the walk is
somewhere high on $T^{-}$. We call the random double tree a Galton-Watson
double tree if $\mathbb{T}^{-}$ and $\mathbb{T}^{+}$ are i.i.d Galton-Watson
trees.

Now we represent vertices on a double tree by two sets of words
$\mathcal{U}^{+}$ and $\mathcal{U}^{-}$. Specifically, we denote by
$\rho^{+}i_{1}\cdots i_{n}\in\mathcal{U}^{+}$ (resp. $\rho^{-}i_{1}\cdots
i_{n}\in\mathcal{U}^{-}$ ) the vertex on the double tree
$T^{-}\rightleftharpoons T^{+}\subset\mathcal{U}^{-}\cup\mathcal{U}^{+}$
corresponding to $\rho i_{1}\cdots i_{n}$ on $T^{+}$ (resp. $T^{-}$ ). If
$x\in T^{+}\backslash\\{\rho^{+}\\}$ (resp. $T^{-}\backslash\\{\rho^{-}\\}$),
we set the parent of $x$, also denoted by $x_{*}$, as its parent on $T^{+}$
(resp. $T^{-}$). We also assume that $(\rho^{+})_{*}=\rho^{-}$ and
$(\rho^{-})_{*}=\rho^{+}$. At last, we stress that afterward we always refer
to a part of the corresponding double tree when we say $x\in T^{+}$, i.e. $x$
is in the $T^{+}$ part of $T^{-}\rightleftharpoons T^{+}$.

Both RWDE and ERRW require specific parameter settings called edge weights.
Parameters $(\alpha_{e})_{e}$ on a double tree $T^{-}\rightleftharpoons T^{+}$
should satisfy

$\alpha_{e}=\left\\{\begin{array}[]{ll}\alpha_{p}&e=(x,x_{*})\text{ for some
}x\in T^{-}\rightleftharpoons T^{+},\\\
\alpha_{c}&\text{otherwise}.\end{array}\right.$ (18)

We say a double tree has $(\alpha_{p},\alpha_{c})$ environment if the weights
of edges satisfy (18).

For each vertex $x\in T^{-}\rightleftharpoons T^{+}$, we assign a group of
Dirichlet random variables $(\eta_{e})_{\underline{e}=x}$ with parameters
$(\alpha_{e})_{\underline{e}=x}$ to edges starting from $x$. Note that for an
arbitrary vertex $x\in T^{-}\rightleftharpoons T^{+}$, there is only one edge
starting from $x$ having weight $\alpha_{p}$.

The transition law of ERRW is determined by the trajectory of the walk. We
call a sequence of words
$\gamma=(y_{i})_{a<i<b},y_{i}\in\mathcal{U}^{-}\cup\mathcal{U}^{+}$ a path if
$y_{i}$ and $y_{i-1}$ are adjacent for $a<i-1<i<b$, where
$a,b\in\mathbb{R}\cup\\{-\infty,\infty\\}$. We say $\gamma$ is left-finite
(resp. right-finite) if $a>-\infty$ (resp. $b<\infty$). Here we do not care
about specific indices of the path, i.e. $(y_{i})_{i\leq 0}$ and
$(y_{i-1})_{i\leq 1}$ are considered the same. We define

$\Omega_{\gamma}:=\\{\gamma=(y_{i})_{i\leq 0},y_{0}=\rho^{+};\exists
M,s.t.\text{ for }i<M,y_{i}=\rho^{-}y_{i}^{(1)}\dots y_{i}^{(n_{i})}\text{ and
}n_{i}\rightarrow\infty\text{ as }i\rightarrow-\infty\\}.$

The set $\Omega_{\gamma}$ contains paths coming from one infinite end of
$T^{-}$.

For a right-finite $\gamma^{(a)}$ and a left-finite $\gamma^{(b)}$, such that
the last word of $\gamma^{(a)}$ is adjacent to the first word of
$\gamma^{(b)}$, we can define their concatenation, denoted by
$\gamma^{(a)}\ast\gamma^{(b)}$. More precisely, if
$\gamma^{(a)}=(y^{(a)}_{i})_{i\leq 0}$ and $\gamma^{(b)}=(y^{(b)}_{i})_{i\geq
0}$, let
$\gamma^{(a)}\ast\gamma^{(b)}:=(\dots,y^{(a)}_{-1},y^{(a)}_{0},y^{(b)}_{0},y^{(b)}_{1},\dots)$.
We also define $Rev(\gamma)$ as the reverse of a path $\gamma$: if
$\gamma=(y_{i})_{i\geq 0}$, then $Rev(\gamma):=(y_{-i})_{i\leq 0}$.

###  3.2 Environment Seen from Fresh Point

Before showing the convergence in distribution of what a particle sees, we
first present some intuitive lemmas similar to those in [2]. Recall that we
define $T_{*}$ as $T\cup\\{\rho_{*}\\}$. Given a word $x\in\mathcal{U}$, let
$T_{x}$ be the subtree in $T_{*}$ rooted at $x$ (that consists of words
$y\in\mathcal{U}$ such that $xy\in T$) and $xT_{x}$ be the tree composed of
words $\\{xy,y\in T_{x}\\}$. Also, set $T^{<x}_{*}$ as the tree obtained by
removing $xT_{x}$ from $T_{*}$. We denote by $T_{*}^{\leq x}$ the tree
obtained from $T^{<x}_{*}$ by adding the word $x$. If $x\notin T$, let $T_{x}$
and $T^{\leq x}_{*}$ be the empty set.

Now we define $\Psi_{x}$ as a map from a tree $T_{*}$ to a double tree that
preserves the connection of vertices. We map $x_{*}$ to $\rho^{-}$and $x$ to
$\rho^{+}$, that is to say, the root edge of $\Psi_{x}(T_{*})$ is
$(\Psi_{x}(x_{*}),\Psi_{x}(x))$. The image of $T_{*}^{\leq x}$,
$\Psi_{x}(T_{*}^{\leq x})$, can be seen as the backward tree at $x$ defined in
[2, Section 2.3]. As for $xT_{x}$, a vertex $y=xi_{1}\dots i_{n}$ is mapped to
$\Psi_{x}(xy):=\rho^{+}i_{1}\dots i_{n}$. An intuitive picture of $\Psi_{x}$
is to hang the tree at vertex $x$ instead of $\rho$. We denote by $\hat{x}$
the word $\Psi_{x}(\rho_{*})$. When $x\not\in T_{*}$, let $\Psi_{x}(T_{*})$ be
the empty set.

######  Lemma 3.1.

[2, Lemma 2.1] Given $x\in\mathcal{U}$ and a Galton-Watson tree $\mathbb{T}$,
the distribution of $\Psi_{x}(\mathbb{T}_{*}^{\leq x})$ and
$\mathbb{T}_{*}^{\leq\hat{x}}$ are the same.

We fix the tree $T$ and specify the weight of each edge on these trees. We
denote a directed edge by $e:=(\underline{e},\overline{e})$ and the reversed
one by $\check{e}:=(\overline{e},\underline{e})$. Also, let
$\check{\gamma}:=Rev(\gamma)$ be the reverse of the path $\gamma$. By
definition, $\Psi_{x}(e)=(\Psi_{x}(\underline{e}),\Psi_{x}(\overline{e}))$ for
$\underline{e}\in T_{*}$. Define

$R_{x}:=\\{e:\rho_{*}\preceq\overline{e}\preceq
x,\rho_{*}\prec\underline{e}\prec x\\}$

and

$\alpha^{\prime}_{\Psi_{x}(e)}:=\left\\{\begin{array}[]{ll}\alpha_{\check{e}}&e\in
R_{x},\\\ \alpha_{e}&\text{otherwise}.\end{array}\right.$

When $x=\rho 11$, for example, $R_{\rho 11}=\\{(\rho,\rho
1),(\rho,\rho_{*}),(\rho 1,\rho 11),(\rho 1,\rho)\\}$.

Figure 4: Trees $T_{*}$ and $\Psi_{\rho 11}(T_{*})$ with edge weights on them.
The purple part and green part of $\Psi_{\rho 11}(T_{*})$ correspond to
$T^{-}$ and $T^{+}$ in the double tree respectively (recall Figure 2).
Therefore, one can consider $\Psi$ as the map from a tree to a double tree.

We list here some basic facts about edge local times.

######  Fact 3.2.

For any fixed tree $T_{*}$, any vertex $x\in T$, and any path
$\gamma=(y_{i})_{0\leq i\leq n}$ on the tree such that
$y_{0}=\rho_{*},y_{n}=x$, we have

  1. (1)

for any edge $e$ such that $\underline{e}\in T_{*}$,
$N_{e}(\check{\gamma})=N_{\check{e}}(\gamma)$;

  2. (2)

for any edge $\underline{e}\in T_{*}$,
$N_{\Psi_{x}(e)}(\Psi_{x}(\gamma))=N_{e}(\gamma)$, i.e. $\Psi_{x}$ does not
change the edge local times;

  3. (3)

for any vertex $y\in T_{*}\backslash\\{\rho_{*},x\\}$,
$\sum_{\underline{e}=y}N_{e}(\gamma)=\sum_{\overline{e}=y}N_{e}(\gamma)$, i.e.
inflow equals outflow except for the source and sink;

  4. (4)

for any edge $e\not\in R_{x}\cup\\{(\rho_{*},\rho),(x,x_{*})\\}$,
$N_{e}(\gamma)=N_{\check{e}}(\gamma)$ since trees are acyclic.

Figure 5: Left: $\gamma$ (red path) on $T_{*}^{\leq\rho 11}$. Right:
$\Psi_{\rho 11}(\check{\gamma})$ (blue path) on $\Psi_{\rho
11}(T_{*}^{\leq\rho 11})$. The black part of the tree is $R_{x}$, where we
exchange the weights; the weights of the gray part stay the same. We use blue
color to indicate that the path is reversed.

For any graph $G$ with edge weights $(\alpha_{e})_{e\in E}$, we denote by
$\mathbf{P}^{G}(\cdot|\alpha)$ the law of the associated ERRW on $G$ for
clarity. Sometimes we write $\mathbf{P}(\cdot|\alpha)$ (resp.
$\mathbf{P}^{G}(\cdot)$) when there is no confusion about the graph (resp.
weight). For a fixed path $\gamma=(y_{i})_{0\leq i\leq n}$, we simplify
$\mathbf{P}((X_{i})_{0\leq i\leq n}=\gamma)$ as $\mathbf{P}(\gamma)$. For
$\gamma=(y_{i})_{i\geq 0}$, we define $\gamma|_{\geq 1}$ as $(y_{i})_{i\geq
1}$.

######  Remark 3.3.

In the following lemma, we use general $(\alpha_{e})_{e}$ instead of
$(\alpha_{p},\alpha_{c})$ since we need the general setting for a later proof.
As for the $(\alpha_{p},\alpha_{c})$-case, the ratio is just 1. It also
explains why we do not consider the case when edges pointing towards offspring
have different weights $\alpha_{c,1},\cdots,\alpha_{c,{\nu}}$.

######  Lemma 3.4.

Fix a tree $T_{*}$ and consider ERRW on $T_{*}^{\leq x}$ and
$\Psi_{x}(T_{*}^{\leq x})$. Take a finite path $\gamma=(y_{i})_{0\leq i\leq
n}$ such that $y_{0}=\rho_{*},y_{n}=x,y_{i}\not\in\\{\rho_{*},x\\},1\leq i\leq
n-1$. Then we have

$\mathbf{P}^{T_{*}^{\leq x}}(\gamma|\alpha)=\mathbf{P}^{T_{*}^{\leq
x}}(\gamma|_{\geq
1}|\alpha)=\frac{\alpha_{(x_{*},x)}}{\alpha_{(\rho_{*},\rho)}}\mathbf{P}^{\Psi_{x}(T_{*}^{\leq
x})}(\Psi_{x}(\check{\gamma})|_{\geq 1}|\alpha^{\prime}),$ (19)

if $(\alpha_{e})_{\underline{e}\in T_{*}^{\leq x}}$ satisfies the condition
that

$\displaystyle\alpha_{(y,y_{*})}+\alpha_{(y,yj)}=\alpha_{(y_{*},y)}+\alpha_{(yj,y)},\text{
for all }y\text{ and }j\text{ s.t. }\rho\preceq y\prec yj\preceq x.$ (20)

###### Proof.

We call $N_{\Psi_{x}(e)}(\Psi_{x}(\check{\gamma})|_{\geq 1})$ the edge local
time of $\Psi_{x}(e)$ w.r.t. path $\Psi_{x}(\check{\gamma})|_{\geq 1}$. It is
easy to check that equation (20) implies

$\sum_{\underline{e}=y}\alpha_{e}=\sum_{\underline{e}=y}\alpha_{\Psi_{x}(e)}^{\prime},\,y\in
T\backslash\\{x\\},$ (21)

since
$\alpha_{(y,y_{*})}+\alpha_{(y,yj)}=\alpha_{(y_{*},y)}+\alpha_{(yj,y)}=\alpha_{\Psi_{x}((y,y_{*}))}^{\prime}+\alpha_{\Psi_{x}((y,yj))}^{\prime}$
for $\rho\preceq y\prec yj\preceq x$. According to Lemma 2.4, we have

$\begin{split}\mathbf{P}^{T_{*}^{\leq x}}(\gamma|\alpha)&=\prod_{y\in
T_{*}}\frac{\Gamma(\sum_{\underline{e}=y}\alpha_{e})}{\Gamma(\sum_{\underline{e}=y}\alpha_{e}+N_{e}(\gamma))}\prod_{\underline{e}\in
T_{*}}\frac{\Gamma(\alpha_{e}+N_{e}(\gamma))}{\Gamma(\alpha_{e})}\\\
&=\prod_{y\in
T^{<x}}\frac{\Gamma(\sum_{\underline{e}=y}\alpha_{e})}{\Gamma(\sum_{\underline{e}=y}\alpha_{e}+N_{e}(\gamma))}\prod_{\underline{e}\in
T^{<x}}\frac{\Gamma(\alpha_{e}+N_{e}(\gamma))}{\Gamma(\alpha_{e})},\end{split}$

and

$\begin{split}&\mathbf{P}^{\Psi_{x}(T_{*}^{\leq
x})}(\Psi_{x}(\check{\gamma})|_{\geq 1}|\alpha^{\prime})\\\
=&\prod_{y\in\Psi_{x}(T_{*})}\frac{\Gamma(\sum_{\underline{e}=y}\alpha^{\prime}_{e})}{\Gamma(\sum_{\underline{e}=y}\alpha^{\prime}_{e}+N_{e}(\Psi_{x}(\check{\gamma})|_{\geq
1}))}\prod_{\underline{e}\in\Psi_{x}(T_{*})}\frac{\Gamma(\alpha^{\prime}_{e}+N_{e}(\Psi_{x}(\check{\gamma})|_{\geq
1}))}{\Gamma(\alpha^{\prime}_{e})}\\\ =&\prod_{y\in
T_{*}}\frac{\Gamma(\sum_{\underline{e}=y}\alpha^{\prime}_{\Psi_{x}(e)})}{\Gamma(\sum_{\underline{e}=y}\alpha^{\prime}_{\Psi_{x}(e)}+N_{\Psi_{x}(e)}(\Psi_{x}(\check{\gamma})|_{\geq
1}))}\prod_{\underline{e}\in
T_{*}}\frac{\Gamma(\alpha^{\prime}_{\Psi_{x}(e)}+N_{\Psi_{x}(e)}(\Psi_{x}(\check{\gamma})|_{\geq
1}))}{\Gamma(\alpha^{\prime}_{\Psi_{x}(e)})}\\\ =&\prod_{y\in
T_{*}^{<x}}\frac{\Gamma(\sum_{\underline{e}=y}\alpha^{\prime}_{\Psi_{x}(e)})}{\Gamma(\sum_{\underline{e}=y}\alpha^{\prime}_{\Psi_{x}(e)}+N_{\Psi_{x}(e)}(\Psi_{x}(\check{\gamma})))}\prod_{\underline{e}\in
T_{*}^{<x}}\frac{\Gamma(\alpha^{\prime}_{\Psi_{x}(e)}+N_{\Psi_{x}(e)}(\Psi_{x}(\check{\gamma})))}{\Gamma(\alpha^{\prime}_{\Psi_{x}(e)})},\end{split}$

where the second line is obtained by the definition of $\Psi_{x}$.

Since
$N_{\Psi_{x}(e)}(\Psi_{x}(\check{\gamma}))=N_{e}(\check{\gamma})=N_{\check{e}}(\gamma)$
for each edge $\underline{e}\in T_{*}$ from Fact 3.2 (2) and (1),

$\displaystyle\prod_{y\in
T_{*}^{<x}}\frac{\Gamma(\sum_{\underline{e}=y}\alpha^{\prime}_{\Psi_{x}(e)})}{\Gamma(\sum_{\underline{e}=y}\alpha^{\prime}_{\Psi_{x}(e)}+N_{\Psi_{x}(e)}(\Psi_{x}(\check{\gamma})))}\prod_{\underline{e}\in
T_{*}^{<x}}\frac{\Gamma(\alpha^{\prime}_{\Psi_{x}(e)}+N_{\Psi_{x}(e)}(\Psi_{x}(\check{\gamma})))}{\Gamma(\alpha^{\prime}_{\Psi_{x}(e)})}$
$\displaystyle=$ $\displaystyle\prod_{y\in
T_{*}^{<x}}\frac{\Gamma(\sum_{\underline{e}=y}\alpha^{\prime}_{\Psi_{x}(e)})}{\Gamma(\sum_{\underline{e}=y}\alpha^{\prime}_{\Psi_{x}(e)}+N_{\check{e}}(\gamma))}\prod_{\underline{e}\in
T_{*}^{<x}}\frac{\Gamma(\alpha^{\prime}_{\Psi_{x}(e)}+N_{\check{e}}(\gamma))}{\Gamma(\alpha^{\prime}_{\Psi_{x}(e)})}$
$\displaystyle=$ $\displaystyle\prod_{y\in
T^{<x}}\frac{\Gamma(\sum_{\underline{e}=y}\alpha^{\prime}_{\Psi_{x}(e)})}{\Gamma(\sum_{\underline{e}=y}\alpha^{\prime}_{\Psi_{x}(e)}+N_{\check{e}}(\gamma))}\prod_{\underline{e}\in
T_{*}^{<x}}\frac{\Gamma(\alpha^{\prime}_{\Psi_{x}(e)}+N_{\check{e}}(\gamma))}{\Gamma(\alpha^{\prime}_{\Psi_{x}(e)})}.$

The last line follows from the fact that $N_{(\rho,\rho_{*})}(\gamma)=0$.

For $y\notin\\{\rho_{*},x\\}$, it holds that
$\sum_{\underline{e}=y}N_{\check{e}}(\gamma)=\sum_{\overline{e}=y}N_{e}(\gamma)=\sum_{\underline{e}=y}N_{e}(\gamma)$
by Fact 3.2 (3). Therefore, together with (21), we have

$\prod_{y\in
T^{<x}}\frac{\Gamma(\sum_{\underline{e}=y}\alpha^{\prime}_{\Psi_{x}(e)})}{\Gamma(\sum_{\underline{e}=y}\alpha^{\prime}_{\Psi_{x}(e)}+N_{\check{e}}(\gamma))}=\prod_{y\in
T^{<x}}\frac{\Gamma(\sum_{\underline{e}=y}\alpha_{e})}{\Gamma(\sum_{\underline{e}=y}\alpha_{e}+N_{e}(\gamma))}.$

We also have $N_{e}(\gamma)=N_{\check{e}}(\gamma),e\not\in
R_{x}\cup\\{(\rho_{*},\rho),(x,x_{*})\\}$ (Fact 3.2(4)), and for $e\not\in
R_{x}\cup\\{(\rho_{*},\rho),(x,x_{*})\\}$,
$\alpha^{\prime}_{\Psi_{x}(e)}=\alpha_{e}$ by definition. Hence,

$\prod_{e\not\in
R_{x}\cup\\{(\rho_{*},\rho),(x,x_{*})\\}}\frac{\Gamma(\alpha^{\prime}_{\Psi_{x}(e)}+N_{\check{e}}(\gamma))}{\Gamma(\alpha^{\prime}_{\Psi_{x}(e)})}=\prod_{e\not\in
R_{x}\cup\\{(\rho_{*},\rho),(x,x_{*})\\}}\frac{\Gamma(\alpha_{e}+N_{e}(\gamma))}{\Gamma(\alpha_{e})}.$

Finally, for $e\in R_{x}\backslash\\{(\rho,\rho_{*}),(x_{*},x)\\}$, we have
$\alpha^{\prime}_{\Psi_{x}(e)}=\alpha_{\check{e}}$. Thus,

$\displaystyle\prod_{e\in
R_{x}\backslash\\{(\rho,\rho_{*}),(x_{*},x)\\}}\frac{\Gamma(\alpha^{\prime}_{\Psi_{x}(e)}+N_{\check{e}}(\gamma))}{\Gamma(\alpha^{\prime}_{\Psi_{x}(e)})}$
$\displaystyle=\prod_{e\in
R_{x}\backslash\\{(\rho,\rho_{*}),(x_{*},x)\\}}\frac{\Gamma(\alpha_{\check{e}}+N_{\check{e}}(\gamma))}{\Gamma(\alpha_{\check{e}})}$
$\displaystyle=\prod_{e\in
R_{x}\backslash\\{(\rho,\rho_{*}),(x_{*},x)\\}}\frac{\Gamma(\alpha_{e}+N_{e}(\gamma))}{\Gamma(\alpha_{e})}.$

The path $\gamma$ never visits $\\{\rho_{*},x\\}$ except for the start and
end, which implies $N_{(\rho_{*},\rho)}(\gamma)=N_{(x_{*},x)}(\gamma)=1$. Till
now, by canceling the corresponding terms, we only have

$\begin{split}\frac{\Gamma(\alpha_{(x_{*},x)}+N_{(x_{*},x)}(\gamma))}{\Gamma(\alpha_{(x_{*},x)})}=\frac{\Gamma(\alpha_{(x_{*},x)}+1)}{\Gamma(\alpha_{(x_{*},x)})}=\alpha_{(x_{*},x)}\end{split}$

left on the left-hand side of (19). In the same way, the right-hand side of
(19) also remains

$\begin{split}\frac{\alpha_{(x_{*},x)}}{\alpha_{(\rho_{*},\rho)}}&\frac{\Gamma(\alpha^{\prime}_{\Psi_{x}((\rho,\rho_{*}))}+N_{(\rho_{*},\rho)}(\gamma))}{\Gamma(\alpha^{\prime}_{\Psi_{x}((\rho,\rho_{*}))})}=\frac{\alpha_{(x_{*},x)}}{\alpha_{(\rho_{*},\rho)}}\frac{\Gamma(\alpha_{(\rho_{*},\rho)}+1)}{\Gamma(\alpha_{(\rho_{*},\rho)})}=\alpha_{(x_{*},x)}.\end{split}$

The proof is complete ∎

As an immediate consequence of Lemma 3.4, we present the distribution of the
tree and path seen at a fresh point $X_{\theta_{k}}$ (see Section 2.1 for the
definition of $\theta_{k}$). Recall that we denote by $\mathbb{P}(\cdot)$ the
annealed distribution of the ERRW $(X_{n})_{n\geq 0}$ on a Galton-Watson tree
and we write $\mathbb{P}_{x}(\cdot):=\mathbb{P}(\cdot|X_{0}=x)$ for
$x\in\mathbb{T}_{*}$ and $\mathbb{E}_{x}$ the corresponding expectation.

######  Corollary 3.5.

Let $\mathbb{T}$ be a Galton-Watson tree. For an
$(\alpha_{p},\alpha_{c})$-ERRW $(X_{n})_{n\geq 0}$, under
$\mathbb{P}_{\rho_{*}}(\cdot|\theta_{k}<\tau_{\rho_{*}})$, we have

$\left(\Psi_{X_{\theta_{k}}}(\mathbb{T}^{\leq
X_{\theta_{k}}}_{*}),\Psi_{X_{\theta_{k}}}((X_{\theta_{k}-j})_{0\leq
j\leq\theta_{k}})\right)\overset{(d)}{=}\left(\mathbb{T}^{\leq
X_{\theta_{k}}}_{*},(X_{j})_{0\leq j\leq\theta_{k}}\right).$

In particular, $\hat{X}_{\theta_{k}}:=\Psi_{X_{\theta_{k}}}(\rho_{*})$ follows
the distribution of the $k$-th fresh point of an
$(\alpha_{p},\alpha_{c})$-ERRW.

Next, we continue to investigate path reversibility for ERRW, when $\gamma$
does not necessarily stop at the first arrival of a point, i.e. $\gamma$ can
be decomposed into a path first arriving at the point and several loops rooted
at it. Recall that the function $\Phi$ was defined in (6).

######  Lemma 3.6.

Fix a tree $T_{*}$ with $(\alpha_{p},\alpha_{c})$-weights. Let $\gamma_{1}$ be
a path as in Lemma 3.4, and $\gamma_{2}$ an arbitrary path that starts from
$x$, ends at a vertex $y\in xT_{x}$, and never visits $\rho_{*}$. We have

$\begin{split}&\mathbf{P}^{T_{*}}(\gamma_{1}|\alpha)\mathbf{P}^{T_{*}}(\gamma_{2}|\alpha+N(\gamma_{1}))\\\
=&\Phi(N_{(x_{*},x)}(\gamma_{2}))\mathbf{P}^{\Psi_{x}(T_{*})}(\Psi_{x}(\check{\gamma}_{1})|_{\geq
1}|\alpha^{\prime})\mathbf{P}^{\Psi_{x}(T_{*})}(\Psi_{x}(\gamma_{2})|\alpha^{\prime}+N(\Psi_{x}(\check{\gamma}_{1})|_{\geq
1})).\end{split}$ (22)

Figure 6: Left: the red path ends at $\rho 11$ and we decompose it into
$\gamma_{1}$ and $\gamma_{2}$ by the time $\tau_{\rho 11}$. Right: the blue
path is $\Psi_{\rho 11}(\check{\gamma}_{1})|_{\geq 1}$ and the red path is
$\Psi_{\rho 11}(\gamma_{2})$. Recall that in Figure 3, we use red color for
$Y$ and blue color for $X$, which is consistent with the colors here.

###### Proof.

We claim that we only need to prove

${\mathbf{P}}^{T_{*}}(\gamma_{2}|\alpha)=\frac{\Gamma(\alpha_{(x,x_{*})})\Gamma(\alpha_{(x_{*},x)}+N_{(x_{*},x)}(\gamma_{2}))}{\Gamma(\alpha_{(x_{*},x)})\Gamma(\alpha_{(x,x_{*})}+N_{(x_{*},x)}(\gamma_{2}))}{\mathbf{P}}^{\Psi_{x}(T_{*})}(\Psi_{x}(\gamma_{2})|\alpha^{\prime})$
(23)

and

${\mathbf{P}}^{T_{*}}(\gamma_{1}|\alpha+N(\gamma_{2}))=\frac{\alpha_{(x_{*},x)}+N_{(x_{*},x)}(\gamma_{2})}{\alpha_{(\rho_{*},\rho)}+N_{(\rho_{*},\rho)}(\gamma_{2})}{\mathbf{P}}^{\Psi_{x}(T_{*})}(\Psi_{x}(\check{\gamma}_{1})|_{\geq
1}|\alpha^{\prime}+N(\Psi_{x}(\gamma_{2}))),$ (24)

where $\alpha,\alpha^{\prime}$ are weights of $T_{*},\Psi_{x}(T_{*})$
respectively. In fact, for the $(\alpha_{p},\alpha_{c})$ case,
$\alpha_{(x,x_{*})}=\alpha_{p}$ and
$\alpha_{(x_{*},x)}=\alpha_{(\rho_{*},\rho)}=\alpha_{c}$. Also, by the
assumption on $\gamma_{2}$ we have $N_{(\rho_{*},\rho)}(\gamma_{2})=0$. Hence,
by the formula $\Gamma(\alpha)\alpha=\Gamma(\alpha+1)$, it holds that

$\displaystyle\frac{\Gamma(\alpha_{(x,x_{*})})\Gamma(\alpha_{(x_{*},x)}+N_{(x_{*},x)}(\gamma_{2}))}{\Gamma(\alpha_{(x_{*},x)})\Gamma(\alpha_{(x,x_{*})}+N_{(x_{*},x)}(\gamma_{2}))}\times\frac{\alpha_{(x_{*},x)}+N_{(x_{*},x)}(\gamma_{2})}{\alpha_{(\rho_{*},\rho)}+N_{(\rho_{*},\rho)}(\gamma_{2})}=\frac{\Gamma(\alpha_{c}+1+N_{(x_{*},x)}(\gamma_{2}))\Gamma(\alpha_{p})}{\Gamma(\alpha_{p}+N_{(x_{*},x)}(\gamma_{2}))\Gamma(\alpha_{c}+1)}$

and the lemma follows.

We first prove (24). Notice that $N_{\check{e}}(\gamma_{2})=N_{e}(\gamma_{2})$
for $e$ such that $\underline{e}\in T^{<x}_{*}$ since $\gamma_{2}$ starts from
$x$ and ends at $y\in xT_{x}$. By Fact 3.2(2), we also have
$N_{\Psi_{x}(e)}(\Psi_{x}(\gamma_{2}))=N_{e}(\gamma_{2})$ and
$N_{\Psi_{x}(\check{e})}(\Psi_{x}(\gamma_{2}))=N_{\check{e}}(\gamma_{2})$. We
replace the weights $\alpha$ by $\alpha+N(\gamma_{2})$ and $\alpha^{\prime}$
by $\alpha^{\prime}+N(\Psi_{x}(\gamma_{2}))$ respectively in (19). Since
$N_{\check{e}}(\gamma_{2})=N_{e}(\gamma_{2})=N_{\Psi_{x}(e)}(\Psi_{x}(\gamma_{2}))=N_{\Psi_{x}(\check{e})}(\Psi_{x}(\gamma_{2}))$
for $e$ such that $\underline{e}\in T^{<x}_{*}$, the new sets of weights,
$(\alpha_{e}+N_{e}(\gamma_{2}))_{\underline{e}\in T_{*}}$ and
$(\alpha_{e}^{\prime}+N_{\Psi_{x}(e)}(\Psi_{x}(\gamma_{2})))_{\underline{e}\in\Psi_{x}(T_{*})}$,
also satisfy the condition in Lemma 3.4. Thus Lemma 3.4 implies (24).

For (23), by Lemma 2.4, we have

$\mathbf{P}^{T_{*}}(\gamma_{2}|\alpha)=\prod_{y\in
T_{*}}\frac{\Gamma(\sum_{\underline{e}=y}\alpha_{e})}{\Gamma(\sum_{\underline{e}=y}\alpha_{e}+N_{e}(\gamma_{2}))}\prod_{\underline{e}\in
T_{*}}\frac{\Gamma(\alpha_{e}+N_{e}(\gamma_{2}))}{\Gamma(\alpha_{e})},$ (25)

and

${\mathbf{P}}^{\Psi_{x}(T_{*})}(\Psi_{x}(\gamma_{2})|\alpha^{\prime})=\prod_{y\in
T^{*}}\frac{\Gamma(\sum_{\underline{e}=y}\alpha_{\Psi_{x}(e)}^{\prime})}{\Gamma(\sum_{\underline{e}=y}\alpha_{\Psi_{x}(e)}^{\prime}+N_{e}(\gamma_{2}))}\prod_{\underline{e}\in
T_{*}}\frac{\Gamma(\alpha_{\Psi_{x}(e)}^{\prime}+N_{e}(\gamma_{2}))}{\Gamma(\alpha_{\Psi_{x}(e)}^{\prime})}.$
(26)

Since for any vertex $y\in T_{*}$,
$\sum_{\underline{e}=y}\alpha_{e}=\sum_{\underline{e}=\Psi_{x}(y)}\alpha_{\Psi_{x}(e)}^{\prime}$,
we have

$\displaystyle\prod_{y\in
T_{*}}\frac{\Gamma(\sum_{\underline{e}=y}\alpha_{e})}{\Gamma(\sum_{\underline{e}=y}\alpha_{e}+N_{e}(\gamma_{2}))}=\prod_{y\in
T^{*}}\frac{\Gamma(\sum_{\underline{e}=y}\alpha_{\Psi_{x}(e)}^{\prime})}{\Gamma(\sum_{\underline{e}=y}\alpha_{\Psi_{x}(e)}^{\prime}+N_{e}(\gamma_{2}))}.$

Note that $\alpha_{e}=\alpha^{\prime}_{\Psi_{x}(e)}$ for $e$ such that
$\underline{e}\in xT_{x}$. For $e\in
R_{x}\backslash\\{(x_{*},x),(\rho,\rho_{*})\\}$, we have $\check{e}\in
R_{x}\backslash\\{(x_{*},x),(\rho,\rho_{*})\\}$,
$\alpha_{e}=\alpha^{\prime}_{\Psi_{x}(\check{e})}$ by definition and
$N_{e}(\gamma_{2})=N_{\check{e}}(\gamma_{2})$ by Fact 3.2(2). For
$e\in\\{e:\underline{e}\in T^{<x}\\}\backslash R_{x}$, we have
$\alpha_{e}=\alpha^{\prime}_{\Psi_{x}(e)}$. Repeating our discussion in Lemma
3.4, the only different parts between (25) and (26) are the probabilities of
going from $x_{*}$ to $x$ and from $\Psi_{x}(x_{*})$ to $\Psi_{x}(x)$, which
are

$\frac{\Gamma(\alpha_{(x_{*},x)}+N_{(x_{*},x)}(\gamma_{2}))}{\Gamma(\alpha_{(x_{*},x)})},$

and

$\frac{\Gamma(\alpha_{\Psi_{x}((x_{*},x))}^{\prime}+N_{(x_{*},x)}(\gamma_{2}))}{\Gamma(\alpha_{\Psi_{x}((x_{*},x))}^{\prime})}$

respectively. Their ratio is

$\displaystyle\frac{\Gamma(\alpha_{(x,x_{*})})\Gamma(\alpha_{(x_{*},x)}+N_{(x_{*},x)}(\gamma_{2}))}{\Gamma(\alpha_{(x_{*},x)})\Gamma(\alpha_{(x,x_{*})}+N_{(x_{*},x)}(\gamma_{2}))}.$

∎

######  Remark 3.7.

The equation (22) still holds when we condition on the environment
$(\eta_{e})_{\underline{e}\in xT_{x}}$ and
$(\eta_{e})_{\underline{e}\in\Psi_{x}(xT_{x})}$ (which means that on $xT_{x}$
the walker follows the quenched law of a RWDE).

###  3.3 Asymptotic distribution of the environment seen from a particle

The main result of this section is Theorem 3.9 which implies that, under the
condition (3.3), the asymptotic distribution of the environment seen from ERRW
is the measure $\mu_{ER}$ defined in the introduction, renormalized to be a
probability measure. We follow the strategy in [2] to establish this result.

We first state a lemma similar to [2, Lemma 4.4].

######  Lemma 3.8.

Let $Y$ be a RWDE on Galton-Watson double tree with
$(\alpha_{p},\alpha_{c})$-environment, then

$\begin{split}&{\rm E}_{\rho^{+}}^{\eta}\left[\sum_{l\geq
0}\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(l))\textbf{1}_{\\{Y_{l}=\rho^{+}\\}}\right]\\\
=&\frac{(1-\beta(\rho^{+}))}{\eta(\rho^{+},\rho^{-})}\sum_{k\geq
0}\Phi(k)(1-\beta(\rho^{+}))^{k}(1-\beta(\rho^{-}))^{k}.\end{split}$

###### Proof.

Recall the definition of $\beta(x)$ in (5) and observe that

$\displaystyle{\rm E}_{\rho^{+}}^{\eta}\left[\sum_{l\geq
0}\Phi(N^{Y}_{(\rho^{-},\rho^{+})}(l))\textbf{1}_{\\{Y_{l}=\rho^{+}\\}}\right]=\sum_{k\geq
0}\Phi(k)\sum_{l\geq 0}{\rm
P}_{\rho^{+}}^{\eta}(Y_{l}=\rho^{+},N_{(\rho^{+},\rho^{-})}^{Y}(l)={k}).$

We can define the stopping times

$\displaystyle s_{k}:=\inf\\{l\geq 0:N_{(\rho^{+},\rho^{-})}^{Y}(l)={k}\\}$

and $t_{k}:=\inf\\{l\geq s_{k}:Y_{l}=\rho^{+}\\}$. We have a formula for
conductance obtained by Markov property that

$\frac{1}{\beta(x)}=1+\frac{\eta(x,x_{*})}{\sum_{i=1}^{\nu(x)}\eta(x,xi)\beta(xi)}.$
(27)

Then by the Markov property at $t_{k}$, we have

$\displaystyle\sum_{l\geq 0}{\rm
P}_{\rho^{+}}^{\eta}(Y_{l}=\rho^{+},N_{(\rho^{-},\rho^{+})}^{Y}(l)={k})={\rm
E}_{\rho^{+}}^{\eta}\left[\textbf{1}_{\\{t_{k}<\infty\\}}\sum_{l=t_{k}}^{s_{{k}+1}}\textbf{1}_{\\{Y_{l}=\rho^{+}\\}}\right]$
$\displaystyle=$ $\displaystyle{\rm P}_{\rho^{+}}^{\eta}(t_{k}<\infty){\rm
E}_{\rho^{+}}^{\eta}\left[\sum_{l=0}^{s_{1}}\textbf{1}_{\\{Y_{l}=\rho^{+}\\}}\right]=(1-\beta(\rho^{-}))^{k}(1-\beta(\rho^{+}))^{k}\frac{1}{1-{\rm
P}_{\rho^{+}}^{\eta}(\tau_{\rho^{+}}<s_{1})}$ $\displaystyle=$
$\displaystyle(1-\beta(\rho^{-}))^{k}(1-\beta(\rho^{+}))^{k}\frac{1}{\eta(\rho^{+},\rho^{-})+\sum_{i=1}^{\nu(\rho^{+})}\eta(\rho^{+},\rho^{+}i)\beta(\rho^{+}i)}$
$\displaystyle=$
$\displaystyle(1-\beta(\rho^{-}))^{k}(1-\beta(\rho^{+}))^{k}\frac{1-\beta(\rho^{+})}{\eta(\rho^{+},\rho^{-})},$

where the last equality comes from the formula (27). The proof is complete. ∎

In order to describe the limit distribution, we construct the law for two
dependent ERRW on a double Galton-Watson tree. We first sample a double
Galton-Watson tree $\mathbb{T}^{-}\rightleftharpoons\mathbb{T}^{+}$ with
weight $\alpha$ defined in (18). We let $(X_{n})_{n\geq 0}$ (resp
$(Y_{n})_{n\geq 0}$) be an ERRW with law
$\mathbf{P}^{\mathbb{T}^{-}\rightleftharpoons\mathbb{T}^{+}}(\cdot|\alpha)$
(resp.
$\mathbf{P}^{\mathbb{T}^{-}\rightleftharpoons\mathbb{T}^{+}}(\cdot|\alpha+N^{X})$)
starting from $\rho^{-}$ (resp. $\rho^{+}$). In other words, we first run an
ERRW $(X_{n})_{n\geq 0}$, add the local time of $(X_{n})_{n\geq 0}$ to the
initial weight $\alpha$ and run another ERRW $(Y_{n})_{n\geq 0}$. We call the
probability measure constructed above
$\mathbb{P}_{(\rho^{-},\rho^{+})}(\cdot)$ and denote by
$\mathbb{E}_{(\rho^{-},\rho^{+})}[\cdot]$ the corresponding expectation.

Recall that the law of an ERRW can be viewed as the annealed law of a RWDE.
From Lemma 2.5, we can view $\mathbb{P}_{(\rho_{*},\rho)}[\cdot]$ as the
annealed law of two independent RWDE on a double Galton-Watson tree. Recall
the definition of $\mathscr{C}$ in (3.3). By independence of $\mathbb{T}^{+}$
and $\mathbb{T}^{-}$ in a double tree,

$\displaystyle\mathscr{C}$
$\displaystyle=\mathbb{E}_{(\rho^{-},\rho^{+})}\left[\frac{\beta(\rho^{-})(1-\beta(\rho^{+}))}{\eta(\rho^{+},\rho^{-})}\sum_{k\geq
0}\Phi(k)(1-\beta(\rho^{+}))^{k}(1-\beta(\rho^{-}))^{k}\right].$

With Lemma 3.8,

$\begin{split}\mathscr{C}=&\mathbb{E}_{(\rho^{-},\rho^{+})}\left[\sum_{l\geq
0}\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(l))\textbf{1}_{\\{\tau^{X}_{\rho^{+}}=\infty\\}}\textbf{1}_{\\{Y_{l}=\rho^{+}\\}}\right].\end{split}$
(28)

We now describe the state space of the environment seen from an ERRW. We
define $(\Omega_{ER},\mathcal{F}_{ER})$ as

$\Omega_{ER}:=\\{(T^{-}\rightleftharpoons
T^{+},\gamma):\gamma\in\Omega_{\gamma}\\},\,\mathcal{F}_{ER}:=\sigma_{finite}((T^{-}\rightleftharpoons
T^{+},\gamma)),$

where $\sigma_{finite}$ is the sigma field generated by information of finite
subtrees and finite subpaths. The measure $\mu_{ER}$ given in (12) is a
measure on $(\Omega_{ER},\mathcal{F}_{ER})$.

######  Theorem 3.9.

Suppose that $m\in(1,\infty)$, and (3), (3.3) hold. Under
$\mathbb{P}(\cdot|\mathcal{S})$, the random variable
$(\Psi_{X_{n}}(\mathbb{T}_{*}^{<X_{n}})\rightleftharpoons\mathbb{T}_{X_{n}},(\eta_{e})_{\underline{e}\in\mathbb{T}_{X_{n}}},\Psi_{X_{n}}((X_{l})_{0\leq
l\leq n}))$ converges in distribution as $n\rightarrow\infty$. More precisely,
for any bounded functional $\mathbf{F}$,

$\begin{split}&\lim_{n\rightarrow\infty}\mathbb{E}_{\rho}\left[\mathbf{F}(\Psi_{X_{n}}(\mathbb{T}_{*}^{<X_{n}})\rightleftharpoons\mathbb{T}_{X_{n}},(\eta_{e})_{\underline{e}\in\mathbb{T}_{X_{n}}},\Psi_{X_{n}}((X_{l})_{0\leq
l\leq n}))|\mathcal{S}\right]=\mathscr{C}^{-1}\times\\\
&\mathbb{E}_{(\rho_{-},\rho^{+})}\left[\sum_{t\geq
0}\mathbf{F}(\mathbb{T}^{-}\rightleftharpoons\mathbb{T}^{+},(\eta_{e})_{\underline{e}\in\mathbb{T}^{+}},Rev((X_{l})_{l\geq
0})\ast(Y_{l})_{0\leq l\leq
t})\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(t))\textbf{1}_{\\{\tau^{X}_{\rho^{+}}=\infty\\}}\textbf{1}_{\\{Y_{t}=\rho^{+}\\}}\right],\end{split}$
(29)

where $\mathscr{C}\in(0,\infty)$ is the renormalising constant defined in
(3.3) and it also equals

$\displaystyle\mathbb{E}_{\rho}[\Theta_{1}\textbf{1}_{\\{\tau_{\rho_{*}}=\infty\\}}]\mathbb{E}_{\rho}\left[\beta(\rho)\right].$
(30)

By averaging over the environment $\eta$, we deduce the following corollary,
which implies that $\mathscr{C}^{-1}\mu_{ER}$ is the limiting measure for the
environment seen from an ERRW on a Galton-Watson tree. It will be proved in a
subsequent paper that $\mu_{ER}$ is an invariant measure even when (3.3) fails
to hold.

######  Corollary 3.10.

Suppose that $m\in(1,\infty)$, and (3), (3.3) hold. Under
$\mathbb{P}(\cdot|\mathcal{S})$, the random variable
$(\Psi_{X_{n}}(\mathbb{T}_{*}^{<X_{n}})\rightleftharpoons\mathbb{T}_{X_{n}},\Psi_{X_{n}}((X_{l})_{0\leq
l\leq n}))$ converges in distribution as $n\rightarrow\infty$ to
$\mathscr{C}^{-1}\mu_{ER}$.

###### Proof of Theorem 3.9.

Let $\mathbf{F}$ be a bounded measurable function on the space of marked
trees. We suppose that there exists a constant $M>0$ such that $\mathbf{F}$
only depends on the subtree
$\\{u\in\mathbb{T}^{-}\rightleftharpoons\mathbb{T}^{+},|u|\leq M\\}$ (and the
part of path on it), where $|u|$ is the graph distance between $u$ and
$\rho^{+}$. We need to show that

$\displaystyle\lim_{n\rightarrow\infty}\mathbb{E}_{\rho}\left[\mathbf{F}(\Psi_{X_{n}}(\mathbb{T}_{*}^{<X_{n}})\rightleftharpoons\mathbb{T}_{X_{n}},(\eta_{e})_{\underline{e}\in\mathbb{T}_{X_{n}}},\Psi_{X_{n}}((X_{l})_{0\leq
l\leq
n}))\textbf{1}_{\mathcal{S}}\right]=\frac{\mathbb{P}(\mathcal{S})}{\mathbb{E}_{\rho}[\Theta_{1}\textbf{1}_{\\{\tau_{\rho_{*}}=\infty\\}}]\mathbb{E}_{\rho}\left[\beta(\rho)\right]}\times$
$\displaystyle\mathbb{E}_{(\rho_{-},\rho^{+})}\left[\sum_{t\geq
0}\mathbf{F}(\mathbb{T}^{-}\rightleftharpoons\mathbb{T}^{+},(\eta_{e})_{\underline{e}\in\mathbb{T}^{+}},Rev((X_{l})_{l\geq
0})\ast(Y_{l})_{0\leq l\leq
t})\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(t))\textbf{1}_{\\{\tau^{X}_{\rho^{+}}=\infty\\}}\textbf{1}_{\\{Y_{t}=\rho^{+}\\}}\right],$

to prove (29) and (30).

By the argument in [2, Section 4.3], it suffices to prove

$\begin{split}&\lim_{n\rightarrow\infty}\mathbb{E}_{\rho}\left[\mathbf{F}(\Psi_{X_{n}}(\mathbb{T}_{*}^{<X_{n}})\rightleftharpoons\mathbb{T}_{X_{n}},(\eta_{e})_{\underline{e}\in\mathbb{T}_{X_{n}}},\Psi_{X_{n}}((X_{l})_{0\leq
l\leq
n}))\textbf{1}_{\\{\tau_{\rho_{*}}>n\\}}\right]=\frac{1}{\mathbb{E}_{\rho}[\Theta_{1}\textbf{1}_{\\{\tau_{\rho_{*}}=\infty\\}}]}\times\\\
&\mathbb{E}_{(\rho_{-},\rho^{+})}\left[\sum_{t\geq
0}\mathbf{F}(\mathbb{T}^{-}\rightleftharpoons\mathbb{T}^{+},(\eta_{e})_{\underline{e}\in\mathbb{T}^{+}},Rev((X_{l})_{l\geq
0})\ast(Y_{l})_{0\leq l\leq
t})\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(t))\textbf{1}_{\\{\tau^{X}_{\rho^{+}}=\infty\\}}\textbf{1}_{\\{Y_{t}=\rho^{+}\\}}\right].\end{split}$
(31)

For a random tree $\mathbb{T}$, we let $\mathcal{S}_{\mathbb{T}}$ be the event
that $\mathbb{T}$ is infinite. By dominated convergence we have

$\displaystyle\mathbb{E}_{\rho}\left[\mathbf{F}(\Psi_{X_{n}}(\mathbb{T}_{*}^{<X_{n}})\rightleftharpoons\mathbb{T}_{X_{n}},(\eta_{e})_{\underline{e}\in\mathbb{T}_{X_{n}}},\Psi_{X_{n}}((X_{l})_{0\leq
l\leq n}))\textbf{1}_{\\{\tau_{\rho_{*}}>n\\}}\right]$ $\displaystyle=$
$\displaystyle\mathbb{E}_{\rho}\left[\mathbf{F}(\Psi_{X_{n}}(\mathbb{T}_{*}^{<X_{n}})\rightleftharpoons\mathbb{T}_{X_{n}},(\eta_{e})_{\underline{e}\in\mathbb{T}_{X_{n}}},\Psi_{X_{n}}((X_{l})_{0\leq
l\leq n}))\textbf{1}_{\\{\tau_{\rho_{*}}>n,|X_{n}|\geq
M\\}}\textbf{1}_{\mathcal{S}_{{\mathbb{T}}_{*}^{\leq
X_{n}}}}\right]+o_{n}(1).$

Recall that $\theta_{k}$ is the $k$-th fresh epoch and
$\xi_{k}=X_{\theta_{k}}$. We see for $n\geq 0$,

$\begin{split}&\mathbb{E}_{\rho}\left[\mathbf{F}(\Psi_{X_{n}}(\mathbb{T}_{*}^{<X_{n}})\rightleftharpoons\mathbb{T}_{X_{n}},(\eta_{e})_{\underline{e}\in\mathbb{T}_{X_{n}}},\Psi_{X_{n}}((X_{l})_{0\leq
l\leq
n}))\textbf{1}_{\\{\tau_{\rho_{*}}>n,|X_{n}|>M\\}}\textbf{1}_{\mathcal{S}_{\mathbb{T}_{*}^{\leq
X_{n}}}}\right]\\\
=&\sum_{k=0}^{\infty}\mathbb{E}_{\rho}\left[\mathbf{F}(\Psi_{\xi_{k}}(\mathbb{T}_{*}^{<\xi_{k}})\rightleftharpoons\mathbb{T}_{\xi_{k}},(\eta_{e})_{\underline{e}\in\mathbb{T}_{\xi_{k}}},\Psi_{\xi_{k}}((X_{l})_{0\leq
l\leq
n}))\textbf{1}_{\\{\tau_{\rho_{*}}>n,|\xi_{k}|>M\\}}\textbf{1}_{\\{X_{n}=\xi_{k}\\}}\textbf{1}_{\mathcal{S}_{\mathbb{T}_{*}^{\leq\xi_{k}}}}\right].\end{split}$
(32)

By Lemma 3.1 and Lemma 3.6, we have for each $k\geq 0$

$\begin{split}&\mathbb{E}_{\rho}\left[\mathbf{F}(\Psi_{\xi_{k}}(\mathbb{T}_{*}^{<\xi_{k}})\rightleftharpoons\mathbb{T}_{\xi_{k}},(\eta_{e})_{\underline{e}\in\mathbb{T}_{\xi_{k}}},\Psi_{\xi_{k}}((X_{l})_{0\leq
l\leq
n}))\textbf{1}_{\\{\tau_{\rho_{*}}>n,|\xi_{k}|>M\\}}\textbf{1}_{\\{X_{n}=\xi_{k}\\}}\textbf{1}_{\mathcal{S}_{\mathbb{T}_{*}^{\leq\xi_{k}}}}\right]\\\
=&\mathbb{E}_{(\rho^{-},\rho^{+})}\bigg{[}\mathbf{F}({(\mathbb{T}}^{-})^{\leq\xi_{k}}\rightleftharpoons\mathbb{T}^{+},(\eta_{e})_{\underline{e}\in\mathbb{T}^{+}},Rev((X_{l})_{0\leq
l\leq\theta_{k}})\ast(Y_{l})_{0\leq l\leq n-\theta_{k}})\\\
&\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(n-\theta_{k}))\textbf{1}_{\\{\tau_{\rho^{+}}^{X}>\theta_{k},|\xi_{k}|>M\\}}\textbf{1}_{\\{\tau_{\xi_{k}}^{Y}>n-\theta_{k},Y_{n-\theta_{k}}=\rho^{+}\\}}\textbf{1}_{\mathcal{S}_{({\mathbb{T}^{-})}_{*}^{\leq\xi_{k}}}}\bigg{]}.\\\
\end{split}$ (33)

Here we reverse the tree and path conditioned on
$(\eta_{e})_{\underline{e}\in\mathbb{T}_{\xi_{k}}}$ by Remark 3.7.

Reasoning on the value of $n-\theta_{k}$ in (33), we see that

$\begin{split}&\sum_{k=0}^{\infty}\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(n-\theta_{k}))\textbf{1}_{\\{\tau_{\rho^{+}}^{X}>\theta_{k},|\xi_{k}|>M\\}}\textbf{1}_{\\{\tau_{\xi_{k}}^{Y}>n-\theta_{k},Y_{n-\theta_{k}}=\rho^{+}\\}}\textbf{1}_{\mathcal{S}_{{(\mathbb{T}}_{*}^{-})^{\leq\xi_{k}}}}\\\
=&\sum_{t=0}^{n}\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(t))\textbf{1}_{\\{\tau_{\rho^{+}}^{X}>n-t,|X_{n-t}|>M,n-t\in\\{\theta_{k},k\geq
0\\}\\}}\textbf{1}_{\\{\tau_{X_{n-t}}^{Y}>t,Y_{t}=\rho^{+}\\}}\textbf{1}_{\mathcal{S}_{{(\mathbb{T}}_{*}^{-})^{\leq
X_{n-t}}}}.\end{split}$

From the definition of the regeneration epoch,

$\begin{split}&\textbf{1}_{\\{\tau_{\rho^{+}}^{X}>n-t,|X_{n-t}|>M,n-t\in\\{\Theta_{k},k\geq
0\\}\\}}\textbf{1}_{\\{\tau_{X_{n-t}}^{Y}>t,Y_{t}=\rho^{+}\\}}\textbf{1}_{\mathcal{S}_{{(\mathbb{T}}_{*}^{-})^{\leq
X_{n-t}}}}\\\
=&\textbf{1}_{\\{\tau_{\rho^{+}}^{X}>n-t,|X_{n-t}|>M,n-t\in\\{\theta_{k},k\geq
0\\}\\}}\textbf{1}_{\\{X_{s}\neq(X_{n-t})_{*},s\geq
n-t\\}}\textbf{1}_{\\{\tau_{X_{n-t}}^{Y}>t,Y_{t}=\rho^{+}\\}}\textbf{1}_{\mathcal{S}_{{(\mathbb{T}}_{*}^{-})^{\leq
X_{n-t}}}}.\\\ \end{split}$ (34)

We apply the Markov property at time $n-t$ for $(X_{n})_{n\geq 0}$ considered
as a RWDE and the branching property of a Galton-Watson tree at $X_{n-t}$. The
term $\textbf{1}_{\\{X_{s}\neq(X_{n-t})_{*},s\geq n-t\\}}$ is independent of
the other terms (it is independent of $\mathbf{F}$ since $|X_{n-t}|>M$), with
expectation $\mathbb{E}_{\rho}[\beta(\rho)]$. Thus

$\begin{split}&\mathbb{E}_{(\rho^{-},\rho^{+})}\left[\mathbf{F}(\cdot)\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(t))\textbf{1}_{\\{\tau_{\rho^{+}}^{X}>n-t,|X_{n-t}|>M,n-t\in\\{\Theta_{k},k\geq
0\\}\\}}\textbf{1}_{\\{\tau_{X_{n-t}}^{Y}>t,Y_{t}=\rho^{+}\\}}\textbf{1}_{\mathcal{S}_{{(\mathbb{T}}_{*}^{-})^{\leq
X_{n-t}}}}\right]\\\
=&\mathbb{E}_{(\rho^{-},\rho^{+})}\left[\mathbf{F}(\cdot)\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(t))\textbf{1}_{\\{\tau_{\rho^{+}}^{X}>n-t,|X_{n-t}|>M,n-t\in\\{\theta_{k},k\geq
0\\}\\}}\textbf{1}_{\\{\tau_{X_{n-t}}^{Y}>t,Y_{t}=\rho^{+}\\}}\textbf{1}_{\mathcal{S}_{{(\mathbb{T}}_{*}^{-})^{\leq
X_{n-t}}}}\right]\times\\\ &\mathbb{E}_{\rho}[\beta(\rho)].\end{split}$ (35)

We also obtain from (28) and our assumption (3.3) that

$\begin{split}&\mathbb{E}_{(\rho^{-},\rho^{+})}\left[\sum_{t=0}^{n}\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(t))\textbf{1}_{\\{\tau_{\rho^{+}}^{X}>n-t,|X_{n-t}|>M,n-t\in\\{\Theta_{k},k\geq
0\\}\\}}\textbf{1}_{\\{\tau_{X_{n-t}}^{Y}>t,Y_{t}=\rho^{+}\\}}\textbf{1}_{\mathcal{S}_{{\mathbb{T}}_{*}^{-}}}\right]\\\
\leq&\mathbb{E}_{(\rho^{-},\rho^{+})}\left[\sum_{t=0}^{\infty}\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(t))\textbf{1}_{\\{\tau_{\rho^{+}}^{X}=\infty\\}}\textbf{1}_{\\{Y_{t}=\rho^{+}\\}}\right]=\mathscr{C}<\infty\end{split}$
(36)

By (36), with the dominating function

$\displaystyle||\mathbf{F}||_{\infty}\sum_{t=0}^{\infty}\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(t))\textbf{1}_{\\{\tau^{X}_{\rho^{+}}=\infty\\}}\textbf{1}_{\\{Y_{t}=\rho^{+}\\}},$

we can apply dominated convergence to see that

$\displaystyle\sum_{t=0}^{n}\mathbb{E}_{(\rho^{-},\rho^{+})}\Bigg{[}\mathbf{F}({(\mathbb{T}}^{-})^{\leq
X_{n-t}}\rightleftharpoons\mathbb{T}^{+},(\eta_{e})_{\underline{e}\in\mathbb{T}^{+}},Rev((X_{l})_{0\leq
l\leq n-t})\ast(Y_{l})_{0\leq l\leq t})$
$\displaystyle\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(t))\textbf{1}_{\\{\tau_{\rho^{+}}^{X}>n-t,|X_{n-t}|>M,n-t\in\\{\Theta_{k},k\geq
0\\}\\}}\textbf{1}_{\\{\tau_{X_{n-t}}^{Y}>t,Y_{t}=\rho^{+}\\}}\textbf{1}_{\mathcal{S}_{{(\mathbb{T}}_{*}^{-})^{\leq
X_{n-t}}}}\Bigg{]}$ $\displaystyle=$
$\displaystyle\mathbb{E}_{(\rho^{-},\rho^{+})}\Bigg{[}\sum_{t=0}^{\infty}\mathbf{F}({\mathbb{T}}^{-}\rightleftharpoons\mathbb{T}^{+},(\eta_{e})_{\underline{e}\in\mathbb{T}^{+}},Rev((X_{l})_{0\leq
l\leq\infty})\ast(Y_{l})_{0\leq l\leq t})$
$\displaystyle\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(t))\textbf{1}_{\\{\tau_{\rho^{+}}^{X}=\infty,n-t\in\\{\Theta_{k},k\geq
0\\}\\}}\textbf{1}_{\\{\tau_{X_{n-t}}^{Y}>t,Y_{t}=\rho^{+}\\}}\textbf{1}_{\mathcal{S}_{{\mathbb{T}}_{*}^{-}}}\Bigg{]}+o_{n}(1).$

Here we replace $\mathbf{F}({(\mathbb{T}}^{-})^{\leq
X_{n-t}}\rightleftharpoons\mathbb{T}^{+},\cdot,\cdot)$ by
$\mathbf{F}({\mathbb{T}}^{-}\rightleftharpoons\mathbb{T}^{+},\cdot,\cdot)$,
since $\mathbf{F}$ only relies on finite subtrees. Note that we can replace
the quantity above by

$\begin{split}&\mathbb{E}_{(\rho^{-},\rho^{+})}\Bigg{[}\sum_{t=0}^{\infty}\mathbf{F}({\mathbb{T}}^{-}\rightleftharpoons\mathbb{T}^{+},(\eta_{e})_{\underline{e}\in\mathbb{T}^{+}},Rev((X_{l})_{0\leq
l\leq\infty})\ast(Y_{l})_{0\leq l\leq t})\\\
&\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(t))\textbf{1}_{\\{\tau_{\rho^{+}}^{X}=\infty,n-t\in\\{\Theta_{k},k\geq
t+M\\}\\}}\textbf{1}_{\\{\tau_{X_{n-t}}^{Y}>t,Y_{t}=\rho^{+}\\}}\textbf{1}_{\mathcal{S}_{{\mathbb{T}}_{*}^{-}}}\Bigg{]}+o_{n}(1)\end{split}$

by dominated convergence. Define
$b_{i}:={\mathbb{P}}_{\rho}(i\in\\{\Theta_{k},k\geq
0\\}|\tau_{\rho_{*}}=\infty)$. According to the renewal theorem,

$\lim_{i\to\infty}b_{i}=\frac{1}{\mathbb{E}_{\rho}[\Theta_{1}|\tau_{\rho_{*}}=\infty]}$
(37)

since $(\Theta_{k+1}-\Theta_{k})_{k\geq 0}$ is an i.i.d. sequence when
conditioned on $\\{\tau_{\rho_{*}}=\infty\\}$. Thus we have

$\begin{split}&\mathbb{E}_{(\rho^{-},\rho^{+})}\Bigg{[}\sum_{t=0}^{\infty}\mathbf{F}({\mathbb{T}}^{-}\rightleftharpoons\mathbb{T}^{+},(\eta_{e})_{\underline{e}\in\mathbb{T}^{+}},Rev((X_{l})_{0\leq
l\leq\infty})\ast(Y_{l})_{0\leq l\leq t})\\\
&\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(t))\textbf{1}_{\\{\tau_{\rho^{+}}^{X}=\infty,n-t\in\\{\Theta_{k},k\geq
t+M\\}\\}}\textbf{1}_{\\{\tau_{X_{n-t}}^{Y}>t,Y_{t}=\rho^{+}\\}}\textbf{1}_{\mathcal{S}_{{\mathbb{T}}_{*}^{-}}}\Bigg{]}\\\
=&\mathbb{E}_{(\rho^{-},\rho^{+})}\Bigg{[}\sum_{t=0}^{\infty}\mathbf{F}({\mathbb{T}}^{-}\rightleftharpoons\mathbb{T}^{+},(\eta_{e})_{\underline{e}\in\mathbb{T}^{+}},Rev((X_{l})_{0\leq
l\leq\infty})\ast(Y_{l})_{0\leq l\leq t})\\\
&\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(t))\textbf{1}_{\\{\tau_{\rho^{+}}^{X}=\infty,n-t\geq\Theta_{t+M}\\}}b_{n-t-\Theta_{t+M}}\textbf{1}_{\\{\tau_{X_{n-t}}^{Y}>t,Y_{t}=\rho^{+}\\}}\textbf{1}_{\mathcal{S}_{{\mathbb{T}}_{*}^{-}}}\Bigg{]}\\\
=&\frac{1}{\mathbb{E}_{\rho}[\Theta_{1}|\tau_{\rho_{*}}=\infty]}\mathbb{E}_{(\rho^{-},\rho^{+})}\Bigg{[}\sum_{t=0}^{\infty}\mathbf{F}({\mathbb{T}}^{-}\rightleftharpoons\mathbb{T}^{+},(\eta_{e})_{\underline{e}\in\mathbb{T}^{+}},Rev((X_{l})_{0\leq
l\leq\infty})\ast(Y_{l})_{0\leq l\leq t})\\\
&\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(t))\textbf{1}_{\\{\tau_{\rho^{+}}^{X}=\infty\\}}\textbf{1}_{\\{Y_{t}=\rho^{+}\\}}\textbf{1}_{\mathcal{S}_{{\mathbb{T}}_{*}^{-}}}\Bigg{]}+o_{n}(1),\end{split}$

where we use regeneration structure, branching property for the first
equality, and (37) for the second. With (35), we conclude that

$\displaystyle\sum_{t=0}^{n}\mathbb{E}_{(\rho^{-},\rho^{+})}\Bigg{[}\mathbf{F}({(\mathbb{T}}^{-})^{\leq
X_{n-t}}\rightleftharpoons\mathbb{T}^{+},(\eta_{e})_{\underline{e}\in\mathbb{T}^{+}},Rev((X_{l})_{0\leq
l\leq n-t})\ast(Y_{l})_{0\leq l\leq t})$
$\displaystyle\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(t))\textbf{1}_{\\{\tau_{\rho^{+}}^{X}>n-t,|X_{n-t}|>M,n-t\in\\{\theta_{k},k\geq
0\\}\\}}\textbf{1}_{\\{\tau_{X_{n-t}}^{Y}>t,Y_{t}=\rho^{+}\\}}\textbf{1}_{\mathcal{S}_{{(\mathbb{T}}_{*}^{-})^{\leq
X_{n-t}}}}\Bigg{]}$ $\displaystyle=$
$\displaystyle\frac{1}{\mathbb{E}_{\rho}[\Theta_{1}\textbf{1}_{\\{\tau_{\rho_{*}}=\infty\\}}]}\mathbb{E}_{(\rho^{-},\rho^{+})}\Bigg{[}\sum_{t=0}^{\infty}\mathbf{F}({\mathbb{T}}^{-}\rightleftharpoons\mathbb{T}^{+},(\eta_{e})_{\underline{e}\in\mathbb{T}^{+}},Rev((X_{l})_{0\leq
l\leq\infty})\ast(Y_{l})_{0\leq l\leq t})$
$\displaystyle\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(t))\textbf{1}_{\\{\tau_{\rho^{+}}^{X}=\infty\\}}\textbf{1}_{\\{Y_{t}=\rho^{+}\\}}\textbf{1}_{\mathcal{S}_{{\mathbb{T}}_{*}^{-}}}\Bigg{]}+o_{n}(1).$

We thus complete the proof of (31) and the theorem. ∎

We now show the equivalence between positiveness of the speed and finiteness
of $\mathscr{C}$.

###### Proof of Theorem 1.2.

By dominated convergence,

$\displaystyle
0<\lim_{n\rightarrow\infty}\mathbb{E}_{\rho}\left[\textbf{1}_{\\{\tau_{\rho_{*}}>n\\}}\right]=\mathbb{E}_{\rho}\left[\beta(\rho)\right]<1$
(38)

since the walk is transient. According to (32), (33) and (35), with $F\equiv
1$ and $M=0$ (we do not use the condition (3.3) and can drop the indicator
function $\textbf{1}_{\mathcal{S}_{\mathbb{T}_{*}^{\leq X_{n}}}}$), we have

$\begin{split}&\mathbb{E}_{\rho}\left[\textbf{1}_{\\{\tau_{\rho_{*}}>n\\}}\right]\mathbb{E}_{\rho}[\beta(\rho)]\\\
=&\mathbb{E}_{(\rho^{-},\rho^{+})}\left[\sum_{l=0}^{n}\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(l))\textbf{1}_{\\{\tau_{\rho^{+}}^{X}>n-l,n-l\in\\{\theta_{k},k\geq
0\\}\\}}\textbf{1}_{\\{\tau_{X_{n-l}}^{Y}>l,Y_{l}=\rho^{+}\\}}\right]\mathbb{E}_{\rho}[\beta(\rho)]\\\
=&\mathbb{E}_{(\rho^{-},\rho^{+})}\left[\sum_{l=0}^{n}\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(l))\textbf{1}_{\\{\tau_{\rho^{+}}^{X}=\infty,n-l\in\\{\Theta_{k},k\geq
0\\}\\}}\textbf{1}_{\\{\tau_{X_{n-l}}^{Y}>l,Y_{l}=\rho^{+}\\}}\right].\end{split}$
(39)

First, suppose the transient ERRW on a Galton-Watson tree $(X_{n})_{n\geq 0}$
has a positive speed. From Fact 2.2, we have
$\mathbb{E}_{\rho}[\Theta_{1}|\tau_{\rho_{*}}=\infty]<\infty$. Fix $K\geq 1$.
We see that

$\displaystyle\textbf{1}_{\\{\tau_{\rho^{+}}^{X}=\infty,n-l\in\\{\Theta_{k},k\geq
0\\}\\}}\textbf{1}_{\\{\tau_{X_{n-l}}^{Y}>l,Y_{l}=\rho^{+}\\}}$
$\displaystyle\geq$
$\displaystyle\textbf{1}_{\\{\tau_{\rho^{+}}^{X}=\infty,n-l\in\\{\Theta_{k},k\geq
K\\}\\}}\textbf{1}_{\\{\tau_{X_{\Theta_{K}}}^{Y}>l,Y_{l}=\rho^{+}\\}}.$

Thus, we can apply the renewal theorem when $n-l$ goes to infinity. Recall
that $b_{i}:={\mathbb{P}}_{\rho}(i\in\\{\Theta_{k},k\geq
0\\}|\tau_{\rho_{*}}=\infty)$. From the regeneration structure and branching
property at $\Theta_{K}$,

$\begin{split}&\mathbb{E}_{(\rho^{-},\rho^{+})}\left[\sum_{l=0}^{n}\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(l))\textbf{1}_{\\{\tau_{\rho^{+}}^{X}=\infty,n-l\in\\{\Theta_{k},k\geq
0\\}\\}}\textbf{1}_{\\{\tau_{X_{n-l}}^{Y}>l,Y_{l}=\rho^{+}\\}}\right]\\\
\geq&\mathbb{E}_{(\rho^{-},\rho^{+})}\left[\sum_{l=0}^{n}\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(l))\textbf{1}_{\\{\tau_{\rho^{+}}^{X}=\infty,n-l\in\\{\Theta_{k},k\geq
K\\}\\}}\textbf{1}_{\\{\tau_{X_{\Theta_{K}}}^{Y}>l,Y_{l}=\rho^{+}\\}}\right]\\\
\geq&\mathbb{E}_{(\rho^{-},\rho^{+})}\left[\sum_{l=0}^{n/2}\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(l))\textbf{1}_{\\{\tau_{\rho^{+}}^{X}=\infty,n-l\geq\Theta_{K}\\}}b_{n-l-\Theta_{K}}\textbf{1}_{\\{\tau_{X_{\Theta_{K}}}^{Y}>l,Y_{l}=\rho^{+}\\}}\right].\end{split}$
(40)

By applying Fatou’s Lemma and (37) on the last display of (40), we see that

$\displaystyle\liminf_{n\rightarrow\infty}\mathbb{E}_{(\rho^{-},\rho^{+})}\left[\sum_{l=0}^{n/2}\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(l))\textbf{1}_{\\{\tau_{\rho^{+}}^{X}=\infty,n-l\geq\Theta_{K}\\}}b_{n-l-\Theta_{K}}\textbf{1}_{\\{\tau_{X_{\Theta_{K}}}^{Y}>l,Y_{l}=\rho^{+}\\}}\right]$
$\displaystyle\geq$
$\displaystyle\frac{1}{\mathbb{E}_{\rho}[\Theta_{1}|\tau_{\rho_{*}}=\infty]}\mathbb{E}_{(\rho^{-},\rho^{+})}\left[\sum_{l=0}^{\infty}\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(l))\textbf{1}_{\\{\tau_{\rho^{+}}^{X}=\infty\\}}\textbf{1}_{\\{\tau_{X_{\Theta_{K}}}^{Y}>l,Y_{l}=\rho^{+}\\}}\right].$

It yields with (39) that

$\begin{split}&\liminf_{n\rightarrow\infty}\mathbb{E}_{\rho}\left[\textbf{1}_{\\{\tau_{\rho_{*}}>n\\}}\right]\geq\frac{1}{\mathbb{E}_{\rho}[\Theta_{1}\textbf{1}_{\\{\tau_{\rho_{*}}=\infty\\}}]}\mathbb{E}_{(\rho^{-},\rho^{+})}\left[\sum_{l=0}^{\infty}\Phi(N_{(\rho^{-},\rho^{+})}^{Y}(l))\textbf{1}_{\\{\tau_{\rho^{+}}^{X}=\infty\\}}\textbf{1}_{\\{\tau_{X_{\Theta_{K}}}^{Y}>l,Y_{l}=\rho^{+}\\}}\right]\end{split}$
(41)

for all $K\geq 1$. By (28) and the fact that
$\mathbb{E}_{\rho}[\Theta_{1}|\tau_{\rho_{*}}=\infty]<\infty$, the right-hand
side of (41) goes to
${\mathscr{C}}/{\mathbb{E}_{\rho}[\Theta_{1}\textbf{1}_{\\{\tau_{\rho_{*}}=\infty\\}}]}$
as $K\rightarrow\infty$ by monotone convergence, which implies that

$\displaystyle\mathbb{E}_{\rho}[\beta]\geq\frac{\mathscr{C}}{\mathbb{E}_{\rho}[\Theta_{1}\textbf{1}_{\\{\tau_{\rho_{*}}=\infty\\}}]},$

so $\mathscr{C}$ is finite.

Next, suppose $\mathscr{C}<\infty$. By Theorem 3.9, specifically (31) with
$F\equiv 1$ (in the proof of Theorem 3.9, we do not use the condition that
$\mathbb{E}_{\rho}[\Theta_{1}\textbf{1}_{\\{\tau_{\rho_{*}}=\infty\\}}]<\infty$),
we have

$\displaystyle\frac{\mathscr{C}}{\mathbb{E}_{\rho}[\Theta_{1}\textbf{1}_{\\{\tau_{\rho_{*}}=\infty\\}}]}=\mathbb{E}_{\rho}[\beta].$

Hence we have the finiteness of the
$E_{\rho}[\Theta_{1}|\tau_{\rho_{*}}=\infty]$, which is equivalent to positive
speed. ∎

##  4 Speed of ERRW

###  4.1 Speed Formula

Recall the definition of $\Phi$ and $F$ in (6) and (8) respectively.

###### Proof of Theorem 1.3.

By dominated converge, we have

$\displaystyle
v=\lim_{n\rightarrow\infty}\mathbb{E}_{\rho}\left[\frac{|X_{n}|}{n}\Bigg{|}\mathcal{S}\right].$

We observe that

$\displaystyle\mathbb{E}_{\rho}\left[|X_{n}|\big{|}\mathcal{S}\right]=\sum_{k=0}^{n-1}\mathbb{E}_{\rho}\left[|X_{k+1}|-|X_{k}|\big{|}\mathcal{S}\right]=\sum_{k=0}^{n-1}\mathbb{E}_{\rho}\left[\sum_{i=1}^{\nu(X_{k})}\eta(X_{k},X_{k}i)-\eta({X_{k}},(X_{k})_{*})\Bigg{|}\mathcal{S}\right].$

We then apply Theorem 3.9 and let the functional $\mathbf{F}$ be
$\sum_{i=1}^{\nu(\rho)}\eta(\rho,\rho i)-\eta({\rho},\rho_{*})$. With Lemma
3.8, we have

$\begin{split}&\lim_{k\rightarrow\infty}\mathbb{E}_{\rho}\left[\sum_{i=1}^{\nu(X_{k})}\eta(X_{k},X_{k}i)-\eta({X_{k}},(X_{k})_{*})\Bigg{|}\mathcal{S}\right]=\mathscr{C}^{-1}\times\\\
&\mathbb{E}_{(\rho^{-},\rho^{+})}\left[\left(\sum_{i=1}^{\nu(\rho^{+})}\eta(\rho^{+},\rho^{+}i)-\eta(\rho^{+},\rho^{-})\right)\frac{\beta(\rho^{-})(1-\beta(\rho^{+}))}{\eta(\rho^{+},\rho^{-})}\sum_{k\geq
0}\Phi(k)(1-\beta(\rho^{+}))^{k}(1-\beta(\rho^{-}))^{k}\right].\end{split}$
(42)

Recall the definition of $(A_{i},1\leq i\leq\nu)$ in (2). From (27), we see
that

$\begin{split}&\mathbb{E}_{(\rho^{-},\rho^{+})}\left[\left(\sum_{i=1}^{\nu(\rho^{+})}\eta(\rho^{+},\rho^{+}i)-\eta(\rho^{+},\rho^{-})\right)\frac{\beta(\rho^{-})(1-\beta(\rho^{+}))}{\eta(\rho^{+},\rho^{-})}\sum_{k\geq
0}\Phi(k)(1-\beta(\rho^{+}))^{k}(1-\beta(\rho^{-}))^{k}\right]\\\
=&\mathbb{E}_{(\rho^{-},\rho^{+})}\left[\frac{\beta_{0}(\sum_{i=1}^{\nu}A_{i}-1)}{1+\sum_{i=1}^{\nu}A_{i}\beta(\rho^{+}i)}\times\sum_{k\geq
0}\Phi(k)(\frac{1-\beta(\rho^{-})}{1+\sum_{i=1}^{\nu}A_{i}\beta(\rho^{+}i)})^{k}\right]\\\
=&\mathbb{E}\left[\frac{\beta_{0}(\sum_{i=1}^{\nu}A_{i}-1)}{1+\sum_{i=1}^{\nu}A_{i}\beta_{i}}\times
F\left(\frac{1-\beta_{0}}{1+\sum_{i=1}^{\nu}A_{i}\beta_{i}}\right)\right]\end{split}$
(43)

where $\beta_{0},\beta_{1},\cdots$ are i.i.d copies of $\beta$. In the same
way,

$\begin{split}\mathscr{C}=&\mathbb{E}_{(\rho^{-},\rho^{+})}\left[\frac{\beta(\rho^{-})(1-\beta(\rho^{+}))}{\eta(\rho^{+},\rho^{-})}\sum_{k\geq
0}\Phi(k)(1-\beta(\rho^{+}))^{k}(1-\beta(\rho^{-}))^{k}\right]\\\
=&\mathbb{E}\left[\frac{\beta_{0}(\sum_{i=1}^{\nu}A_{i}+1)}{1+\sum_{i=1}^{\nu}A_{i}\beta_{i}}\times
F\left(\frac{1-\beta_{0}}{1+\sum_{i=1}^{\nu}A_{i}\beta_{i}}\right)\right].\end{split}$
(44)

Then we conclude from (42)-(44) that

$\displaystyle v=$
$\displaystyle\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{k=0}^{n-1}\mathbb{E}_{\rho}\left[\sum_{i=1}^{\nu(X_{k})}\eta(X_{k},X_{k}i)-\eta({X_{k}},(X_{k})_{*})\Bigg{|}\mathcal{S}\right]$
$\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\mathbb{E}_{\rho}\left[\sum_{i=1}^{\nu(X_{k})}\eta(X_{k},X_{k}i)-\eta({X_{k}},(X_{k})_{*})\Bigg{|}\mathcal{S}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\frac{\beta_{0}(\sum_{i=1}^{\nu}A_{i}+1)}{1+\sum_{i=1}^{\nu}A_{i}\beta_{i}}\times
F\left(\frac{1-\beta_{0}}{1+\sum_{i=1}^{\nu}A_{i}\beta_{i}}\right)\right]^{-1}\mathbb{E}\left[\frac{\beta_{0}(\sum_{i=1}^{\nu}A_{i}-1)}{1+\sum_{i=1}^{\nu}A_{i}\beta_{i}}\times
F\left(\frac{1-\beta_{0}}{1+\sum_{i=1}^{\nu}A_{i}\beta_{i}}\right)\right].$

∎

We show briefly how to get Corollary 1.4. Let

$\displaystyle G(x)={{}_{2}F_{1}}(1,\alpha_{c};\alpha_{p};x):=\sum_{k\geq
0}\frac{\Gamma(\alpha_{p})\Gamma(\alpha_{c}+k)}{\Gamma(\alpha_{c})\Gamma(\alpha_{p}+k)}x^{k},$

and

$F(x)=\left(G(x)+\frac{xG^{\prime}(x)}{\alpha_{c}}\right).$

By taking $\alpha_{c}=\alpha_{p}=\alpha$, $G(x)=1/(1-x)$. We can readily get
the first formula in Corollary 1.4. When $\alpha_{p}=1,\alpha_{c}=1/2$, we can
express $G$ as

$G(x)=\frac{1}{\sqrt{1-x}},$

by considering the expansion of binomial series

$\frac{1}{\sqrt{1-x}}=\sum_{k\geq 0}\frac{(2k-1)!!}{(2k)!!}x^{k}.$

Then we obtain the second formula (11) for ERRW without direction.

###  4.2 Conditions for positive speed

In remaining part of the section, we set $\nu(\rho^{+})$ as $\nu$,
$\beta(\rho^{+})$ as $\beta$, $\beta(\rho^{+}i)$ as $\beta_{i}$,
$\beta(\rho^{-})$ as $\beta_{0}$, $\eta(\rho^{+},\rho^{+}i)$ as $\eta_{i}$ and
$\eta(\rho^{+},\rho^{-})$ as $\eta_{0}$ when we work on a double tree. For a
Galton-Watson tree, we also use $\nu$ for $\nu(\rho)$ and
$\eta_{0},\eta_{i},\beta_{i}$ for $\eta(\rho,\rho_{*}),\eta(\rho,\rho
i),\beta(\rho i),1\leq i\leq\nu$ respectively. Note that
$A_{i}=\eta_{i}/\eta_{0},1\leq i\leq\nu$ have a generic distribution $A$,
which is independent of $\nu$. Let $\rm GW(\cdot)$ denote the Galton-Watson
measure, and $\mathbb{E}_{GW}$ the corresponding expectation. We assume in
this section that $\mathbb{E}_{GW}[\nu]<\infty$. We first show the moment
estimation of $1/\beta$ is related to $A$. It is in fact a generalization of
[1, Lemma 2.2].

Recall that $\beta(x)$ can be seen as the effective conductance of the subtree
rooted at $x$, and

$\frac{1}{\beta}=1+\frac{1}{\sum_{i=1}^{\nu}A_{i}\beta_{i}}.$ (45)

Let $\mu$ be the number of vertices in the first generation that are the roots
of an infinite subtrees. We mention that $\mu$ follows the offspring
distribution of another Galton-Watson tree denoted by
$\mathbb{T}_{\mathcal{S}}$, which is made up of vertices
$\\{x\in\mathbb{T}:\mathbb{T}_{x}\text{ is infinite}\\}$ with the generating
function $\mathbb{E}_{GW}[s^{\mu}]=(f(q+(1-q)s)-q)/(1-q)$ [15, Proposition
5.28].

Based on the knowledge above, we state a frequently used lemma.

######  Lemma 4.1.

For a transient $(\alpha_{p},\alpha_{c})$-ERRW on a Galton-Watson tree and a
non-negative real number $k$, we have when $p_{0}+p_{1}>0$,

$\mathbb{E}\left[\frac{\textbf{1}_{\mathcal{S}}}{\beta^{k}}\right]<\infty$

if and only if $\mathbb{E}\left[A^{-k}\right]f^{\prime}(q)<1$.

######  Remark 4.2.

The Lemma can be extended to the random walk in random environment on a
Galton-Watson tree such that $A$ is independent of $\nu$.

###### Proof.

We start from the ‘if’ part and we assume
$\mathbb{E}\left[A^{-k}\right]f^{\prime}(q)<1$. Let $\beta^{(n)}(x):={{\rm
P}}^{\eta}_{x}(\tau_{n}^{e}<\tau_{x_{*}})$, where $\tau_{n}^{e}=\inf\\{k\geq
0:|X_{k}|=n\\}$ is the entrance time of level $n$ and $\beta^{(n)}$ is the
conductance of a tree with every vertex above level $n$ removed. All
discussions about conductance still work for $\beta^{(n)}$, and in particular,

$\frac{1}{\beta^{(n)}(\rho)}=1+\frac{1}{\sum_{i=1}^{\nu}A(\rho
i)\beta^{(n)}{(\rho i)}}.$

For $N>1$, it holds for any $x>0$ that

$(1+x)^{k}\leq 1+C(N)x^{k}\textbf{1}_{\\{x>N-1\\}}+N^{k}\textbf{1}_{\\{x\leq
N-1\\}}\leq 1+C(N)x^{k}+N^{k}$

where $C(N)>1$ goes to $1$ as $N$ goes to infinity. Hence

$\displaystyle\frac{\textbf{1}_{\mathcal{S}}}{(\beta^{(n)}(\rho))^{k}}\leq
1+C(N)\frac{\textbf{1}_{\mathcal{S}}}{(\sum_{i=1}^{\nu}A(\rho
i)\beta^{(n)}{(\rho i)})^{k}}+N^{k}.$

Let $I$ be the index of the children of $\rho$ such that $A(\rho
I)=\max\\{A(\rho i):1\leq i\leq\nu(\rho),\beta(\rho i)>0\\}$. We have that

$\frac{\textbf{1}_{\mathcal{S}}}{(\sum_{i=1}^{\nu}A(\rho i)\beta^{(n)}{(\rho
i)})^{k}}\leq\frac{\textbf{1}_{\\{\exists I\\}}}{(A(\rho I)\beta^{(n)}(\rho
I))^{k}}\textbf{1}_{\\{A(\rho i)\beta^{(n)}(\rho i)<\epsilon,\forall
i\not=I\\}}+\frac{1}{\epsilon^{k}}.$

Observe that

$\begin{split}&\lim_{\epsilon\to
0}\mathbb{E}\left[\frac{\textbf{1}_{\\{\exists I\\}}}{(A(\rho
I)\beta^{(n)}(\rho I))^{k}}\textbf{1}_{\\{A(\rho i)\beta^{(n)}(\rho
i)<\epsilon,\forall i\not=I\\}}\right]\\\
\leq&\mathbb{E}\left[\frac{\textbf{1}_{\mathcal{S}}}{(\beta^{(n-1)}(\rho))^{k}}\right]\lim_{\epsilon\rightarrow
0}\mathbb{E}\left[\nu(\rho)A(\rho
1)^{-k}\textbf{1}_{\\{\nu(\rho)>0\\}}\textbf{1}_{\\{A(\rho i)\beta(\rho
i)<\epsilon,\forall i\not=1\\}}\right]\\\
=&\mathbb{E}\left[\frac{\textbf{1}_{\mathcal{S}}}{(\beta^{(n-1)}(\rho))^{k}}\right]\mathbb{E}\left[A^{-k}(\nu
q^{\nu-1}\textbf{1}_{\\{\nu>1\\}}+\textbf{1}_{\\{\nu=1\\}})\right]\end{split}$

by dominated convergence. Hence we have

$\mathbb{E}\left[\frac{\textbf{1}_{\mathcal{S}}}{(\beta^{(n)})^{k}}\right]\leq
1+N^{k}+C(N)\lambda_{\epsilon}\mathbb{E}\left[\frac{\textbf{1}_{\mathcal{S}}}{(\beta^{(n-1)})^{k}}\right]+C(N)\epsilon^{-k},$

where
$\lambda_{\epsilon}:={\mathbb{E}}\left[A^{-k}\right]f^{\prime}(q)+\delta<1/C(N)$
as long as $\epsilon$ is small enough and $N$ large enough. Finally,

$\mathbb{E}\left[\frac{\textbf{1}_{\mathcal{S}}}{(\beta^{(n)})^{k}}\right]\leq(1+C(N)\epsilon^{-k}+N^{k})\frac{1}{(1-C(N)\lambda_{\epsilon})}+(C(N)\lambda_{\epsilon})^{n}(1-q).$

We let $n$ go to infinity and apply Fatou’s lemma to complete the proof.

We continue to prove the ‘only if’ part. Assume that
${\mathbb{E}}\left[A^{-k}\right]f^{\prime}(q)\geq 1$. Recall that $\mu$ is the
number of children of $\rho$ where an infinite subtree is rooted. By (45), we
have that conditioned on survival,

$\displaystyle\frac{1}{\beta}\geq
1+\textbf{1}_{\\{\mu=1\\}}\frac{1}{A_{1}\beta_{1}}.$

Therefore,

$\displaystyle\frac{1}{\beta^{k}}>\textbf{1}_{\\{\mu=1\\}}\frac{1}{A_{1}^{k}\beta^{k}_{1}}.$

By taking expectations on both sides, we have

$\displaystyle\mathbb{E}\left[\beta^{-k}|\mathcal{S}\right]>f^{\prime}(q){\mathbb{E}}\left[A_{1}^{-k}\right]\mathbb{E}\left[\beta_{1}^{-k}|\mathcal{S}\right],$

where $f^{\prime}(q)$ comes from the fact that
$\mathbb{P}(\mu=1|\mathcal{S})=f^{\prime}(q)$. Since $\beta$ and $\beta_{1}$
have the same distribution, and ${\mathbb{E}}[A^{-k}]f^{\prime}(q)\geq 1$ by
assumption, we have $\mathbb{E}\left[\beta^{-k}|\mathcal{S}\right]=\infty$.

∎

Now assume ${\mathbb{E}}[A^{-k}]f^{\prime}(q)=1$. We can also deduce by
induction that

$\displaystyle\frac{\textbf{1}_{\mathcal{S}}}{\beta^{k}}\geq\textbf{1}_{\mathcal{S}}(1+\textbf{1}_{\\{\mu(0)=1\\}}\frac{1}{A(0)}+\textbf{1}_{\\{\mu(0)=1,\mu(1)=1\\}}\frac{1}{A(0)A(1)}\dots)^{k},$

where $\mu(n)$, $n\geq 0$ are i.i.d with the law of $\mu$ and $A(n)$ are i.i.d
with the law of $A$. Set $\textbf{1}_{\\{\mu(n)=1\\}}A(n)$ as $\Xi_{n}$ for
$n\geq 0$, which are i.i.d, with

$\displaystyle\mathbb{E}\left[(\Xi_{n})^{k}|\mathcal{S}\right]=f^{\prime}(q){\mathbb{E}}\left[\frac{1}{A^{k}}\right]=1.$

Then $\psi:=1+\Xi_{0}+\Xi_{0}\Xi_{1}\dots$ satisfies that

$\displaystyle\lim_{x\rightarrow\infty}\frac{{\mathbb{P}}(\psi>x|\mathcal{S})}{x^{-k}}=C,$

for a positive constant $C$ by the Kesten–Grincevicius–Goldie theorem. (See,
for example, [10] for a statement of the theorem.) Hence

$\displaystyle\liminf_{x\rightarrow\infty}\frac{{\mathbb{P}}(\beta^{-1}>x|\mathcal{S})}{x^{-k}}\geq
C.$ (46)

It indicates the ‘heavy tail’ property of $1/\beta$.

For an ERRW, there is analogous result when $p_{0}+p_{1}=0$. Recall that
$d:=\min\\{n\geq 1,p_{n}>0\\}$.

######  Lemma 4.3.

For a transient $(\alpha_{p},\alpha_{c})$-ERRW on a Galton-Watson tree such
that $d\geq 2$ and a real number $k\geq 0$,

$\displaystyle\mathbb{E}\left[\frac{1}{\beta^{k}}\right]<\infty$

if and only if $k<d\alpha_{c}$.

###### Proof.

Mimic the ‘if’ part of Lemma 4.1, and we have for $k<d\alpha_{c}$

$\displaystyle\frac{1}{(\beta^{(n)}(\rho))^{k}}\leq
1+C(N)\frac{1}{(\sum_{i=1}^{\nu}A(\rho i)\beta^{(n)}{(\rho i)})^{k}}+N^{k}$
$\displaystyle\leq$ $\displaystyle 1+C(N)\frac{1}{(\sum_{i=1}^{d}A(\rho
i)\beta^{(n)}{(\rho i)})^{k}}+N^{k},$

where $C(N)$ goes to $1$ as $N$ goes to infinity. Then we can prove by
induction. In fact,

${\mathbb{E}}\left[\max_{1\leq i\leq d}A(\rho i)^{-k}\right]\leq
d^{k}{\mathbb{E}}\left[\left(\sum_{i=1}^{d}A(\rho
i)\right)^{-k}\right]<\infty$

by Lemma 2.3. By taking $1\leq I\leq d$ that maximizes $\\{A_{i}\\}_{1\leq
i\leq d}$, it holds that

$\displaystyle 1+C(N)\frac{1}{(\sum_{i=1}^{d}A(\rho i)\beta^{(n)}{(\rho
i)})^{k}}+N^{k}$ $\displaystyle\leq$ $\displaystyle 1+C(N)\frac{1}{(A(\rho
I)\beta^{(n)}(\rho I))^{k}}\textbf{1}_{\\{A(\rho i)\beta^{(n)}(\rho
i)<\epsilon,\,\forall i\neq I\\}}+C(N)\frac{1}{\epsilon^{k}}+N^{k}$

When $\epsilon$ is small enough, we have

$\displaystyle\mathbb{E}\left[\frac{1}{(\beta^{(n)}(\rho))^{k}}\right]\leq
1+C(N)\delta(\epsilon)\mathbb{E}\left[\frac{1}{(\beta^{(n)}(\rho
I))^{k}}\right]+C(N)\frac{1}{\epsilon^{k}}+N^{k}$

for $\delta(\epsilon):=\mathbb{E}\left[A(\rho I)^{-k}\textbf{1}_{\\{A(\rho
i)\beta^{(n-1)}(\rho i)<\epsilon,\,\forall i\neq I\\}}\right]$ goes to $0$ as
$\epsilon$ goes to $0$ by dominated convergence. Fix $\epsilon$ and $N$ such
that $C(N)\delta(\epsilon)<1$, by the induction argument, we have that
$(1/\beta^{(n)}(\rho))^{k}$ is integrable and so is $(1/\beta(\rho))^{k}$ by
Fatou’s lemma.

On the other hand, if $k\geq d\alpha_{c}$,

$\displaystyle\frac{1}{(\beta(\rho))^{k}}=\left(1+\frac{1}{\sum_{i=1}^{\nu}A(\rho
i)\beta{(\rho
i)}}\right)^{k}\geq\textbf{1}_{\\{\nu=d\\}}\frac{1}{(\sum_{i=1}^{d}A(\rho
i)\beta{(\rho
i)})^{k}}\geq\textbf{1}_{\\{\nu=d\\}}\frac{1}{(\sum_{i=1}^{d}A(\rho i))^{k}}.$

Thus, we have $\mathbb{E}\left[\beta^{-k}\right]=\infty$ from
${\mathbb{E}}\left[(\sum_{i=1}^{d}A(\rho i))^{-k}\right]=\infty$. ∎

Now we are ready to investigate when $\mathscr{C}$ is finite. We need a
technical condition that

$\displaystyle\mathbb{E}_{GW}\left[\nu^{K}\right]<\infty,$ (47)

where $K:=d\alpha_{c}+3+\alpha_{p}$ . The condition is not necessary for the
finiteness of $\mathscr{C}$. As is shown in Figure 1, we deal with three
different situations separately:

  * 1.

$p_{0}=0,p_{1}>0$;

  * 2.

$p_{0}=0,p_{1}=0$;

  * 3.

$p_{0}>0$.

First assume that $p_{0}=0$ and $0<p_{1}\leq 1$. For simplicity of notation,
let $s:=\alpha_{c}-\alpha_{p}+2$ and

$\displaystyle r:=\sup\\{t:{\mathbb{E}}\left[A^{-t}\right]p_{1}<1\\}.$ (48)

The function ${\mathbb{E}}\left[A^{-t}\right]$ is decreasing for
$t\in(-\alpha_{p},(\alpha_{c}-\alpha_{p})/2)$ and increasing for
$t\in((\alpha_{c}-\alpha_{p})/2,\alpha_{c})$. It implies that
$(\alpha_{c}-\alpha_{p})\vee 0\leq r<\alpha_{c}$, a fact we often need in the
proof below. Now we claim the proposition in this case.

######  Proposition 4.4.

For a transient $(\alpha_{p},\alpha_{c})$-ERRW, when $p_{0}=0$, $p_{1}>0$, and
(47) holds,

$\displaystyle\mathbb{E}\left[\frac{\beta_{0}(1-\beta)}{\eta_{0}}\sum_{k\geq
0}\dfrac{\Gamma(\alpha_{p})\Gamma(\alpha_{c}+k+1)}{\Gamma(\alpha_{c}+1)\Gamma(\alpha_{p}+k)}(1-\beta)^{k}(1-\beta_{0})^{k}\right]<\infty$
(49)

if and only if $2r-\alpha_{c}+\alpha_{p}-1>0$.

######  Remark 4.5.

In the special case $p_{1}=1$, where the tree degenerates to $\mathbb{Z}_{+}$,
we need $\alpha_{c}>\alpha_{p}$ to make the walk transient. Then
$r=\alpha_{c}-\alpha_{p}$ and the criterion becomes
$\alpha_{c}-\alpha_{p}-1>0$, which coincides with the condition

$\displaystyle{\mathbb{E}}\left[\frac{1}{A}\right]^{-1}=\frac{\alpha_{c}-1}{\alpha_{p}}>1$

given in [21, Theorem 1.16].

###### Proof.

For two quantities $A$ and $B$, we write $A\lesssim B$ (resp. $A\gtrsim B$)
when there exists a positive constant $c$, such that $A\leq cB$ (resp. $A\geq
cB$). Also, write $A\approx B$ if $A\lesssim B$ and $A\gtrsim B$. The
condition $2r-\alpha_{c}+\alpha_{p}-1>0$ is equivalent to $2r-s+1>0$.

Since as $k\rightarrow\infty$,

$\displaystyle\dfrac{\Gamma(\alpha_{p})\Gamma(\alpha_{c}+k+1)}{\Gamma(\alpha_{c}+1)\Gamma(\alpha_{p}+k)}\sim
k^{\alpha_{c}-\alpha_{p}+1},$

we have for $s>0$,

$\displaystyle\sum_{k\geq
0}\dfrac{\Gamma(\alpha_{p})\Gamma(\alpha_{c}+k+1)}{\Gamma(\alpha_{c}+1)\Gamma(\alpha_{p}+k)}(1-\beta)^{k}(1-\beta_{0})^{k}\approx\frac{1}{(1-(1-\beta)(1-\beta_{0}))^{s}},$

for $s=0$,

$\displaystyle\sum_{k\geq
0}\dfrac{\Gamma(\alpha+p)\Gamma(\alpha_{c}+k+1)}{\Gamma(\alpha_{c}+1)\Gamma(\alpha_{p}+k)}(1-\beta)^{k}(1-\beta_{0})^{k}\approx\ln(1-(1-\beta)(1-\beta_{0})),$

and for $s<0$,

$\displaystyle\sum_{k\geq
0}\dfrac{\Gamma(\alpha+p)\Gamma(\alpha_{c}+k+1)}{\Gamma(\alpha_{c}+1)\Gamma(\alpha_{p}+k)}(1-\beta)^{k}(1-\beta_{0})^{k}\approx
1.$

We first deal with the last case. When $s=\alpha_{c}-\alpha_{p}+2<0$, we see
$\alpha_{p}>2$, and

$\displaystyle\mathbb{E}\left[\frac{\beta_{0}(1-\beta)}{\eta_{0}}\sum_{k\geq
0}\dfrac{\Gamma(\alpha_{p})\Gamma(\alpha_{c}+k+1)}{\Gamma(\alpha_{c}+1)\Gamma(\alpha_{p}+k)}(1-\beta)^{k}(1-\beta_{0})^{k}\right]$
$\displaystyle\approx$
$\displaystyle\mathbb{E}\left[\frac{\beta_{0}(1-\beta)}{\eta_{0}}\right]\leq\mathbb{E}\left[\frac{1}{\eta_{0}}\right]\lesssim\mathbb{E}_{GW}\left[\nu\right]<\infty.$

In the next step, we assume $s\geq 0$. Let $s^{\prime}:=s+\epsilon
1_{\\{s=0\\}}$. First notice that

$\displaystyle\mathbb{E}\left[\frac{\beta_{0}(1-\beta)}{\eta_{0}(1-(1-\beta)(1-\beta_{0}))^{s^{\prime}}}\right]=\mathbb{E}\left[\dfrac{\beta_{0}(\eta_{0}+\sum_{i=1}^{\nu}\eta_{i}\beta_{i})^{s^{\prime}-1}}{(\eta_{0}\beta_{0}+\sum_{i=1}^{\nu}\eta_{i}\beta_{i})^{s^{\prime}}}\right]$
$\displaystyle\lesssim$
$\displaystyle\mathbb{E}\left[\dfrac{\beta_{0}\eta_{0}^{s^{\prime}-1}}{(\eta_{0}\beta_{0}+\sum_{i=1}^{\nu}\eta_{i}\beta_{i})^{s^{\prime}}}\right]+\mathbb{E}\left[\dfrac{\beta_{0}(\eta_{0}\beta_{0}+\sum_{i=1}^{\nu}\eta_{i}\beta_{i})^{s^{\prime}-1}}{(\eta_{0}\beta_{0}+\sum_{i=1}^{\nu}\eta_{i}\beta_{i})^{s^{\prime}}}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\dfrac{\beta_{0}\eta_{0}^{s^{\prime}-1}}{(\eta_{0}\beta_{0}+\sum_{i=1}^{\nu}\eta_{i}\beta_{i})^{s^{\prime}}}\right]+\mathbb{E}\left[\dfrac{\beta_{0}}{\eta_{0}\beta_{0}+\sum_{i=1}^{\nu}\eta_{i}\beta_{i}}\right]=:I_{1}+I_{2},$

where we use $1-\beta=\eta_{0}/(\eta_{0}+\sum_{i=1}^{\nu}\eta_{i}\beta_{i})$
for the first equality;
$(\eta_{0}+\sum_{i=1}^{\nu}\eta_{i}\beta_{i})^{s^{\prime}-1}\lesssim\eta_{0}^{s^{\prime}-1}+(\sum_{i=0}^{\nu}\eta_{i}\beta_{i})^{s^{\prime}-1}$
for the second inequality.

Under the condition $2r-s+1>0$, we intend to prove that (taking $\epsilon>0$
small enough when $s=0$) $I_{1}+I_{2}<\infty$, which implies (49). By
discussing whether $\eta_{0}$ is small, we have

$\displaystyle I_{1}$
$\displaystyle\lesssim\mathbb{E}\left[\nu^{s^{\prime}}\dfrac{\beta_{0}\eta_{0}^{s^{\prime}-1}}{(\eta_{0}\beta_{0}+\beta_{1})^{s^{\prime}}}1_{\\{\eta_{0}\leq
1/2\\}}\bigg{|}\eta_{1}=\max_{1\leq
i\leq\nu}\\{\eta_{i}\\}\right]+\mathbb{E}\left[\dfrac{\beta_{0}}{(\beta_{0}+\eta_{1}\beta_{1})^{s^{\prime}}}1_{\\{\eta_{0}\geq
1/2\\}}\right]$
$\displaystyle=\mathbb{E}\left[\nu^{s^{\prime}}\dfrac{\beta_{0}\eta_{0}^{s^{\prime}-1}}{(\eta_{0}\beta_{0}+\beta_{1})^{s^{\prime}}}1_{\\{\eta_{0}\leq
1/2\\}}\right]+\mathbb{E}\left[\dfrac{\beta_{0}}{(\beta_{0}+\eta_{1}\beta_{1})^{s^{\prime}}}1_{\\{\eta_{0}\geq
1/2\\}}\right]=:I_{3}+I_{4},$

where we use the observation that $\\{\eta_{0}\leq 1/2\\}$ implies that
$\\{\max_{1\leq i\leq\nu}\eta_{i}>1/2\nu\\}$.

For $I_{3}$, it holds that

$\displaystyle
I_{3}\lesssim\mathbb{E}\left[\nu^{s^{\prime}}\dfrac{\beta_{0}\eta_{0}^{s^{\prime}-1}}{(\eta_{0}\beta_{0}+\beta_{1})^{s^{\prime}}}\right]\lesssim\mathbb{E}\left[\nu^{s^{\prime}}\frac{1}{\beta_{0}^{s^{\prime}-1}\eta_{0}}\textbf{1}_{\\{\beta_{1}\leq\eta_{0}\beta_{0}\\}}+\nu^{s^{\prime}}\frac{\beta_{0}\eta_{0}^{s^{\prime}-1}}{\beta_{1}^{s^{\prime}}}\textbf{1}_{\\{\beta_{1}>\eta_{0}\beta_{0}\\}}\right].$

Since $\mathbb{E}[(\beta_{1})^{-r+\delta}]<\infty$ for any positive $\delta$
by Lemma 4.1, $\mathbb{P}(\beta_{1}\leq x)\lesssim x^{r-\delta}$ by Markov
inequality. The density of $\eta_{0}\in(0,1)$ is given by

$\displaystyle\frac{\mathrm{d}\mathbb{P}(\eta_{0}\leq
w|\nu)}{\mathrm{d}w}=\frac{\Gamma(\alpha_{p}+\nu\alpha_{c})}{\Gamma(\nu\alpha_{c})\Gamma(\alpha_{p})}w^{\alpha_{p}-1}(1-w)^{\nu\alpha_{c}-1}\lesssim\frac{\Gamma(\alpha_{p}+\nu\alpha_{c})}{\Gamma(\nu\alpha_{c})\Gamma(\alpha_{p})}w^{\alpha_{p}-1}\approx\nu^{\alpha_{p}}w^{\alpha_{p}-1}$
(50)

by (15) and Stirling’s approximation. Hence, we have

$\displaystyle\mathbb{E}\left[\nu^{s^{\prime}}\frac{1}{\beta_{0}^{s^{\prime}-1}\eta_{0}}\textbf{1}_{\\{\beta_{1}\leq\eta_{0}\beta_{0}\\}}\right]=\mathbb{E}_{GW}\left[\nu^{s^{\prime}}\int_{x\leq
zw}\frac{1}{z^{s^{\prime}-1}w}\mathrm{d}\mathbb{P}(\beta_{0}\leq
z)\mathrm{d}\mathbb{P}(\eta_{0}\leq w|\nu)\mathrm{d}\mathbb{P}(\beta_{1}\leq
x)\right]$ $\displaystyle\lesssim$
$\displaystyle\mathbb{E}_{GW}\left[\nu^{s^{\prime}+\alpha_{p}}\int
z^{r-s^{\prime}+1-\delta}w^{r+\alpha_{p}-\delta-2}\mathrm{d}\mathbb{P}(\beta_{0}\leq
z)\mathrm{d}w\right]\lesssim\mathbb{E}_{GW}\left[\nu^{s^{\prime}+\alpha_{p}}\right]<\infty,$

where the last approximation follows from $2r-s^{\prime}+1>0$ (and thus
$r+\alpha_{p}-1>\alpha_{c}-r>0$) by taking $\epsilon$ and $\delta$ small
enough. Similarly, together with integration by parts, we have

$\displaystyle\mathbb{E}\left[\nu^{s^{\prime}}\frac{\beta_{0}\eta_{0}^{s^{\prime}-1}}{\beta_{1}^{s^{\prime}}}\textbf{1}_{\\{\beta_{1}>\eta_{0}\beta_{0}\\}}\right]=\mathbb{E}_{GW}\left[\nu^{s^{\prime}}\int_{x>zw}\frac{zw^{s^{\prime}-1}}{x^{s^{\prime}}}\mathrm{d}\mathbb{P}(\beta_{0}\leq
z)\mathrm{d}\mathbb{P}(\eta_{0}\leq w|\nu)\mathrm{d}\mathbb{P}(\beta_{1}\leq
x)\right]$ $\displaystyle\lesssim$
$\displaystyle\mathbb{E}\left[\nu^{s^{\prime}}\beta_{0}\eta_{0}^{s^{\prime}-1}\right]+\mathbb{E}_{GW}\left[\nu^{s^{\prime}}\int_{x>zw}\frac{zw^{s^{\prime}-1}}{x^{s^{\prime}+1}}\mathbb{P}(\beta_{1}\leq
x)\mathrm{d}x\mathrm{d}\mathbb{P}(\beta_{0}\leq
z)\mathrm{d}\mathbb{P}(\eta_{0}\leq w|\nu)\right]$ $\displaystyle\lesssim$
$\displaystyle\mathbb{E}_{GW}\left[\nu^{s^{\prime}}\int
zw^{s^{\prime}-1}(z^{r-s^{\prime}-\delta}w^{r-s^{\prime}-\delta}\vee
1)\mathrm{d}\mathbb{P}(\beta_{0}\leq z)\mathrm{d}\mathbb{P}(\eta_{0}\leq
w|\nu)\right]\lesssim\mathbb{E}_{GW}\left[\nu^{s^{\prime}+\alpha_{p}}\right]<\infty,$

where we use the fact that
$\mathbb{E}\left[\nu^{s^{\prime}}\beta_{0}\eta_{0}^{s^{\prime}-1}\right]$ is
finite since $\alpha_{p}+s^{\prime}-1\geq\alpha_{c}+1>0$ and
$\mathbb{E}[\nu]\leq\mathbb{E}[\nu^{\alpha_{c}+3+\alpha_{p}}]<\infty$.

For $I_{4}$, the same deduction yields that

$\displaystyle\mathbb{E}\left[\frac{\beta_{0}}{(\beta_{0}+\eta_{1}\beta_{1})^{s^{\prime}}}\right]\lesssim\mathbb{E}\left[\frac{\beta_{0}}{\beta_{1}^{s^{\prime}}\eta_{1}^{s^{\prime}}}\textbf{1}_{\\{\beta_{0}\leq\eta_{1}\beta_{1}\\}}+\frac{1}{\beta_{0}^{s^{\prime}-1}}\textbf{1}_{\\{\beta_{0}>\eta_{1}\beta_{1}\\}}\right]$
$\displaystyle\lesssim$ $\displaystyle\mathbb{E}_{GW}\left[\int
w^{r-s^{\prime}+1-\delta}z^{r-s^{\prime}+1-\delta}\mathrm{d}\mathbb{P}(\beta_{1}\leq
z)\mathrm{d}\mathbb{P}(\eta_{1}\leq
w|\nu)\right]\lesssim\mathbb{E}_{GW}\left[\nu^{\alpha_{c}}\right]<\infty,$

since $\mathbb{E}[(\beta_{1})^{-r+\delta}]<\infty$,

$\displaystyle\frac{\mathrm{d}\mathbb{P}(\eta_{1}\leq
w|\nu)}{\mathrm{d}w}\lesssim\frac{\Gamma(\alpha_{p}+\nu\alpha_{c})}{\Gamma(\alpha_{c})\Gamma((\nu-1)\alpha_{c}+\alpha_{p})}w^{\alpha_{c}-1}\approx\nu^{\alpha_{c}}w^{\alpha_{c}-1}$
(51)

and $2r-s^{\prime}+1>0$ (which implies $\alpha_{c}+r-s^{\prime}+1>0$ due to
$\alpha_{c}>r$).

We then deal with $I_{2}$. We claim that $I_{2}$ is integrable under the
condition $2r-\alpha_{c}+\alpha_{p}-1>0$. In fact, if $r>0$, we see $2r-1+1>0$
and $r+\alpha_{p}-1>\alpha_{c}-r>0$, By plugging $s^{\prime}=1$ into $I_{1}$,
we obtain $I_{2}<\infty$ immediately. Note that when $s^{\prime}=1$, we have
$\mathbb{E}_{GW}\left[\nu^{1+\alpha_{p}}\right]\leq\mathbb{E}_{GW}\left[\nu^{3+\alpha_{c}+\alpha_{p}}\right]<\infty$.
If $r=0$, we have $\nu\equiv 1$ and $\alpha_{c}\leq\alpha_{p}$, which falls
into the region of recurrence.

Now we continue to prove that $2r-s+1>0$ is necessary by contradiction. It is
true even if the condition (47) is dropped. Assume that $2r-s+1\leq 0$ (which
implies $s\geq 1$). It yields that

$\displaystyle\mathbb{E}\left[\frac{\beta_{0}(1-\beta)}{\eta_{0}}\sum_{k\geq
0}\dfrac{\Gamma(\alpha_{p})\Gamma(\alpha_{c}+k+1)}{\Gamma(\alpha_{c}+1)\Gamma(\alpha_{p}+k)}(1-\beta)^{k}(1-\beta_{0})^{k}\right]$
$\displaystyle\approx$
$\displaystyle\mathbb{E}\left[\dfrac{\beta_{0}(\eta_{0}+\sum_{i=1}^{\nu}\eta_{i}\beta_{i})^{s-1}}{(\eta_{0}\beta_{0}+\sum_{i=1}^{\nu}\eta_{i}\beta_{i})^{s}}\right]\gtrsim\mathbb{E}\left[\dfrac{\beta_{0}\eta_{0}^{s-1}}{(\eta_{0}\beta_{0}+\sum_{i=1}^{\nu}\eta_{i}\beta_{i})^{s}}\right]=I_{1}$

If $s=1$, $r=0$, which implies recurrence. If $s>1$, since event $\\{\nu=1\\}$
has positive probability, we have

$\displaystyle I_{1}$
$\displaystyle\gtrsim\int\frac{zw^{s-1}}{(zw+x)^{s}}\mathrm{d}\mathbb{P}(\beta_{0}\leq
z)\mathrm{d}\mathbb{P}(\eta_{0}\leq w)\mathrm{d}\mathbb{P}(\beta_{1}\leq x)$
$\displaystyle\gtrsim\int\dfrac{w^{s-1}}{(1+w)^{s}}\mathrm{d}\mathbb{P}(\eta_{0}\leq
w)\int_{x<z}z^{-s+1}\mathrm{d}\mathbb{P}(\beta_{0}\leq
z)\mathrm{d}\mathbb{P}(\beta_{1}\leq x)$
$\displaystyle\gtrsim\mathbb{E}\left[\beta_{1}^{-s+1}\wedge\beta_{0}^{-s+1}\right]\gtrsim\int_{z\geq
1}z^{s-2}\mathbb{P}({\beta_{1}}^{-1}\wedge{\beta_{0}}^{-1}\geq
z)\mathrm{d}z=\int_{z\leq 1}\mathbb{P}(\beta_{0}\leq z)^{2}z^{-s}\mathrm{d}z,$

since $\beta_{0}$ and $\beta_{1}$ have the same law. On the other hand, as is
shown in (46), there is a positive constant $C$ such that

$\displaystyle\liminf_{x\rightarrow\infty}\frac{\mathbb{P}({\beta}^{-1}>x)}{x^{-r}}\geq
C.$

Therefore, $\int_{z\leq 1}\mathbb{P}^{2}(\beta_{0}\leq
z)z^{-s}\mathrm{d}z=\infty$ since $2r-s+1\leq 0$, which implies that (49) does
not hold.

∎

We continue to deal with the case when $p_{0}=0$, $p_{1}=0$. Recall
$d:=\min\\{n\geq 1:p_{n}>0\\}$ and $\mathbb{E}[\beta^{-k}]<\infty$ if and only
if $k<d\alpha_{c}$ by Lemma 4.3.

######  Proposition 4.6.

For a transient $(\alpha_{p},\alpha_{c})$-ERRW, when $p_{0}=0$, $p_{1}=0$, and
(47) holds,

$\displaystyle\mathbb{E}\left[\frac{\beta_{0}(1-\beta)}{\eta_{0}}\sum_{k\geq
0}\dfrac{\Gamma(\alpha_{p})\Gamma(\alpha_{c}+k+1)}{\Gamma(\alpha_{c}+1)\Gamma(\alpha_{p}+k)}(1-\beta)^{k}(1-\beta_{0})^{k}\right]<\infty,$

if and only if $(2d-1)\alpha_{c}+\alpha_{p}-1>0$.

###### Proof.

Follow the notation in Proposition 4.4. Recall that
$1-\beta=\eta_{0}/(\eta_{0}+\sum_{i=1}^{\nu}\eta_{i}\beta_{i})$ and

$\displaystyle\frac{\mathrm{d}\mathbb{P}(1-\eta_{1}\leq
x|\nu)}{\mathrm{d}x}=\frac{\Gamma(\alpha_{p}+\nu\alpha_{c})}{\Gamma(\alpha_{c})\Gamma((\nu-1)\alpha_{c}+\alpha_{p})}x^{(\nu-1)\alpha_{c}+\alpha_{p}-1}(1-x)^{\alpha_{c}-1}.$

To prove the necessity, suppose $(2d-1)\alpha_{c}+\alpha_{p}-1\leq 0$, we see

$\displaystyle\mathbb{E}\left[\frac{\beta_{0}(1-\beta)}{\eta_{0}}\sum_{k\geq
0}\dfrac{\Gamma(\alpha_{p})\Gamma(\alpha_{c}+k+1)}{\Gamma(\alpha_{c}+1)\Gamma(\alpha_{p}+k)}(1-\beta)^{k}(1-\beta_{0})^{k}\right]$
$\displaystyle\gtrsim$
$\displaystyle\mathbb{E}\left[\frac{1-\beta}{\eta_{0}}\right]\gtrsim\mathbb{E}\left[\frac{\textbf{1}_{\\{\nu=d\\}}}{\eta_{0}+\sum_{i=1}^{d}\eta_{i}\beta_{i}}\right]$
$\displaystyle\gtrsim$
$\displaystyle\int\frac{1}{x+y}\mathrm{d}\mathbb{P}(\eta_{0}+\sum_{2}^{d}\eta_{i}\leq
x|\nu=d)\mathbb{\mathrm{d}}\mathbb{P}(\beta_{1}\leq y)$ $\displaystyle\gtrsim$
$\displaystyle\int_{x\leq y\leq
1/2}\frac{1}{y}\mathrm{d}\mathbb{P}(1-\eta_{1}\leq
x|\nu=d)\mathbb{\mathrm{d}}\mathbb{P}(\beta_{1}\leq y)$ $\displaystyle\gtrsim$
$\displaystyle\int_{y\leq
1/2}y^{(d-1)\alpha_{c}+\alpha_{p}-1}\mathrm{d}\mathbb{P}(\beta_{1}\leq
y)=\infty$

since $(d-1)\alpha_{c}+\alpha_{p}-1\leq-d\alpha_{c}$.

Following the proof in Proposition 4.4, we only need to prove for sufficiency
that when $(2d-1)\alpha_{c}+\alpha_{p}-1>0$ and
$\mathbb{E}\left[\nu^{K}\right]<\infty$ (recall that
$K=d\alpha_{c}+3+\alpha_{p}$),

$\displaystyle
I_{1}=\mathbb{E}\left[\dfrac{\beta_{0}\eta_{0}^{s^{\prime}-1}}{(\eta_{0}\beta_{0}+\sum_{i=1}^{\nu}\eta_{i}\beta_{i})^{s^{\prime}}}\right]<\infty$

where $s^{\prime}=s+\textbf{1}_{\\{s=0\\}}\epsilon$. (Note that $I_{2}$ is
finite automatically by taking $s^{\prime}=1$ in $I_{1}$.) By separating the
case $\eta_{0}>1/2$ and $\eta_{0}\leq 1/2$, we have by symmetry of
$\eta_{i},1\leq i\leq\nu$,

$\displaystyle I_{1}$
$\displaystyle\lesssim\mathbb{E}\left[\dfrac{\beta_{0}\textbf{1}_{\\{\eta_{0}>1/2\\}}}{(\beta_{0}+\sum_{i=1}^{\nu}\eta_{i}\beta_{i})^{s^{\prime}}}\right]+\mathbb{E}\left[\nu\dfrac{\beta_{0}\eta_{0}^{s^{\prime}-1}\textbf{1}_{\\{\eta_{1}=\max\\{\eta_{i},1\leq
i\leq\nu\\},\eta_{0}<1/2\\}}}{(\beta_{0}\eta_{0}+\sum_{i=1}^{\nu}\eta_{i}\beta_{i})^{s^{\prime}}}\right]$
$\displaystyle\lesssim\mathbb{E}\left[\dfrac{\beta_{0}\textbf{1}_{\\{\eta_{0}>1/2\\}}}{(\beta_{0}+\sum_{i=1}^{\nu}\eta_{i}\beta_{i})^{s^{\prime}}}\right]+\mathbb{E}\left[\nu^{s^{\prime}+1}\dfrac{\beta_{0}\eta_{0}^{s^{\prime}-1}\textbf{1}_{\\{\eta_{1}=\max\\{\eta_{i},1\leq
i\leq\nu\\},\eta_{0}<1/2\\}}}{(\beta_{0}\eta_{0}+\beta_{1}+\sum_{i=2}^{\nu}\eta_{i}\beta_{i})^{s^{\prime}}}\right]$
$\displaystyle\lesssim\mathbb{E}\left[\dfrac{\beta_{0}\textbf{1}_{\\{\eta_{0}>1/2\\}}}{(\beta_{0}+\sum_{i=1}^{\nu}\eta_{i}\beta_{i})^{s^{\prime}}}\right]+\mathbb{E}\left[\nu^{s^{\prime}+1}\dfrac{\beta_{0}\eta_{0}^{s^{\prime}-1}\textbf{1}_{\\{\eta_{1}>1/(2\nu)\\}}}{(\beta_{0}\eta_{0}+\beta_{1}+\sum_{i=2}^{\nu}\eta_{i}\beta_{i})^{s^{\prime}}}\right]$
$\displaystyle\lesssim\mathbb{E}\left[\dfrac{\beta_{0}\textbf{1}_{\\{\eta_{0}>1/2\\}}}{(\beta_{0}+\sum_{i=1}^{d}\eta_{i}\beta_{i})^{s^{\prime}}}\right]+\mathbb{E}\left[\nu^{s^{\prime}+1}\dfrac{\beta_{0}\eta_{0}^{s^{\prime}-1}\textbf{1}_{\\{\eta_{1}>1/(2\nu)\\}}}{(\beta_{0}\eta_{0}+\beta_{1}+\sum_{i=2}^{d}\eta_{i}\beta_{i})^{s^{\prime}}}\right]=:I_{3}+I_{4}.$

For $I_{4}$, it holds by the definition of Dirichlet distribution (15) that

$\displaystyle\mathbb{E}\left[\nu^{s^{\prime}+1}\dfrac{\beta_{0}\eta_{0}^{s^{\prime}-1}\textbf{1}_{\\{\eta_{1}>1/(2\nu)\\}}}{(\beta_{0}\eta_{0}+\beta_{1}+\sum_{i=2}^{d}\eta_{i}\beta_{i})^{s^{\prime}}}\right]$
$\displaystyle\lesssim$
$\displaystyle\mathbb{E}\Bigg{[}\nu^{s^{\prime}+1}\dfrac{\Gamma(\alpha_{p}+\nu\alpha_{c})}{\Gamma((\nu-d+1)\alpha_{c})}\int_{1-w-\sum_{i=2}^{d}x_{i}\geq\frac{1}{2\nu}}\dfrac{\beta_{0}w^{s^{\prime}-1}}{(\beta_{0}w+\beta_{1}+\sum_{i=2}^{d}x_{i}\beta_{i})^{s^{\prime}}}$
$\displaystyle[(\frac{1}{2\nu})^{(\nu-d+1)\alpha_{c}-1}\vee
1]w^{\alpha_{p}-1}\mathrm{d}w\prod_{i=2}^{d}(x_{i}^{\alpha_{c}-1}\mathrm{d}x_{i})\Bigg{]}$
$\displaystyle\approx$
$\displaystyle\mathbb{E}\left[\nu^{s^{\prime}+1+(d-1)\alpha_{c}+\alpha_{p}}\dfrac{\beta_{0}\bar{\eta}_{0}^{s^{\prime}-1}}{(\beta_{0}\bar{\eta}_{0}+\beta_{1}+\sum_{i=2}^{d}\bar{\eta}_{i}\beta_{i})^{s^{\prime}}}\right],$

where the density of $\bar{\eta}_{0}$ is proportional to
$w^{\alpha_{p}-1},0<w<1$ and that of $\bar{\eta}_{i},2\leq i\leq d$ are
proportional to $w^{\alpha_{c}-1},0<w<1$. The random variables
$\bar{\eta}_{i},2\leq i\leq d$, and $\bar{\eta}_{0}$ are independent of each
other and of other random variables. In the first inequality, we use the fact
that when $(\nu-d+1)\alpha_{c}-1<0$, on the event that
$\\{\eta_{1}>1/(2\nu)\\}$,

$\displaystyle\left(1-w-\sum_{i=2}^{d}x_{i}\right)^{(\nu-d+1)\alpha_{c}-1}\leq\left(\frac{1}{2\nu}\right)^{(\nu-d+1)\alpha_{c}-1}.$

Note that by independence

$\displaystyle\mathbb{P}\left(\beta_{1}+\sum_{i=2}^{d}\bar{\eta}_{i}\beta_{i}<x\right)\leq\mathbb{P}(\max\\{\beta_{1},\bar{\eta}_{2}\beta_{2},\dots\bar{\eta}_{d}\beta_{d}\\}<x)=\mathbb{P}(\beta_{1}\leq
x)\prod_{i=2}^{d}\mathbb{P}({\bar{\eta}_{i}}\beta_{i}\leq x).$

Thus we have
$\mathbb{P}(\beta_{1}+\sum_{i=2}^{d}\bar{\eta}_{i}\beta_{i}<x)\lesssim
x^{(2d-1)\alpha_{c}-\delta}$ from $\mathbb{P}(\beta\leq y)\lesssim
y^{d\alpha_{c}-\delta}$ and
$\mathbb{P}({\bar{\eta}_{i}}\beta_{i}<x)=\mathbb{E}[\mathbb{P}(\bar{\eta}_{i}<x/\beta_{i}|\beta_{i})]\lesssim
x^{\alpha_{c}},2\leq i\leq d$. Therefore, it holds by the same deduction as in
Proposition 4.4 that

$\displaystyle\mathbb{E}\left[\nu^{s^{\prime}+1+(d-1)\alpha_{c}+\alpha_{p}}\dfrac{\beta_{0}\bar{\eta}_{0}^{s^{\prime}-1}}{(\beta_{0}\bar{\eta}_{0}+\beta_{1}+\sum_{i=2}^{d}\bar{\eta}_{i}\beta_{i})^{s^{\prime}}}\right]$
$\displaystyle\lesssim$
$\displaystyle\mathbb{E}_{GW}\left[\nu^{s^{\prime}+1+(d-1)\alpha_{c}+\alpha_{p}}\int\dfrac{zw^{s^{\prime}-1}}{(zw+x)^{s^{\prime}}}\mathrm{d}\mathbb{P}(\beta_{0}\leq
z)\mathrm{d}\mathbb{P}(\bar{\eta}_{0}\leq
w)\mathrm{d}\mathbb{P}(\beta_{1}+\sum_{i=2}^{d}\bar{\eta}_{i}\beta_{i}\leq
x|\nu)\right]$ $\displaystyle\lesssim$
$\displaystyle\mathbb{E}_{GW}\left[\nu^{d\alpha_{c}+3+\epsilon}\int
z^{(2d-1)\alpha_{c}-\delta+1-s-\epsilon}w^{(2d-1)\alpha_{c}-\delta+\alpha_{p}-2}\mathrm{d}\mathbb{P}(\beta_{0}\leq
z)\mathrm{d}w\right]$

which is finite when $(2d-1)\alpha_{c}+\alpha_{p}-1>0$ (and thus
$(3d-2)\alpha_{c}+\alpha_{p}-1>0$) and
$\mathbb{E}[\nu^{d\alpha_{c}+3+\epsilon}]\leq\mathbb{E}[\nu^{d\alpha_{c}+3+\alpha_{p}}]<\infty$
when $\epsilon$ small enough.

We then deal with $I_{3}$ in the same way. By the substitution mentioned
above,

$\displaystyle\mathbb{E}\left[\dfrac{\beta_{0}\textbf{1}_{\\{\eta_{0}>1/2\\}}}{(\beta_{0}+\sum_{i=1}^{d}\eta_{i}\beta_{i})^{s^{\prime}}}\right]\lesssim\mathbb{E}_{GW}\left[\nu^{d\alpha_{c}}\int\dfrac{z}{(z+x)^{s^{\prime}}}\mathrm{d}\mathbb{P}(\beta_{0}\leq
z)\mathrm{d}\mathbb{P}(\sum_{i=1}^{d}{\bar{\eta}_{i}}\beta_{i}\leq x)\right].$

Recall that $\mathbb{P}(\beta\leq y)\lesssim y^{d\alpha_{c}-\delta}$ by Lemma
4.3 and $\mathbb{P}(\bar{\eta}_{i}\leq x_{i})\lesssim x_{i}^{\alpha_{c}}$ by
definition. Then we have
$\mathbb{P}(\sum_{i=1}^{d}{\bar{\eta}_{i}}\beta_{i}<x)\leq\mathbb{P}(\max_{1\leq
i\leq d}\\{{\bar{\eta}_{i}}\beta_{i}\\}<x)\lesssim x^{d\alpha_{c}}$ from
$\mathbb{P}({\bar{\eta}_{i}}\beta_{i}<x)=\mathbb{E}[\mathbb{P}(\bar{\eta}_{i}<x/\beta_{i}|\beta_{i})]\lesssim
x^{\alpha_{c}},1\leq i\leq d$ and independence of
$(\bar{\eta}_{i}\beta_{i})_{1\leq i\leq d}$. Following the proof of
Proposition 4.4 , for some $\delta>0$ small enough,

$\displaystyle\mathbb{E}_{GW}\left[\nu^{d\alpha_{c}}\int\dfrac{z}{(z+x)^{s^{\prime}}}\mathrm{d}\mathbb{P}(\beta_{0}\leq
z)\mathrm{d}\mathbb{P}(\sum_{i=1}^{d}{\bar{\eta}_{i}}\beta_{i}\leq
x)\right]\lesssim\mathbb{E}_{GW}\left[\nu^{d\alpha_{c}}\int
z^{d\alpha_{c}+1-s^{\prime}}\mathrm{d}\mathbb{P}(\beta_{0}\leq z)\right],$

which is finite when $\mathbb{E}[\nu^{d\alpha_{c}}]<\infty$ and
$(2d-1)\alpha_{c}+\alpha_{p}-1>0$. ∎

Finally, we assume that $p_{0}>0$. Define

$\displaystyle r:=\sup\\{k:{\mathbb{E}}[A^{-k}]f^{\prime}(q)<1\\}.$

We also have $0<r<\alpha_{c}$ from $f^{\prime}(q)<1$.

######  Proposition 4.7.

For a transient $(\alpha_{p},\alpha_{c})$-ERRW, when $p_{0}>0$ and (47) holds,

$\displaystyle\mathbb{E}\left[\frac{\beta_{0}(1-\beta)}{\eta_{0}}\sum_{k\geq
0}\dfrac{\Gamma(\alpha_{p})\Gamma(\alpha_{c}+k+1)}{\Gamma(\alpha_{c}+1)\Gamma(\alpha_{p}+k)}(1-\beta)^{k}(1-\beta_{0})^{k}\Bigg{|}\mathcal{S}_{\mathbb{T}^{-}}\right]<\infty,$
(52)

if and only if $r-\alpha_{c}+\alpha_{p}-1>0$.

###### Proof.

Let us first deal with the ‘if’ part. The inequality (52) holds if

$\displaystyle\mathbb{E}\left[\frac{\beta_{0}}{\eta_{0}}\sum_{k\geq
0}\dfrac{\Gamma(\alpha_{p})\Gamma(\alpha_{c}+k+1)}{\Gamma(\alpha_{c}+1)\Gamma(\alpha_{p}+k)}(1-\beta_{0})^{k}\right]<\infty.$

If $s=\alpha_{c}-\alpha_{p}+2<0$, then the summation is bounded and we only
need to ensure that $\mathbb{E}[1/\eta_{0}]<\infty$. It is naturally satisfied
since $r-\alpha_{c}+\alpha_{p}-1>0$ (which implies $\alpha_{p}>1$ by
$r<\alpha_{c}$), and $\mathbb{E}_{GW}[\nu]<\infty$. When $s\geq 0$, let us
consider $s^{\prime}=s+\epsilon\textbf{1}_{\\{s=0\\}}>0$ for $\epsilon>0$
small enough. We see

$\displaystyle\mathbb{E}\left[\frac{\beta_{0}}{\eta_{0}}\sum_{k\geq
0}\dfrac{\Gamma(\alpha+p)\Gamma(\alpha_{c}+k+1)}{\Gamma(\alpha_{c}+1)\Gamma(\alpha_{p}+k)}(1-\beta_{0})^{k}\right]\lesssim\mathbb{E}[\frac{\beta_{0}}{\eta_{0}(1-(1-\beta_{0}))^{s^{\prime}}}]={\mathbb{E}}\left[\eta_{0}^{-1}\right]\mathbb{E}\left[\beta_{0}^{1-s^{\prime}}\right]$

is finite when $r-\alpha_{c}+\alpha_{p}-1>0$ (which implies $\alpha_{p}>1$ and
$1-s^{\prime}>-r$) and $\mathbb{E}_{GW}[\nu]<\infty$.

For the ‘only if ’ part, when $r-\alpha_{c}+\alpha_{p}-1\leq 0$, we have
$s\geq r+1>0$. Since $p_{0}>0$, $\mathbb{P}(\beta=0)>0$. On the event
$\\{\nu=0\\}$, the left-hand side of (52) becomes

$\displaystyle\mathbb{E}\left[\frac{\beta_{0}}{\eta_{0}}\sum_{k\geq
0}\dfrac{\Gamma(\alpha+p)\Gamma(\alpha_{c}+k+1)}{\Gamma(\alpha_{c}+1)\Gamma(\alpha_{p}+k)}(1-\beta_{0})^{k}\textbf{1}_{\\{\nu=0\\}}\right]\approx\mathbb{E}\left[\frac{\beta_{0}}{(1-(1-\beta_{0}))^{s}}\right]\approx\mathbb{E}\left[\beta_{0}^{1-s}\right]$

which is infinite by Lemma 4.1. ∎

Now Theorem 1.1 is obtained from Proposition 4.4, 4.6 and 4.7.

## References

  * [1] Elie Aïdékon.  Transient random walks in random environment on a galton–watson tree.  Probability Theory and Related Fields, 142(3):525–559, 2008.
  * [2] Elie Aïdékon.  Speed of the biased random walk on a galton–watson tree.  Probability Theory and Related Fields, 159(3):597–617, 2014.
  * [3] Harry Bateman.  Higher transcendental functions [volumes i-iii], volume 1.  McGRAW-HILL book company, 1953.
  * [4] Gerard Ben Arous, Yueyun Hu, Stefano Olla, and Ofer Zeitouni.  Einstein relation for biased random walk on galton-watson trees.  In Annales de l’IHP Probabilités et statistiques, volume 49, pages 698–721, 2013.
  * [5] Erwin Bolthausen and Alain-Sol Sznitman.  Ten lectures on random media, volume 32.  Springer Science & Business Media, 2002.
  * [6] Andrea Collevecchio.  Limit theorems for reinforced random walks on certain trees.  Probability theory and related fields, 136(1):81–101, 2006.
  * [7] Don Coppersmith and Persi Diaconis.  Random walks with reinforcement.  Unpublished manuscript, 1986.
  * [8] Gabriel Faraud.  A Central Limit Theorem for Random Walk in a Random Environment on a Marked Galton-Watson Tree.  Electronic Journal of Probability, 16(none):174 – 215, 2011.
  * [9] Thierry Gross.  Marche aléatoire en milieu aléatoire sur un arbre.  PhD thesis, Paris 7, 2004.
  * [10] Péter Kevei.  A note on the Kesten–Grincevičius–Goldie theorem.  Electronic Communications in Probability, 21(none):1 – 12, 2016\.
  * [11] Shen Lin.  Harmonic measure for biased random walk in a supercritical Galton–Watson tree.  Bernoulli, 25(4B):3652 – 3672, 2019.
  * [12] Russell Lyons and Robin Pemantle.  Random walk in a random environment and first-passage percolation on trees.  The Annals of Probability, pages 125–136, 1992.
  * [13] Russell Lyons, Robin Pemantle, and Yuval Peres.  Ergodic theory on galton—watson trees: speed of random walk and dimension of harmonic measure.  Ergodic Theory and Dynamical Systems, 15(3):593–619, 1995.
  * [14] Russell Lyons, Robin Pemantle, and Yuval Peres.  Biased random walks on galton–watson trees.  Probability theory and related fields, 106(2):249–264, 1996.
  * [15] Russell Lyons and Yuval Peres.  Probability on trees and networks, volume 42.  Cambridge University Press, 2017.
  * [16] Jacques Neveu.  Arbres et processus de galton-watson.  In Annales de l’IHP Probabilités et statistiques, volume 22, pages 199–207, 1986.
  * [17] Robin Pemantle.  Phase transition in reinforced random walk and rwre on trees.  The Annals of Probability, pages 1229–1241, 1988.
  * [18] Yuval Peres and Ofer Zeitouni.  A central limit theorem for biased random walks on galton–watson trees.  Probability Theory and Related Fields, 140(3-4):595–629, 2008.
  * [19] Christophe Sabot.  Random Dirichlet environment viewed from the particle in dimension $d\geq 3$.  The Annals of Probability, 41(2):722 – 743, 2013.
  * [20] Christophe Sabot and Laurent Tournier.  Random walks in dirichlet environment: an overview.  In Annales de la Faculté des sciences de Toulouse: Mathématiques, volume 26, pages 463–509, 2017.
  * [21] Fred Solomon.  Random walks in a random environment.  The annals of probability, 3(1):1–31, 1975.