RIMS Kôkyûroku Bessatsu
B79 (2020), 163–177

Scaling limit of a biased random walk on a criticalbranching random walk
By

George Andriopoulos∗

Abstract
Relying on powerful resistance techniques developed in [8], the recent paper ‘Invarianceprinciples for random walks in random environment on trees’ [4] investigates random walks in
random environment on tree-like spaces and their scaling limits in a certain regime, that iswhen the potential of the random walk in random environment converges. We introduce andsummarise a result from [4]. We choose to review the example of a novel scaling continuum
limit of a biased random walk on large critical branching random walk. In this case the diﬀusionthat is not on natural scale is identified as a Brownian motion on a continuum random fractal
tree with its canonical metric replaced by a distorted resistance metric. This example allows
the least technical presentation (compared to the others covered in the main article). Moreover,
it is nevertheless of current interest, given its relation to critical percolation.

§ 1.

Introduction

We consider branching walk on a rooted ordered finite tree in which every edge
is marked by a real-valued vector (it is equivalent to have vectors assigned to vertices
instead). We associate with each vertex a trajectory of a killed walk defined by summing
all the values of the edges that belong to the unique path from the root to that particularvertex. Obviously, the walk is killed after as many steps as the number of the generationof the vertex evaluated at (see (2.1)). The multiset of trajectories of the killed walk is
Received February 28, 2019. Revised December 3, 2019.
2010 Mathematics Subject Classification(s): 60K37, 60F17 (Primary), 82D30 (Secondary).
Key Words: random walk in random environment, diﬀusion in random potential, biased random
walk, branching random walk, Galton-Watson tree, Sinai’s regime.
Supported by EPSRC as part of the MASDOC DTC at the University of Warwick. Grant No.
EP/HO23364/1.
∗ Institute of Mathematical Sciences at NYU Shanghai, China.
e-mail: ga73@nyu.edu
c 2020 Research Institute for Mathematical Sciences, Kyoto University. All rights reserved.
⃝

164

George Andriopoulos

called the branching walk. A branching random walk is constructed by choosing theshape of the tree and the marks at random.
Next, we consider a weakly biased random walk on branching random walk ϕnconditioned to have n particles, where the shape of the underlying tree Tn is generated
by a critical Galton-Watson process with exponential tails for the oﬀspring distribution,and the marks are independent, each distributed as a random variable Y in a way that
ensures that the multiset of trajectories of ϕn is a tree when regarded as an embedded
subgraph of Rd . Here, the name weakly we gave to the biased random walk is inheritedby the discrete scheme we provide that ‘flattens’ the cartesian bias to a single direction
appropriately at every step. We show that this weakly biased random walk on the
aforementioned model converges to a Brownian motion on a random Gaussian potential
on a continuum random fractal tree, which in not on natural scale. See Theorem 2.1
for a definitive statement. We should stress that diﬀusion processes on classes of real
trees that are not on natural scale have been alluded to before in the literature. In[10], the processes considered evolve by retreating back along an ancestral line or by
moving among lineages of branch points according to weights chosen by a possibly
infinite measure on the family of ancestral lines. The last example in [5, Example 3.8]
formalizes the notion of the potential of diﬀusions, which are not necessarily on naturalscale.
One model for which an appealing conjecture can be made is the incipient infinite
cluster (IIC) of high-dimensional Bernoulli-bond percolation (each edge is open withprobability p, and closed with probability 1 − p, independently of the states of otheredges) on Zd , that is when d > 6. Below, the measure is denoted by Pp . At criticality,
i.e. p = pc (d) ∈ (0, 1), it is partially confirmed that there is no infinite open cluster.
Instead, one could study random walks on the IIC:PIIC (·) := lim Ppc (·|0 ↔ ∂Λn ),n→∞where 0 ↔ ∂Λn if there exists a vertex of the boundary of Λn := [−n, n]d ∩ Zd connectedto the origin (see [12] for a construction).
It is expected that this model satisfies the same scaling properties as branchingrandom walk (see [11] for an up-to-date survey). In particular, in high dimensions, thescaling limit of the IIC is related to the integrated super-Brownian excursion (ISE) (see[3] for a definition). In comparison, the scaling limit of a large size-conditioned criticalbranching random walk, after rescaling space by n−1/4 , is the ISE (see (3.4) and [9] forthe construction of the Brownian motion on the latter object for d ≥ 8). The following
question was posed by Ben Arous and Fribergh in the notes [7]:‘What is the right scaling for a biased random walk on the IIC of Zd ?’One might anticipate that the scaling limit of a biased random walk with a weak carte-Scaling limit of a biased random walk on a critical branching random walk165

