# Building your path to escape from home

D. Figueiredo1 ,  G. Iacobelli1 ,  R. Oliveira2 ,  B. Reed3 4 and  R. Ribeiro2

(Date:
1 UFRJ, Universidade Federal do Rio de Janeiro
2 IMPA, Instituto de Matemática Pura e Aplicada
3 School of Computer Science, McGill Univeristy
4 Laboratoire I3S, CNRS, France. )

###### Abstract.

Random walks on dynamic graphs have received increasingly more attention from
different academic communities over the last decade. Despite the relatively
large literature, little is known about random walks that construct the graph
where they walk while moving around. In this paper we study one of the
simplest conceivable discrete time models of this kind, which works as
follows: before every walker step, with probability $p$ a new leaf is added to
the vertex currently occupied by the walker. The model grows trees and we call
it the Bernoulli Growth Random Walk (BGRW). We show that the BGRW walker is
transient and has a well-defined linear speed $c(p)>0$ for any $0<p\leq 1$. We
also show that the tree as seen by the walker converges (in a suitable sense)
to a random tree that is one-ended. Some natural open problems about this tree
and variants of our model are collected at the end of the paper.
_Keywords_ : random walks, random environments, dynamic random environments,
local weak convergence, random trees, rooted graphs, transience

##  1\. Introduction

Random walks on graphs that change over time have received much attention over
the past decades. Within this context, a large body of work assumes only edge
(or node) weights change over time while the graph structure (i.e., edge set)
remains constant. Examples include reinforced random walks and random walks in
random environments [1, 8, 9, 10, 14]. A much smaller line of work assumes
that the graph structure (edges and nodes) changes over time. However, such
works generally assume graph dynamics to be independent of the walker [3, 12,
16] (an exception is [13]).

This work explores a novel model where the random walk constructs its own
graph, mutually coupling the walker and graph dynamics. This model is defined
as follows:

  1. (0)

start with a finite tree with the walker sitting on one of the vertices;

  2. (1)

with probability $p$, add and connect a new leaf to the current location of
the walker;

  3. (2)

let the walker take one step on the current graph;

  4. (3)

go to step 1.

We refer to this model as BGRW (Bernoulli Growth Random Walk). Note that or
model may be seen as a sequence of pairs $(T_{n},X_{n})_{n\in\mathbb{N}}$,
where $T_{n}$ is a tree and $X_{n}$ is the walker’s position on the tree
$T_{n}$. A more formal definition is given in Section 2. This model is a
variant of the Non-Restart Random Walk (NRRW) proposed by Amorim et al. [2].
There, the initial graph is a vertex with a loop edge, and new leafs are
created every $s$ steps for a fixed $s>0$. Prior to [2], other models of walks
creating graphs had been proposed, but they all had periodic restart step
where the random walker would jump to a uniform vertex in the tree [5, 17].

A fundamental question on dynamic graphs is the recurrent or transient nature
of the walker. Figure 1 shows simulated sample paths from the BGRW model for
different values of $p$. While all trees have exactly the same number of nodes
($n=5000$) their structural difference is striking. For larger values of $p$
the generated trees are very slim and long, as $p$ decreases the trees become
fatter and shorter. Intuitively, with large $p$ the random walk can escape
more easily, while for small $p$ the random walk wanders more.

|  |  |
---|---|---|---
$p=0.9$ | $p=0.5$ | $p=0.1$ | $p=0.01$

Figure 1. Trees with $n=5000$ nodes generated by simulating BGRW using
different values for $p$, illustrating the diversity in the tree structure.

Our findings show that for any fixed $p$, the random walk escapes with a
positive speed $c(p)>0$. This is similar to the results of Amorim et al. [2]
on the NRRW model with $s=1$; a similar result is expected to hold for all odd
$s>1$ [11] 111The case of even $s>1$ is recurrent due to parity issues [11]..
Indeed, when $p$ is close to $1$, the proof for $s=1$ presented in [2] can be
adapted to show transience.

As mentioned, most prior models and results constrain the walker to some
graph. Our finding suggests that when the walker is a prori unconstrained, it
constructs a graph that allows it to escape. In fact, we will see that the
initial graph is in some sense “forgotten”. More specifically, we will see
that the tree around the walker converges (in a suitable sense) to an infinite
random tree whose law does not depend on the initial states. We believe these
findings are a significant contribution to the ongoing discussion of random
walks on dynamic graphs.

###  1.1. Main results

Our first main result shows that our process has a well-defined, linear222We
also use the term “positive speed” to mean linear speed. asymptotic speed.

######  Theorem 1.1 (Positive speed).

For each $0<p\leq 1$, there exists a well-defined speed $0<c(p)\leq p$ for the
BGRW process with parameter $p$. That is, for any initial condition
$(T_{0},x_{0})$ of the process, the distance between $X_{n}$ and $x_{0}$
satisfies:

$\lim_{n\to\infty}\,\frac{{\rm
dist}_{T_{n}}(X_{n},x_{0})}{n}=c(p),\;\mathbb{P}_{T_{0},x_{0},p}\mbox{-almost
surely.}$

To obtain this result, we had to understand the distribution of degrees that
$X_{t}$ sees along the way. A more general question is what is the frequency
of (finite) trees that $X_{t}$ sees in a radius $r\geq 0$ around itself. To
make this precise, we consider pairs $(T_{t},X_{t})$ as random elements of the
space $\mathcal{T}_{*}$ of rooted locally finite trees considered up to
isomorphisms, with the local topology. The definition of $\mathcal{T}_{*}$ and
its local metric (which makes it a Polish space) are recalled in Section 6.

For each $t\in\mathbb{N}$, one may define an element
$[T_{t},X_{t}]\in\mathcal{T}_{*}$ as the equivalence class of the tree $T_{t}$
rooted at $X_{t}$. In what follows, $[T_{t},X_{t}]_{r}$ is the subtree of
height $r$ consisting of $X_{t}$ and all nodes of $T_{t}$ within distance at
most $r$ from $X_{t}$. The next theorem counts how many times the tree of
radius $r$ around $X_{t}$ takes a certain shape.

######  Theorem 1.2 (Convergence of the tree as seen by the walker).

For each $0<p\leq 1$, there exists a probability distribution $P_{p}$ over
rooted trees such that, for any initial condition $(T_{0},x_{0})$ and any
finite rooted tree $[S,x]\in\mathcal{T}_{*}$ with height $r>0$,

$\frac{1}{n+1}\sum_{t=0}^{n}\mathbb{1}_{\\{[T_{t},X_{t}]_{r}=[S,x]\\}}\rightarrow
P_{p}(\\{[T,o]\in\mathcal{T}_{*}\,:\,[T,o]_{r}=[S,x]\\})\;,\quad\mathbb{P}_{T_{0},x_{0},p}\mbox{-almost
surely.}$

This is essentially a mixing property of the BGRW when viewed as a Markov
chain over $\mathcal{T}_{*}$. Our proof reveals that $P_{p}$ is the unique
stationary measure of this chain with the following property: if the process
is started from $P_{p}$, then almost surely, for all $\ell\geq 1$, the walker
will eventually be at the tip of a path of length $\ell$. Theorem 1.2 follows
from a stronger statement, Theorem 7.1 in Section 7.

The measure $P_{p}$ is an interesting object in itself. The next Theorem gives
us some limited information on this probability measure. Recall that an
infinite rooted tree is one-ended if it contains a single infinite path
starting from the root.

######  Theorem 1.3 (Support of $P_{p}$).

Given $0<p\leq 1$, let $P_{p}$ be the limit measure in Theorem 1.2. Then
$P_{p}$ is supported on one-ended infinite trees. Any rooted tree $[S,x]$
(with a certain height $r$) satisfies

$P_{p}(\\{[T,o]\in\mathcal{T}_{*}\,:\,[T,o]_{r}=[S,x]\\})>0.$

Moreover, the degree of the root has exponential tails under $P_{p}$: that is,
there exist $c,C>0$ such that for all $k\geq 1$:

$P_{p}(\\{[T,o]\in\mathcal{T}_{*}\,:\,{\rm deg}_{T}(o)\geq k\\})\leq
C\,e^{-ck}.$

Theorem 1.3 is in fact a corollary of Theorem 7.2, which we present in Section
7.

###  1.2. Intuition and some difficulties

Behind our Theorems, there is a simple probabilistic mechanism that explains
our claims.

  1. (1)

Given a constant $\ell$, the BGRW will often create new induced paths of
length $\ell$. That is, there will be frequent times when the walker is at the
“tip” of a path of length $\ell$.

  2. (2)

On the other hand, the probability of backtracking on a path of length $\ell$
by more than $\ell/2$ steps goes to zero very fast with $\ell$.

The moments when BGRW creates a long path and does not backtrack by more than
half its length are “local regeneration times” in the following precise sense:
the sequence of neighborhoods of radius $\ell/2$ seen by the walker from that
point on are independent of the past. From this perspective, the Laws of Large
Numbers implicit in Theorems 1.1 and 1.2 are not surprising.

As it turns out, there are difficulties in establishing the intuitive picture
drawn by items $1$ and $2$ above. Creating paths looks easy enough: all one
needs is to create a new leaf and jump to it $\ell$ consecutive times.
However, in order for this to happen often, the walker needs to come across
lots of nodes of low degree. For this to take place, it is necessary that
nodes are usually not visited too many times. To prove that returns to a
vertex are unlikely to be numerous, one needs to show that the walk moves away
fast enough from any vertex. The upshot is that a weaker form of positive
speed is needed before we can justify the above items.

Proving that ${\rm dist}_{T_{n}}(X_{n},X_{0})$ grows at least linearly with
time will thus be the first major goal in our proof. Omer Angel (personal
communication) suggested to us that this might be done comparing our process
to a once reinforced random walk on trees. The rationale is that one may
imagine that BGRW “discovers” new edges rather than create them.
Unfortunately, we could not see a way to make the elegant arguments of
Colevecchio [6, 7] work in our setting. We thus resort to a bare-hands
argument.

Given the preliminary result on the growth of ${\rm
dist}_{T_{n}}(X_{n},X_{0})$, we can move on to establishing the existence of
the speed and the convergence of the tree as seen by the walker. It will be
crucial for us that this tree – or rather, the corresponding empirical measure
– converges almost surely to an invariant measure $P_{p}$ for the dynamics on
rooted trees, for all “nice” initial conditions. There is a high-level
similarity to the work of Lyons, Pemantle and Peres [15] on random walk on
Galton-Watson trees, where the existence of a speed relies on ergodic-
theoretic arguments in the space $\mathcal{T}_{*}$. However, in that paper the
stationary measure can be described explicitly (leading to an explicit formula
for the speed), which is not the case in our setting. Our analysis will also
require more quantitative estimates on the convergence. Finally, we note that
the random trees we consider are very different (eg. our tree is a.s. one-
ended).

###  1.3. Organization and main proof steps

The remainder of the paper is organized as follows. In Section 2 we define our
process formally. One important conceptual point will be to define it on
locally finite trees from the start.

The proof of linear growth of $\mathrm{dist}_{T_{n}}(X_{n},X_{0})$ begins in
Section 3, where we show that, for any positive $M$, it is very likely that
$\mathrm{dist}_{T_{m}}(X_{m},X_{0})\geq\log^{M}n$ for some $m\leq n$. This
requires comparisons with simple one dimensional random walk. The argument
continues in Section 4, where we prove that backtracking on a long path, if it
happens at all, typically takes a really long time. For this we introduce a
simplified “loop process” that only keeps track of the path itself along the
way. Combining polylog distances and long times to backtrack, we prove in
Section 5 that our process has positive drift away from $X_{0}$, and derive
some consequences of this fact for the degrees in the tree.

We switch gears for the remainder of the paper, as our arguments become more
abstract. In Section 6 we extend the definition of our process to the space of
rooted locally finite trees. The statement in Theorem 1.2, on the convergence
of the tree as seen by the walker, can then be stated as a weak convergence
result for the empirical measure of this process. Tightness and weak
convergence criteria are discussed in this section, and tightness is proven
right away.

Section 5 begins to study the loss-of-memory mechanism described above,
whereby long paths are created and never backtracked on. Since we deal with
infinite trees, we need some condition on the initial distribution to ensure
that this takes place. We use this in Section 6 to prove that the averages of
“local functions” along the trajectories of the process always converge almost
surely. This is basically the last ingredient we need to prove stronger
versions of Theorems 1.2 and 1.3 in Section 7. One key point is that the
limiting measure $P_{p}$ is a stationary distribution for our process.

The paper wraps up with Section 8, with some final comments, and an Appendix
containing technical results.

##  2\. Definition of the model

###  2.1. Preliminaries

All trees in this paper are locally finite (all vertices have finite degree).
Given a tree $T$, we let $V(T)$ and $E(T)$ denote its vertex and edge sets.
For $x,y\in V(T)$, $d_{T}(x)$ denotes the degree (number of neighbors) of $x$
in $T$ and ${\rm dist}_{T}(x,y)$ is the shortest-path distance between $x$ and
$y$.

We let $\Omega$ denote the set of all pairs $(T,x)$, where $T$ is locally
finite tree with $V(T)\subset\mathbb{N}$ and $\mathbb{N}\backslash V(T)$
infinite, and $x\in V(T)$. This set $\Omega$ can be described as a subset of a
product space
$\\{0,1\\}^{\mathbb{N}\cup\binom{\mathbb{N}}{2}}\times\mathbb{N}$ with a
natural $\sigma$-field; we omit the details.

Given a probability measure $\mu$ over some space, we use the symbol
$U\sim\mu$ to mean that $U$ is a random element with law $\mu$.

###  2.2. Definition of the process

Let $p\in(0,1]$. The BGRW process with parameter $p$ is a Markov chain with
transition kernel $K_{p}$. To define this kernel, given $(T,x)$, we sample
$(T^{\prime},x^{\prime})\sim K_{p}((T,x),\cdot)$ as follows.

  1. (1)

Let $m=\min\mathbb{N}\backslash V(T)$. With probability $p$, set
$V(T^{\prime})=V(T)\cup\\{m\\}$ and $E(T^{\prime})=E(T)\cup\\{\\{m,x\\}\\}$.
Otherwise, set $T^{\prime}=T$.

  2. (2)

Conditionally on the above, let $x^{\prime}$ be a uniformly chosen neighbor of
$x$ in $T^{\prime}$.

It is easy to see that this does define a valid Markov transition kernel on
$\Omega$. We use $(T_{t},X_{t})_{t\geq 0}$ to denote a trajectory of $K_{p}$
and ${\mathbb{P}}_{\mu,p}$ and ${\mathbb{E}}_{\mu,p}$ to denote probabilities
and expectations when $(T_{0},X_{0})\sim\mu$. If $\mu$ is a point mass on
$(S_{0},x_{0})$, we replace $\mu$ by $S_{0},x_{0}$ in the subscripts.

######  Remark 2.1.

Most of the time we will ignore this formal definition of the process and
stick with the informal version presented in the introduction. We will later
need to define this process on the set of rooted trees up to isomorphisms. See
Section 6 for details.

##  3\. Nontrivial distance from the root

In this section we show the following property of our process: for any $y\in
T_{0}$, and any constant $M>0$, the random walker will most likely reach
distance $\geq\log^{M}n$ from $y$ in at most $n$ steps.

######  Lemma 3.1.

For any $M>0$ and $0<p\leq 1$ there exist $n_{0}=n_{0}(p,M)\in\mathbb{N}$,
depending only on $p$ and $M$ such that, for all $n\geq n_{0}$, all finite
trees $T_{0}$ and all $x_{0},y\in T_{0}$,

${\mathbb{P}}_{T_{0},x_{0},p}\left(\exists m\leq
n,\mathrm{dist}_{T_{m}}(X_{m},y)\geq\log^{M}n\right)\geq 1-e^{-n^{1/4}}.$

For the proof of this Lemma, we make a definition.

######  Definition 3.1.

Say that $M>0$ is admissible if the conclusion of the Lemma holds for this
specific value of $M$. That is, $M$ is admissible if, for any $0<p\leq 1$,
there exist $n_{0}=n_{0}(p,M)\in\mathbb{N}$, depending only on $p$ and $M$
such that, for all $n\geq n_{0}$, all finite trees $T_{0}$ and all $x_{0},y\in
T_{0}$,

${\mathbb{P}}_{T_{0},x_{0},p}\left(\exists m\leq
n,\mathrm{dist}_{T_{m}}(X_{m},y)\geq\log^{M}n\right)\geq 1-e^{-n^{1/4}}.$

Clearly, if $M$ is admissible, so are all $0<M^{\prime}<M$. Our Lemma follows
from the next two Propositions.

######  Proposition 3.1 (“Easy”; proof in subsection 3.1).

$M=\frac{1}{2}$ is admissible.

######  Proposition 3.2 (“Harder”; proof in subsection 3.3).

If $M\geq\frac{1}{2}$ is admissible, so is $M+1/2$.

In between these two statements, we will also need to prove an intermediate
result. It basically says that, when $M$ is admissible and $x_{0}$ is “far”
from $y$, then it is likely that the distance from the walker to $y$ will
increase by at least one unit by time $n$. This probability is large enough
that we are likely to see many such increases in a small time window.

######  Claim 3.1 (Small growth in distance; proof in subsection 3.2).

Assume $M\geq\frac{1}{2}$ is admissible (cf. Definition 3.1). Then there exist
$n_{1}(p,M)\in\mathbb{N}$ such that, for $n\geq n_{1}(p,M)$, the following
property holds. Take a finite tree $T$ and $x,y\in T$ with
$\mathrm{dist}_{T}(x,y)\geq\log^{M}n$. Then

${\mathbb{P}}_{T,x,p}\left(\mathrm{dist}_{T_{t}}(X_{t},y)=\mathrm{dist}_{T}(x,y)+1\mbox{
for some }t\leq n\right)\geq 1-2\frac{(\log\log n)^{2}}{\log n}.$

As we will see, the “harder” Proposition 3.2 follows from this claim and the
assumption that $M$ is admissible applied to time $\approx\sqrt{n}$ instead of
$n$.

Throughout this section we will use the following simple and standard Lemma,
which we prove in the Appendix for completeness.

######  Lemma 3.2 (Proof in Appendix A).

Suppose $(I_{j})_{j\in\mathbb{N}\backslash\\{0\\}}$ are indicator random
variables. Assume $\mu$ is such that ${\mathbb{P}}\left(I_{1}=1\right)\geq\mu$
and

$\forall j>1\,:\,{\mathbb{P}}\left({I_{j}=1\mid
I_{1},\dots,I_{j-1}}\right)\geq\mu.$

Then for any $k,m\in\mathbb{N}\backslash\\{0\\}$

${\mathbb{P}}\left(\mbox{at least $k$ consecutive $1$'s in the sequence
$(I_{j})_{j=1}^{m}$}\right)\geq 1-(1-\mu^{k})^{\lfloor m/k\rfloor}.$

###  3.1. The “easy” proposition

###### Proof of Proposition 3.1.

It suffices to show that there exist $n_{0}=n_{0}(p)\in\mathbb{N}$ such that,
for all $n\geq n_{0}$, for any initial tree $T_{0}$ and initial vertex
$x_{0}\in T_{0}$,

${\mathbb{P}}_{T_{0},x_{0},p}\left(\exists t\leq
n\,:\,\mathrm{dist}_{T_{t}}(X_{t},y)\geq\log^{\frac{1}{2}}n\right)\geq
1-e^{-n^{1/4}}.$

To do this, we define, for each time $1\leq t\leq n$,

$I_{t}:=\mathbb{1}\\{\mathrm{dist}_{T_{t}}(X_{t},y)=\mathrm{dist}_{T_{t-1}}(X_{t-1},y)+1\\}.$

Notice that we have the following inclusion of events

$\left\\{\exists t\leq
n\,:\,\mathrm{dist}_{T_{t}}(X_{t},y)\geq\log^{\frac{1}{2}}n\right\\}\supset\left\\{\mbox{at
least $\lceil\log^{\frac{1}{2}}n\rceil$ consecutive 1's in
$(I_{t})_{t=1}^{n}$}\right\\}.$

So we will apply Lemma 3.2. The point is that, by the Markov property:

(3.3) ${\mathbb{P}}_{T_{0},x_{0},p}\left(I_{t}=1\mid
I_{1},\dots,I_{t-1}\right)\geq\inf_{T,x}{\mathbb{P}}_{T,x,p}\left(I_{1}=1\right)\geq\frac{p}{2}.$

Indeed, the the value $p/2$ is achieved when $x$ is a leaf of $T$. In that
case $I_{1}=1$ only occurs when a new neighbor is created for $x$ (with
probability $p$) and then the walker jumps to that neighbor (with probability
$1/2$). If $x$ is not a leaf, then the probability is $>1/2$.

Combining (3.3) with Lemma 3.2, we obtain:

(3.4) ${\mathbb{P}}_{T_{0},x_{0},p}\left(\exists t\leq
n\,:\,\mathrm{dist}_{T_{t}}(X_{t},y)\geq\log^{\frac{1}{2}}n\right)\geq
1-\left(1-\left(\frac{p}{2}\right)^{\lceil\log^{\frac{1}{2}}n\rceil}\right)^{\left\lceil\frac{n}{\lceil\log^{\frac{1}{2}}n\rceil}\right\rceil}.$

Now, observe that

$\begin{split}\left(1-\left(\frac{p}{2}\right)^{\lceil\log^{\frac{1}{2}}n\rceil}\right)^{\left\lceil\frac{n}{\lceil\log^{\frac{1}{2}}n\rceil}\right\rceil}&\leq\exp\left\\{-\exp\left\\{\log
n\left(1-\frac{\log\left(\frac{2}{p}\right)\left(\sqrt{\log n}+1\right)}{\log
n}-\frac{\log\log n}{\log n}\right)\right\\}\right\\}.\end{split}$

Choosing $n_{0}$ sufficiently large such that
$\frac{\log\left(\frac{2}{p}\right)\left(\sqrt{\log n}+1\right)}{\log
n}+\frac{\log\log n}{\log n}<\frac{3}{4}$, the lower bound (3.4) is $\geq
1-e^{-n^{1/4}}$ for all $n\geq n_{0}$. For later purposes we point out that,
$n_{0}(p)$ is not-increasing as a function of $p$.

###  3.2. A key claim

We now come to the proof of Claim 3.1, which connects the “easy” and “hard”
proposition in the proof.

###### Proof of Claim 3.1.

Consider the vertex $y_{*}$ on the unique path from $x$ to $y$ with
$\mathrm{dist}_{T}(x,y_{*})=\lceil\log^{M}n\rceil-1$. We recall that the
admissibility of $M$ implies, for all $0<p\leq 1$, the existence of $n_{0}$
depending only on $M$ and $p$ such that:

(3.5) $\forall n\geq n_{0}\,:\,{\mathbb{P}}_{T,x,p}(\exists t\leq
n\,:\,\mathrm{dist}_{T_{t}}(X_{t},y_{*})\geq\log^{M}n)\geq 1-e^{-n^{1/4}}.$

Now let $F$ (for failure) denote the event that
$\mathrm{dist}_{T_{t}}(X_{t},y_{*})\leq\mathrm{dist}_{T}(x,y)$ for all $t\leq
n$. Let $\tau_{y_{*}}$ the hitting time of $y_{*}$

$\tau_{y_{*}}:=\inf\\{t\in\mathbb{N}\,:\,X_{t}=y_{*}\\}\in\mathbb{N}\cup\\{+\infty\\}.$

Define $\tau^{+k}_{x}$ the $k$-th return time to $x$. That is, we set
$\tau^{+0}_{x}:=0$, and then (recursively for
$k\in\mathbb{N}\backslash\\{0\\}$):