sian bias to a single direction on the IIC of Zd is a Brownian motion in a random
Gaussian potential on an unbounded version of the continuum random fractal tree,
where the latter objects appear in the definition of the limiting diﬀusion in Theorem
2.1. See also the recent conjecture of [8] regarding the associated simple random walks
on the IIC (when individual edges have unit resistance).
§ 2.

Biased random walk on the range of a branching random walkTo state our main result, we first need to formally define a biased random walkon the range of a critical branching random walk. For this, we will consider a critical
Galton-Watson tree, which is a branching process with i.i.d. oﬀspring that are copies
of a random variable ξ defined under a law P satisfying E(ξ) = 1. Given a random
realization of a Galton-Watson tree T , we can consider a simple random walk indexedby T , which means that we assign a spatial location ϕT (u) ∈ Rd for every u ∈ T . First,
the spatial location ϕT (ρ) of the root ρ is the origin of Rd . Then, each edge e ∈ E(T )gets assigned, in an i.i.d. manner, a random variable y(e) which is distributed according
to a mean 0 continuous random variable Y . The spatial location ϕT (u) of a vertex u is
the sum of the quantities y(e) over all edges contained to the simple path from the root
to u in the tree. In other words, given a value function y : E(T ) → Rd , we defined a
map ϕT : T → Rd by setting ϕT (ρ) := 0 and ϕT (⃗ρ) := 0 1 ,∑(2.1)
ϕT (u) :=y(e),u ∈ T \ {ρ},e∈Eρ,uwhere the sum is taken over the set of all edges belonging to the simple path between
ρ and u. Also, we interpolate linearly along the edges. The couple (T, ϕT ) is a random
spatial tree under a measure that we will still denote by P. This object will be called thecritical branching random walk. This spatial tree can be viewed as a random embeddingof T into Rd , by considering the graph G with vertices given by
V (G) := {x ∈ Rd : x = ϕT (u) with u ∈ T }and edge set
E(G) := {{x1 , x2 } ∈ E(Rd ) : xi = ϕT (ui ), i = 1, 2 with {u1 , u2 } ∈ E(T )}.
Remark. Obviously, since the increments (y(e))e∈E(T ) of the spatial element ϕT
are independent and identically distributed as a continuous random variable Y , the1 Throughout this note we use ⃗u to denote the father in the genealogy of a vertex u. In particular,when u = ρ, we add a new vertex b which we call the base and stick it only to the root by an edge⃗. This yields a planted tree T̄ . For notational simplicity, even if thewith unit weight, so that b = ρstatements hold with respect to T̄ , we still phrase them in terms of T .

166

George Andriopoulos

embedded subgraph G = (V (G), E(G)) is a tree. If each edge e ∈ E(T ) gets assigned
instead, in an i.i.d. fashion, a random variable x(e) which is distributed according to
the step distribution of a simple random walk in Zd , still induces a spatial tree that canbe similarly viewed as a subgraph of Zd , which is not necessarily a tree. To contrast
the former and the latter cases, one usually refers to the corresponding spatial trees ascritical non-lattice and lattice branching random walk respectively.
In this paper, we are interested in large critical branching random walk, which we
obtain from the previous construction by conditioning the vertex cardinality of T to
be n, i.e. by letting {(Tn , ϕn )}n≥1 be the family of random spatial trees, where Tn
is generated by a Galton-Watson process with critical oﬀspring distribution ξ defined
under the measure Pn := P(·| |T | = n), which is asymptotically well-defined under
the the inherent assumption that the distribution of ξ is aperiodic (meaning that is
not supported on a sub-lattice of Z). In this case, we denote the embedded subgraphassociated with the spatial tree (Tn , ϕn ) by Gn .
Now, fix a bias β ≥ 1, and to each edge {x1 , x2 } ∈ E(Gn ), assign a conductance
(1)

(1)

c({x1 , x2 }) := β max{ϕn (u1 ),ϕn (u2 )}

(2.2)
(1)

where ϕn (ui ) denotes the first coordinate of ϕn (ui ). Check that c({ϕn (ρ⃗n ), ϕn (ρn )}) =(1)(1)
β max{ϕn (ρ⃗n ),ϕn (ρn )} = 1, which agrees with putting a unit conductance between ρnand its base bn = ρ⃗n . The biased random walk on Gn is then the time-homogeneous
Markov chain X = ((Xn )n≥0 , PGxn , x ∈ V (Gn )) on V (Gn ) with transition probabilities
given byc({x1 , x2 }),
PGn (x1 , x2 ) :=c({x1 })∑
where c is a measure on V (Gn ) defined by c({x}) := e∈E(Gn ):x∈e c(e). It is simple
to check that c is the invariant measure for X as the detailed balance equations are
satisfied. Note that if β > 1, then the biased random walk X prefers to move towards
the direction of the first coordinate. Besides, if β = 1, there is no bias and the preceding
definition leads to the simple random walk on Gn . Finally, using the usual terminologynfor random walks in random environments, for x ∈ V (Gn ), we say that PGx is thequenched law of X started from x. Since ρn is an element of V (Gn ), we can also define
an annealed law Pρn for the biased random walk on Gn started from ρn by setting:∫(2.3)
Pρn := PGρnn (·)dP.
Under this law we can prove Theorem 2.1, which shows that, a weakly biased random
walk on the critical non-lattice branching random walk converges to a Brownian motion
in random Gaussian potential on Aldous’ continuum random tree (CRT).

Scaling limit of a biased random walk on a critical branching random walk

167

More formally, denote by e := (e(t))0≤t≤1 a normalized Brownian excursion. Informally, e is a Brownian motion started at the origin and conditioned to remain positive
over the time interval (0, 1), and to return back to 0 at time 1. By convention, lete(t) := 0 if t > 1. For every s, t ≥ 0, we setdT (s, t) := e(s) + e(t) − 2

inf

e(r).

r∈[s∧t,s∨t]

The random real tree coded by e (see [15] for more details)(2.4)

T := [0, ∞)/ ∼e ,where s ∼e t if and only if dT (s, t) = 0 (or equivalently if and only if e(s) = e(t) =inf r∈[s∧t,s∨t e(r)), is called Aldous’ continuum random tree and will be denoted by(T , dT ) when endowed with its canonical metric dT . Furthermore, the equivalence classof t with respect to the relation defined above will be denoted by pe (t). We may consider
an Rd -valued tree-indexed Gaussian process (ϕ(σ))σ∈T with
Eϕ(σ) = 0,
(2.5)

Cov(ϕ(σ), ϕ(σ ′ )) = dT (ρ, σ ∧ σ ′ )I,

where I is the d-dimensional identity matrix and σ ∧ σ ′ is the most recent common
ancestor of σ and σ ′ . For almost-every realization of T (w.r.t the normalized Itô excursion measure N1 ), this process has a continuous modification. Our main result is thefollowing.
Theorem 2.1.
Assume that E(ξ) = 1, σξ2 := Var(ξ) ∈ (0, ∞) and E(eλξ ) < ∞,for λ > 0 and that the distribution of ξ is aperiodic. The increments of the spatial
element ϕn , conditional on Tn , are assumed to be i.i.d. copies of a mean 0 continuous
random variable Y with finite variance Σ2Y < ∞ that furthermore satisfies the tailcondition
P(dE (0, Y ) ≥ y) = o(y −4 ).
nConsider the weakly biased random walk X n = (Xm)m≥1 on Tn with bias parameter−1/4nβ, for β > 1. There exists constant σT > 0 and a positive definite d × d-matrix Σϕsuch that the following convergence in law holds
)
(
(
)
,
n−1/4 ϕn (Xnn3/2 t )→ Σϕ ϕ(Xtσ−1 )
t≥0

T

t≥0

where X n is chosen under the annealed law Pρn and the limiting process (Xt )t≥0 is a
Brownian motion in a random Gaussian potential ϕ(1) on the CRT, where ϕ(1) is thefirst coordinate of the tree-indexed Gaussian process (ϕ(σ))σ∈T . The convergence isannealed and occurs in D(R+ , Rd ).

168

George Andriopoulos

Remark. As suggested by [13, Theorem 2], the fourth order polynomial decay ofthe step variable Y is necessary to obtain the convergence of a two-dimensional process(Ĉn (i), R̂n (i)). Here, Ĉn (i) is the distance to the root of the position of a particle thattraverses the outline of Tn from left to right at unit speed (notice that we visit every
vertex apart from the root a number of times given by its degree), and R̂n (i) := ϕn (ûni ),where ûni denotes the i-th visited vertex in exploration of Tn by the particle. It will
be convenient to define a somewhat shifted version of (Ĉn (i) : 0 ≤ i ≤ 2(n − 1))to correspond to the exploration of the outline of the planted tree T̄n : let Cn (0) =Cn (2n) = 0 and, for 0 ≤ i ≤ 2n − 1, Cn (i) := 1 + Ĉn (i − 1).
§ 3.

Biased random walk as a random walk in a random environment

The aim of this section is to describe how a biased random walk on a non-latticebranching random walk, which is essentially a biased random walk on a self-avoiding
path can be expressed as a random walk in a random envrironment on a tree. As wewill demonstrate, this will enable us to transfer results known for the latter model tothe particular model we study.
For u ∈ Tn , we denote its children by u1 , ..., uξ(u) and its parent by u0 . Let us
define the random walk in a random environment of interest to us in this section. Theξ(u)random environment ω will be represented by a random sequence {(ωuui )i=0 : u ∈ Tn }∑ξ(u)in (0, 1)ξ(u)+1 such that i=0 ωuui = 1, and will be built on the probability space withprobability measure P as well. The random walk in a random environment will be thetime-homogeneous Markov chain X ′ = ((Xn′ )n≥0 , Pωu , u ∈ Tn ) on Tn with transition
probabilities′{(Pω (Xn+1= ui |Xn′ = u))i=0 : u ∈ Tn } = {(ωuui )i=0 : u ∈ Tn }.
ξ(u)

ξ(u)

′
For u ∈ Tn , the law Pω
u is the quenched law of X started from u. Furthermore, we candefine an annealed law for X ′ similarly to (2.3). To connect this model with the biased
random walk on the critical non-lattice branching random walk conditioned to have nparticles, suppose that the transition probabilities are defined by setting
ξ(u)

ξ(u)

{(ωuui )i=0 : u ∈ Tn } := {(PGn (ϕn (u), ϕn (ui )))i=0 : u ∈ Tn }.
For this choice of random environment, it is immediate that the quenched law of ϕn (X ′ )is the same as that of X. A corresponding identity holds for the relevant annealed laws.
It is also important to connect the first coordinate of the random embedding ϕnwith the potential of the random walk in the random environment. To be more precice,let (∆n (u))u∈Tn be its increments process, i.e.
(1)∆n (u) := ϕ(1)u).
n (u) − ϕn (⃗Scaling limit of a biased random walk on a critical branching random walk

169

Then, if ρ⃗uu := ω⃗u⃗⃗u /ω⃗uu 2 , where ω is defined as in the previous paragraph, the potential(Vn (u))u∈Tn of the random walk in a random environment, is obtained by setting∑
if u ∈ Tn \ {ρn },e∈Eρn ,u log ρe ,(3.1)
Vn (u) :=0,
if u = ρn .
The elementary calculation involving the telescopic sum∑(3.2)
log ρe = − log β · max{ϕ(1)u), ϕ(1)n (⃗n (u)},e∈Eρn ,uyields that the potential satisfies(3.3)

Vn (u) = − log β(ϕ(1)u) + max{0, ∆n (u)}).
n (⃗
(1)

Therefore, if the individual increments are negligible, ϕn (multiplied by a negative
constant that depends on β) nearly gives the leading order of the potential of therandom walk in the random environment.
The potential is relevant when understanding the behaviour of the random walkin a random environment in Sinai’s regime. When ϕn rescales in such a way that it
incorporates a functional invariance principle on the first coordinate, we demonstrate(1)
through the connection between Vn and ϕn derived above, that the potential Vn converges to an embedding of the CRT into the Euclidean space, so that an arc of length
t in the CRT is mapped to the range of a Brownian motion run for time t. In otherwords, Vn converges to ϕ as defined in (2.5).
For trees that satisfy the assumptions in Theorem 2.1, [9, Corollary 10.3] ensures
the following convergence in law. If dTn gives the length of the shortest path between
elements of Tn and µTn is the empirical measure on Tn which puts mass n−1 on eachvertex, we have that
(
)
(3.4)
(Tn , n−1/2 dTn , µTn , ρn ), n−1/4 ϕn → ((T , σT dT , µT , ρ), Σϕ ϕ) ,where σT := 2/σξ and Σϕ := ΣY√

σT . Combining (3.3) with (3.4) yields(3.5) ((Tn , n−1/2 dTn , µTn , ρn ), n−1/4 ϕn , n−1/4 Vn ) → ((T , σT dT , µT , ρ), Σϕ ϕ, σβ,ϕ ϕ(1) ),in the spatial Gromov-Hausdorﬀ-vague topology, where ϕ(1) denotes the first coordinateof ϕ and σβ,ϕ = − log β · (Σϕ )11 .
In Theorem 2.1, on account of the ‘flattening’ that the bias has to undergo, we
referred to X n as the weakly biased random walk on Gn with bias parameter βn :=−1/4
βn, for some β > 1. Observing that n−1/4 Vn is the potential of the random walk
2 The fraction is well-defined for every node of T except the root ρ .
n
n

170

George Andriopoulos

in a random environment X ′ when β is replaced by βn , and in combination with (3.5),
indicates why we chose to change the bias at every step in that way. From now on, we
will solely work with this random walk in a random environment and keep referring to it
as such. One of the crucial facts for the random walk in a random environment is that,for fixed ω, the random walk is a reversible Markov chain and can therefore be described−1/4
Vn (u)as an electrical network. The conductances are given by c({⃗u, u}) = e−n(see(3.1), (3.2) and cf. (2.2)) and the stationary reversible measure which is unique up to
multiplication by constant is given pointwise in u by
∑

ξ(u)

(3.6)

νn ({u}) = e−n−1/4 Vn (u)

+

e−n

−1/4

Vn (ui ),

i=1

where the sum is taken over the set of all vertices contained in the neighborhood of u
excluding its parent. The reversibility means that, for all m ∈ N0 and u1 , u2 ∈ Tn , wehave that′′νn ({u1 })Pωu1 (Xm= u2 ) = νn ({u2 })Pωu2 (Xm= u1 ).
Let (c(e))e∈E(Tn ) be the collection of edge weights given by the conductances describedabove. The electrical resistance between u1 ̸= u2 is given byrn (u1 , u2 )−1 = inf{En (f, f ) : f (u1 ) = 0, f (u2 ) = 1},
where
En (f, g) =1∑c({x, y})(f (x) − f (y))(g(x) − g(y))
2 x∼yis a quadratic form on Tn . One can check that rn is a metric on Tn (e.g. [16] andcharacterises the weights and the quadratic form uniquely [14]). Moreover, since Tn is agraph tree, one has that rn is identical to the weighted shortest path metric, with edges
weighted according to (1/c(e))e∈E(Tn ) , i.e.
(3.7)

rn (u1 , u2 ) =

∑

en

−1/4

Vn (u),

u1 , u2 ∈ Tn ,u∈[u1 ,u2 ]]where for u1 , u2 in a rooted metric tree (T, r, ρ) by[[u1 , u2 ]] := {u ∈ T : r(u1 , u2 ) = r(u1 , u) + r(u, u2 )},[u1 , u2 ]] := [[u1 , u2 ]]\{u1 }, [u1 , u2 ] := [[u1 , u2 ]]\{u1 , u2 }, we denoted the path intervals.
In the rest of the paper we verify that (3.5) also holds when the shortest path
metric dTn and the empirical measure which puts mass n−1 on each of the vertices of
Tn are perturbed by exponential functionals of the potential of the random walk in arandom environment as can be seen by the form of the stationary reversible measureScaling limit of a biased random walk on a critical branching random walk171