$\tau^{+k}_{x}:=\left\\{\begin{array}[]{ll}+\infty,&\mbox{ if
}\tau_{x}^{+(k-1)}=+\infty;\\\
\inf\\{t>\tau^{+(k-1)}_{x}\,:\,X_{t}=x\\}\in\mathbb{N}\cup\\{+\infty\\},&\mbox{otherwise}.\end{array}\right.$

Note that, for any $k$, we may upper bound the probability of $F$ by three
terms, which we will bound separately.

(3.6)
${\mathbb{P}}_{T,x,p}(F)\leq{\mathbb{P}}_{T,x,p}(F\cap\\{\tau_{y_{*}}>n\\})+{\mathbb{P}}_{T,x,p}(F\cap\\{\tau^{+k}_{x}<\tau_{y_{*}}\leq
n\\})+{\mathbb{P}}_{T,x,p}(\tau^{+k}_{x}>\tau_{y_{*}}).$

We start with the first term in the RHS. Note that if $\tau_{y_{*}}>n$, then
the unique path from $X_{t}$ to $y$ passes through $y_{*}$ at all times $t\leq
n$. Therefore,

$\forall t\leq
n\,:\,\mathrm{dist}_{T_{t}}(X_{t},y)-\mathrm{dist}_{T}(x,y)=\mathrm{dist}_{T_{t}}(X_{t},y_{*})-\mathrm{dist}_{T}(x,y_{*}).$

In particular, when $F\cap\\{\tau_{y_{*}}>n\\}$ holds, we must have

$\forall t\leq
n\,:\,\mathrm{dist}_{T_{t}}(X_{t},y_{*})\leq\mathrm{dist}_{T}(x,y_{*})<\log^{M}n\mbox{,
i.e. the event in (\ref{eq:admissibleystar}) does not hold}.$

We conclude:

(3.7) ${\mathbb{P}}_{T,x,p}(F\cap\\{\tau_{y_{*}}>n\\})\leq e^{-n^{1/4}}.$

We now consider the second term in the RHS of (3.6). In order for
$F\cap\\{\tau^{+k}_{x}<\tau_{y_{*}}\leq n\\}$ to take place, it must be that
$X_{t}$ returns at least $k$ times to $x$ before visiting $y_{*}$ but never
gets to jump to a neighbor $x^{\prime}$ of $x$ with ${\rm
dist}(x^{\prime},y)={\rm dist}(x,y)+1$. Now, at each return to $x$, the
probability that $X_{t}$ jumps to such a neighbor conditionally on the process
up to that point is at least $p/2$: the probability of creating a leaf and
then not jumping in the direction of $y$333This is similar to what we did when
we proved equation (3.3) in the proof of Proposition 3.1.. We deduce:

(3.8) ${\mathbb{P}}_{T,x,p}(F\cap\\{\tau^{+k}_{x}<\tau_{y_{*}}\leq
n\\})\leq\left(1-\frac{p}{2}\right)^{k}.$

Finally, we come to the third term in the RHS of (3.6). Consider the walk
$X_{t}$ at the sequence of time steps that it spends on the path from $x$ to
$y$, up to the time $\tau_{y_{*}}$. The resulting process is a simple random
walk on the path with potential delays and reflecting barriers: indeed, since
our graph is a tree at all times, whenever the random walk leaves the path, it
must return to it (if it does return) at the same point that was last visited.
Now, in order that $\tau_{x}^{+k}>\tau_{y_{*}}$, it must be that this simple
random walk on the path hits $y_{*}$ before returning $k$ times to $x$. Since
the path has length $\mathrm{dist}_{T}(x,y)=\lceil\log^{M}n\rceil-1$, the
probability of this happening is $\leq k/(\lceil\log^{M}n\rceil-1)$, and we
obtain:

(3.9)
${\mathbb{P}}_{T,x,p}(\tau^{+k}_{x}>\tau_{y_{*}})\leq\frac{k}{\lceil\log^{M}n\rceil-1}.$

Combining the terms in (3.7), (3.8) and (3.9), we obtain a bound in (3.6):

(3.10) $\begin{split}{\mathbb{P}}_{T,x,p}(F)&\leq
e^{-n^{1/4}}+\left(1-\frac{p}{2}\right)^{k}+\frac{k}{\lceil\log^{M}n\rceil-1}\\\
&\leq\frac{\lceil(\log\log
n)^{2}\rceil}{\log^{M}n}\left[e^{-n^{1/4}}\frac{\log^{M}n}{\lceil(\log\log
n)^{2}\rceil}+e^{-\frac{p}{2}(\log\log n)^{2}}\frac{\log^{M}n}{\lceil(\log\log
n)^{2}\rceil}+\frac{\log^{M}n}{\log^{M}n-1}\right],\\\ \end{split}$

where the last inequality follows by choosing $k:=\lceil(\log\log
n)^{2}\rceil$. Choosing $n_{1}=n_{1}(p,M)$ sufficiently large in (3.10) such
that $e^{-n^{1/4}}\frac{\log^{M}n}{\lceil(\log\log
n)^{2}\rceil}+e^{-\frac{p}{2}(\log\log n)^{2}}\frac{\log^{M}n}{\lceil(\log\log
n)^{2}\rceil}+\frac{\log^{M}n}{\log^{M}n-1}<2$ we obtain that, for all $n\geq
n_{1}$,

(3.11) $\begin{split}{\mathbb{P}}_{T,x,p}(F)&\leq 2\frac{(\log\log
n)^{2}}{\log^{M}n}.\end{split}$

This proves the claim. Note that $n_{1}(p,M)$ is not-increasing in $p$.

###  3.3. The “harder” proposition

We now prove Proposition 3.2, thus finishing the proof of Lemma 3.1.

###### Proof of Proposition 3.2.

Fix an admissible $M\geq\frac{1}{2}$. Define (with hindsight) two time
lengths:

(3.12)
$t_{*}:=\lceil\log^{M+1/2}\,n\rceil,\,\ell_{*}:=\left\lfloor\sqrt{n}\right\rfloor.$

Both of these time lengths depend on $n$, but we omit this dependency from the
notation to avoid clutter. The definitions of these quantities will probably
seem misterious, but we comment on them in due time; see Remarks 3.1, 3.2 and
3.3 below.

The fact that $M$ is admissible and $\ell_{*}\to+\infty$ when $n\to+\infty$
implies that, for any $0<p\leq 1$, there exists $n_{2}(p,M)$ such that if
$n\geq n_{2}(p,M)$, we have the following properties for any finite tree
$T_{0}$ and any $x_{0}\in T_{0}$.

  1. (1)

By the definition of admissibility (Definition 3.1) applied with $\ell_{*}$
replacing $n$:

(3.13) ${\mathbb{P}}_{T_{0},x_{0},p}\left(\exists
m\leq\ell_{*},\mathrm{dist}_{T_{m}}(X_{m},y)\geq 2^{-M}\log^{M}n\right)\geq
1-e^{-\ell_{*}^{1/4}}\geq 1-e^{-\frac{1}{2}n^{1/8}}$

  2. (2)

By Claim 3.1 applied with $\ell_{*}$ replacing $n$, if $T$ is finite and
$x,y\in T$ with $\mathrm{dist}_{T}(x,y)\geq 2^{-M}\log^{M}n$, then:

(3.14)
${\mathbb{P}}_{T,x,p}\left(\mathrm{dist}_{T_{t}}(X_{t},y)=\mathrm{dist}_{T}(x,y)+1\mbox{
for some }t\leq\ell_{*}\right)\geq 1-2\frac{(\log\log
n)^{2}}{2^{-M}\log^{M}n}.$

Again we used that $\log\ell_{*}\approx\log n$.

######  Remark 3.1 ($\ell_{*}$ is large enough).

In the above we used the fact that $\log\ell_{*}\approx\log n$ to guarantee
that the two events under consideration have high probability. We will later
need that $n/\ell_{*}t_{*}$ is large; see Remark 3.2 below.

We now define a sequence of stopping times $\sigma_{j}$ and indicators
$I_{j}$. Intuitively, we will want that
$\mathrm{dist}_{T_{\sigma_{j}}}(X_{\sigma_{j}},y)>\mathrm{dist}_{T_{\sigma_{j-1}}}(X_{\sigma_{j-1}},y)$,
and we will signal such a success by setting $I_{j}=1$. More formally, for
$j=0$, $\sigma_{j}=0$ and $I_{j}=0$. We define $\sigma_{j}$ and $I_{j}$ for
$j>0$, with the following two choices.

  1. (a)

When $X_{\sigma_{j-1}}$ is too close to $y$: if
$\mathrm{dist}_{T_{\sigma_{j-1}}}(X_{\sigma_{j-1}},y)<2^{-M}\log^{M}n$, we
let:

(3.15) $\displaystyle\sigma_{j}$ $\displaystyle:=$
$\displaystyle\inf\\{t\geq\sigma_{j-1}\,:\,\mathrm{dist}_{T_{t}}(X_{t},y)\geq
2^{-M}\log^{M}n\mbox{ or }t-\sigma_{j-1}=\ell_{*}\\}\;$ (3.16) $\displaystyle
I_{j}$ $\displaystyle=$
$\displaystyle\mathbb{1}\\{\mathrm{dist}_{T_{\sigma_{j}}}(X_{\sigma_{j}},y)\geq
2^{-M}\log^{M}n\\}$

  2. (b)

When $X_{\sigma_{j-1}}$ is not too close to $y$: if
$\mathrm{dist}_{T_{\sigma_{j-1}}}(X_{\sigma_{j-1}},y)\geq 2^{-M}\log^{M}n$, we
set

(3.17) $\displaystyle\sigma_{j}$ $\displaystyle:=$
$\displaystyle\inf\\{t\geq\sigma_{j-1}\,:\,\mathrm{dist}_{T_{t}}(X_{t},y)=\mathrm{dist}_{T_{\sigma_{j-1}}}(X_{\sigma_{j-1}},y)+1\mbox{
or }t-\sigma_{j-1}=\ell_{*}\\}\;$ (3.18) $\displaystyle I_{j}$
$\displaystyle=$
$\displaystyle\mathbb{1}\\{\mathrm{dist}_{T_{t}}(X_{t},y)=\mathrm{dist}_{T_{\sigma_{j-1}}}(X_{\sigma_{j-1}},y)+1\\}$

We note some basic properties of these new random variables. First, we have
the deterministic bound $\sigma_{j}-\sigma_{j-1}\leq\ell_{*}$. In particular,
$\sigma_{j}\leq\ell_{*}\,j$ for all $j$. Second, we observe that, if we have
$m+1$ consecutive successes, i.e. if
$I_{j_{0}}=I_{j_{0}+1}=\dots=I_{j_{0}+m}=1$ for some
$j_{0},m\in\mathbb{N}\backslash\\{0\\}$, then:

$\mathrm{dist}_{T_{\sigma_{j_{0}}}}(X_{\sigma_{j_{0}}},y)\geq 2^{-M}\log^{M}n$

and

$\mathrm{dist}_{T_{\sigma_{j_{0}+m}}}(X_{\sigma_{j_{0}+m}},y)=\mathrm{dist}_{T_{\sigma_{j_{0}+m-1}}}(X_{\sigma_{j_{0}+m-1}},y)+1=\dots=\mathrm{dist}_{T_{\sigma_{j_{0}}}}(X_{\sigma_{j_{0}}},y)+m.$

We thus arrive at the following crucial observation (recall the time lengths
$t_{*},\ell_{*}$ in (3.12)).

######  Observation 3.1.

Assume that there are $t_{*}+1$ consecutive ones in the sequence
$(I_{j})_{j=1}^{\lfloor n/\ell_{*}\rfloor}$. Then, there exists $t\leq n$ such
that

$\mathrm{dist}_{T_{t}}(X_{t},y)\geq t_{*}\geq\log^{M+1/2}n.$

Indeed, if we have $t_{*}+1$ consecutive ones in this sequence there exists
$j_{0}$ with $(j_{0}+t_{*})\ell_{*}\leq n$ and
$I_{j_{0}}=I_{j_{0}+1}=\dots=I_{j_{0}+t_{*}}=1$. What we are after is to show
that the probability of $t_{*}+1$ consecutive ones is very likely. The upshot
is that we may apply Lemma 3.2 above to control the probability that the RW
reaches distance $\log^{M+1/2}n$ from $y$ in $n$ time steps, i.e. that $M+1/2$
is admissible.

######  Remark 3.2.

Note that for the Lemma to be effective we need $n/\ell_{*}\gg 1$ so that
there are “many indicators” to consider, and also that $n/\ell_{*}t_{*}\gg 1$.
It will later become clear that (for $t_{*}$ polylogarithmic) it suffices that
$n/\ell_{*}\geq n^{1/4+c+o(1)}$ for some $c>0$.

To apply Lemma 3.2, we must lower bound
${\mathbb{P}}_{T_{0},x_{0},p}(I_{1}=1)$ and
${\mathbb{P}}_{T_{0},x_{0},p}\left(I_{j}=1\mid I_{1},\dots,I_{j-1}\right)$. By
the strong Markov property, these quantities are lower bounded by

$\inf_{T,x}{\mathbb{P}}_{T,x,p}\left(I_{1}=1\right)$

Crucially, conditions (a) and (b) in the definition of $\sigma_{1}$ and
$I_{1}$ correspond precisely to the situations in the two bounds (3.13) and
(3.14) (respectively). It follows that, for any $0<p\leq 1$, there exists a
$n_{3}=n_{3}(p,M)$ such that, for all $n\geq n_{3}$,

$\inf_{T,x}{\mathbb{P}}_{T,x,p}\left(I_{1}=1\right)\geq\mu:=1-2\,\frac{(\log\log
n)^{2}}{2^{-M}\log^{M}n}.$

Lemma 3.2 implies that:

${\mathbb{P}}_{T_{0},x_{0},p}\left(\mbox{at least $t_{*}+1$ consecutive ones
in $(I_{j})_{j=1}^{\lfloor n/\ell_{*}\rfloor}$}\right)\geq
1-(1-\mu^{t_{*}+1})^{\left\lfloor\frac{\lfloor
n/\ell_{*}\rfloor}{t_{*}+1}\right\rfloor}.$

What is left to show is that, for any $0<p\leq 1$, there exists
$n_{4}=n_{4}(p,M)$ such that

(3.19) $\forall n\geq n_{4}\,:\,(1-\mu^{t_{*}+1})^{\left\lfloor\frac{\lfloor
n/\ell_{*}\rfloor}{t_{*}+1}\right\rfloor}\leq\exp(-n^{1/4}),$

which would imply

$\forall n\geq n_{4}\,:\,{\mathbb{P}}_{T_{0},x_{0},p}\left(\mbox{at least
$t_{*}$ consecutive ones in $(I_{j})_{j=1}^{\lfloor
n/\ell_{*}\rfloor}$}\right)\geq 1-\exp(-n^{1/4}).$

The latter bound, which is uniform in $T_{0},x_{0}$, together with Observation
3.1, will prove that $M+1/2$ is admissible.

######  Remark 3.3.

The important thing here is that, because $t_{*}=\log^{M+1/2}n$, the
probability of $t_{*}+1$ consecutive ones, i.e. $\mu^{t_{*}+1}$, goes to $0$
slowly. Remark 3.2 shows we are considering “polynomially many indicators”, so
such not-too-small probabilities make a long run of ones very likely.

Let us show that for our choices of $t_{*}$ and $\ell_{*}$ we can find an
$n_{4}$ sufficiently large such that Equation (3.19) holds. We point out that
we will implicitly assume $n_{4}>n_{3}$ so to guarantee that
$\inf_{T,x}{\mathbb{P}}_{T,x,p}\left(I_{1}=1\right)\geq\mu$. It is for this
reason that $n_{4}$ will depend on $p$ (in particular, $n_{4}$ will be non-
increasing in $p$).

$(1-\mu^{t_{*}+1})^{\left\lfloor\frac{\lfloor
n/\ell_{*}\rfloor}{t_{*}+1}\right\rfloor}\leq\exp\left(-\mu^{t_{*}+1}\frac{n^{1/2}}{2(\log^{M+1/2}n+1)}\right)$

Since $t_{*}=\lceil\log^{M+1/2}n\rceil$, for sufficiently large $n$ we have

$\mu^{t_{*}+1}\geq\exp\left(-\left(2(\log\log n)^{2}2^{M+1}+o((\log\log
n)^{2})\right)\sqrt{\log n}\right)\mu=n^{-o(1)}\mu\,$

where we are using that $\left(1-\frac{b_{n}}{a_{n}}\right)^{a_{n}}\approx
e^{-b_{n}-o(b_{n})}$ for sufficiently large $n$ whenever
$a_{n},b_{n}\to+\infty$ and $b_{n}=o(a_{n})$. Thus,

$(1-\mu^{t_{*}+1})^{\left\lfloor\frac{\lfloor
n/\ell_{*}\rfloor}{t_{*}+1}\right\rfloor}\leq\exp\left(-n^{1/4}\,\frac{n^{1/4-o(1)}\mu}{2(\log^{M+1/2}n+1)}\right)\leq\exp\left(-n^{1/4}\right)$

for large enough $n$.

##  4\. The loop process, or why it’s hard to go back

Now we stop the discussion about the BGRW process, to introduce a simpler
process which will help us to understand how long the walker $X$ stays on
specific subgraphs of the random trees $\\{T_{n}\\}_{n\in\mathbb{N}}$. Roughly
speaking, a loop process on an initial graph $G$ is a random walker such that
at each step adds a loop to its position according to a coin and then chooses
uniformly one edge of its current position to walk on. In other words, the
process is quite similar to the BGRW but here the walker adds loops instead of
leaves, which makes it possible for it to stand still.

We will be particularly interested in the loop process over specific graphs
which we define before the definition of the process itself. We call a finite
graph $\mathcal{B}$ a backbone of length $\ell$ if $\mathcal{B}$ is a path of
length $\ell$ having a loop attached to its $\ell+1$-th vertex and possibly to
its other vertices, see Figure 2.

Figure 2. A backbone of length $\ell$

In this section, we will abuse the graph terminology saying degree of a vertex
even though we do not count loops twice. We then reserve the special notation
$\text{deg}_{t}(i)$ to denote the number of edges attached to vertex $i$ at
time $t$.

The model has one parameter $p\in[0,1]$ which is the parameter of a sequence
$\\{Z_{t}\\}_{t\in\mathbb{N}}$ of i.i.d random variables with law
$\text{Ber}(p)$. The loop process on a backbone of length $\ell$ is a Markov
chain $\\{(\mathcal{B}_{t},X^{\text{loop}}_{t})\\}_{t\in\mathbb{N}}$ where
$\mathcal{B}_{t}$ denotes the resultant backbone at time $t$ and
$X^{\text{loop}}_{t}$ is one of its $\ell+1$ vertices. The loop process is
also defined inductively according to the update rules below

  1. (1)

Obtain $\mathcal{B}_{t+1}$ from $\mathcal{B}_{t}$ by adding a new loop to
$X^{\text{loop}}_{t}$ whether $Z_{t+1}=1$;

  2. (2)

Choose uniformly one edge attached to $X^{\text{loop}}_{t}$ in
$\mathcal{B}_{t+1}$. Whether the chosen edge is a loop set
$X^{\text{loop}}_{t+1}$ as $X^{\text{loop}}_{t}$. Otherwise,
$X^{\text{loop}}_{t+1}$ becomes the $X^{\text{loop}}_{t}$ neighbor.

We stress out to the index $t+1$ of $\mathcal{B}$ on (2). It means that we may
add a new loop at (1) and then choose it at (2).

For a fixed backbone $\mathcal{B}$ of length $\ell$ and
$i\in\\{0,1,\cdots,\ell\\}$ we let ${\mathbb{P}}_{i}(\cdot)$ denote the law of
$\\{(\mathcal{B}_{t},X^{\text{loop}}_{t})\\}_{t\in\mathbb{N}}$ when
$(\mathcal{B}_{0},X^{\text{loop}}_{0})\equiv(\mathcal{B},i)$.

Once we have defined the loop process, we are interested on the time it takes
to go from one end of the backbone to another. More precisely, we would like
to obtain bounds on the stopping time bellow

(4.1) $\eta^{\text{loop}}_{0}:=\inf\left\\{t\geq
1\middle|X^{\text{loop}}_{t}=0\right\\}$

when the process starts from $\ell$. The next Lemma gives us some estimates.

######  Lemma 4.1.

There exist positive constants $c_{1}$ and $c_{2}$ depending on $p$ only, such
that, for all integer $K$

${\mathbb{P}}_{\ell}\left(\eta^{\text{loop}}_{0}\leq e^{K}\right)\leq
1-\left(1-\frac{1}{2\ell}\right)^{c_{2}K}+e^{-c_{1}K}$

###### Proof.

We need some notation and definitions. Consider the following sequence of
stopping times

(4.2) $\begin{split}&\tau_{0}\equiv 0,\\\
&\tau_{k}:=\inf\left\\{t>\tau_{k-1}|X^{\text{loop}}_{t}\neq
X^{\text{loop}}_{\tau_{k-1}}\right\\}.\end{split}$

Observe that the probability of $X^{\text{loop}}_{t}$ leaving its current
position is at least $1/t$ since the degree of a vertex at time $t$ is at most
$t$. This implies that $\tau_{k}$ is finite a.s. for all $k$. This allow us to
define the process

(4.3) $Y_{k}:=X^{\text{loop}}_{\tau_{k}}.$

Note that by strong Markov Property, $\\{Y_{k}\\}_{k}$ is a simple RW on
$\\{0,1,\cdots,\ell\\}$ with reflecting barriers. Regarding the process
$\\{Y_{k}\\}_{k}$ we let $\sigma$ be the following stopping time

(4.4) $\sigma:=\inf\left\\{k>0|Y_{k}=0\right\\}.$

Observe that $\eta^{\text{loop}}_{0}=\tau_{\sigma}$.

We prove the Lemma by showing that $X^{\text{loop}}$ spends at least
$\exp\\{K\\}$ steps on the vertex $\ell$. More precisely, we prove that the
degree of $\ell$ at time $\tau_{\sigma}$ is at least $\exp\\{K\\}$, w.h.p. To
do this, first observe that the degree of a vertex may be written in terms of
$Y_{k}$ and $\Delta\tau_{k}$ as follows

(4.5)
$\mathrm{deg}_{\tau_{n}}(\ell)=2+\sum_{k=0}^{n}\mathbb{1}\\{Y_{k}=\ell\\}\left(\sum_{m=\tau_{k}}^{\tau_{k+1}-1}Z_{m}\right)=2+\sum_{k=0}^{n}\mathbb{1}\\{Y_{k}=\ell\\}\mathrm{Bin}\left(\Delta\tau_{k},p\right).$

Also notice that if $Y_{k}=\ell$, then the number of steps $X^{\text{loop}}$
spends on $\ell$ is exactly $\Delta\tau_{k}$, which satisfies

$\Delta\tau_{k}\geq\mathrm{Geo}\left(1/\mathrm{deg}_{\tau_{k}}(\ell)\right).$

To see the bound above, consider the random variable which counts the number
of steps $X^{\text{loop}}$ spends on $\ell$ by choosing only the loops which
were already attached on $\ell$ when $X^{\text{loop}}$ arrived at $\ell$. This
random variable is clearly smaller than $\Delta\tau_{k}$ and follows a
geometric distribution of parameter $1/\mathrm{deg}_{\tau_{k}}(\ell)$. Thus,
we have

(4.6)
$\mathrm{deg}_{\tau_{n}}(\ell)\geq\sum_{k=0}^{n}\mathbb{1}\\{Y_{k}=\ell\\}\mathrm{Bin}\left(\mathrm{Geo}\left(1/\mathrm{deg}_{\tau_{k}}(\ell)\right),p\right).$

Regarding the random variables
$\mathrm{Bin}\left(\mathrm{Geo}\left(1/\mathrm{deg}_{\tau_{k}}(\ell)\right),p\right)$,
we claim that

######  Claim 4.1.

For all $\varepsilon\in(0,1)$, there exists a positive constant
$q=q(\varepsilon,p)$ such that

(4.7)
${\mathbb{P}}_{\ell}\left(Y_{k}=\ell,\mathrm{Bin}\left(\mathrm{Geo}\left(1/\mathrm{deg}_{\tau_{k}}(\ell)\right),p\right)\geq\varepsilon
p\mathrm{deg}_{\tau_{k}}(\ell)\middle|\mathcal{F}_{\tau_{k}}\right)\geq
q\mathbb{1}\\{Y_{k}=\ell\\}.$

Proof of the claim: To simplify our writing, write

$G_{k}:=\mathrm{Geo}\left(1/\mathrm{deg}_{\tau_{k}}(\ell)\right);\;d_{k}:=\mathrm{deg}_{\tau_{k}}(\ell)$

and let $\tilde{\mathcal{F}}_{\tau_{k}}$ be the $\sigma$-algebra generated by
$G_{k}$ and $\mathcal{F}_{\tau_{k}}$. Now, by Chernoff bounds, we have that

(4.8)
$\begin{split}{\mathbb{P}}_{\ell}\left(Y_{k}=\ell,\mathrm{Bin}\left(G_{k},p\right)\geq\varepsilon
pd_{k},G_{k}\geq
d_{k}\middle|\tilde{\mathcal{F}}_{\tau_{k}}\right)&\geq\left(1-e^{-(1-\varepsilon)^{2}pG_{k}}\right)\mathbb{1}\\{Y_{k}=\ell,G_{k}\geq
d_{k}\\}\\\
&\geq\left(1-e^{-(1-\varepsilon)^{2}pd_{k}}\right)\mathbb{1}\\{Y_{k}=\ell,G_{k}\geq
d_{k}\\}.\end{split}$

Recall that $d_{k}$ is greater than $2$ for all $k$. So, taking the
conditional expectation wrt $\mathcal{F}_{\tau_{k}}$ on the above inequality
yields

(4.9)
$\begin{split}{\mathbb{P}}_{\ell}\left(Y_{k}=\ell,\mathrm{Bin}\left(G_{k},p\right)\geq\varepsilon
pd_{k},G_{k}\geq
d_{k}\middle|\mathcal{F}_{\tau_{k}}\right)&\geq\left(1-e^{-2(1-\varepsilon)^{2}p}\right){\mathbb{P}}_{\ell}\left(Y_{k}=\ell,G_{k}\geq
d_{\tau_{k}}\middle|\mathcal{F}_{\tau_{k}}\right)\\\
&\geq\left(1-e^{-2(1-\varepsilon)^{2}p}\right)\left(1-e^{-1}\right)\mathbb{1}\\{Y_{k}=\ell\\},\end{split}$

which proves the claim. $\blacksquare$

The above claim tells us that conditionally on the past, every time
$\\{Y_{k}\\}_{k}$ visits $\ell$ it has probability at least $q$ of increasing
the degree of $\ell$ by a factor of at least $1+\varepsilon p$. This points
out that the degree of $\ell$ must be at least exponential of the number of
visits $\ell$ receives from $\\{Y_{k}\\}_{k}$. So, let $N_{\sigma}(\ell)$ the
number of visits made by $Y$ to $\ell$ before it reaches vertex $0$. Since $Y$
is a simple random walk on $\\{0,1,\cdots,\ell\\}$, $N_{\sigma}(\ell)$ follows
a geometric distribution of parameter $1/2{\ell}$. Moreover, the random
variable $W$ that counts how many times we have successfully multiplied the
degree of $\ell$ by $1+\varepsilon p$ may be written as follows

(4.10)
$W:=\sum_{k=0}^{\sigma}\mathbb{1}\\{Y_{k}=\ell\\}\mathbb{1}\\{\mathrm{Bin}\left(\mathrm{Geo}\left(1/\mathrm{deg}_{\tau_{k}}(\ell)\right),p\right)\geq\varepsilon
p\mathrm{deg}_{\tau_{k}}(\ell)\\}$

and dominates a random variable distributed as $\text{Bin}(N_{\sigma}(l),q)$.
Consequently, by Chernoff bounds

(4.11) $\begin{split}{\mathbb{P}}_{\ell}\left(W\leq\frac{K}{\log(1+\varepsilon
p)}\right)&\leq{\mathbb{P}}_{\ell}\left(\mathrm{Bin}(N_{\sigma}(\ell),q)\leq\frac{K}{\log(1+\varepsilon
p)}\right)\\\
&\leq{\mathbb{P}}_{\ell}\left(\mathrm{Bin}(N_{\sigma}(\ell),q)\leq\frac{K}{\log(1+\varepsilon
p)}\middle|N_{\sigma}(\ell)\geq\frac{2K}{q\log(1+\varepsilon p)}\right)\\\
&+{\mathbb{P}}_{\ell}\left(N_{\sigma}(\ell)<2q^{-1}K/\log(1+\varepsilon
p)\right)\\\
&\leq\exp\\{-c_{1}K\\}+1-\left(1-\frac{1}{2\ell}\right)^{c_{2}K}.\end{split}$

Finally, observe that if $W\geq K/\log(1+\varepsilon p)$, then
$\mathrm{deg}_{\tau_{\sigma}}(\ell)\geq 2e^{K}$ which implies that
$\tau_{\sigma}$ is at least this amount, finishing the proof.

The following special case of the above Lemma will be particularly useful to
our proposes.

######  Corollary 4.1.

There exists a positive constant $C$ depending on $p$ only, such that

${\mathbb{P}}_{\ell}\left(\eta^{\text{loop}}_{0}\leq
e^{\sqrt{\ell}}\right)\leq\frac{C}{\sqrt{\ell}}.$

###### Proof.

Letting $K=\sqrt{\ell}$ on (4.11) of Lemma 4.1 we obtain

(4.12)
$\begin{split}{\mathbb{P}}_{\ell}\left(W\leq\frac{\sqrt{\ell}}{\log(1+\varepsilon
p)}\right)&\leq{\mathbb{P}}_{\ell}\left(\text{
Bin}(N_{\sigma}(\ell),q)\leq\frac{\sqrt{\ell}}{\log(1+\varepsilon
p)}\right)\\\
&\leq{\mathbb{P}}_{\ell}\left(\mathrm{Bin}(N_{\sigma}(\ell),q)\leq\frac{\sqrt{\ell}}{\log(1+\varepsilon
p)}\middle|N_{\sigma}(\ell)\geq\frac{2\sqrt{\ell}}{q\log(1+\varepsilon
p)}\right)\\\ &+{\mathbb{P}}_{\ell}\left(N_{\sigma}(\ell)\leq
2q^{-1}\sqrt{\ell}/\log(1+\varepsilon p)\right)\\\
&\leq\exp\\{-c_{1}\sqrt{\ell}\\}+1-\left(1-\frac{1}{2\ell}\right)^{c_{2}\sqrt{\ell}}.\end{split}$

Since $\left(1-\frac{1}{2\ell}\right)^{c_{2}\sqrt{\ell}}\approx
e^{-c_{3}/\sqrt{\ell}}$ and $1-e^{-x}\leq x$, choosing properly the constants
we obtain the desired result.

###  4.1. Coupling the BGRW and the loop process

In this subsection we construct a coupling of the BGRW and loop processes in
such way that the loop process is always closer to the root than the walker
$X$. For this, let $T$ be a rooted locally finite tree of height at least
$2(\ell+1)$, $x$ a vertex such that $\mathrm{dist}_{T}(x,\text{root})\geq\ell$
and $d_{T}(x)\geq 2$ and $y$ its ancestor at distance $\ell$. Since $T$ is a
tree, there exists only one path $\mathcal{P}$ connecting $x$ to the $y$. With
this in mind, we define a graph operation $\mathcal{B}$ which associates to
each pair $(T,x)$ and ancestor $y$ satisfying the aforementioned conditions a
backbone $\mathcal{B}(T,y,x)$ of length $\ell$ as follows:

  1. (1)

delete all vertices of $T$ whose distance from $\mathcal{P}$ is at least $2$;

  2. (2)

replace each edge $xy\in E(T)$ with $x\in\mathcal{P}$ and
$y\not\in\mathcal{P}$ with a loop edge at $x$ (so each edge stemming out of
the path becomes a loop).

  3. (3)

label the vertices on $\mathcal{P}$ by their distance from $y$ (so $y$ gets
label $0$, its neighbor on $\mathcal{P}$ gets label $1$ and so on).

The figure below gives a concrete example of $\mathcal{B}$ in action when $y$
is taken as the root:

Figure 3. Example of a pair $(T,x)$ transformed into a backbone

So far, we have shown that the BGRW is capable of reaching long distances –
powers of $\log n$ – away from the root. Now, we would like to argue that once
it has gone so far, it takes too long to return. More generally, if the BGRW
starts on $T_{0},x_{0}$ and $y$ is one of its ancestors, we would like to
obtain lower bounds on the following stopping time

(4.13) $\eta_{y}:=\inf\left\\{n\geq 1\middle|X_{n}=y\right\\}.$

The way we bound $\eta_{y}$ from below is comparing it with
$\eta^{\text{loop}}_{0}$, which we recall its definition

$\eta^{\text{loop}}_{0}:=\inf\left\\{t\geq
1\middle|X^{\text{loop}}_{t}=0\right\\}.$

The next proposition tells us that we may couple the BGRW and the loop process
in such way that $\eta_{y}$ is greater than $\eta^{\text{loop}}_{0}$ almost
surely.

######  Proposition 4.14 (Coupling).

Let $T_{0}$ be a rooted locally finite tree, $x_{0}$ one of its vertices
different from the root and $y$ an ancestor of $x_{0}$. Then, there exists a
coupling of $\\{(T_{n},X_{n})\\}_{n\in\mathbb{N}}$ starting from
$(T_{0},x_{0})$ and a loop process
$\\{(\mathcal{B}_{n},X^{\text{loop}}_{n})\\}_{n\in\mathbb{N}}$ starting from
$(\mathcal{B}(T_{0},y,x_{0}),x_{0})$ such that

${\mathbb{P}}\left(\eta_{y}\geq\eta^{\text{loop}}_{0}\right)=1.$

###### Proof.

Let $\mathcal{P}$ denote the path connecting $x_{0}$ to its ancestor $y$ on
$T_{0}$ and $\ell$ its length. Also consider the following sequence of
stopping times,

(4.15) $\zeta_{0}\equiv
0;\quad\zeta_{k}:=\inf\left\\{m>\zeta_{k-1}\middle|X_{m}\in\mathcal{P}\right\\},$

and let $\\{W_{k}\\}_{k\in\mathbb{N}}$ be a sequence of i.i.d. r.v’s
independent of the process BGRW, such that $W_{k}\sim\text{Ber}(p)$. We couple
a loop process $\\{(\mathcal{B}_{k},X^{\text{loop}}_{k})\\}_{k\in\mathbb{N}}$
to the BGRW inductively as follows. Start by defining

$(\mathcal{B}_{0},X^{\text{loop}}_{0}):=(\mathcal{B}(T_{0},y,x_{0}),x_{0})$

and assume we have defined
$\\{(\mathcal{B}_{i},X^{\text{loop}}_{i})\\}_{i=0}^{k-1}$ in such way that
this random vector is distributed as $k-1$ steps of a loop process starting
from $(\mathcal{B}_{0},\ell)$. Now, we define
$(\mathcal{B}_{k},X^{\text{loop}}_{k})$

  * •

If $\zeta_{k-1}<\infty$, we set
$\mathcal{B}_{k}=\mathcal{B}(T_{\zeta_{k-1}+1},y,x_{0})$;

  * •

If $\zeta_{k-1}=\infty$, we make use of our independent sequence
$\\{W_{k}\\}_{k\in\mathbb{N}}$. We modify $\mathcal{B}_{k-1}$ adding a loop to
$X^{\text{loop}}_{k-1}$ whether $W_{k}=1$;

Observe that if $\zeta_{k-1}$ is finite, then
$X_{k-1}^{\text{loop}}=X_{\zeta_{k-1}}$. In fact, when
$X_{k-1}^{\text{loop}}=X_{\zeta_{k-2}}$ we know that $X_{\zeta_{k-2}}$ has
jumped outside $\mathcal{P}$. Thus, the only way of $X$ coming back to
$\mathcal{P}$ is through $X_{\zeta_{k-2}}$, which implies
$X_{\zeta_{k-1}}=X_{\zeta_{k-2}}$. On the other hand, when
$X_{k-1}^{\text{loop}}=X_{\zeta_{k-2}+1}$ we know that $X_{\zeta_{k-2}}$ has
moved on $\mathcal{P}$ implying that $\zeta_{k-1}=\zeta_{k-2}+1$.
Consequently, regardless the finiteness of $\zeta_{k-1}$ – since $W_{k}$ is
independent of the BGRW, $\mathcal{B}_{k}$ is obtained by adding a loop on
$X^{\text{loop}}_{k-1}$ independently of the whole past and with probability
$p$.

To define $X_{k}^{\text{loop}}$ we proceed in the following way

  * •

If $\zeta_{k-1}<\infty$,

    * –

we set $X_{k}^{\text{loop}}=X_{\zeta_{k-1}+1}$, if $X_{\zeta_{k-1}}$ moves on
$\mathcal{P}$;

    * –

otherwise, when $X_{\zeta_{k-1}}$ jumps outside $\mathcal{P}$, we let
$X_{k}^{\text{loop}}$ be $X_{\zeta_{k-1}}$.

  * •

In case $\zeta_{k-1}=\infty$, we select uniformly an edge of
$X_{k-1}^{\text{loop}}$ on $\mathcal{B}_{k}$ to walk $X_{k-1}^{\text{loop}}$
through.

By definition of the above coupling, we obtain that
$\eta_{y}\geq\eta_{0}^{\text{loop}}$. The best scenario would be that in which
the BGRW only walks over $\mathcal{P}$, in this case the stopping times are
equals. This concludes the proof.

As a straightforward consequence of the above coupling, we restate Corollary
4.1 in terms of the hitting time $\eta_{y}$.

######  Corollary 4.2.

Let $T_{0}$ be a rooted locally finite tree, $x_{0}$ one of its vertices
different from the root and $y$ an ancestor of $x_{0}$ at distance $\ell$.
Then there exists a constant $C$ depending on $p$ only, such that

${\mathbb{P}}_{T_{0},x_{0},p}\left(\eta_{y}\leq
e^{\sqrt{\ell}}\right)\leq\frac{C}{\sqrt{\ell}}.$

##  5\. Positive drift and its consequences

In this section we show that the BGRW has a positive drift away from the root.
In particular, we show that

$\liminf_{n\rightarrow\infty}\frac{\mathrm{dist}_{T_{n}}(X_{n},\text{root})}{n}>0,$

almost surely, which implies the transience of the walker $X$. We do that by
tracking the distance of $X$ from the root at random times and comparing it to
a right biased simple random walk on $\mathbb{Z}$. Furthermore, this
comparison with the right biased simple random walk allows us to improve the
results given in Proposition 3.2 and Corollary 4.2. Specifically, we can now
prove

  * •

the walker achieves distances of order $n$ in $n$ steps w.h.p;

  * •

the probability of the walker going back long distances is exponentially rare.

Intuitively, the main message of this section is that if we look at the
distance of $X$ from the root properly normalized and at some “random times”
we see a random walk on the line that dominates a right biased simple random
walk. Let us begin by formally define what we mean by “random times”. For a
fixed positive integer $r$, we define three stopping conditions from a vertex
$x_{0}$.

  1. (1)

$\mathrm{dist}_{T_{n}}(X_{n},\text{root})-\mathrm{dist}_{T_{0}}(x_{0},\text{root})=r$;

  2. (2)

$\mathrm{dist}_{T_{n}}(X_{n},\text{root})-\mathrm{dist}_{T_{0}}(x_{0},\text{root})=-r$;

  3. (3)

$X$ walks $\exp\\{{\sqrt{r}}\\}$ steps and none of the previous conditions
occurs.

We say $(1)-(3)$ occurred from $X_{m}$ whenever one of the three stopping
conditions occurred when we put $x_{0}$ as $X_{m}$. We must point out that if
$\mathrm{dist}_{T_{m}}(X_{m},\text{root})<r$, then stopping condition $(2)$
cannot be attained.

We define our sequence of stopping times as follows:

(5.1) $\begin{split}\sigma_{0}\equiv&0;\\\
\sigma_{k}:=&\inf\left\\{m>\sigma^{(r)}_{k-1}\mid(1)-(3)\text{ occurs from
}X_{\sigma_{k-1}}\right\\}.\end{split}$

From the definition of $(1)-(3)$ follows that, for all $k$, $\sigma^{(r)}_{k}$
is bounded from above by $\exp\\{{\sqrt{r}}\\}k$. To avoid clutter, when $r$
is fixed we suppress the upper script from the nation of $\sigma^{(r)}_{k}$.

######  Lemma 5.1 (Coupling to the biased random walk).

Let $T_{0}$ be a rooted locally finite tree, $x_{0}$ one of its vertices and
$\left\\{S_{k}\right\\}_{k\geq 0}$ a right biased simple random walk on
$\mathbb{Z}$. Then, there exists a large enough $r=r(p)$ depending on $p$
only, such that the process
$\\{\mathrm{dist}_{T_{\sigma_{k}}}(X_{\sigma_{k}},\text{root})/r\\}_{k\geq 0}$
starting from $(T_{0},x_{0})$ and $\left\\{S_{k}\right\\}_{k\geq 0}$ starting
from $\lfloor\mathrm{dist}_{T_{0}}(x_{0},\text{root})/r\rfloor$ can be coupled
in such way that

${\mathbb{P}}\left(\mathrm{dist}_{T_{\sigma_{k}}}(X_{\sigma_{k}},\text{root})\geq
rS_{k},\forall k\right)=1.$

###### Proof.

We begin by a few notations. To simplify our writing, put
$d_{k}:=\mathrm{dist}_{T_{\sigma_{k}}}(X_{\sigma_{k}},\text{root})$. Note that
the process $\left\\{d_{k}\right\\}_{k\geq 0}$ is a random walk on the half
line whose increments belong to the interval $[-r,r]$. Let
$\left\\{U_{k}\right\\}_{k\geq 0}$ be a sequence of i.i.d random variables
independent of the BGRW and following uniform distribution on $[0,1]$. Also
let $\tilde{\mathcal{F}}_{k}$ be the $\sigma$-algebra generated by the BGRW
process up to time $\sigma_{k}$ and let $\mathcal{H}_{k}$ be the
$\sigma$-algebra encoding all information of $\tilde{\mathcal{F}}_{k}$ and all
the uniform random variables up to time $k$.

Regarding the increments of $\left\\{d_{k}\right\\}_{k\geq 0}$, we claim

######  Claim 5.1.

There exist positive constants $r$ and $C$ depending on $p$ only, such that
for all $k$

(5.2) $\inf_{T_{0},x_{0}}{\mathbb{P}}_{T_{0},x_{0},p}\left(\Delta
d_{k+1}=r\middle|\tilde{\mathcal{F}}_{k}\right)>1-\frac{C}{\sqrt{r}}.$

Proof of the claim: First of all, observe that $\Delta d_{k+1}=r$ if, and only
if, $\sigma_{k+1}$ stops because of condition $(1)$. Also, by the strong
Markov Property, it is enough to prove the claim for $\sigma_{1}$. Said that,
let us first assume we start from an initial condition $(T_{0},x_{0})$ with
$\mathrm{dist}_{T_{0}}(x_{0},\text{root})\geq r$. We derive the desired lower
bound by proving upper bounds for the probability of the events $\\{\Delta
d_{1}=-r\\}$ and $\\{|\Delta d_{1}|<r\\}$. The former occurs if, and only if,
$\sigma_{1}$ stops because condition $(2)$ and the latter because of condition
$(3)$.

Observe that if $\sigma_{1}$ stops because of $(2)$ then the walker $X$
visited the ancestor $y$ of $x_{0}$ at distance $r$, since
$\mathrm{dist}_{T_{0}}(x_{0},\text{root})\geq r$, spending at most
$\exp\\{\sqrt{r}\\}$ steps. So, using Corollary 4.2 we have

(5.3) ${\mathbb{P}}_{T_{0},x_{0},p}\left(\sigma_{1}\textit{ stops because of
}(2)\right)\leq{\mathbb{P}}_{T_{0},x_{0},p}\left(\eta_{y}\leq
e^{\sqrt{r}}\right)\leq\frac{C^{\prime}}{\sqrt{r}}.$

Note that the above upper bound holds for all possible pairs of a rooted
locally finite tree $T_{0}$ and one of its vertex $x_{0}$ at distance greater
than $r$ from the root.

Finally, if $X$ stops because of the occurrence of $(3)$ then $X$ has walked
for $e^{\sqrt{r}}$ steps and has not visited the ancestor $y$ of $x_{0}$ at
distance $r$ neither has increased its distance from $y$ by $r$. This is the
same that we observe a process $\tilde{X}$ on the subtree $T_{y}$ that in
$e^{\sqrt{r}}$ steps does not be at distance $2r$ from the root $y$. Applying
Proposition 3.2 (page 3.2) with $n=e^{\sqrt{r}}$ and $M=4$ we obtain that
there exist $r_{0}=r(p)$ such that for all $r\geq r_{0}$ we have

(5.4) $\inf_{T_{0},x_{0}}{\mathbb{P}}_{T_{0},x_{0},p}\left(\exists m\leq
e^{\sqrt{r}},\mathrm{dist}_{T_{m}}(\tilde{X}_{m},\tilde{\textit{root}})>r^{2}\right)\geq
1-\exp\\{-e^{\sqrt{r}/4}\\}.$

Choosing $r$ large enough so that $r\geq r_{0}$,
$\exp\\{-e^{\sqrt{r}/4}\\}\leq C^{\prime}/\sqrt{r}$ and $r^{2}>2r$ we conclude
that

(5.5) $\sup_{T_{0},x_{0}}{\mathbb{P}}_{T_{0},x_{0},p}\left(\sigma_{1}\textit{
stops because of }(3)\right)\leq\exp\\{-e^{\sqrt{r}/4}\\}.$

To drop our assumption that we start at distance greater than $r$ from the
root, just recall that when this is not the case the condition $(2)$ has
probability zero and the above upper bound for condition $(3)$ still holds.
This implies that

(5.6) $\inf_{T_{0},x_{0}}{\mathbb{P}}_{T_{0},x_{0},p}\left(\sigma_{1}\textit{
stops because of }(1)\right)\geq 1-\frac{C}{\sqrt{r}}$

which combined with strong Markov Property proves the claim. $\blacksquare$

Since we may increase $r$, we choose it large enough so

(5.7) $q:=1-\frac{C}{\sqrt{r}}>\frac{1}{2}.$

Now we couple the process $\\{d_{k}/r\\}_{k\geq 1}$ and $\\{S_{k}\\}_{k\geq
1}$ in the following way. Set

(5.8)
$S_{0}:=\left\lfloor\frac{\mathrm{dist}_{T_{0}}(x_{0},\text{root})}{r}\right\rfloor$

and assume we have defined $\\{S_{j}\\}_{j=0}^{k-1}$ in such way that it has
the distribution of $k-1$ steps of the desired right biased random walk. Let
$Q_{k-1}$ denote

(5.9) $Q_{k-1}:={\mathbb{P}}_{T_{0},x_{0},p}(\Delta
d_{k}=r|\tilde{\mathcal{F}}_{k-1})$

and recall from Claim 5.1 that $Q_{k}\geq q$ for all $k$. We then define
$S_{k}$ in the following way

(5.10) $S_{k}=\left\\{\begin{array}[]{ll}S_{k-1}+1&\mbox{if }\Delta
d_{k}=r\text{ and }U_{k}\leq q/Q_{k-1},\\\ S_{k-1}-1&\mbox{otherwise.
}\end{array}\right.$

In words, if at time $\sigma_{k}$ the walker $X$ increased its distance from
the root by $r$, then $S_{k}$ jumps to the right with probability $q/Q_{k-1}$.
In this way, whenever the process $\\{d_{k}/r\\}_{k\geq 0}$ jumps back (at
most one unit), the SRW also jumps back one unit.

Now, we show that the process $\\{S_{k}\\}_{k\geq 0}$ does have the
distribution we desire. We start by checking that the increments are $1$ with
probability $q$ or $-1$ with probability $1-q$. By the definition of $S$ we
have

(5.11) $\begin{split}{\mathbb{P}}_{T_{0},x_{0},p}\left(\Delta
S_{k}=1\middle|\mathcal{H}_{k-1}\right)&={\mathbb{P}}_{T_{0},x_{0},p}\left(\Delta
d_{k+1}=r,U_{k}\leq q/Q_{k-1}\middle|\mathcal{H}_{k-1}\right)\\\
&={\mathbb{P}}_{T_{0},x_{0},p}(\Delta
d_{k}=r|\mathcal{H}_{k-1})\frac{q}{Q_{k-1}}\\\ &=q,\end{split}$

since $U_{k}$ is independent of $\mathcal{H}_{k-1}$ and $Q_{k-1}$ is
measurable with respect to $\mathcal{H}_{k-1}$. Moreover, the equality below
holds

$Q_{k-1}={\mathbb{P}}_{T_{0},x_{0},p}(\Delta
d_{k}=r|\tilde{\mathcal{F}}_{k-1})={\mathbb{P}}_{T_{0},x_{0},p}(\Delta
d_{k}=r|\mathcal{H}_{k-1})$

since $\mathcal{H}_{k-1}$ is $\tilde{\mathcal{F}}_{k-1}$ added of information
independent of the whole process $\\{(T_{k},X_{k})\\}_{k\geq 1}$. Equation
(5.11) allows us to derive the independence of all the increments of our right
biased random walk $\\{S_{k}\\}_{k\geq 1}$. For any fixed set of indexes
$k_{1}<k_{2}<\cdots<k_{j}$ and any vector
$(a_{1},\cdots,a_{j})\in\\{-1,1\\}^{j}$ we have

$\begin{split}{\mathbb{P}}\left(\Delta S_{k_{1}}=a_{1},\cdots,\Delta
S_{k_{j}}=a_{j}\right)&={\mathbb{E}}\left[\mathbb{1}_{\\{\Delta
S_{k_{1}}=a_{1}\\}}\cdots\mathbb{1}_{\\{\Delta
S_{k_{j-1}}=a_{j-1}\\}}{\mathbb{E}}\left[\mathbb{1}_{\\{\Delta
S_{k_{j}}=a_{j}\\}}\middle|\mathcal{H}_{k_{j}-1}\right]\right]\\\
&={\mathbb{P}}\left(\Delta S_{k_{1}}=a_{1},\cdots,\Delta
S_{k_{j-1}}=a_{j-1}\right){\mathbb{P}}\left(\Delta
S_{k_{j}}=a_{j}\right)\end{split}$

which implies the independence of the increments $\Delta S_{k}$. So,
$\\{S_{k}\\}_{k\geq 0}$ is distributed as simple random walk on $\mathbb{Z}$
with probability $q>1/2$ of jumping to the right starting at the left of
$d_{0}/r$. And, by construction, we have that $d_{k}/r\geq S_{k}$ for all $k$.
This concludes the proof of the lemma.

As a consequence of the coupling above, we prove the transience of the walker.

######  Proposition 5.12 (Transience of the walker).

There exists a constant $c>0$ depending on $p$ only, such that

$\liminf_{n\rightarrow\infty}\frac{\mathrm{dist}_{T_{n}}(X_{n},\mathrm{root})}{n}\geq
c,\;{\mathbb{P}}_{T_{0},x_{0},p}\textit{- almost surely},$

for all initial conditions $(T_{0},x_{0})$.

###### Proof.

Lemma 5.1 guarantees the existence of a positive constant $r$, depending on
$p$ only, so that, for any initial condition on the BGRW,

(5.13) $\mathrm{dist}_{T_{\sigma_{k}}}(X_{\sigma_{k}},\text{root})\geq
rS_{k},\textit{a.s.,}$

where $\\{S_{k}\\}_{k\geq 0}$ is a right biased simple random walk on
$\mathbb{Z}$. By the Strong Law of Large Numbers we also have that

(5.14) $\lim_{k\rightarrow\infty}\frac{S_{k}}{k}=\mu(r)=\mu\textit{, a.s..}$

This implies that

(5.15)
$\liminf_{k\rightarrow\infty}\frac{\mathrm{dist}_{T_{\sigma_{k}}}(X_{\sigma_{k}},\text{root})}{k}\geq
r\mu\textit{, a.s..}$

On the other hand, by the definition of the stopping times $\sigma_{k}$ we
have that, for all $k$, the following inequality holds

$|\sigma_{k+1}-\sigma_{k}|\leq\exp\\{\sqrt{r}\\},$

almost surely, as well as

$\left|\mathrm{dist}_{T_{\sigma_{k}}}\left(X_{\sigma_{k}},\text{root}\right)-\mathrm{dist}_{T_{\sigma_{k-1}}}\left(X_{\sigma_{k-1}},\text{root}\right)\right|\leq
r,$

almost surely. Thus, if $n$ is an integer such that
$n\in[\sigma_{k},\sigma_{k+1}]$ we have

(5.16)
$\frac{\mathrm{dist}_{T_{n}}\left(X_{n},\text{root}\right)}{n}\geq\frac{\mathrm{dist}_{T_{\sigma_{k+1}}}\left(X_{\sigma_{k+1}},\text{root}\right)-r}{e^{\sqrt{r}}(k+1)}$

which combined with (5.15) proves the that

(5.17)
$\liminf_{n\rightarrow\infty}\frac{\mathrm{dist}_{T_{n}}(X_{n},\mathrm{root})}{n}=c>0,\textit{a.s},$

for some positive constant $c$ depending on $p$ only.

###  5.1. Controlling returns and degrees

The coupling gives us a picture of the dynamics of the walker: it is moving
away from the root at linear speed. Before moving on, we use the coupling to
show that vertices are not visited many times and (as a result) degrees in our
tree tend to be small.

######  Lemma 5.2.

Let $(T_{0},x_{0})$ be the initial state of the dynamics and $y\in T_{0}$ be
given. Then for any $0<p\leq 1$, the number $v(y)$ of visits to $y$,

$v(y):=|\\{0\leq t<+\infty\,:\,X_{t}=y\\}|$

satisfies

$\forall k\geq 0\,:\,{\mathbb{P}}_{T_{0},x_{0},p}(v(y)\geq k)\leq
C\,e^{-\beta\,k}$

and

${\mathbb{P}}_{T_{0},x_{0},p}(v(y)>0)\leq C\,e^{-\beta\,{\rm
dist}_{T_{0}}(x_{0},y)}$

for some $\beta,C>0$ depend only on $p$. Moreover, if $p_{0}>0$ and $p_{0}\leq
p\leq 1$, $C$ and $\alpha$ can be chosen uniformly in $p_{0}$.

###### Proof.

Recall from the coupling we just constructed that we may choose $r$ large
enough so that the process
$\\{\mathrm{dist}_{T_{\sigma_{k}}}(X_{\sigma_{k}},y)/r\\}_{k}$ dominates a
right biased random walk $\\{S_{k}\\}_{k}$ on $\mathbb{Z}$ starting on
$s_{0}:=\lfloor\frac{\mathrm{dist}_{T_{0}}(x_{0},y)}{r}\rfloor$. We count the
visits to $y$ per time interval $(\sigma_{k-1},\sigma_{k}]$ (with a possible
additional visit at time $0$).

$v(y):=\mathbb{1}_{\\{X_{0}=y\\}}+\sum_{k=1}^{\infty}\sum_{t=\sigma_{k-1}+1}^{\sigma_{k}}\mathbb{1}_{\\{X_{t}=y\\}}.$

Recalling that $\sigma_{k}-\sigma_{k-1}\leq e^{\sqrt{r}}$, we may rewrite the
expression as:

$v(y)\leq\mathbb{1}_{X_{0}=y}+e^{\sqrt{r}}\sum_{k=1}^{\infty}\mathbb{1}_{\\{X_{t}=y\text{
for some }\sigma_{k-1}<t\leq\sigma_{k}\\}}.$

Now, by the definition of the stopping time sequence $\\{\sigma_{k+1}\\}_{k}$,
for $t\in[\sigma_{k},\sigma_{k+1}]$ then

$|\mathrm{dist}_{T_{\sigma_{k}}}(X_{\sigma_{k}},y)-\mathrm{dist}_{T_{t}}(X_{t},y)|\leq
r.$

As a result, if $X_{t}=y$ for some $\sigma_{k-1}\leq t\leq\sigma_{k}$, then
$S_{k}\leq\mathrm{dist}_{T_{\sigma_{k}}}(X_{\sigma_{k}},y)/r\leq 1$. In
particular,

$v(y)\leq\mathbb{1}_{\\{X_{0}=y\\}}+e^{\sqrt{r}}\sum_{k=1}^{\infty}\mathbb{1}_{\\{S_{k}\leq
1\\}}.$

The RHS is (up to a constant) the number of visits of a right-biased random
walk started from $S_{0}\geq 0$ to the interval $(-\infty,1]$. This number has
an exponential tail that only depends on the bias. The first inequality
follows because we can choose $r=r(p_{0})$ to guarantee a bias of $1/3$ (say)
for all $p_{0}\leq p\leq 1$. The second inequality also follows (perhaps with
changes to $C,\beta$) once we realize that
$S_{0}\geq\mathrm{dist}_{T_{0}}(x_{0},y)/r$.

######  Lemma 5.3.

Given $p_{0}>0$, there exist constants $C,\alpha>0$ depending only on $p_{0}$
such that, for all $p_{0}\leq p\leq 1$, all finite $(T_{0},x_{0})$, and all
$n,k\geq 1$,

$\sum_{t=0}^{n}{\mathbb{P}}_{T_{0},x_{0},p}(d_{T_{t}}(X_{t})\geq k)\leq
C\,(n+|V(T_{0})|)\,e^{\alpha\,(\Delta(T_{0})-k)}.$

###### Proof.

Assume without loss of generality that $V(T)=\\{1,\dots,\ell\\}$. Also let
${\ell+1},{\ell+2},\dots$ be the vertices that the BGRW process started from
$T,x$ creates. Finally, we let $v_{t}(i)$ denote the number of visits to $i$
up to time $t$, so that $v_{t}(i)=0$ if $i>t+\ell$. Note that
$d_{t}(v_{i})\geq k$ implies that $v_{n}(i)\geq k-\Delta(T)$, as the degree
only grows at times when $i$ is visited. Therefore, for all $0\leq t\leq n$,
$\alpha>0$ and $k\geq\ell+1$:

$\begin{split}{\mathbb{P}}_{T,o,p}(d_{T_{t}}(X_{t})\geq
k)=&\sum_{i=1}^{\ell+n}{\mathbb{P}}_{T,o,p}(X_{t}=i,d_{T_{t}}(i)\geq k)\\\
&\leq
e^{\alpha\,(\Delta(T)-k)}\,\sum_{i=1}^{\ell+n}{\mathbb{E}}_{T,o,p}[\mathbb{1}_{\\{X_{t}=i\\}}\,\exp(\alpha\,v_{n}(i))].\end{split}$

As a consequence:

$\displaystyle\sum_{t=0}^{n}{\mathbb{P}}_{T,o,p}(d_{T_{t}}(X_{t})\geq k)$
$\displaystyle\leq$ $\displaystyle
e^{\alpha\,(\Delta(T)-k)}\,\sum_{t=0}^{n}\sum_{i=1}^{\ell+n}{\mathbb{E}}_{T,o,p}[\mathbb{1}_{\\{X_{t}=i\\}}\,\exp(\alpha\,v_{n}(i))]$
(use $\sum_{t\leq n}\mathbb{1}_{\\{X_{t}=i\\}}=V_{n}(i)$) $\displaystyle\leq$
$\displaystyle
e^{\alpha\,(\Delta(T)-k)}\sum_{i=1}^{\ell+n}{\mathbb{E}}_{T,o,p}[v_{n}(i)\,\exp(\alpha\,v_{n}(i))].$

By Lemma 5.2, $v_{n}(i)\leq v(i)$ has an exponential tail uniformly in
$i,n,T_{0},x_{0}$ and $p\in[p_{0},1]$. Thus we may take $\alpha=\beta/2$ (with
$\beta$ from that Lemma) and adjust $C$ to obtain our result.

##  6\. The local point of view on infinite trees

In the last section we obtained that the distance between the random walker
and its starting position grows at least like $n$. Obtaining sharper results
will require a deeper understanding of the process. This section makes some
progress in this direction by introducing the right state space for this
purpose.

###  6.1. Rooted graphs and trees

We recall the definition of rooted graphs, rooted trees and the local topology
on these objects. All notions we need are defined and studied in Bordenave’s
lecture notes [4].

A rooted graph is a pair $(G,o)$ where $G$ is a connected, locally finite
graph and $o$ is vertex of $G$. Note that any rooted graph must have a
countable vertex set which we may assume to be a subset of $\mathbb{N}$ or
$\mathbb{Z}$. Two rooted graphs $(G,o)$ and $(G^{\prime},o^{\prime})$ are
rooted-isomorphic – denoted by $(G,o)\simeq(G,o^{\prime})$ – if there is a
bijection of the vertex sets of $G$ and $G^{\prime}$ that maps $o$ to
$o^{\prime}$ and preserves edges. We let $[G,o]$ denote the equivalence class
of $(G,o)$ under rooted isomorphisms, and let $\mathcal{G}_{*}$ denote the set
of all such $[G,o]$.

Given $r\in\mathbb{N}$ and a rooted graph $(G,o)$, $(G,o)_{r}$ denotes the
graph obtained by retaining only the vertices of $G$ within graph-theoretic
distance $r$ from $o$ and the edges between those vertices. Clearly,
$(G,o)\simeq(G^{\prime},o^{\prime})$ implies
$(G,o)_{r}\simeq(G^{\prime}o^{\prime})_{r}$ for all $r>0$, and we may define
$[G,o]_{r}$ as the equivalence class of $(G,o)_{r}$. The distance between
$[G,o],[G^{\prime},o^{\prime}]\in\mathcal{G}_{*}$ is defined by:

$\rho([G,o],[G^{\prime},o^{\prime}]):=\frac{1}{1+\sup\\{r\in\mathbb{N}\,:\,[G,o]_{r}=[G^{\prime},o^{\prime}]_{r}\\}}.$

One can show that $(\mathcal{G}_{*},\rho)$ is a Polish metric space.

The set $\mathcal{T}_{*}\subset\mathcal{G}_{*}$ of rooted trees is the set of
equivalence classes $[T,o]$ where $T$ is a locally finite tree. This is a
closed subset of $\mathcal{G}_{*}$ and is therefore a Polish space with the
metric $\rho$.

Our BGRW dynamics (see, Section 2.2) may be naturally extended to the set
$\mathcal{T}_{*}$ of random rooted trees. The idea is that the state
$[T_{t},X_{t}]$ describes the tree “rooted at the position of the walker”.
With some abuse of notation, we use $K_{p}$ to denote the Markov transition
kernel of our process over this space as well.

###  6.2. Empirical measures and local functions

Much of the remainder of the paper will be spent dealing with the tree as
viewed by the walker. More precisely, we will study the empirical measure of
the tree around the walker.

######  Definition 6.1.

Given a realization $[T_{t},X_{t}]$ of the process $K_{p}$, we let
$\widehat{P}_{n}$ denote the empirical measure, that is, the random
probability measure over $\mathcal{T}_{*}$ given by:

$\widehat{P}_{n}=\frac{1}{n+1}\sum_{t=0}^{n}\delta_{[T_{t},X_{t}]}.$

Thus for a given element $[T,v]\in\mathcal{T}_{*}$ and $r\in\mathbb{N}$,

$(n+1)\widehat{P}_{n}([G,o]\in\mathcal{T}_{*}\,:\,[G,o]_{r}=[T,v]_{r})$

counts the number of times $0\leq t\leq n$ at which the ball of radius $r$
around $X_{t}$ in $T_{t}$ is isomorphic to $[T,v]_{r}$.

In this section we show that, under suitable assumptions on $[T_{0},x_{0}]$,
the walker has a well-defined positive speed and in Section 7 that
$\widehat{P}_{n}\Rightarrow P_{p}$ almost surely, where $P_{p}$ is an
invariant measure for the process $K_{p}$. In the proof of such results, local
functions will play an important role.

######  Definition 6.2 (Local function).

A function $\psi:\mathcal{T}_{*}\to\mathbb{R}$ is said to be $r$-local if
$\psi([T,o])=\psi([T,o]_{r})$ for all $[T,o]\in\mathcal{T}_{*}$. A function
$\psi$ is local if it is $r$-local for some $r\in\mathbb{N}$.

To avoid clutter, with a slight abuse of notation, we will write $\psi(G,o)$
instead of $\psi([G,o])$.

The main result of this section is about the convergence of empirical averages
of bounded local functions on the space $\mathcal{T}_{*}$ along trajectories.
In order to do that we restrict ourselves on measures on $\mathcal{T}_{*}$
which have some nice properties. To define this class of measures we first
define certain stopping times. Given $\ell\in\mathbb{N}\backslash\\{0\\}$, let
$Q_{\ell}$ be the path of length $\ell$, i.e. the graph with vertex set
$\\{0,1,\dots,\ell\\}$ and edges $\\{(i-1),i\\}$ ($1\leq i\leq\ell$). We
define $\tau_{\ell}$ as the first time when the graph around $X_{t}$ in
$T_{t}$ is $Q_{\ell}$.

$\tau_{\ell}:=\inf\\{t\geq 0\,:\,[T_{t},X_{t}]_{\ell}=[Q_{\ell},\ell]\\}.$

######  Definition 6.3.

A measure $\mu$ over pairs $(T,x)$ is called $p$-escapable if
$\tau_{\ell}<+\infty$ ${\mathbb{P}}_{\mu,p}$-almost surely for every $\ell\geq
1$.

We can now state the main theorem of this section.

######  Theorem 6.1.

For each parameter $0<p\leq 1$ and each bounded integer $r\geq 1$ and all
$r$-local function $\psi:\mathcal{T}_{*}\to\mathbb{R}$, there exists a
constant $\mathcal{M}_{p}\psi$ such that

$\lim_{n\to+\infty}\widehat{P}_{n}\psi=\mathcal{M}_{p}\psi\mbox{
}\mathbb{P}_{\mu,p}\mbox{-a.s.},$

for all $p$-escapable distribution $\mu$ on $\mathcal{T}_{*}$.

As we will see in Section 7, this result implies that “the tree seen by the
walker” converges to an infinite random tree when $n\to+\infty$.

The proof of the theorem relies on the following results. The first Lemma
shows that the empirical measures of processes started from two $p$-escapable
measures are asymptotically the same, i.e. the initial distribution is
“forgotten”. The second Lemma shows that the empirical measures of local
functions when our process starts from specific $p$-escapable measures,
corresponding to $\delta_{[T_{0},x_{0}]}$ with $T_{0}$ finite, converges to a
constant.

######  Lemma 6.1 (Forgetfulness of empirical measures; proof in §6.5).

Let $\mu$, $\nu$ be two $p$-escapable measures. Let $r$ be a positive integer
and $\psi:\mathcal{T}_{*}\to\mathbb{R}$ be a bounded $r$-local function. If
there exists a constant $\mathcal{M}_{p}\psi$ such that
$\widehat{P}_{n}\psi\to\mathcal{M}_{p}\psi$ ${\mathbb{P}}_{\nu,p}$-almost-
surely, then we also have $\widehat{P}_{n}\psi\to\mathcal{M}_{p}\psi$
${\mathbb{P}}_{\mu,p}$-almost-surely.

The above statement allows us to restrict ourselves to subclasses of initial
distributions and then extend the results to the whole class of $p$-escapable
distributions. This procedure greatly reduces the amount of work in our
proofs. The next lemma is a finite version of Theorem 6.1.

######  Lemma 6.2 (proof in §6.6).

Consider an initial condition $(T_{0},x_{0})$ with $T_{0}$ finite. Fix
$0<p\leq 1$ and a bounded $r$-local function
$\psi:\mathcal{T}_{*}\to\mathbb{R}$ (with $r$ a positive integer). Then there
exists a constant $\mathcal{M}_{p}\psi$ such that
$\widehat{P}_{n}\psi\to\mathcal{M}_{p}\psi,\mbox{
}\mathbb{P}_{T_{0},x_{0},p}$-a.s.

Combining the two lemmas gives us a straightforward proof of Theorem 6.1.

###### Proof of Theorem 6.1.

Let $[T_{0},x_{0}]$ be a finite rooted tree and consider
$\nu=\delta_{[T_{0},x_{0}]}$. By Lemma 6.2, we have that
$\widehat{P}_{n}\psi\to\mathcal{M}_{p}\psi,\mbox{ }\mathbb{P}_{\nu,p}$-a.s.
But, by Lemma 5.3, $\nu$ is $p$-escapable. Therefore, by Lemma 6.1,
$\widehat{P}_{n}\psi\to\mathcal{M}_{p}\psi,\mbox{ }\mathbb{P}_{\mu,p}$-a.s.

Now we know how the main theorem follows from our lemmas we organize the
remainder of this section as follows. In the next subsection we prove Theorem
1.1 as an application of Theorem 6.1. Then, in Subsection 6.4, we discuss the
concept of $p$-escapable trees and give quantitative criteria for
escapabality. Finally, in Subsections 6.5 and 6.6, we prove lemmas 6.1 and
6.2, respectively.

###  6.3. Existence of the speed

In this section we prove a stronger version of Theorem 1.1 as an application
of Theorem 6.1. We prove that the random walker in the BGRW model has a well-
defined positive speed for any $p$-escapable initial distribution on
$\mathcal{T}_{*}$.

######  Theorem 6.2 (Linear speed of the walker).

For each $0<p\leq 1$, there exists a constant $0<c(p)\leq p$ such that, for
any $p$-escapable distribution $\mu$ on $\mathcal{T}_{*}$,

$\lim_{n\rightarrow\infty}\frac{\mathrm{dist}_{T_{n}}(X_{n},\mathrm{root})}{n}=c(p)\;{\mathbb{P}}_{\mu,p}\textit{-a.s.}.$

###### Proof.

Our strategy is to prove that the distance from the root at time $n$ may be
written as a sum of a bounded term, a martingale, and a sum of a $1$-local
function computed along the trajectory. The result will then follow from
Theorem 6.1.

Fix a $p$-escapable measure $\mu$ and define the following bounded $1$-local
function:

$\psi(T,x):=\frac{p(d_{T}(x)-1)}{d_{T}(x)+1}+\frac{(1-p)(d_{T}(x)-2)}{d_{T}(x)}.$

Note that:

(6.1)
$\begin{split}\mathbb{E}_{\mu,p}\left[\Delta\mathrm{dist}_{T_{n}}(X_{n},\mathrm{root})\mid\mathcal{F}_{n}\right]&=\psi(T_{n},X_{n})+(1-\psi(T_{n},X_{n}))\,\mathbb{1}_{\\{X_{n}=\mathrm{root}\\}}.\end{split}$

Thus

(6.2)
$\mathrm{dist}_{T_{n+1}}(X_{n+1},\mathrm{root})=M_{n+1}+\sum_{j=0}^{n}\psi(T_{j},X_{j})+C_{n+1},$

where $\\{M_{j}\\}_{j}$ is a martingale with bounded increments and

$C_{n+1}:=\sum_{j=0}^{n}(1-\psi(T_{n},X_{n}))\,\mathbb{1}_{\\{X_{n}=\mathrm{root}\\}}$

is bounded by the total number of visits to the root, which is a.s. finite
because our process is transient.

Since the martingale has bounded increments, Azuma’s inequality implies that
$M_{n}/n\to 0$ almost surely. Since $C_{n}$ is a.s. bounded, $C_{n}/n\to 0$
almost surely as well. Theorem 6.1 gives us that

(6.3)
$\lim_{n\to+\infty}\frac{\mathrm{dist}_{T_{n+1}}(X_{n+1},\mathrm{root})}{n+1}=\lim_{n\rightarrow\infty}\frac{1}{n+1}\sum_{j=0}^{n}\psi(T_{j},X_{j})=c(p):=\mathcal{M}_{p}(\psi),\;{\mathbb{P}}_{\mu,p}\textit{-a.s},$

with $\mathcal{M}_{p}(\psi)$ is a constant depending on $p$ and $\psi$ only
(but not on $\mu$). Proposition 5.12 implies $c(p)>0$.

###  6.4. Escapable trees and mixing

The concept of escapable trees is closely related to the forgetfulness of the
walker. Roughly speaking, once the walker has escaped it may never come back
to its initial tree. In this section we prove a quantitative criteria for
checking “escapability”. Let us notice that not all trees are $p$-escapable.
The next example gives a useful example to keep in mind.

######  Example 6.1 (A hard tree).

Consider an infinite rooted tree $T_{\rm hard}$, with a root node $x_{\rm
hard}$, such that each node at distance $h$ from the root has $g(h)>0$
children, with $1/g(h)$ summable. Consider the BGRW from $(T_{\rm hard},x_{\rm
hard})$. One can show via the Borel-Cantelli Lemma that there is a positive
probability that ${\rm dist}_{T_{t}}(X_{t},x_{\rm hard})=t$ for all
$t\in\mathbb{N}$ (i.e. the walker simply “walks down the tree” for eternity).
For the same reason, for any $\ell\in\mathbb{N}\backslash\\{0\\}$ there is a
positive probability that $\tau_{\ell}=+\infty$.

The next Lemma (proven subsequently) explains one reason why $p$-escapability
is important to us. The Lemma gives a quantitative criterion for
“escapability”. In a way, it says that what makes the tree in Example 6.1 non-
escapable is that $X_{t}$ sees very large degrees along the way.

######  Lemma 6.3 (Quantitative escapability).

Assume $\mu$ is a starting measure for which there exist $C,D,\alpha>0$ such
that, for all $n,k\geq 1$,

(6.4) $\sum_{t=0}^{n}{\mathbb{P}}_{\mu,p}(d_{T_{t}}(X_{t})\geq k)\leq
C\,(n+D)\,e^{-\alpha\,k}.$

Then $\mu$ is $p$-escapable and

(6.5) ${\mathbb{E}}_{\mu,p}[\tau_{\ell}\wedge n]\leq\frac{\ell
2^{\ell-1}}{p^{\ell}}\left\lceil\frac{2\log(n+D)+\log
C}{\alpha}\right\rceil+1.$

Moreover, the following event holds with probability $\geq 1-1/n^{16}$: for
all times $1\leq t\leq n$,

(6.6) ${\mathbb{E}}_{T_{t},X_{t},p}[\tau_{\ell}\wedge n]\leq\frac{\ell
2^{\ell-1}}{p^{\ell}}\left\lceil\frac{\log(2n+D)+17\log n+\log
C}{\alpha}\right\rceil+1.$

In particular, all measures $\mu=\delta_{(T,x)}$, with $T$ a finite tree,
satisfy the above inequalities, with $C\leq e^{\alpha\,\Delta(T)}$ by virtue
of Lemma 5.3.

So Lemma 6.3 also guarantees that not only $\mu$ is $p$-escapable, but also
that, with high probability, each intermediate $[T_{t},X_{t}]$ satisfies a
quantitative escapability property. One important point is that the
assumptions of Lemma 6.3 always apply to initial trees that are finite, by
virtue of Lemma 5.3.

###### Proof.

We first prove inequality (6.5) for ${\mathbb{E}}_{\mu,p}[\tau_{\ell}\wedge
n]$, noting that it implies $p$-escapability because, assuming it, we can
show:

${\mathbb{P}}_{\mu,p}(\tau_{\ell}=+\infty)\leq\frac{{\mathbb{E}}_{\mu,p}[\tau_{\ell}\wedge
n]}{n}\leq\frac{1}{n}\left(\frac{\ell
2^{\ell-1}}{p^{\ell}}\left\lceil\frac{2\log(n+D)+\log
C}{\alpha}\right\rceil+1\right)\stackrel{{\scriptstyle n\to+\infty}}{{\to}}0,$

Fix some $\Delta>0$. Let $\eta_{\Delta}$ be the first time the walker “sees” a
node with degree $\geq\Delta$,

(6.7) $\eta_{\Delta}:=\inf\left\\{m\geq
0\;\middle|\;d_{T_{m}}(X_{m})\geq\Delta\right\\}$

and consider the event $A_{i}$ in which at time $i\ell$ the walker creates a
new leaf, jumps to it and grows a path of length $\ell-1$ from it in such way
that at time $i\ell+\ell-1$ the walker finds itself at the tip of a path of
length $\ell$. Now we define another stopping time

(6.8) $\tilde{\tau_{\ell}}:=\inf\left\\{i\geq 0\;\middle|\;A_{i}\text{ occurs
}\right\\}$

and note that $\tau_{\ell}\leq\ell\tilde{\tau_{\ell}}$.

By the definition of the event $A_{i}$, we have that

${\mathbb{P}}_{\mu,p}\left(A_{i}\middle|\mathcal{F}_{i\ell}\right)=\frac{p}{d_{T_{i\ell}}(X_{i\ell})}\left(\frac{p}{2}\right)^{\ell-1}.$

Thus, by the definition of the stopping time $\eta_{\Delta}$, we also have

(6.9)
$\mathbb{1}\\{\eta_{\Delta}>i\ell\\}{\mathbb{P}}_{\mu,p}\left(A_{i}\middle|\mathcal{F}_{i\ell}\right)\geq\frac{p}{\Delta}\left(\frac{p}{2}\right)^{\ell-1}\mathbb{1}\\{\eta_{\Delta}>i\ell\\}.$

Using the above inequality and noticing that
$\mathbb{1}\\{\eta_{\Delta}>k\ell\\}\leq\mathbb{1}\\{\eta_{\Delta}>(k-1)\ell\\}$,
we obtain

(6.10) $\begin{split}{\mathbb{P}}_{\mu,p}\left(\tilde{\tau_{\ell}}\geq
k,\eta_{\Delta}>k\ell\right)&={\mathbb{E}}_{\mu,p}\left[{\mathbb{E}}_{\mu,p}\left[\mathbb{1}_{A^{c}_{k}}\middle|\mathcal{F}_{k\ell}\right]\mathbb{1}\\{\eta_{\Delta}>k\ell\\}\prod_{i=0}^{k-1}\mathbb{1}_{A^{c}_{i}}\right]\\\
&\leq\left(1-\frac{p}{\Delta}\left(\frac{p}{2}\right)^{\ell-1}\right){\mathbb{P}}_{\mu,p}\left(\tilde{\tau_{\ell}}\geq
k-1,\eta_{\Delta}>(k-1)\ell\right).\end{split}$

Then, proceeding by induction, we obtain the following upper bound

(6.11) ${\mathbb{P}}_{\mu,p}\left(\tilde{\tau_{\ell}}\geq
k,\eta_{\Delta}>k\ell\right)\leq\left(1-\frac{p}{\Delta}\left(\frac{p}{2}\right)^{\ell-1}\right)^{k}.$

Since

${\mathbb{P}}_{\mu,p}\left(\tau_{\ell}\wedge n\geq
k\ell\right)\leq\left\\{\begin{array}[]{ll}{\mathbb{P}}_{\mu,p}\left(\tilde{\tau_{\ell}}\geq
k\right),&k\ell\leq n\\\ 0,&\mbox{otherwise};\end{array}\right.$

we have:

$\displaystyle{\mathbb{P}}_{\mu,p}\left(\tau_{\ell}\wedge n\geq
k\ell\right)\leq{\mathbb{P}}_{\mu,p}\left(\tilde{\tau_{\ell}}\geq
k,\eta_{\Delta}>k\ell\right)+{\mathbb{P}}_{\mu,p}\left(\eta_{\Delta}\leq
k\ell\right),$

and consequently,

(6.12) ${\mathbb{E}}_{\mu,p}\left[\tau_{\ell}\wedge
n\right]\leq\sum_{j=0}^{\lfloor\frac{n}{\ell}\rfloor}\ell{\mathbb{P}}_{\mu,p}\left(\tau_{\ell}\wedge
n\geq
j\,r\right)\leq\frac{\ell\,2^{\ell-1}}{p^{\ell}}\Delta+n\,{\mathbb{P}}_{\mu,p}\left(\eta_{\Delta}\leq
n\right).$

But, by our condition (7.2),

(6.13) ${\mathbb{P}}_{\mu,p}\left(\eta_{\Delta}\leq
n\right)\leq\sum_{t=0}^{n}{\mathbb{P}}_{\mu,p}(d_{T_{t}}(X_{t})\geq\Delta)\leq
C\,(n+1)\,e^{-\alpha\,\Delta}.$

so

${\mathbb{E}}_{\mu,p}\left[\tau_{\ell}\wedge n\right]\leq\frac{\ell
2^{\ell-1}}{p^{\ell}}\Delta+C\,(n+1)^{2}e^{-\alpha\,\Delta}.$

We may choose

$\Delta=\left\lceil\frac{2\log(n+1)+\log C}{\alpha}\right\rceil$

to finish the proof of (6.5).

To prove the last statement in the Theorem, we go back to (6.13) and note that
was the only step in that proof where we used (6.4). In particular, we can go
back to (6.12) and obtain:

${\mathbb{E}}_{T_{t},X_{t},p}\left[\tau_{\ell}\wedge n\right]\leq\frac{\ell
2^{\ell-1}}{p^{\ell}}\Delta+n\,{\mathbb{P}}_{T_{t},X_{t},p}(\eta_{\Delta}\leq
n).$

In particular, if $\Delta$ is given and we consider the event

$\mathcal{G}(\Delta):=\bigcap_{t=0}^{n}\\{{\mathbb{P}}_{T_{t},X_{t},p}(\eta_{\Delta}\leq
n)\leq 1/n)\\},$

we have that, when $\mathcal{G}(\Delta)$ holds, then:

(6.14) ${\mathbb{E}}_{T_{t},X_{t},p}[\tau_{\ell}\wedge n]\leq\frac{\ell
2^{\ell-1}}{p^{\ell}}\Delta+1.$

for each $0\leq t\leq n$. To finish, we show that
${\mathbb{P}}_{\mu,p}(\mathcal{G}(\Delta))\geq 1-n^{-16}$ for an appropriate
choice of $\Delta$. Indeed, by union bound and Markov’s inequality:

$1-{\mathbb{P}}_{\mu,p}(\mathcal{G}(\Delta))\leq
n\sum_{t=0}^{n}{\mathbb{E}}_{\mu,p}[{\mathbb{P}}_{T_{t},X_{t},p}(\eta_{\Delta}\leq
n)].$

Now by the Simple Markov property, for $0\leq t\leq n$

${\mathbb{E}}_{\mu,p}[{\mathbb{P}}_{T_{t},X_{t},p}(\eta_{\Delta}\leq
n)]={\mathbb{P}}_{\mu,p}(\exists\;t\leq s\leq
t+n\,:\,d_{T_{s}}(X_{s})\geq\Delta)\leq{\mathbb{P}}_{\mu,p}(\eta_{\Delta}\leq
2n).$

And again, by condition (6.4),

$1-{\mathbb{P}}_{\mu,p}(\mathcal{G})\leq
n\,{\mathbb{P}}_{\mu,p}(\eta_{\Delta}\leq 2n)\leq
n\,\sum_{t=0}^{2n}{\mathbb{P}}_{\mu,p}(d_{t}(X_{t})\geq\Delta)\leq
C\,n\,(2n+D)\,e^{-\alpha\,\Delta}.$

Taking

$\Delta:=\left\lceil\frac{\log(2n+D)+17\log n+\log C}{\alpha}\right\rceil$

guarantees ${\mathbb{P}}_{\mu,p}(\mathcal{G}(\Delta))\geq 1-n^{-16}$. Plugging
this choice of $\Delta$ into (6.14) gives (6.6) inside the event
$\mathcal{G}(\Delta)$.

###  6.5. Forgetfulness of empirical measures: proof of Lemma 6.1

The proof of the lemma will follow as a consequence of another result that
highlight the relation between “escapabability” and forgetfulness. As we will
see, it implies an approximated renewal property of the BGRW process in the
sense that after a random time it may be coupled to a BGRW process starting
from a semi-infinite path. Then, both walkers see around them the same tree
structure as long as this coupling works.

For this purpose, we will need additional notation. Let $Q^{*}$ be a semi-
infinite path, i.e.,

(6.15) $Q^{*}=\\{v_{0},v_{1},v_{2},\dots\\}$

rooted at $v_{0}$ and consider a trajectory $(T^{*}_{t},X_{t}^{*})_{t\geq 0}$
of BGRW started from $(Q^{*},v_{0})$ with empirical measures
$\widehat{P}^{*}_{n}$. Also, for each pair of integers $r$ and $n$, let
$\pi(r,n)$ be

(6.16) $\pi(r,n):={\mathbb{P}}_{Q^{*}_{0},v_{0},p}\left(\exists m\leq
n,\;X^{*}_{m}=x_{r}\right).$

######  Lemma 6.4.

Let $\psi:\mathcal{T}_{*}\to\mathbb{R}$ be a $r$-local and bounded and $\mu$
be a $p$-escapable distribution. Consider a trajectory $(T_{t},X_{t})_{t\geq
0}$ of BGRW starting from $\mu$, with empirical measures $\widehat{P}_{n}$.
Then,

  * (a)

for every $\varepsilon\in(0,1)$, there exist a coupling of the processes
$(T_{t},X_{t})_{t\geq 0}$ and $(T^{*}_{t},X^{*}_{t})_{t\geq 0}$ such that:

${\mathbb{P}}\left(\lim_{n\to+\infty}|(\widehat{P}_{n}-\widehat{P}^{*}_{n})\psi|=0\right)\geq
1-\varepsilon.$

  * (b)

$\left|{\mathbb{E}}_{\mu,p}\left[\widehat{P}_{n}\psi\right]-{\mathbb{E}}_{Q^{*},v_{0},p}\left[\widehat{P}^{*}_{n}\psi\right]\right|\leq
2\|\psi\|_{\infty}\pi(r,n)+\frac{2\|\psi\|_{\infty}{\mathbb{E}}_{\mu,p}[\tau_{2r}\wedge
n]}{n+1}.$

###### Proof.

Part (a). Take an $\ell\in\mathbb{N}$ bigger than $2r$. Consider a chain
started from measure $\mu$. Since $\mu$ is $p$-escapable, the stopping time
$\tau_{\ell}$ is finite ${\mathbb{P}}_{\mu,p}$-almost-surely.

Let $y_{0}=X_{\tau_{\ell}}$, $y_{1}$, $\dots$, $y_{\ell}$ be the unique
vertices at distances $0,1,2,\dots,\ell$ at time $\tau_{\ell}$. Define a
random time $\tau^{\prime}_{\ell,r}$ as follows:

$\tau^{\prime}_{\ell,r}:=\inf\\{t\geq 0\,:\,X_{\tau_{\ell}+t}=y_{\ell-r}\\}.$

Notice that this time may well be infinite. In fact, since ${\rm
dist}(X_{\tau_{\ell}},y_{\ell-r})=\ell-r$, the second statement in Lemma 5.2,
combined with the strong Markov property and the $p$-escapability of $\mu$,
implies.

${\mathbb{P}}_{\mu,p}\left(\tau^{\prime}_{\ell,r}<+\infty\right)\leq
C\,e^{-\beta\,(\ell-r)}.$

Note that $\tau_{\ell}$ is the time $X_{t}$ is at the tip of a path of length
$\ell$ and $\tau_{\ell}+\tau^{\prime}_{\ell,r}$ is the first time at which
$X_{t}$ comes within distance $r$ of the other end of that path.

Now consider the process $(T^{*}_{t},X^{*}_{t})$ started on vertex $v_{0}$ of
the infinite path $v_{0},v_{1},\dots,v_{m},\dots$. Let

$\tau^{*}_{\ell,r}:=\inf\\{t\geq 0\,:\,X^{*}_{t}=v_{\ell-r}\\}.$

This time may also be infinite. It is easy to see that one can couple
$(T^{*}_{t},X^{*}_{t})$ to $(T_{\tau_{\ell}+t},X_{\tau_{\ell}+t})$ so that
$\tau_{\ell,r}=\tau^{\prime}_{\ell,r}$ and
$[T^{*}_{t},X^{*}_{t}]_{r}=[T_{\tau_{\ell}+t},X_{\tau_{\ell}+t}]_{r}$ for all
$0\leq t\leq\tau^{\prime}_{\ell,r}$. Under this coupling, if
$\tau^{\prime}_{\ell,r}>n$ and $\tau_{\ell}\leq n$, then

$\displaystyle\widehat{P}_{n}\psi$ $\displaystyle=$
$\displaystyle\frac{1}{n+1}\sum_{i=0}^{n}\psi(T_{i},X_{i})$ (6.17) (use
coupling and r-locality) $\displaystyle=$
$\displaystyle\frac{1}{n+1}\sum_{i=0}^{\tau_{\ell}\wedge
n-1}\psi(T_{i},X_{i})+\frac{1}{n+1}\sum_{t=0}^{n-\tau_{\ell}\wedge
n}\psi(T^{*}_{t},X^{*}_{t})$ $\displaystyle=$
$\displaystyle\widehat{P}^{*}_{n}\psi+\frac{1}{n+1}\sum_{i=0}^{\tau_{\ell}\wedge
n-1}(\psi(T_{i},X_{i})-\psi(T_{n-\tau_{\ell}\wedge
n+i+1},X_{n-\tau_{\ell}\wedge n+i+1})).$

Since $\tau_{\ell}<+\infty$ is bounded and
$\widehat{P}_{n}\psi\leq\|\psi\|_{\infty}$, this implies that, under the
coupling:

$\tau^{\prime}_{\ell,r}>n\Rightarrow|\widehat{P}_{n}\psi-\widehat{P}^{*}_{n}\psi|\leq\frac{2\|\psi\|_{\infty}\,(\tau_{\ell}\wedge
n)}{n+1}\to 0.$

So, for any fixed $\ell$, we have

${\mathbb{P}}\left(\lim_{n\to+\infty}|(\widehat{P}_{n}-\widehat{P}^{*}_{n})\psi|=0\right)\geq{\mathbb{P}}(\tau^{\prime}_{\ell,r}=+\infty)\geq
1-C\,e^{-\beta\,(\ell-r)}.$

In particular, this can be made greater than $1-\varepsilon$ with an
appropriate choice of $\ell$. This proves part $(a)$.

Part (b). Put $\ell=2r$. From Equation (6.17) and the fact that under the
coupling $\tau^{\prime}_{\ell,r}=\tau^{*}_{\ell,r}$, we may obtain that

(6.18)
$\begin{split}\left|\widehat{P}_{n}\psi-\widehat{P}^{*}_{n}\psi\right|&=\left|\widehat{P}_{n}\psi-\widehat{P}^{*}_{n}\psi\right|\mathbb{1}\\{\tau^{\prime}_{\ell,r}\leq
n\\}+\left|\widehat{P}_{n}\psi-\widehat{P}^{*}_{n}\psi\right|\mathbb{1}\\{\tau^{\prime}_{\ell,r}>n\\}\\\
&\leq 2\|\psi\|_{\infty}\mathbb{1}\\{\tau^{*}_{\ell,r}\leq
n\\}+\frac{2\|\psi\|_{\infty}\,(\tau_{\ell}\wedge n)}{n+1}\end{split}$

taking the expected value both sides it is enough to proves part (b) and
finally proves the lemma.

Now we see how Lemma 6.1 follows immediately from the above result.

###### Proof of Lemma 6.1.

From part (a) of Lemma 6.4, one sees that, given a deterministic
$c\in\mathbb{R}$,

${\mathbb{P}}_{\mu,p}(\widehat{P}_{n}\psi\to
c)=1\Leftrightarrow{\mathbb{P}}_{Q^{*},v_{0},p}(\widehat{P}^{*}_{n}\psi\to
c)=1.$

This holds for any $p$-escapable measure $\mu$. In particular, if $\nu$ is
also $p$-escapable $\widehat{P}_{n}\psi\to c$ ${\mathbb{P}}_{\nu,p}$-a.s., the
same must hold with $\nu$ replacing $\mu$. In other words, Lemma 6.4 (a)
implies the lemma.

###  6.6. Convergence of average of local functions: proof of Lemma 6.2

The proof of Lemma 6.2 will follow essentially from the lemma below that
states that, when started from a finite initial condition, the average of
local functions is close to its expected value but started from the semi-
finite path $Q^{*}$ introduced in (6.15).

######  Lemma 6.5.

Given $p_{0}>0$, there exist constants $C,\alpha>0$ depending only on $p_{0}$
such that, for all $p_{0}\leq p\leq 1$, all finite $(T_{0},x_{0})$, all
$-1\leq\psi\leq 1$ $r$-local, all $\varepsilon>0$, and all $1\leq q<n$,
$\lfloor n/q\rfloor>0$,

(6.19)
${\mathbb{P}}_{T_{0},x_{0},p}\left(\left|\widehat{P}_{n}\psi-{\mathbb{E}}_{Q^{*},v_{0},p}\left[\widehat{P}_{q}\psi\right]\right|\geq\varepsilon+\frac{2q}{n}+err(q,r)\right)\leq
2\exp\\{-\varepsilon^{2}\lfloor n/q\rfloor/32\\}+\frac{1}{q^{16}},$

where

(6.20)
$err(q,r):=4\pi(r,q)+\frac{r2^{2r}}{q\,p^{2r}}\left\lceil\frac{\log(2q+|V(T_{0})|)+17\log
q+\alpha\Delta(T_{0})\log C}{\alpha}\right\rceil+\frac{1}{q}.$

###### Proof.

Let $n=kq+s$, with $k\geq 1$. Obseve that, for every $k,q\geq 1$, we can write

(6.21)
$\begin{split}\widehat{P}_{kq-1}\psi=\frac{1}{kq}\sum_{i=0}^{kq-1}\psi(T_{i},X_{i})&=\frac{1}{k}\left(\frac{1}{q}\sum_{i=0}^{q-1}\psi(T_{i},X_{i})+\cdots+\frac{1}{q}\sum_{i=kq-q}^{kq-1}\psi(T_{i},X_{i})\right)\\\
&=\frac{1}{k}\sum_{j=1}^{k}S_{j}\;,\end{split}$

where,
$S_{j}:=\displaystyle\frac{1}{q}\sum_{i=(j-1)q}^{jq-1}\psi(T_{i},X_{i})$, for
$j\in\\{1,\cdots,k\\}$. Let us denote by $\\{\tilde{\mathcal{F}}_{j}\\}_{j\geq
0}$ the following filtration:

(6.22)
$\tilde{\mathcal{F}}_{0}=\mathcal{F}_{0};\;\;\tilde{\mathcal{F}}_{j}=\mathcal{F}_{jq-1}.$

By the definition of $S_{j}$, the process $\\{S_{j}\\}_{j\geq 1}$ is adapted
to the filtration $\\{\tilde{\mathcal{F}}_{j}\\}_{j\geq 0}$. Moreover, the
process $\\{M_{k}\\}_{k\geq 1}$ defined as

(6.23)
$M_{k}:=\sum_{j=1}^{k}S_{j}-{\mathbb{E}}_{T_{0},x_{0},p}\left[S_{j}\middle|\tilde{\mathcal{F}}_{j-1}\right]=M_{k-1}+S_{k}-{\mathbb{E}}_{T_{0},x_{0},p}\left[S_{k}\middle|\tilde{\mathcal{F}}_{k-1}\right]$

is a mean zero martingale with respect to
$\\{\tilde{\mathcal{F}}_{j}\\}_{j\geq 0}$, whose increments are bounded by
$2$, since $S_{j}$ is an average of random variables bounded by $1$.

With all these definitions, by triangle inequality, we have that

(6.24)
$\begin{split}\left|\widehat{P}_{n}\psi-{\mathbb{E}}_{Q^{*},v_{0},p}\left[\widehat{P}_{q}\psi\right]\right|&\leq\left|\widehat{P}_{n}\psi-\widehat{P}_{kq-1}\psi\right|\quad(a)\\\
&+\left|\widehat{P}_{kq-1}(\psi)-\frac{1}{k}\sum_{j=1}^{k}{\mathbb{E}}_{T_{0},x_{0},p}\left[S_{j}\middle|\tilde{\mathcal{F}}_{j-1}\right]\right|\quad(b)\\\
&+\left|\frac{1}{k}\left(\sum_{j=1}^{k}{\mathbb{E}}_{T_{0},x_{0},p}\left[S_{j}\middle|\tilde{\mathcal{F}}_{j-1}\right]-{\mathbb{E}}_{Q^{*},v_{0},p}\left[\widehat{P}_{q}\psi\right]\right)\right|\quad(c).\end{split}$

As far as $(a)$ is concerned, we observe that the following deterministic
bound holds:

$\begin{split}\left|\widehat{P}_{n}\psi-\widehat{P}_{kq-1}\psi\right|&=\left|\left(\frac{kq}{n+1}-1\right)\frac{1}{kq}\sum_{i=0}^{kq-1}\psi(T_{i},X_{i})+\frac{1}{n+1}\sum_{i=kq}^{kq+s}\psi(T_{i},X_{i})\right|\\\
&\leq\frac{2\|\psi\|_{\infty}(s+1)}{n+1}<\frac{2q}{n},\end{split}$

since, by hypothesis, $\|\psi\|_{\infty}\leq 1$. Thus, to prove the claim, it
suffices to show that

(6.25)
${\mathbb{P}}_{T_{0},x_{0},p}\Big{(}(b)+(c)\geq\varepsilon+err(q,r)\Big{)}\leq
2\exp\\{-\varepsilon^{2}k/32\\}+\frac{1}{q^{16}}\;.$

Using the simple observation that

${\mathbb{P}}_{T_{0},x_{0},p}\Big{(}(b)+(c)\geq\varepsilon+err(q,r)\Big{)}\leq{\mathbb{P}}_{T_{0},x_{0},p}\left((b)\geq\frac{\varepsilon+err(q,r)}{2}\right)+{\mathbb{P}}_{T_{0},x_{0},p}\left((c)\geq\frac{\varepsilon+err(q,r)}{2}\right)\;,$

we will prove Equation (6.25) by showing

$\displaystyle(1):\qquad{\mathbb{P}}_{T_{0},x_{0},p}\left((b)\geq\frac{\varepsilon}{2}\right)\leq
2\exp\\{-\varepsilon^{2}k/32\\}\,$
$\displaystyle(2):\qquad{\mathbb{P}}_{T_{0},x_{0},p}\left((c)>\frac{err(q,r)}{2}\right)\leq\frac{1}{q^{16}}\,$

To show $(1)$, we observe that the martingale $M_{k}$ can be written as the
following difference

(6.26)
$M_{k}=k\widehat{P}_{kq-1}(\psi)-\sum_{j=1}^{k}{\mathbb{E}}_{T_{0},x_{0},p}\left[S_{j}\middle|\tilde{\mathcal{F}}_{j-1}\right].$

Thus, $(b)$ is equal to $|M_{k}/k|$ and we apply Azuma’s inequality which
gives us:

(6.27)
${\mathbb{P}}_{T_{0},x_{0},p}\left(\left|M_{k}\right|\geq\frac{\varepsilon
k}{2}\right)\leq 2\exp\\{-\varepsilon^{2}k/32\\}\,.$

To show $(2)$, we first observe that, by the Simple Markov Property, for all
$j\in\\{2,\cdots,k\\}$ the following identity holds

(6.28)
${\mathbb{E}}_{T_{0},x_{0},p}\left[S_{j}\middle|\tilde{\mathcal{F}}_{j-1}\right]=\frac{1}{q}\sum_{i=1}^{q}{\mathbb{E}}_{T_{(j-1)q-1},X_{(j-1)q-1},p}\left[\psi(T_{i},X_{i})\right]={\mathbb{E}}_{T_{(j-1)q-1},X_{(j-1)q-1},p}\left[\widehat{P}_{q}(\psi)\right].$

Then, by Part (b) of Lemma 6.4 we have

(6.29)
$\begin{split}\left|{\mathbb{E}}_{T_{0},x_{0},p}\left[S_{j}\middle|\tilde{\mathcal{F}}_{j-1}\right]-{\mathbb{E}}_{Q^{*},v_{0},p}\left[\widehat{P}_{q}(\psi)\right]\right|&\leq
2\pi(r,q)+\frac{2{\mathbb{E}}_{T_{(j-1)q-1},X_{(j-1)q-1},p}\left[\tau_{2r}\wedge
q\right]}{q}\,,\end{split}$

and implies

$(c)\leq
2\pi(r,q)+\frac{1}{k}\sum_{j=1}^{k}\frac{2{\mathbb{E}}_{T_{(j-1)q-1},X_{(j-1)q-1},p}\left[\tau_{2r}\wedge
q\right]}{q}\;.$

Therefore, it is enough to show that the following events

(6.30)
$B:=\left\\{\sum_{j=0}^{k-1}\frac{2{\mathbb{E}}_{T_{jq-1},X_{jq-1},p}\left[\tau_{2r}\wedge
q\right]}{k\,q}>\frac{r2^{2r}}{q\,p^{2r}}\left\lceil\frac{\log(2q+|V(T_{0})|)+17\log
q+\alpha\Delta(T_{0})\log C}{\alpha}\right\rceil+\frac{1}{q}\right\\}$

happens with probability at most $q^{-16}$.

By Lemma 6.3 (using the constants coming from Lemma 5.3) we know that, if we
define

$A_{t}:=\left\\{{\mathbb{E}}_{T_{t},X_{t},p}[\tau_{2r}\wedge
q]\leq\frac{r2^{2r}}{p^{2r}}\left\lceil\frac{\log(2q+|V(T_{0})|)+17\log
q}{\alpha}+\Delta(T_{0})\log C\right\rceil+1\right\\}\,,$

it holds that

${\mathbb{P}}_{T_{0},x_{0},p}\left(\bigcap_{t=0}^{q}A_{t}\right)\geq
1-\frac{1}{q^{16}}\;,$

which implies
${\mathbb{P}}_{T_{0},x_{0},p}\left(B\right)\leq\frac{1}{q^{16}}$, and
concludes the proof.

######  Corollary 6.1.

Given $p_{0}>0$, for all $p\in[p_{0},1]$, for all finite $(T_{0},x_{0})$ and
for all $r$-local function $\psi$ such that $-1\leq\psi\leq 1$,
$\\{P_{n}\psi\\}_{n\in\mathbb{N}}$ is a Cauchy sequence
$\mathbb{P}_{T_{0},x_{0}}$-a.s.

###### Proof.

The proof will follow from the claim below.

######  Claim 6.1.

Given $p_{0}>0$ and $(T_{0},x_{0})$ finite, there exists $n_{0}$ and a
constant $c$ depending only on $p_{0},T_{0}$ such that, for all $n\geq n_{0}$
and for all $p\in[p_{0},1]$:

(6.31)
${\mathbb{P}}_{T_{0},x_{0},p}\left(\left|\widehat{P}_{m}\psi-\widehat{P}_{m^{\prime}}\psi\right|>\frac{c}{\log
n},\text{ for some
}m,m^{\prime}\in\\{n,n+1,\cdots,n^{2}\\}\right)\leq\frac{4}{n^{4}}.$

Proof of the claim: To prove the claim we show that there exists $n_{0}$ such
that for all $n\geq n_{0}$ and for all
$m,m^{\prime}\in\\{n,n+1,\cdots,n^{2}\\}$,

(6.32)
${\mathbb{P}}_{T_{0},x_{0},p}\left(\left|\widehat{P}_{m}\psi-\widehat{P}_{m^{\prime}}\psi\right|>\frac{c}{\log
n}\right)\leq\frac{4}{n^{8}}\ ,$

and then use union bound. We proceed by showing that for all
$m\in\\{n,n+1,\cdots,n^{2}\\}$ we can find values for $r$ and $q$ such that

(6.33)
${\mathbb{P}}_{T_{0},x_{0},p}\left(\left|\widehat{P}_{m}\psi-{\mathbb{E}}_{Q^{*},v_{0}}\left[\widehat{P}_{q}(\psi)\right]\right|>\frac{c}{2\log
n}\right)\leq\frac{2}{n^{8}}\ ,$

which implies Equation (6.32) by using triangle inequality. In order to show
that Equation (6.33) holds, we use Lemma 6.5, suitably choosing the values of
$q$, $r$ and $\varepsilon$. We begin observing that by Corollary 4.2 we have
that

$\pi(r,q)\leq\frac{C_{1}}{\log n}\,.$

Choosing $q=n^{1/2}$ and $r=\left\lfloor\frac{\log
n}{8\log(2/p)}\right\rfloor$, we obtain that

(6.34)
$\begin{split}err(q,r)&=4\pi(r,q)+\frac{4r2^{2r}}{q\,p^{2r}}\left\lceil\frac{\log(2q+|V(T_{0})|)+17\log
q+\alpha\Delta(T_{0})\log C}{\alpha}\right\rceil+\frac{1}{q}\\\
&\leq\frac{4C_{1}}{\log n}+\frac{\log n}{2n^{1/4}\log(2/p)}\left(\frac{\log
2n^{1/2}+|V(T_{0})|+9\log n}{\alpha}+\Delta(T_{0})\log
C\right)+\frac{1}{n^{1/2}}\\\ &\leq\frac{4C_{1}}{\log
n}+\frac{\log^{2}2n}{\alpha\,n^{1/4}}+\frac{|V(T_{0})|\log n}{\alpha
n^{1/4}}+\frac{9\log^{2}n}{\alpha n^{1/4}}+\frac{\log n\,\Delta(T_{0})\log
C}{n^{1/4}}+\frac{1}{n^{1/2}}\end{split}$

Given that the constants $C,C_{1},\alpha$ only depend on $p_{0}$, and $T_{0}$
is finite, there exists a constant $c$ and a sufficiently large $n_{0}$, both
depending on $p_{0}$ and $T_{0}$ only, such that

$err(q,r)\leq\frac{c}{6\log n}\;.$

Setting $\varepsilon=c/6\log^{-1}n$ and since $2q/m\leq 2n^{-1/2}\leq
c/6\log^{-1}n$ for sufficiently large $n$, by Lemma 6.5, for all
$m\in\\{n,n+1,\cdots,n^{2}\\}$, we have that

(6.35)
${\mathbb{P}}_{T_{0},x_{0},p}\left(\left|\widehat{P}_{m}\psi-{\mathbb{E}}_{Q^{*},v_{0}}\left[\widehat{P}_{q}\psi\right]\right|>\frac{c}{2\log
n}\right)\leq
2e^{-\varepsilon^{2}/32\sqrt{n}}+\frac{1}{q^{16}}\leq\frac{2}{n^{8}}\,,$

for sufficiently large $n$ (how large depends on $\varepsilon$ which only
depends on $p_{0},T_{0}$). Thus, for all
$m,m^{\prime}\in\\{n,n+1,\cdots,n^{2}\\}$ we have

(6.36)
${\mathbb{P}}_{T_{0},x_{0},p}\left(\left|\widehat{P}_{m}\psi-\widehat{P}_{m^{\prime}}\psi\right|>\frac{c}{\log
n}\right)\leq\frac{4}{n^{8}}\ ,$

and finally, by union bound, the claim follows.

$\blacksquare$

The above claim, together with a Borel-Cantelli argument, implies Corollary
6.1, i.e, $\mathbb{P}_{T_{0},x_{0},p}$ almost surely there exist $n_{0}$ such
that, for all $n\geq n_{0}$ and for all
$m,m^{\prime}\in\\{n,n+1,\cdots,n^{2}\\}$ we have

$\left|\widehat{P}_{m}\psi-\widehat{P}_{m^{\prime}}\psi\right|\leq\frac{c}{\log
n}.$

For any $\delta>0$, we can choose $n_{1}$ large enough so that $\frac{c}{\log
n}<\delta/2$ and $n_{1}\geq n_{0}$. Now, for $m,m^{\prime}\geq n_{1}$,
assuming $m\leq m^{\prime}$, there exists $k_{0}$ such that
$m^{\prime}\in\\{m^{2^{k_{0}}},\cdots,m^{2^{k_{0}+1}}\\}$. Thus,

(6.37)
$\begin{split}\left|\widehat{P}_{m}\psi-\widehat{P}_{m^{\prime}}\psi\right|&\leq\sum_{j=0}^{k_{0}-1}\left|\widehat{P}_{m^{2^{j}}}\psi-\widehat{P}_{m^{2^{j+1}}}\psi\right|+\left|\widehat{P}_{m^{2^{k_{0}}}}\psi-\widehat{P}_{m^{\prime}}\psi\right|\\\
&\leq\sum_{j=0}^{k_{0}}\frac{c}{({2^{j}\log m})}\leq\frac{2c}{\log
m}\leq\frac{2c}{\log n_{1}}<\delta\,.\end{split}$

Now we are able to prove Lemma 6.2.

###### Proof of Lemma 6.2.

We prove first that the sequence $\\{\widehat{P}_{n}\psi\\}_{n\in\mathbb{N}}$
started from any finite initial condition always converges to the same limit.
Finally, we prove that this limit must be a constant.

Consider two independent BGRW processes $(T_{t},X_{t})_{t\in\mathbb{N}}$ and
$(T^{\prime}_{t},X^{\prime}_{t})_{t\in\mathbb{N}}$ starting from two finite
initial conditions $(T_{0},x_{0})$ and $(T^{\prime}_{0},x_{0}^{\prime})$
respectively. Let $\\{\widehat{P}_{n}\psi\\}_{n\in\mathbb{N}}$ and
$\\{\widehat{P}^{\prime}_{n}\psi\\}_{n\in\mathbb{N}}$ be the averages
associated to each process. The proof follows from (6.35) and triangle
inequality, which combined give us that

(6.38)
$\begin{split}{\mathbb{P}}\left(\left|\widehat{P}_{n}\psi-\widehat{P}_{n}^{\prime}\psi\right|\geq\frac{c}{\log
n}\right)\leq\frac{4}{n^{8}}.\end{split}$

for some positive constant $c$ depending on $p$, $T_{0}$ and $T_{0}^{\prime}$
only. Then, an application of Borel-Cantelli Lemma allows us to conclude that
both processes converge to the same limit $\mathcal{M}_{p}\psi$. Once we have
that, we finally observe that since the BGRW processes are independent, the
events $\\{\mathcal{M}_{p}\psi\in A\\}$ and $\\{\mathcal{M}_{p}\psi\in B\\}$
are independents for all Borel sets on the real line. This implies that
$\mathcal{M}_{p}\psi$ is independent of itself, thus, constant almost surely.

##  7\. Weak convergence of empirical measures

In this section we prove Theorem 1.2 and Theorem 1.3 in the Introduction. In
fact, we prove slightly stronger statements that only require the initial
measure to be $p$-escapable, which in particular applies to all initial
measures supported on finite trees (cf. Lemma 6.3). Specifically, we will show
that, for any $p$-escapable initial measure $\mu$, there exits a measure
$P_{p}$ on the space $\mathcal{T}_{*}$ such that, when $n\to+\infty$,

$\displaystyle\widehat{P}_{n}$
$\displaystyle:=\frac{1}{n+1}\sum_{t=0}^{n}\delta_{[T_{t},X_{t}]}\Rightarrow
P_{p}\,\quad\mbox{ ${\mathbb{P}}_{\mu,p}$-a.s.}$ $\displaystyle P_{n}$
$\displaystyle:=\frac{1}{n+1}\sum_{t=0}^{n}\,\mu K_{p}^{t}\Rightarrow P_{p}\,$

where $K_{p}$ denotes the Markov transition kernel of the BGRW process over
$\mathcal{T}_{*}$.

In our proof we use the next proposition, which gives a convenient criterion
for checking weak convergence of distributions over $\mathcal{T}_{*}$. Before
stating the proposition we need to define a specific kind of local function.
Given $r\in\mathbb{N}$ and $[T,o]\in\mathcal{T}_{*}$, let $D_{r}([T,o])$
denote the largest degree of a vertex in $T$ at distance $r$ from $o$:

$D_{r}(T,o):=\max\\{d_{T}(x)\,:\,x\in V(T),\,{\rm dist}_{T}(x,o)\leq r\\}.$

One can check that $D_{r}:\mathcal{T}_{*}\to\mathbb{R}$ is $(r+1)$-local.

######  Proposition 7.1 (Proof in Appendix B.2).

Suppose $\\{Q_{n}\\}_{n\in\mathbb{N}}$ is a sequence of probability measures
over $\mathcal{T}_{*}$. Then:

  1. (1)

Tightness: If
$\lim_{k\to+\infty}\limsup_{n\in\mathbb{N}}Q_{n}(\\{[T,o]\in\mathcal{T}_{*}\,:\,D_{r}(T,o)\geq
k\\})=0$ for any $r\geq 0$, then $\\{Q_{n}\\}_{n\in\mathbb{N}}$ is tight.

  2. (2)

Weak convergence: Assume $\\{Q_{n}\\}_{n\in\mathbb{N}}$ satisfies item (1).
Then there exists a countable family $\mathcal{S}$ of bounded local functions
such that, if $\lim_{n}Q_{n}f$ exists for all $f\in\mathcal{S}$, then
$Q_{n}\Rightarrow Q$ for some $Q$ that is uniquely defined by:

$Qf=\lim_{n}Q_{n}f,\,f\in\mathcal{S}.$

We begin with addressing tightness for $\\{P_{n}\\}_{n\in\mathbb{N}}$. The
next Lemma shows Cèsaro-mean-type sequences of measures generated by our
Markov chain are tight when the initial measure satisfy the quantitative
criterion of $p$-escapability defined in Lemma 6.3.

######  Lemma 7.1.

Assume $\mu$ is a measure over $\mathcal{T}_{*}$ with the following property:
there exist $C,\alpha,D>0$ such that for all $n,k\geq 1$:

(7.2) $\sum_{t=0}^{n}{\mathbb{P}}_{\mu,p}(d_{T_{t}}(X_{t})\geq k)\leq
C\,(n+D)\,e^{-\alpha\,k}.$

Then the sequence

$P_{n}:=\frac{1}{n+1}\sum_{t=0}^{n}\mu K_{p}^{t}$

satisfies the tightness criterion in Proposition 7.1. In fact, the following
quantitative estimate is satisfied: for all $r,k\geq 1,n\in\mathbb{N}$:

$P_{n}(\\{[G,o]\in\mathcal{T}_{*}\,:\,D_{r}(G,o)\geq k\\})\leq
C\,\frac{(n+D+r)}{n+1}\,\left(\frac{(k+1)^{r+1}-1}{k}\right)\,e^{-\alpha\,k}.$

###### Proof.

Note that:

$(n+1)P_{n}(\\{[G,o]\in\mathcal{T}_{*}\,:\,D_{r}(G,o)\geq
k\\})=\sum_{t=0}^{n}{\mathbb{P}}_{\mu,p}(D_{r}([T_{t},X_{t}])\geq k).$

So it suffices to prove the following quantitative estimate: for all
$r,n,k\geq 1$,

(7.3) $\mbox{\bf Goal:
}\sum_{t=0}^{n}{\mathbb{P}}_{\mu,p}(D_{r}(T_{t},X_{t})\geq k)\leq
C\,(n+D+r)\,\left(\frac{(k+1)^{r+1}-1}{k}\right)\,e^{-\alpha\,k},$

which is true for $r=0$ by our assumption (7.2).

Consider $r>0$ and assume that we have proven that, for each $j\leq r-1$,
there exists $C_{j}>0$ depending only on $j$ and $p$, and an exponent $\alpha$
as in the base case, such that

$\mbox{\bf(induction hyp.) }\forall
m\in\mathbb{N}\,:\,\sum_{t=0}^{m}\,{\mathbb{P}}_{\mu,p}(D_{j}(T_{t},X_{t})\geq
k)\leq C_{j}\,(m+D+j)\,e^{-\alpha\,k},$

for all $k\geq 1$ (again, this is true for $j=0$ with $C_{0}=C$). We claim
that a similar statement holds for $j=r$ with $C_{r}=C_{0}+kC_{r-1}$. A simple
induction would then imply our goal:

$C_{r}=C_{0}\,\sum_{i=0}^{r}(k+1)^{i}=\frac{(k+1)^{r+1}-1}{k}\,C.$

To obtain our bound, note that

$\displaystyle\sum_{t=0}^{n}\,{\mathbb{P}}_{\mu,p}(D_{r}(T_{t},X_{t})\geq k)$
$\displaystyle\leq$
$\displaystyle\sum_{t=0}^{n}\,{\mathbb{P}}_{\mu,p}(d_{T_{t}}(X_{t})\geq k)$
$\displaystyle+\sum_{t=0}^{n}\,{\mathbb{P}}_{\mu,p}(D_{r}(T_{t},X_{t})\geq
k,d_{T_{t}}(X_{t})\leq k).$

The first term in the RHS is $\leq C_{0}\,(n+D)\,e^{-\alpha\,k}$ by the base
case. For the second term, we observe that $D_{r}(T_{t},X_{t})\geq k$ – i.e.
some vertex at distance $r$ from $X_{t}$ has degree $\geq k$ – means
$D_{r-1}(T_{t},v)\geq k$ for one of the neighbors of $X_{t}$ in $T_{t}$. Now,
if $d_{T_{t}}(X_{t})\leq k$, there is a chance of at least $1/(k+1)$ that
$X_{t+1}=v$ and thus $D_{r-1}(T_{t+1},X_{t+1})\geq k$. We conclude:

$\frac{{\mathbb{P}}_{\mu,p}(D_{r}(T_{t},X_{t})\geq k,d_{T_{t}}(X_{t})\leq
k)}{k+1}\leq{\mathbb{P}}_{\mu,p}(D_{r-1}(T_{t+1},X_{t+1})\geq k).$

So:

$\displaystyle\sum_{t=0}^{n}\,{\mathbb{P}}_{\mu,p}(D_{r}(T_{t},X_{t})\geq k)$
$\displaystyle\leq$ $\displaystyle C_{0}\,(n+D)\,e^{-\alpha\,k}$
$\displaystyle+(k+1)\,\sum_{t=0}^{n}\,{\mathbb{P}}_{\mu,p}(D_{r-1}(T_{t+1},X_{t+1})\geq
k)$ (induction hyp. for $j=r-1,m=n+1$) $\displaystyle\leq$ $\displaystyle
C_{0}\,(n+D)\,e^{-\alpha\,k}$ $\displaystyle+(k+1)C_{r-1}\,(n+r+D)\,e^{-\alpha
k}$ $\displaystyle\leq$ $\displaystyle C_{r}\,(n+r+D)\,e^{-\alpha\,k},$

where $C_{r}:=C+(k+1)\,C_{r-1}$ as desired.

In the next result – a strengthening of Theorem 1.2 –, we prove convergence of
empirical measures $\widehat{P}_{n}$ and Cesàro-style convergence of the chain
$K_{p}$ from any initial measure that is $p$-escapable. We also characterize
the limiting probability measure of the chain as a stationary distribution for
$K_{p}$.

######  Theorem 7.1 (Convergence of the empirical measure; proof in §7.1).

Given $p\in(0,1]$, there exists a probability measure $P_{p}$ on the space
$\mathcal{T}_{*}$ of rooted trees such that, for any $p$-escapable initial
measure $\mu$,

$\widehat{P}_{n}\Rightarrow P_{p}\;\mbox{ ${\mathbb{P}}_{\mu,p}$-a.s. \quad
and \quad}\frac{1}{n+1}\sum_{t=0}^{n}\,\mu K_{p}^{t}\Rightarrow P_{p}\;\mbox{
when $n\to+\infty$}.$

For $0<p_{0}\leq p\leq 1$, the measure $P_{p}$ satisfies:

(7.4) $\forall k,r\geq 1\,:\,P_{p}(\\{[T,o]\in\mathcal{T}\,:\,D_{r}([T,o])\geq
k\\})\leq C\,\frac{(k+1)^{r+1}-1}{k}\,e^{\alpha\,(2-k)}$

where $C,\alpha>0$ only depend on $p_{0}$. Moreover, $P_{p}$ is an invariant
measure for $K_{p}$.

Note that the measure $P_{p}$ itself is $p$-escapable, by Lemma 6.3 combined
with (7.4). That is, $P_{p}$ is the unique $p$-escapable invariant measure for
$K_{p}$. On the other hand, the hard tree in Example 6.1 shows that one does
not have convergence to $P_{p}$ from all initial measures.

Our next result extends Theorem 1.3 from the introduction.

######  Theorem 7.2 (Support of $P_{p}$; §7.2).

Given $0<p\leq 1$, let $P_{p}$ be the limit measure in Theorem 7.1. Then
$P_{p}$ is supported on one-ended infinite trees. Moreover, given a finite
rooted tree $(S_{0},x_{0})$ of diameter $\leq h$,

$P_{p}(\\{[T,o]\in\mathcal{T}_{*}\,:\,[T,o]_{h}=[S_{0},x_{0}])\\})>0.$

In particular, this shows that, if $\mu$ is such that
$\widehat{P}_{n}\Rightarrow P_{p}$ ${\mathbb{P}}_{\mu,p}$-a.s., then
${\mathbb{P}}_{\mu,p}(\tau_{\ell}<+\infty)=1$ i.e. $\mu$ is $p$-escapable. In
this sense, $p$-escapability is a necessary condition in Theorem 7.1.

###  7.1. Weak convergence of empirical measures: proof of Theorem 7.1

We present here the proof of convergence to the stationary measure.

###### Proof of Theorem 7.1.

Fix $\mu$ and $p$. Theorem 6.1 guarantees that

(7.5) ${\mathbb{P}}_{\mu,p}(\widehat{P}_{n}\psi\to\mathcal{M}_{p}\psi)=1$

for all bounded local functions, where $\mathcal{M}_{p}\psi$ does not depend
on $\mu$. If we write:

$P_{n}:=\frac{1}{n+1}\sum_{t=0}^{n}\,\mu K_{p}^{t},$

we also have

(7.6)
$P_{n}\psi={\mathbb{E}}_{\mu,p}[\widehat{P}_{n}\psi]\to\mathcal{M}_{p}\psi$

by the Bounded Convergence Theorem.

We claim that the sequences $\\{P_{n}\\}_{n}$ and $\\{\widehat{P}_{n}\\}_{n}$
are tight (almost surely, in the second case). More specifically, we will
apply the criterion in Proposition 7.1, part $(1)$. In fact, fixing
$k,r\in\mathbb{N}$, we may take

$\phi_{k,r}(T,x):=\mathbb{1}_{\\{D_{r}(T,x)\geq
k\\}}\,\,([T,x]\in\mathcal{T}_{*})$

which is a $(r+1)$-local function, so that

$P_{n}\phi_{k,r}\to\mathcal{M}_{p}\phi_{k,r},\;\text{ and
}\;\widehat{P}_{n}\phi_{k,r}\to\mathcal{M}_{p}\phi_{k,r}\,\;\;\mbox{
${\mathbb{P}}_{\mu,p}$-a.s.}$

Now, to evaluate the limit in the RHS, we replace the initial measure $\mu$
with a measure $\mu_{0}$ supported on a finite tree with two vertices.
Applying Lemma 7.1 in conjunction with Lemma 5.3, and letting $n\to+\infty$,
we obtain:

$\mathcal{M}_{p}\phi_{k,r}\leq
C\left(\frac{(k+1)^{r+1}-1}{k}\right)\,e^{\alpha\,(2-k)}.$

Since the RHS of this inequality goes to $0$ as $k\to+\infty$, we obtain the
required tightness.

We now prove that the weak convergence criterion of Proposition 7.1 (part
$(2)$) is also satisfied, which asks for the convergence of expectations of
all bounded local functions. For $P_{n}$ this is immediate from (7.6). For
$\widehat{P}_{n}$ there is the slight issue that we have:

$\forall\mbox{ bounded local
}\psi\,:\,{\mathbb{P}}_{\mu,p}(\widehat{P}_{n}\psi\to\mathcal{M}_{p}(\psi))=1$

and we now need to “move the quantifier $\forall$ inside the probability”.
However, Proposition 7.1 shows that we only need to worry about a countable
family of $\psi$, and there is no problem in moving the quantifier inside for
a countable family.

The upshot is that, assuming this claim, we have that Proposition 7.1 assures
that $P_{n}$ and $\widehat{P}_{n}$ converge weakly (almost surely, in the
second case) to the same probability measure $P_{p}$, which is uniquely
characterized by the fact that $P_{p}\psi=\mathcal{M}_{p}\psi$. In particular,
this measure satisfies the property that:

$\forall r,k\geq 1\,:\,P_{p}(\\{[T,o]\,:\,D_{r}(T,o)\geq k)\leq
C\left(\frac{(k+1)^{r+1}-1}{k}\right)\,e^{\alpha\,(2-k)}.$

Finally, we show that $P_{p}$ is an invariant measure for $K_{p}$. To this
aim, we need the following fact assuring that if $\psi$ is bounded Lipschitz,
so is $K_{p}(\psi)$.

######  Fact 7.1.

Given a bounded measurable function $\psi:\mathcal{T}_{*}\to\mathbb{R}$, let

$K_{p}(\psi)([T,o]):=\int_{\mathcal{T}_{*}}\,\psi([T^{\prime},o^{\prime}])\,K_{p}([T,o],{\rm
d}[T^{\prime},o^{\prime}]).$

If $\psi$ is bounded and Lipschitz, so is $K_{p}(\psi)$.

###### Proof sketch.

This follows from the fact that, if $[T,o]$ and $[S,v]$ satisfy
$\rho([T,o],[S,v])\leq 1/(1+r)$ for some $r>0$, one can couple
$[T^{\prime},o^{\prime}]\sim K([T,o],\cdot)$ and $[S^{\prime},v^{\prime}]\sim
K([S,v],\cdot)$ so that
$\rho([T^{\prime},o^{\prime}],[S^{\prime},v^{\prime}])\leq 1/r$.

So we may apply $P_{p}$ to the function $K_{p}(\psi)$ and obtain:

$P_{p}K_{p}(\psi)=\lim_{n\to+\infty}P_{n}K_{p}(\psi)=\lim_{n\to+\infty}\frac{1}{n+1}\sum_{t=0}^{n}\mu
K_{p}^{t+1}(\psi)=\lim_{n\to+\infty}\frac{1}{n+1}\sum_{t=1}^{n+1}\mu
K_{p}^{t}(\psi)=P_{p}(\psi).$

Since $\psi$ is an arbitrary bounded Lipschitz function, this implies
$P_{p}K_{p}=P_{p}$. So $P_{p}$ is a stationary measure for the chain $K_{p}$.

###  7.2. On the support of the limiting distribution: proof of Theorem 7.2

###### Proof of Theorem 7.2.

That $P_{p}$ is supported on infinite trees is immediate. We prove next the
final statement in the theorem, namely:

$P_{p}(\\{[T,o]\in\mathcal{T}_{*}\,:\,[T,o]_{h}=[S,x_{0}])\\})>0.$

To see this, recall that $(S,x_{0})$ has height $h$. Let $x_{1}$ be a leaf
node of $S$ at distance $h$ from $x_{0}$. One may traverse the tree $S$ by
first walking $h$ steps from $x_{1}$ to $x_{0}$ and then doing a depth-first
search on $S$ from $x_{0}$, which will end back at $x_{0}$.

This traversal gives us a recipe for “creating” $S$ inside $T_{t_{0}}$, for a
certain $t_{0}$. Namely, all we need is that:

  1. (1)

The walk creates leaves and jumps to them for $h$ consecutive steps (this
corresponds to moving from $x_{1}$ to $x_{0}$

  2. (2)

The walk then follows the sequence of steps given by the DFS in $S$, adding
leaves as needed.

The above sequence of steps has positive probability and, if followed, ensures
$[T_{t_{0}},X_{t_{0}}]_{h}=[S,x_{0}]$. By stationarity of the process

$P_{p}(\\{[T,o]\in\mathcal{T}_{*}\,:\,[T,o]_{h}=[S,x_{0}])\\})={\mathbb{P}}_{P_{p},p}([T_{t_{0}},X_{t_{0}}]_{h}=[S,x_{0}])>0.$

We now prove one-endedness. Denote by $O(s)$ the set of all rooted trees
$[T,o]$ that satisfy the following two properties:

  1. (1)

$T$ is infinite (but locally finite, as all other trees in $\mathcal{T}_{*}$);

  2. (2)

there exists a $h\geq s$ such that all paths of length $\geq h$ starting from
$o$ pass through a single vertex at distance $s$ from $o$.

One may check that the set of one-ended trees is precisely
$\cap_{s\in\mathbb{N}}O(s)$. Therefore, it is enough to show that
$P_{p}(O(s))=1$ for all $s\in\mathbb{N}$.

So fix $s\in\mathbb{N}$ and take a trajectory $[T_{t},X_{t}]$ of BGRW started
from $P_{p}$. Since $P_{p}$ is stationary,

$\forall n\in\mathbb{N}\,:\,{\mathbb{P}}_{P_{p},p}([T_{n},X_{n}]\in
O(s))=P_{p}(O(s)).$

We will show that, for all $\varepsilon>0$, one can choose $n\in\mathbb{N}$ so
that the LHS above is $\geq 1-\varepsilon$, which suffices to finish the
proof.

Recall that $P_{p}$ is $p$-escapable, as we commented after the statement of
Theorem 7.1. This means that $\tau_{\ell}<+\infty$ almost surely for all
$\ell\in\mathbb{N}$. Take $\ell\geq s$. We will follow the reasoning in the
proof Lemma 6.1 – more specifically the Claim at the end of the proof – and
argue as follows. Let $X_{\tau_{\ell}}=v_{0},v_{1},\dots,v_{\ell}$ is the
(induced) path of length $\ell$ around $X_{\tau_{\ell}}$ at time
$\tau_{\ell}$. Define

$\tau^{\prime}_{\ell,s}:=\inf\\{t\geq 0\,:\,X_{\tau_{\ell}+t}=v_{\ell-s}\\}.$

Notice that if $\tau_{\ell}\leq n<\tau_{\ell}+\tau^{\prime}_{\ell,s}$, then
$[T_{n},X_{n}]\in O(s)$ almost surely. Indeed, $\tau_{\ell}\leq
n<\tau_{\ell}+\tau^{\prime}_{\ell,s}$ has the following consequences:

  1. (1)

$X_{n}$ and $v_{\ell}$ lie on “opposite sides” of $v_{\ell-s}$, so ${\rm
dist}_{T_{n}}(X_{n},v_{\ell})\geq{\rm dist}_{T_{n}}(v_{\ell-s},v_{\ell})=s$.

  2. (2)

The subtree consisting of $v_{\ell-s}$ and all nodes on the same side as
$X_{n}$ is finite, as it consists of $v_{i}$ for $0\leq i\leq\ell-s$ plus the
new nodes added between times $\tau_{\ell}$ and $n$.

  3. (3)

The subtree consisting of $v_{\ell-s}$ and all nodes on the same side as
$v_{\ell}$ is a.s. infinite, as it contains the tree $T_{0}$ at time $0$.

Combining these properties, we see that all long enough paths in $T_{n}$ that
start from $X_{n}$ must pass through $v_{\ell}$, which lies at distance $\geq
s$ from $X_{n}$. This implies $[T_{n},X_{n}]\in O(s)$, since these same paths
must pass through the unique vertex at distance $s$ from $X_{n}$ that lies on
the path from $X_{n}$ to $v_{\ell}$. We have thus shown that if
$\tau_{\ell}\leq n<\tau_{\ell}+\tau^{\prime}_{\ell,s}$, then $[T_{n},X_{n}]\in
O(s)$, as claimed.

We deduce:

${\mathbb{P}}_{P_{p},p}([T_{n},X_{n}]\in
O(s))\geq{\mathbb{P}}_{P_{p},p}(\tau_{\ell}\leq
n<\tau_{\ell}+\tau^{\prime}_{\ell,s}).$

Since

${\mathbb{P}}_{P_{p},p}(\tau_{\ell}\leq
n<\tau_{\ell}+\tau^{\prime}_{\ell,s})\geq
1-{\mathbb{P}}_{P_{p},p}(\tau_{\ell}>n)-{\mathbb{P}}_{P_{p},p}(\tau^{\prime}_{\ell,s}<+\infty),$

we may observe as in the proof of Lemma 6.1 that

${\mathbb{P}}_{P_{p},p}(\tau^{\prime}_{\ell,s}<+\infty)\leq
Ce^{-\beta\,(\ell-s)}\leq\frac{\varepsilon}{2}$

if $\ell$ is large enough. Since $P_{p}$ is $p$-escapable, we may ensure that
${\mathbb{P}}_{P_{p},p}(\tau_{\ell}>n)\leq\frac{\epsilon}{2}$ by taking $n$
large enough (in terms of $\ell$). So for some choice of $\ell,n$ we obtain
the desired inequality:

${\mathbb{P}}_{P_{p},p}(\tau_{\ell}\leq
n<\tau_{\ell}+\tau^{\prime}_{\ell,s})\geq 1-\varepsilon.$

##  8\. Final comments

Our analysis leaves open many problems about the BGRW process and its
variants. We briefly discuss five of these.

######  Problem 8.1.

Is the speed $c(p)$ given by Theorem 1.1 a monotone function of $p$?

It is possible to show using our techniques that $p\mapsto c(p)$ is
continuous. Monotonicity is much less clear, though our (limited) simulations
suggest it should hold.

######  Problem 8.2.

Give bounds on $c(p)$ as a function of $p$.

For small $p$, one can extract from our proof a lower bound of the form
$c(p)\geq\exp(-Cp^{-C})$ for some universal $C>0$. The best upper bound we
know is $c(p)\leq p$, which comes from noting that, if $T_{0}$ is finite, then
$T_{n}$ has $(1+o(1))\,pn$ vertices a.s..

######  Problem 8.3.

Prove more properties of the random measure $P_{p}$.

All we know about this measure is what is contained in Theorem 7.2.

######  Problem 8.4.

Consider a model where $p=p_{n}$ decreases with $n$, and find a threshold
function for transience.

That is, how fast can $p_{n}$ decay while maintaining transience? Clearly, our
arguments break down in this regime.

######  Problem 8.5.

Consider models with cycles.

A “cheap” way to create cycles would be to connect the current vertex to some
uniformly random vertex at distance $K$, with $K$ a random variable. If $K$
has light tails, it should still be possible to use the local topology to
study the structure of our model.

Acknowledgement. We thank Remco van der Hofstad for suggesting the one-
endedness statement in Theorems 1.3 and 7.2.

##  Appendix A A simple lemma on dependent indicators

We prove here Lemma 3.2.

###### Proof of Lemma 3.2.

For $r=1,\dots,\lfloor m/k\rfloor$ define blocks events

$F_{r}:=\\{\forall j=(r-1)\,k+1,(r-1)\,k+2\,\dots,rk\,:\,I_{j}=1\\}.$

Note that $k$ consecutive indices $j$ appear in each $F_{r}$, so:

${\mathbb{P}}\left(\mbox{ at least $k$ consecutive $1$'s in the sequence
$(I_{j})_{j=1}^{m}$}\right)\geq{\mathbb{P}}\left(\bigcup_{r=1}^{\lfloor
m/k\rfloor}F_{r}\right).$

Moreover, the values of indices $j$ involved in events $F_{r},F_{r^{\prime}}$
are disjoint for $r\neq r^{\prime}$. With this in mind one may easily show
(via our assumptions) that ${\mathbb{P}}(F_{1})\geq\mu^{k}$ and
${\mathbb{P}}(F_{r}\mid F_{1}^{c}\cap\dots F_{r-1}^{c})\geq\mu^{k}$.

$1-{\mathbb{P}}\left(\bigcup_{r=1}^{\lfloor
m/k\rfloor}F_{r}\right)={\mathbb{P}}\left(\bigcap_{r=1}^{\lfloor
m/k\rfloor}F_{r}^{c}\right)\leq(1-\mu^{k})^{\lfloor m/k\rfloor}.$

##  Appendix B Some facts on weak convergence and the local topology

###  B.1. General facts

In this section, $(M,d)$ is a Polish metric space and ${\rm Prob}(M,d)$ is the
set of all probability measures over the Borel $\sigma$-field over $M$. We
need criteria to ascertain the weak convergence of a sequence
$\\{P_{n}\\}_{n\in\mathbb{N}}\subset{\rm Prob}(M,d)$.

####  B.1.1. Criterion for tightness

######  Proposition B.1.

Suppose we are given a doubly-indexed family

$F^{(r)}_{k}\,:\,r\in\mathbb{N},\,k\in\mathbb{N}$

of closed subsets of $M$ with the following two properties.

  1. (1)

For each $r\in\mathbb{N}$, the sets $F_{k}^{(r)}$ are increasing and satisfy

$F_{k}^{(r)}\nearrow M\mbox{ as }k\to+\infty.$

  2. (2)

For all choices of $k_{1},k_{2},k_{3},\dots\in\mathbb{N}$, the set

$K(\\{k_{r}\\}_{r=1}^{+\infty}):=\bigcap_{r=1}^{+\infty}\,F_{k_{r}}^{(r)}$

is compact.

Assume $\\{P_{n}\\}_{n\in\mathbb{N}}\subset{\rm Prob}(M,d)$ is such that

$\forall
r\in\mathbb{N}\,:\,\lim_{k\to+\infty}\liminf_{n\in\mathbb{N}}P_{n}(F^{(r)}_{k})=1.$

Then $\\{P_{n}\\}_{n\in\mathbb{N}}$ is tight.

###### Proof.

Given $\epsilon>0$, we will argue that there exists a choice of sequence
$\\{k_{r}\\}_{r=1}^{+\infty}$ for which

$\mbox{\bf Goal: }\forall
n\in\mathbb{N}\,:\,P_{n}(K(\\{k_{r}\\}_{r=1}^{+\infty}))\geq 1-\varepsilon.$

Notice that, no matter what sequence we choose, we get:

$\forall
n\in\mathbb{N}\,:\,1-P_{n}(K(\\{k_{r}\\}_{r=1}^{+\infty}))=P_{n}\left(\bigcup_{r=1}^{+\infty}\,(F^{(r)}_{k_{r}})^{c}\right)\leq\sum_{r=1}^{+\infty}P_{n}((F^{(r)}_{k_{r}})^{c}).$

So it suffices to show that for each $r\in\mathbb{N}$ we can choose
$k_{r}\in\mathbb{N}$ with
$\sup_{n}P_{n}((K^{(r)}_{k_{r}})^{c})\leq\epsilon/2^{r}$.

To do this, fix some $r$. By our assumption that
$\lim_{k\to+\infty}\liminf_{n\in\mathbb{N}}P_{n}(F^{(r)}_{k})=1$, we can find
$k^{*}_{r}\in\mathbb{N}$, $n_{0}\in\mathbb{N}$ such that

$\forall n\geq n_{0}\,:\,P_{n}(F^{(r)}_{k^{*}_{r}})\geq 1-\epsilon/2^{r}.$

On the other hand, for $n<n_{0}$ we still have:

$P_{n}(F^{(r)}_{k})\nearrow 1\mbox{ as }k\to+\infty\mbox{ due to assumption
1}.$

Since there are only finitely many $n<n_{0}$, we can find $k^{**}_{r}$ such
that

$\forall n<n_{0}\,:\,P_{n}(F^{(r)}_{k^{**}_{r}})\geq
1-\frac{\epsilon}{2^{r}}.$

We may now choose $k_{r}:=\max\\{k^{*}_{r},k^{**}_{r}\\}$. Since the sets
$F^{(r)}_{k}$ are nested, we see at once that

$\forall n\in\mathbb{N}\,:\,P_{n}(F^{(r)}_{k_{r}})\geq
1-\frac{\epsilon}{2^{r}},$

which is the property we needed.

####  B.1.2. Criterion for convergence

######  Proposition B.2.

Assume $\\{P_{n}\\}_{n\in\mathbb{N}}$ is a tight sequence of probability
measures, with a sequence of compact sets $\\{K_{k}\\}_{k\in\mathbb{N}}$
attesting tightness in the sense that.

$\lim_{k}\\{\liminf_{n}P_{n}(K_{k})\\}=1.$

Then there exists a countable family $\mathcal{A}$ of bounded Lipschitz
functions from $M$ to $\mathbb{R}$, which depends only on
$\\{K_{k}\\}_{k\in\mathbb{N}}$, such that, if $\lim_{n}P_{n}f$ exists for all
$f\in\mathcal{A}$, then $P_{n}\Rightarrow P$ for some probability measure $P$.
In that case, $P$ is uniquely characterized by the fact that
$Pf=\lim_{n}P_{n}f$ for all $f\in\mathcal{A}$.

###### Proof.

It is known that a tight sequence $\\{P_{n}\\}_{n\in\mathbb{N}}$ converges
weakly if and only $\lim_{n}P_{n}f$ exists for each function in the set

$\mathcal{A}_{0}:=\\{f:M\to\mathbb{R}\,:\,\|f\|_{\infty}\leq 1\mbox{ and
}\|f\|_{\rm Lip}\leq 1\\}.$

In that case, $Pf$ is uniquely defined by the fact that $Pf=\lim_{n}P_{n}f$
for all $f\in\mathcal{A}_{0}$.

Now consider a positive rational $\epsilon>0$. The fact that
$\\{P_{n}\\}_{n\in\mathbb{N}}$ is tight implies that there exists a compact
set $K_{k}\subset M$, with $k=k(\epsilon)$, so that with
$P_{n}(K_{\epsilon})\geq 1-\epsilon$ for all large enough $n$. For each such
set, the functions $\mathcal{A}_{0}$ restricted to $K_{k(\epsilon)}$ form a
bounded equicontinuous family. Thus the Ascoli-Arzèla Theorem implies that
there exists a countable subset $A_{\epsilon}\subset\mathcal{A}_{0}$ with

(B.3) $\forall\delta>0\,\forall f\in\mathcal{A}_{0}\,\exists
f_{\epsilon,\delta}\in
A_{\epsilon}\,:\,\sup_{x\in{k(\epsilon)}}|f(x)-f_{\epsilon,\delta}(x)|\leq\delta.$

We claim

$\mathcal{A}:=\bigcup_{\epsilon\in\mathbb{Q}_{+}}A_{\epsilon}$

is the set we are looking for. For assume that $\lim_{n}P_{n}f$ exists for
each $f\in\mathcal{A}$. For each $f\in\mathcal{A}_{0}$, one can choose
$f_{\epsilon,\delta}\in\mathcal{A}$ as in (B.3) and obtain:

$|P_{n}(f-f_{\epsilon,\delta})|\leq|P_{n}\mathbb{1}_{K_{k(\epsilon)}}(f-f_{\epsilon,\delta})|+P_{n}(K_{k(\epsilon)}^{c})\leq\delta+\epsilon\mbox{
for large enough $n$}.$

With this, one can show that $\\{P_{n}f\\}_{n\in\mathbb{N}}$ is Cauchy.
Indeed,

$\limsup_{m,n\to+\infty}|(P_{n}-P_{m})\,f|\leq
2(\epsilon+\delta)+\limsup_{m,n\to+\infty}|(P_{n}-P_{m})\,f_{\epsilon,\delta}|=2(\epsilon+\delta)$

since we are assuming $\\{P_{n}f_{\epsilon,\delta}\\}_{n}$ is Cauchy. Letting
$\epsilon,\delta\to 0$, we obtain that $\\{P_{n}f\\}_{n}$ is Cauchy, as
desired. A similar reasoning shows that:

$\lim_{n}P_{n}f=\lim_{\epsilon,\delta\to 0}\lim_{n}P_{n}f_{\epsilon,\delta}$

exists for all $f\in\mathcal{A}_{0}$. So $P_{n}\Rightarrow P$. Passing to
limits, we obtain from the above estimates that

$|P(f-f_{\epsilon,\delta})|\leq\epsilon+\delta.$

In particular, $P$ is uniquely defined by the values of $Pf=\lim_{n}P_{n}f$
for $f\in\mathcal{A}_{0}$, which are uniquely specified by the numbers
$Pf=\lim_{n}P_{n}f$ for $f\in\mathcal{A}$.

###  B.2. Application to local topology over rooted graphs

The general theory of the previous section will now be applied to the space
$\mathcal{T}_{*}$ of rooted, locally finite trees.

###### Proof of Proposition 7.1.

We apply the criteria for tightness and convergence in Propositions B.1 and
B.2. For each $r,k\in\mathbb{N}$ the set:

$F^{(r)}_{k}:=\\{[T,o]\in\mathcal{T}_{*}\,:\,D_{r}([T,o])\leq k\\}$

is closed and $\cup_{k}F^{(r)}_{k}=\mathcal{T}_{*}$ for each fixed $r$. Lemma
3.5 in [4] implies that all sets of the form
$K(\\{k_{r}\\}_{r\in\mathbb{N}})=\cap_{r=1}^{+\infty}F^{(r)}_{k_{r}}$ are
compact. Moreover, Assumption $1$ implies that

$\forall r\in\mathbb{N}\,:\,\lim_{k}\liminf_{n}P_{n}(F^{(r)}_{k})=1.$

So $\\{P_{n}\\}_{n\in\mathbb{N}}$ is tight by virtue of Proposition B.1.

We now use Proposition B.2 to show convergence. That Proposition gives us a
countable family of functions such that if $P_{n}f$ converges for all
$f\in\mathcal{A}$, then $P_{n}$ converges. In the present setting, we need a
countable family of $r$-local functions. To do this, define for each
$n\in\mathbb{N}$ the projection map
$\Pi_{m}:\mathcal{T}_{*}\to\mathcal{T}_{*}$ that takes $[G,o]$ to the
$m$-neighborhood $[G,o]_{m}$. This map is a contraction of $\mathcal{T}_{*}$
and is therefore continuous, and moreover

$\forall[G,o]\in\mathcal{G}_{*}\,:\,d([G,o],\Pi_{m}([G,o]))=d([G,o],[G,o]_{m})\leq\frac{1}{m+1}.$

In particular, this implies that for any bounded Lipschitz
$f:\mathcal{T}_{*}\to\mathbb{R}$,

$\sup\\{|f([G,o])-f\circ\Pi_{m}([G,o])|\,:\,[G,o]\in K\\}\leq\frac{\|f\|_{\rm
Lip}}{m+1}.$

It transpires that one can replace the family $\mathcal{A}$ with

$\mathcal{S}:=\\{f\circ\Pi_{m}\,:\,f\in\mathcal{A},m\in\mathbb{N}\\},$

which is still countable, and obtain the desired result.

## References

  * [1] G. Amir, I. Benjamini, O. Gurel-Gurevich, and G. Kozma.  Random Walk in Changing Environment.  ArXiv e-prints, April 2015.
  * [2] Bernardo Amorim, Daniel R. Figueiredo, Giulio Iacobelli, and Giovanni Neglia.  Growing networks through random walks without restarts.  In Proc 7th Workshop on Complex Networks (CompleNet’16), pages 199–211, 2016.
  * [3] Luca Avena, Hakan Guldas, Remco van der Hofstad, and Frank den Hollander.  Mixing times of random walks on dynamic configuration models.  The Annals of Probability, 2017.  (to appear).
  * [4] Charles Bordenave.  Lecture notes on random graphs and probabilistic combinatorial optimization.  https://www.math.univ-toulouse.fr/$\sim$bordenave/coursRG.pdf, 2016.
  * [5] Chris Cannings and Jonathan Jordan.  Random walk attachment graphs.  Electronic Communications in Probability, 18:1–5, 2013.
  * [6] Andrea Collevecchio.  On the transience of processes defined on galton-watson trees.  The Annals of Probability, pages 870–878, 2006.
  * [7] Andrea Collevecchio, Mark Holmes, and Daniel Kious.  On the speed of once-reinforced biased random walk on trees.  arXiv preprint arXiv:1702.01982, 2017.
  * [8] Codina Cotar, Debleena Thacker, et al.  Edge-and vertex-reinforced random walks with super-linear reinforcement on infinite graphs.  The Annals of Probability, 45(4):2655–2706, 2017.
  * [9] Amir Dembo, Ruojun Huang, Ben Morris, and Yuval Peres.  Transience in growing subgraphs via evolving sets.  Ann. Inst. H. Poincaré Probab. Statist., 53(3):1164–1180, 08 2017\.
  * [10] Margherita Disertori, Christophe Sabot, and Pierre Tarrès.  Transience of edge-reinforced random walk.  Communications in Mathematical Physics, 339(1):121–148, 2015.