νn and the electrical resistance rn in (3.6) and (3.7) respectively. Before stating thisresult, we need to introduce the notion of a length measure on separable rooted metricspaces (T, r, ρ). Denote the skeleton of T as Sk(T ) := ∪u∈T [ρ, u] ∪ Is(T ), where Is(T ) :={u1 , u2 ∈ T \ {ρ} : u1 ̸= u2 and [[u1 , u2 ]] = {u1 , u2 }} is the set of isolated points of T ,excluding ρ. Then, the length measure of T is the unique σ-finite measure λ, such thatλ(T \ Sk(T )) = 0 and for all u ∈ T ,(3.8)

λ([ρ, u]]) = r(ρ, u).

Since all the points in (Tn , rn , ρn ) are isolated, note that the length measure of Tn shifts
the length of an edge to the endpoint that is further away from ρn , and therefore it does
depend on ρn .
§ 4.

Convergence of the distorted metric measure trees

The convergence of the processes mentioned in Theorem 2.1 will essentially emanatefrom the convergence of the distorted metrics (3.7) and measures (3.6) that provide thescale functions and speed measures in this framework. Indeed, as an application of themain results in [6] and [8], this will lead to the convergence of the associated random
walks in random environment. We prove the former below and leave the latter as aconcluding remark to the article.
Theorem 4.1.

The following convergence in law holds((Tn , n−1/2 rn , (2n)−1 νn , ρn ), n−1/4 ϕn , n−1/4 Vn ) → ((T , σT rϕ(1) , νϕ(1) , ρ), Σϕ ϕ, σβ,ϕ ϕ(1) )in the spatial Gromov-Hausdorﬀ-vague topology, where
∫ u2
(1)
(4.1)
rϕ(1) (u1 , u2 ) :=eσβ,ϕ ϕ (v) dλ(v),u1and νϕ(1) is the image measure (pẽ )∗ ℓ by the canonical projection pẽ of the Lebesgue
measure ℓ on [0, 1], where(∫)
pe (t)

(4.2)

ẽ :=

e−σβ,ϕ ϕ

(1)

(v)

dλ(v)

pe (0).
0≤t≤1Remark. Note that ẽ is a random excursion, which means that ẽ ∈ C([0, 1], R+ )and ẽ(0) = ẽ(1) = 0. Thus, pẽ (t) is well-defined to represent the equivalence class of twith respect to the relations ∼ẽ t ⇐⇒ ẽ(s) = ẽ(t) =infr∈[s∧t,s∨t]ẽ(r).

172

George Andriopoulos

It is easy to check that rϕ(1) defines a metric on T . In addition, dT and rϕ(1) are
topologically equivalent and the metric space (T , σT rϕ(1) ) is also a compact real tree
coded by ẽ in the sense of (2.4).
Proof. Using Skorohod’s representation, we can assume that we are working ina probability space under which the exploration of the outline of Tn (for a definition,
see the remark that lies below the statement of Theorem 2.1), which is normalized by
setting:()(C(n) (t))0≤t≤1 := n−1/2 Cn (2nt) : 0 ≤ t ≤ 1 ,converges almost-surely (in the uniform norm) to a normalized Brownian excursion e.
The convergence in law
C(n) → σT e in C([0, 1], R+ )(4.3)

was originally shown by Aldous in [2]. We construct an appropriate correspondence
Rn := {(uni , pe (t)) : ∃t ∈ [0, 1] s.t. i = ⌊2nt⌋} ,where uni is the i-th visited vertex in the exploration of the outline of Tn and pe (t) isthe equivalence class of t with respect to the relation s ∼e t. The trees are defined as
projections from [0, 1] (with some additional equivalence structure), so taking pairs ofprojections from [0, 1] gives a natural correspondence.
The first part of the proof shows that the distortion of the natural correspondencedis(Rn ) := sup{|n−1/2 rn (uni , unj ) − rϕ(1) (pe (s), pe (t))| : (uni , pe (s)), (unj , pe (t)) ∈ Rn }converges to 0. Now, suppose that (uni , pe (s)) ∈ Rn . Thenn−1/2 rn (un0 , uni ) − rϕ(1) (pe (0), pe (s))

= n

∑

−1/2

e

n−1/4 Vn (v)

∫
−

(4.4)

n−1/4 Vn (v)

e

=
n
[un
0 ,ui ]]

(v)

dλ(v)

(1)

(v)

dλ(v) ,[[pe (0),pe (s)]]nv∈[un0 ,ui ]]∫

(1)eσβ,ϕ ϕ∫dλn (v) −eσβ,ϕ ϕ[[pe (0),pe (s)]]where λn is the length measure of the discrete rooted metric tree (Tn , n−1/2 dTn , un0 ).
The second equality follows from the fact that λn shifts the length of an edge to theendpoint that is further away from un0 , while also observing that λn ([unk , unk′ ]]) = n−1/2 ,for all unk ∼ unk′ .

Scaling limit of a biased random walk on a critical branching random walk173

Recall here that Cn := (Cn (i) : 0 ≤ i ≤ 2n) is a random excursion with length 2n.
For every i, j ≥ 0, setting
dCn (i, j) := Cn (i) + Cn (j) − 2infk∈[i∧j,i∨j]

Cn (k),

we identify i and j if and only if dCn (i, j) = 0 (or equivalently if and only if Cn (i) =Cn (j) = inf k∈[i∧j,i∨j] Cn (k)). In the terminology as well as in the notation of (2.4),
we have that Tn coincides with the tree coded by the function Cn . Furthermore, theequivalence class of i with respect to the relation defined above will be denoted bypCn (i). Note that the previous quantity represents uni . It is not diﬃcult to convince
oneself that∫∫
−1/4
Vn (unn−1/4 Vn (v)⌊2nr⌋ ) dλ(4.5)
edλn (v) =en(n) (r),n[un
0 ,ui ]]

As(n)where As(n) := {r ≤ s : inf u∈[r,s] C(n) (u) = C(n) (r)} and λ(n) := λn ◦ (pC(n) ). Similarly,∫∫(1)
σβ,ϕ ϕ(1) (v)(4.6)edλ(v) =
eσβ,ϕ ϕ (pe (r)) dλe (r),Ase[[pe (0),pe (s)]]where Ase := {r ≤ s : inf u∈[r,s] e(u) = e(r)} and λe := λ ◦ (pe ).
−1/4

n

(1)

Vn (u⌊2nr⌋ )Let us set gn (r) = enand g(r) = eσβ,ϕ ϕ(4.6) with (4.4), for (uni , pe (s)) ∈ Rn , we deduce

∫

∫

As(n)

gn (r)dλ(n) (r) −(pe (r)). Combining (4.5) and∫∫g(r)dλe (r) ≤

Ase

As(n)

gn (r)dλ(n) (r) −

∫
+

As(n)

∫
g(r)dλ(n) (r) −

∫
+

As(n)

g(r)dλ(n) (r)As(n)g(r)dλe (r)

∫

As(n)

g(r)dλe (r) −g(r)dλe (r) .
Ase

Hence
(4.7)

n

−1/2

∫
rn (un0 , uni ) − rϕ(1) (pe (0), pe (s))

≤

∫

As(n)

g(r)dλ(n) (r) −∫+||g||∞

g(r)dλe (r)As(n)|1As(n) (r) − 1Ase (r)|dλe (r)+||gn − g||∞ λ(n) (As(n) ).
There are several steps along the way to show that the right-hand side converges to 0
uniformly in s ∈ [0, 1]. First, by definition
(4.8)

n→∞

|λ(n) (As(n) ) − λe (Ase )| = |C(n) (s) − e(s)| −−−−→ 0,174

George Andriopoulos

uniformly in s ∈ [0, 1]. Now suppose that (uni , pe (s)), (unj , pe (t)) ∈ Rn with s ≤ t. In asecond place, it is not hard to see that
λ(n) ([s, t]) − λe ([s, t]) =(λ(n) (As(n) ) + λ(n) (As(n) ) − 2λ(n) (Ar(n) ))()− λe (Ase ) + λe (Ate ) − 2λe (Are ) ,(4.9)

if r is any time which achieves the minimum between s and t of C(n) and e, when thelatter processes are coupled in such a way that (4.3) holds almost-surely. Together with
(4.8), this shows that (4.9) converges to 0 uniformly in s, t ∈ [0, 1], and consequently
that λ(n) converges strongly to λe . This entails that the first term on the right-handside of the inequality in (4.7) converges to 0 uniformly in s ∈ [0, 1]. The same can besaid of the second term sincen→∞|1As(n) (r) − 1Ase (r)| −−−−→ 0,
uniformly in s ∈ [0, 1]. Its convergence simply follows by applying the dominatedconvergence theorem. Finally, the convergence to 0 of the third term on the right-handside of the inequality in (4.7) stems from a combination of (3.5) and (4.8).
It remains to bound dis(Rn ). The roots enable an orientation sensitive integration
given by|n−1/2 rn (uni , unj ) − rϕ(1) (pe (s), pe (t))| ≤ 2|n−1/2 rn (un0 , unk ) − rϕ(1) (pe (0), pe (r))|+ |n−1/2 rn (un0 , uni ) − rϕ(1) (pe (0), pe (s))|+ |n−1/2 rn (un0 , unj ) − rϕ(1) (pe (0), pe (t))|,where (unk , pe (r)) ∈ Rn and r ∈ [s, t] as in the previous paragraph. As we have shownon our work on the bound of (4.7), each individual term converges to 0 uniformly inr, s, t ∈ [0, 1] respectively, and this completes the first part of the proof about theconvergence to 0 of the distortion dis(Rn ) of the natural correspondence.
We introduce what we call the distorted exploration of the outline of Tn . It actually−1/4
Vn (uni ) whenever the directed edge connecting thecollects a weight equal to e−nparent of uni to uni is traversed in the canonical exploration of the outline of Tn . Morespecifically, we set
C̃n (i) :=

∑

e−n

−1/4

Vn (u),

0 < i < 2n.

nu∈[un
0 ,ui ]]

By convention: C̃n (0) = C̃n (2n) = 0. Extend C̃n by linear interpolation to non-integers.
Then, (Tn , rn ) when endowed with the distorted metric rn coincides with the real tree

Scaling limit of a biased random walk on a critical branching random walk175

coded by the function C̃n . In parallel with this, (T , rϕ(1) ) coincides with the real tree
coded by the function ẽ as defined in (4.2).
The last step in the proof consists of showing that the Prokhorov distance dP(Tn ,rn )−1
between (2n) µC̃n := (pC̃n )∗ ℓ and νϕ(1) is negligible. This is suﬃcient since
(
)
−1
dP
µC̃n , (2n)−1 νn ≤ (2n)−1 .
(Tn ,rn ) (2n)Consulting the proof of [1, Proposition 2.10], there exists a common metric space (K, dK )such that
) 1
(
−1
dP
µC̃n , νϕ(1) ≤ dis(Rn ) + |supp(C̃n ) − supp(ẽ)|.
(K,dK ) (2n)2
The right-hand side converges to 0 as n → ∞, and since()
dGHP (Tn , n−1/2 rn , (2n)−1 νn ), (T , σT rϕ(1) , νϕ(1) ) ≤ |supp(C̃n ) − supp(ẽ)|+ dis(Rn ),the desired result follows.
The process associated with (T , σT rϕ(1) ), or the νϕ(1) -Brownian motion in a random
Gaussian potential ϕ(1) on the CRT as we called it, is a new object that appears as thescaling limit of the weakly biased random walk X n on Tn with bias parameter βn . To
make this precise, we assume that the random elements involved in the statement ofTheorem 4.1 belong to a probability space with probability measure P under which theprobability measure such that the pair of the normalized discrete tours (Ĉn , R̂n ) is in its
support, converges weakly to a probability measure defined in such a way that (T , ϕ) has
it as its marginal (see [13, Theorem 2]). Using Skorohod’s representation, the annealed
laws Pρn and Pρ of the weakly biased random walk X n and the νϕ(1) -Brownian motion
in a random Gaussian potential ϕ(1) are constructed by integrating the randomness outof the state spaces with respect to P.
Finally, we are able to prove our result. The subspace of continuous functions
f : T → T vanishing at infinity will be denoted by C∞ . A continuous function f : T → R
is called locally absolutely continuous if for every ε > 0 and all subsets T ′ ⊆ T with
λ(T ′ ) < ∞, there exists a δ ≡ δ(T ′ , ε), such that if [[ui , vi ]]ni=1 ⊆ T is a disjoint∑n∑ncollection with i=1 r(ui , vi ) < δ, then i=1 |f (ui ) − f (vi )| < ε. Denote the subspaceof locally absolutely continuous functions by A.
Proof of Theorem 2.1. As a consequence of Theorem 4.1 and since the spaces
involved in the spatial Gromov-Hausdorﬀ-vague convergence are compact, for Lebesgue
a.e. R ≥ 0,lim lim inf P (rn (ρn , Bn (ρn , R)c ) ≥ λ) = 1,

R→∞ n→∞∀λ ≥ 0.

176

George Andriopoulos

Therefore, as a corollary of [8, Theorem 1.2], the νn -speed motion on (Tn , rn ) converges
to the νϕ(1) -Brownian motion on (T , σT rϕ(1) ) in the annealed sense weakly on D(R+ , Rd ),when continuously embedded into Rd by n−1/4 ϕn and Σϕ ϕ respectively. The νn -speed
motion on (Tn , rn ) is the continuous-time nearest neighbor random walk on (Tn , rn )with jump rates
qn (u1 , u2 )−1 := 2 · νn ({u1 }) · rn (u1 , u2 ),u1 ∼ u2 ,which is equal in law to (Xnn3/2 t )t≥0 . Finally, the νϕ(1) -Brownian motion on (T , σT rϕ(1) )is the νϕ(1) -symmetric strong Markov process associated with the regular Dirichlet form
(E, D̄(E)) on (T , σT rϕ(1) , νϕ(1) ) given by∫(1)
1
E(f, g) :=∇f (v) · ∇g(v)eσβ,ϕ ϕ (v) dλ(v),f, g ∈ D(E),
2
where
(1)

D(E) := {f ∈ L2 (νϕ(1) ) ∩ C∞ ∩ A : ∇f ∈ L2 (eσβ,ϕ ϕ dλ)},and this concludes the proof.

References[1] R. Abraham, J.-F. Delmas, and P. Hoscheit. Exit times for an increasing Lévy tree-valued
process. Probab. Theory Related Fields, 159(1-2):357–403, 2014.
[2] D. Aldous. The continuum random tree. III. Ann. Probab., 21(1):248–289, 1993.
[3] D. Aldous. Tree-based models for random distribution of mass. J. Statist. Phys., 73(3–4):625-641, 1993.
[4] G. Andriopoulos. Invariance principles for random walks in random environment on trees.
preprint available at arXiv:1812.10197.
[5] S. Athreya, M. Eckhoﬀ and A. Winter. Brownian motion on R-trees. Trans. Amer. Math.
Soc., 365(6):3115–3150, 2013.
[6] S. Athreya, W. Löhr, and A. Winter. Invariance principle for variable speed random walks
on trees. Ann. Probab., 45(2):625–667, 2017.
[7] G. Ben Arous and A. Fribergh. Biased random walks on random graphs. In Probability
and statistical physics in St. Petersburg, volume 91 of Proc. Sympos. Pure Math., pages
99–153. Amer. Math. Soc., Providence, RI, 2016.
[8] D. A. Croydon. Scaling limits of stochastic processes associated with resistance forms.
Ann. Inst. Henri Poincaré Probab. Stat., 54(4):1939–1968, 2016.
[9] D. A. Croydon. Hausdorﬀ measure of arcs and Brownian motion on Brownian spatial
trees. Ann. Probab., 37(3):946–978, 2009.
[10] S. N. Evans. Snakes and spiders: Brownian motion on R-trees. Probab. Theory Related
Fields, 117(3):361–386, 2000.
[11] M. Heydenreich and R. van der Hofstad. Progress in high-dimensional percolation and random graphs. CRM Short Courses. Springer, Cham; Centre de Recherches Mathématiques,
Montreal, QC, 2017.

Scaling limit of a biased random walk on a critical branching random walk177[12] R. van der Hofstad and A. A. Járai. The incipient infinite cluster for high-dimensional
unoriented percolation. J. Statist. Phys., 114(3–4):625-663, 2004.
[13] S. Janson and J.-F. Marckert. Convergence of discrete snakes. J. Theoret. Probab.,18(3):615–647, 2005.
[14] J. Kigami. Harmonic calculus on limits of networks and its application to dendrites. J.
Funct. Anal., 128(1):48–86, 1995.
[15] J-F. Le Gall. Random real trees. Ann. Fac. Sci. Toulouse Math. (6), (15)1:35-62, 2006.
[16] P. Tetali. Random walks and the eﬀective resistance of networks J. Theoret. Probab.,4(1):101-109, 1991.