Yueyun Hu

Zhan Shi

The potential energy of biased random walks on trees by

Keywords: Biased random walk on the Galton-Watson tree, branching random walk, slow movement, random walk in a random environment, potential energy. 2010 Mathematics Subject Classification. 60J80, 60G50, 60K37

HAL is a

Introduction

Let T be a supercritical Galton-Watson tree rooted at ∅. Let ω := (ω(x), x ∈ T) be a sequence of vectors: for each x ∈ T, ω(x) := (ω(x, y), y ∈ T) is such that ω(x, y) ≥ 0 (∀y ∈ T) and that y∈T ω(x, y) = 1.

Partly supported by ANR project MEMEMO2 (2010-BLAN-0125). 1 LAGA, Université Paris XIII, 99 avenue J-B Clément, F-93430 Villetaneuse, France, yueyun@math.univ-paris13.fr 2 LPMA, Université Paris VI, 4 place Jussieu, F-75252 Paris Cedex 05, France, zhan.shi@upmc.fr 1 Given ω, we define a random walk (X n , n ≥ 0) on T, started at X 0 = ∅, with transition probabilities given by

P ω {X n+1 = y | X n = x} = ω(x, y).
We assume that for each pair of vertices x and y, ω(x, y) > 0 if and only if y ∼ x, i.e., y is either a child, or the parent, of x; in particular, the walk is nearest-neighbour.

We are going to study a slow regime of the random walk (X n , n ≥ 0). In order to observe such a slow regime, the transition probabilities ω(x, y) are random; i.e., given a realisation of ω, we run a (conditional) Markov chain (X n ). So (X n ) is a randomly biased walk on the Galton-Watson tree T, and can also be considered as a random walk in random environment.

We use P to denote the law of the environment ω, and P := P ⊗ P ω the annealed probability measure. Randomly biased walks on trees have a large literature. The model is introduced by Lyons and Pemantle [START_REF] Lyons | Random walk in a random environment and first-passage percolation on trees[END_REF], extending the previous model of deterministically biased walks studied in Lyons [START_REF] Lyons | Random walks and percolation on trees[END_REF]- [START_REF] Lyons | Random walks, capacity and percolation on trees[END_REF]. In [START_REF] Lyons | Random walk in a random environment and first-passage percolation on trees[END_REF], a general recurrence vs. transience criterion is obtained;

for walks on Galton-Watson trees, the question is later also studied by Menshikov and Petritis [START_REF] Menshikov | On random walks in random environment on trees and their relationship with multiplicative chaos[END_REF] and Faraud [START_REF] Faraud | A central limit theorem for random walk in a random environment on marked Galton-Watson trees[END_REF]. Ben Arous and Hammond [START_REF] Ben Arous | Randomly biased walks on subcritical trees[END_REF] prove that in some sense, randomly biased walks on T are more regular than deterministically biased walks on T, preventing some "cyclic phenomena" from happening. Often motivated by results and questions in Lyons, Pemantle and Peres [START_REF] Lyons | Ergodic theory on Galton-Watson trees: speed of random walk and dimension of harmonic measure[END_REF] and [START_REF] Lyons | Biased random walks on Galton-Watson trees[END_REF], the transient case has received much research attention recently ( [START_REF] Aïdékon | Transient random walks in random environment on a Galton-Watson tree[END_REF], [START_REF] Aïdékon | Large deviations for transient random walks in random environment on a Galton-Watson tree[END_REF], [START_REF] Aïdékon | Speed of the biased random walk on a Galton-Watson tree[END_REF], [START_REF] Ben Arous | Biased random walks on a Galton-Watson tree with leaves[END_REF], [START_REF] Ben Arous | Einstein relation for biased random walk on Galton-Watson trees[END_REF]). The recurrent case has also been studied in recent papers of [START_REF] Andreoletti | The number of generations entirely visited for recurrent random walks on random environment[END_REF], [START_REF] Andreoletti | Spread of visited sites of a random walk along the generations of a branching process[END_REF], [START_REF] Faraud | A central limit theorem for random walk in a random environment on marked Galton-Watson trees[END_REF], [START_REF] Faraud | Almost sure convergence for stochastically biased random walks on trees[END_REF], [START_REF] Hu | A subdiffusive behaviour of recurrent random walk in random environment on a regular tree[END_REF] and [START_REF] Hu | Slow movement of recurrent random walk in random environment on a regular tree[END_REF]. For a more general account of study on biased walks on trees, we refer to the forthcoming book of Lyons and Peres [START_REF] Lyons | Probability on Trees and Networks[END_REF], as well as Saint-Flour lectures notes of [START_REF] Peres | Probability on Trees: An Introductory Climb, École d' Été de Saint-Flour[END_REF] and [START_REF] Shi | Branching Random Walks, École d' Été de Saint-Flour XLII[END_REF].

Although it is not necessary, we add a special vertex, ← ∅, which is the parent of ∅; this simplifies our representation. The values of the transition probabilities at a finite number of vertices bringing no change to results of the paper, we can modify the value of ω(∅, •), the transition probability at ∅, in such a way that (ω(x, y), y ∼ x), for x ∈ T, are an i.i.d. family of random variables.

A crucial notion in the study of the behaviour of the random walk (X n ) is the potential on T, which we define by V ( Since (ω(x, y), y ∼ x), for x ∈ T, are i.i.d., the potential process (V (x), x ∈ T) is a branching random walk, in the usual sense of Biggins [START_REF] Biggins | Chernoff's theorem in the branching random walk[END_REF], for example.

Throughout the paper, we assume (1.2) E

x: |x|=1 e -V (x) = 1, E

x: |x|=1

V (x)e -V (x) = 0.

We also assume the existence of δ > 0 such that (1.

3) E

x: |x|=1

e -(1+δ)V (x) + E

x: |x|=1 e δV (x) + E

x: |x|=1

1 1+δ < ∞.
A general result of Lyons and Pemantle [START_REF] Lyons | Random walk in a random environment and first-passage percolation on trees[END_REF], applied to our special setting of the Galton-Watson tree, implies that under (1.2), the random walk (X n ) is almost surely recurrent. This is proved in [START_REF] Lyons | Random walk in a random environment and first-passage percolation on trees[END_REF] under an additional condition on the exchangeability of (V (x), |x| = 1); the condition is removed in Faraud [START_REF] Faraud | A central limit theorem for random walk in a random environment on marked Galton-Watson trees[END_REF]. See also Menshikov and Petritis [START_REF] Menshikov | On random walks in random environment on trees and their relationship with multiplicative chaos[END_REF] for another proof, using Mandelbrot's multiplicative cascades, modulo some additional assumptions. In the language of branching random walks, (1.2) refers to the "boundary case" in the sense of Biggins and Kyprianou [START_REF] Biggins | Fixed points of the smoothing transform: the boundary case[END_REF]. In the boundary case, the biased walk (X n ) has a slow movement: under (1.2) and (1.3) and upon the system's survival, it is first proved in [START_REF] Hu | Slow movement of recurrent random walk in random environment on a regular tree[END_REF] (under some additional conditions) that max 0≤i≤n |X i | is of order of (log n) 3 , and is later improved in [START_REF] Faraud | Almost sure convergence for stochastically biased random walks on trees[END_REF] in the form of almost sure convergence:

on the system's non-extinction, (1.4)

lim n→∞ 1 (log n) 3 max 0≤i≤n |X i | = 8 3π 2 σ 2 ,
P-a.s., where (1.5)

σ 2 := E |x|=1 V (x) 2 e -V (x) ∈ (0, ∞).
In dimension 1 (which corresponds heuristically to the case that every vertex has one child), a well known result of Sinai [START_REF] Sinai | The limiting behavior of a one-dimensional random walk in a random medium[END_REF] tells that Xn (log n) 2 converges weakly to a nondegenerate limit; so (1.4) can be considered as a kind of companion of Sinai's theorem for the Galton-Watson tree.

In this paper, we are interested in the maximal potential energy,

max 0≤k≤n V (X k ) ,
of the random walk (X i ) in the first n steps. In the literature, results on the maximal energy of random walks in random environment or related models are obtained in the one-dimensional case by Monthus and Le Doussal [START_REF] Monthus | Energy dynamics in the Sinai model[END_REF], and for the Metropolis algorithm by Aldous [START_REF] Aldous | A Metropolis-type optimization algorithm on the infinite tree[END_REF], and recently by Maillard and Zeitouni [START_REF] Maillard | Performance of the Metropolis algorithm on a disordered tree: the Einstein relation[END_REF].

For one-dimensional random walks in random environment, it is known (Sinai [41], Brox [START_REF] Brox | A one-dimensional diffusion process in a Wiener medium[END_REF], Zeitouni [START_REF] Zeitouni | Random Walks in Random Environment, École d' Été de Saint-Flour[END_REF]) that in n steps, the maximal potential energy is bounded by (1 + o(1)) log n (for n → ∞); more precisely, the ratio between the maximal potential energy and log n converges to a non-degenerate random variable taking values in [0, 1]. For the tree-valued random walk (X i ), its restriction to each branch of T being a onedimensional walk in random environment, the maximal potential energy along a given branch is thus bounded by ( 1

+ o(1)) log n, for n → ∞.
Let us present the main result of the paper.

Theorem 1.1 Assume (1.2) and (1.3). We have, on the set of non-extinction,

lim n→∞ 1 (log n) 2 max 0≤k≤n V (X k ) = 1 2 , P-a.s.
Even though it is more natural to study the maximal potential energy (Aldous [START_REF] Aldous | A Metropolis-type optimization algorithm on the infinite tree[END_REF]) instead of the potential energy itself, we may wonder how V (X n ) behaves as n → ∞. We believe that V (X n ) would be much smaller than max 0≤k≤n V (X k ): Conjecture 1.2 Assume (1.2) and (1.3). Under P, on the set of non-extinction, V (Xn) log n converges weakly to a limit law which is (finite and strictly) positive.

In the one-dimensional recurrent case, it is proved by Monthus and Le Doussal [START_REF] Monthus | Energy dynamics in the Sinai model[END_REF] that log n is the common order of magnitude for both V (X n ) and max 0≤k≤n V (X k ).

The rest of the paper is as follows. Section 3 recalls some known techniques of branching random walks which are going to be used in the proof of the theorem. The section is preceded by a brief Section 2, where we outline the main ideas in the proof of Theorem 1.1. It turns out that the proof relies essentially on a quenched tail estimate of excursion heights of biased walks. This tail estimate, stated in (2.8), is proved in Section 4 by means of a second moment argument. The second moment argument being rather involving, we present it by means of two lemmas (Lemmas 4.1 and 4.2), serving as the key step in the proof of the upper and lower bounds, respectively, in (2.8). Lemma 4.2 is quite technical; its proof is the heart of the paper.

Throughout the paper, we write f (r) ∼ g(r), r → ∞, to denote lim r→∞ f (r) g(r) = 1, and f (r) = o(1), r → ∞, to denote lim r→∞ f (r) = 0. For any pair of vertices x and y in T, we write x < y (or y > x) to say that y is a descendant of x, and x ≤ y (or y ≥ x) to say that y is either a descendant of x or is x itself.

Proof of Theorem 1.1: an outline

We assume (1.2) and (1.3), and briefly describe the proof of Theorem 1.1. Let ̺ 0 := 0 and let (2.1)

̺ n := inf{i > ̺ n-1 : X i = ← ∅}, n ≥ 1.
In words, ̺ n denotes the n-th hits to ← ∅ by the walk (X i ). It turns out that ̺ n = n 1+o(1) P-a.s. for n → ∞: Lemma 2.1 Assume (1.2) and (1.3). On the set of non-extinction,

lim n→∞ log ̺ n log n = 1 , P-a.s.
The lemma is (implicitly) in [START_REF] Hu | Slow movement of recurrent random walk in random environment on a regular tree[END_REF] or [START_REF] Andreoletti | The number of generations entirely visited for recurrent random walks on random environment[END_REF]. We present the proof at the end of this section, for the sake of completeness, and also to justify the passage from hitting times at ∅ to hitting times at ← ∅. In view of Lemma 2.1, Theorem 1.1 is equivalent to the following estimate: for Palmost all ω in the set of non-extinction,

(2.2) 1 (log n) 2 max 0≤k≤̺n V (X k ) → 1 2 , P ω -a.s.
At this stage, we recall an elementary result:

Fact 2.2 Let α > 0. Let (ξ n ) n≥1 be a sequence of i.i.d. real-valued random variables such that P(ξ 1 ≥ u) = exp[-(α + o(1))u], u → ∞. Then lim n→∞ 1 log n max 1≤k≤n ξ k = 1 α , P-a.s.
Let us go back to (2.2). For fixed ω, max 0≤k≤̺n V (X k ) is the maximum of n independent copies of max 0≤k≤̺ 1 V (X k ); so applying Fact 2.2 to ξ :

= [max 0≤k≤̺ 1 V (X k )] 1/2
(on the set of non-extinction) and α := 2 1/2 , we see that the proof of (2.2) is reduced to verifying the following: for P-almost all ω in the set of non-extinction, (2.3)

P ω max 0≤k≤̺ 1 V (X k ) ≥ r = exp -(1 + o(1)) (2r) 1/2 , r → ∞.
For any r > 0, let us consider the following subset of the genealogical tree:

(2.4)

H r := {x ∈ T : V (x) ≥ r, V ( ← x) < r},
where

←
x denotes as before the parent of x, and for any vertex y ∈ T,

(2.5) V (y) := max z∈[[∅, y]] V (z),
which is the maximal value of the potential

V (•) along the path [[∅, y]].
By definition, {max 0≤k≤̺ 1 V (X k ) ≥ r} = {T Hr < T← ∅ }, where

T Hr := inf{i ≥ 0 : X i ∈ H r }, (2.6) T← ∅ := inf{i ≥ 0 : X i = ← ∅} = ̺ 1 . (2.7)
In words, T Hr is the first hitting time of the set H r by the biased walk (X i ). We mention that H r depends only on the environment, whereas T Hr involves also the behaviour of the biased walk. So (2.3) is equivalent to the following: P-almost surely on the set of non-extinction, (2.8)

P ω (T Hr < T← ∅ ) = exp -(1 + o(1)) (2r) 1/2 , r → ∞.
It is (2.8) we are going to prove, in Section 4.

Let us close this section with the proof of Lemma 2.1.

Proof of Lemma 2.1. For any j ≥ 1, we have

P ω max 0≤i≤̺ 1 |X i | ≥ j = ∞ k=1 P ω max 0≤i≤̺ 1 |X i | ≥ j, ̺ 1 i=1 1 {X i =∅} = k .
Observe that

P ω ̺ 1 i=1 1 {X i =∅} = k = [1 -ω(∅, ← ∅)] k ω(∅, ← ∅) ,
and that

P ω max 0≤i≤̺ 1 |X i | ≥ j ̺ 1 i=1 1 {X i =∅} = k = 1 -1 -P ω max 0≤i≤̺ ∅ |X i | ≥ j |X 1 | = 1 k = 1 -1 - P ω {max 0≤i≤̺ ∅ |X i | ≥ j} 1 -ω(∅, ← ∅) k ,
where

̺ ∅ := inf{i ≥ 1 : X i = ∅}. Thus P ω max 0≤i≤̺ 1 |X i | ≥ j = ∞ k=1 P ω { max 0≤i≤̺ ∅ |X i | ≥ j} k ω(∅, ← ∅) = P ω {max 0≤i≤̺ ∅ |X i | ≥ j} ω(∅, ← ∅) + P ω {max 0≤i≤̺ ∅ |X i | ≥ j} ≤ P ω {max 0≤i≤̺ ∅ |X i | ≥ j} ω(∅, ← ∅)
.

So for any n ≥ 1,

P ω max 0≤i≤̺n |X i | ≥ j = 1 -1 -P ω max 0≤i≤̺ 1 |X i | ≥ j n ≤ 1 -1 - P ω {max 0≤i≤̺ ∅ |X i | ≥ j} ω(∅, ← ∅) n .
By [START_REF] Faraud | Almost sure convergence for stochastically biased random walks on trees[END_REF],

1 j 1/3 log P ω {max 0≤i≤̺ ∅ |X i | ≥ j} → -( 3π 2 σ 2 8
) 1/3 (for j → ∞) P-almost surely on the set of non-extinction. Taking j := ⌈(1 + ε) 3 8 3π 2 σ 2 (log n) 3 ⌉ with ε > 0, we immediately see that P-a.s. on the set of non-extinction,

ℓ P ω {max 0≤i≤̺n ℓ |X i | ≥ (1 + ε) 3 8 3π 2 σ 2 (log n ℓ ) 3 } < ∞ if we take the subsequence n ℓ := ⌊ℓ 2/ε ⌋, ℓ ≥ 1.
By the Borel-Cantelli lemma, this yields that P-almost surely, on the set of non-extinction and for all sufficiently large ℓ,

max 0≤i≤̺n ℓ |X i | < (1 + ε) 3 8 3π 2 σ 2 (log n ℓ ) 3 , which, in turn, implies that for n ∈ [n ℓ-1 , n ℓ ], max 0≤i≤̺n |X i | < (1 + ε) 3 8 3π 2 σ 2 (log n ℓ ) 3 ≤ (1 + 2ε) 3 8 3π 2 σ 2 (log n) 3 .
Therefore, on the set of non-extinction, lim sup

n→∞ 1 (log n) 3 max 0≤i≤̺n |X i | ≤ 8 3π 2 σ 2 , P-a.s.
On the other hand, since ̺ n → ∞ P-a.s., it follows from (1.4) that on the set of non-extinction,

lim inf n→∞ 1 (log ̺ n ) 3 max 0≤i≤̺n |X i | ≥ 8 3π 2 σ 2 , P-a.s.
Combining the last two displayed formulas yields lim sup n→∞ log ̺n log n ≤ 1 P-a.s. on the set of non-extinction. This is the desired upper bound in Lemma 2.1. The lower bound is trivial since ̺ n ≥ 2n -1, ∀n ≥ 1.

Preliminaries: spinal decompositions

We recall a useful consequence of the spinal decomposition for branching random walks. The idea of the spinal decomposition, of which we find roots in [START_REF] Kahane | Sur certaines martingales de Mandelbrot[END_REF] and [START_REF] Bingham | Asymptotic properties of supercritical branching processes. II. Crump-Mode and Jirina processes[END_REF], has been developed in the literature independently by various groups of researchers in different contexts and forms. We use here the formulation of Lyons, Pemantle and Peres [START_REF] Lyons | Conceptual proofs of L log L criteria for mean behavior of branching processes[END_REF] and Lyons [START_REF] Lyons | A simple path to Biggins' martingale convergence for branching random walk[END_REF], based on a change-of-probabilities technique on the space of trees. We only give a brief description, referring to [START_REF] Lyons | Conceptual proofs of L log L criteria for mean behavior of branching processes[END_REF] and [START_REF] Lyons | A simple path to Biggins' martingale convergence for branching random walk[END_REF] for more details.

Throughout this section, we assume E( |x|=1 e -V (x) ) = 1, which is guaranteed by (1.2). Let

W n := x: |x|=n e -V (x) , n ≥ 0,
which is an (F n )-martingale, where F n denotes the σ-field generated by the branching random walk (V (x)) in the first n generations. Kolmogorov's extension theorem ensures the existence of a probability measure Q on F ∞ , the σ-field generated by the entire branching random walk, such that for any n and any

A ∈ F n , (3.1)
Q(A) = E(W n 1 A ) .
The distribution of (V (x)) under the new probability Q is called the distribution of a sizebiased branching random walk. It is immediately observed that the size-biased branching random walk survives with probability one. For future use, we record here a consequence of Hölder's inequality: assumption (1.3) implies the existence of a constant c 1 > 0 such that

(3.2) E Q x: |x|=1 e -V (x) c 1 = E x: |x|=1 e -V (x) 1+c 1 < ∞ .
We identify a branching random walk (V (x)) with a marked tree. On the enlarged probability space formed by marked trees with distinguished rays,3 it is possible to construct a probability Q satisfying (3.1), and an infinite ray {w 0 = ∅, w 1 , . . . , w n , . . . } (i.e., w n is the parent of w n+1 , and |w n | = n, ∀n ≥ 0) such that for any n ≥ 0 and any vertex x with |x| = n,

(3.3) Q{w n = x | F n } = e -V (x) W n .
Let us write from now on

S n := V (w n ), n ≥ 0.
For any vertex x ∈ T\{∅}, we define

(3.4) ∆V (x) := V (x) -V ( ← x) .
Let f : R → [0, ∞) be a Borel function, and write

η (f ) i := y: ← y =w i-1
f (∆V (y)) .

[In particular, η

:= y: |y|=1 f (V (y)).] According to the spinal decomposition (see Lyons [START_REF] Lyons | A simple path to Biggins' martingale convergence for branching random walk[END_REF]), (S i -S i-1 , η

(f ) i ), i ≥ 1, are i.i.d. under Q.
For any vertex x ∈ T, let x i be the ancestor of x in the i-th generation for 0 ≤ i ≤ |x| (so x 0 = ∅, and x |x| = x). Let n ≥ 1, and let g : R 2n → [0, ∞) be a Borel function. By definition of Q, we have

E x: |x|=n g V (x i ), y: ← y =x i-1 f (∆V (y)), 1 ≤ i ≤ n = E Q 1 W n x: |x|=n g V (x i ), y: ← y =x i-1 f (∆V (y)), 1 ≤ i ≤ n ,
which, according to (3.3), is

= E Q x: |x|=n e V (x) 1 {wn=x} g V (x i ), y: ← y =x i-1 f (∆V (y)), 1 ≤ i ≤ n = E Q e V (wn) g V (w i ), y: ← y =w i-1 f (∆V (y)), 1 ≤ i ≤ n .
In our notation, this means

E x: |x|=n g V (x i ), y: ← y =x i-1 f (∆V (y)), 1 ≤ i ≤ n = E Q e Sn g S i , η (f ) i , 1 ≤ i ≤ n . (3.5)
A special case of (3.5) is of particular interest: for any n ≥ 1 and any Borel function

g : R n → R + , (3.6) E x: |x|=n g(V (x 1 ), • • • , V (x n )) = E Q e Sn g(S 1 , • • • , S n ) .
This is the so-called many-to-one formula, and can also be directly checked by induction on n without using (3.3). An immediate consequence of (3.6) is that assumption (1.2) yields E Q (S 1 ) = 0, whereas assumption (1.3) implies

E Q (e a S 1 ) < ∞, ∀0 ≤ a < δ .
The existence of some finite exponential moments allows us to use the last displayed formula on page 1229 of Chang [START_REF] Chang | Inequalities for the overshoot[END_REF] 4 to see that there exists a constant c 2 > 0 satisfying

(3.7) sup b>0 E Q exp(c 2 ∆S H (S) b ) < ∞ ,
where

∆S i := S i -S i-1 , i ≥ 1, (3.8) H (S) r := inf{i ≥ 0 : S i ≥ r}, r ≥ 0 . (3.9)
The formula (3.5) is stated for any given generation n. It turns out that it remains (2.4). Indeed, according to Proposition 3 of [START_REF] Aïdékon | The precise tail behavior of the total progeny of a killed branching random walk[END_REF], for any r > 0 and any measurable functions f and g,

valid if n is replaced by H r , with H r := {x ∈ T : V (x) ≥ r, V ( ← x) < r} as in
E x∈Hr g V (x i ), y: ← y =x i-1 f (∆V (y)), 1 ≤ i ≤ |x| = E Q exp(S H (S) r ) g S i , η (f ) i , 1 ≤ i ≤ H (S) r , (3.10) where η (f ) i := y: ← y =w i-1 f (∆V (y)) as before. We recall that (S i -S i-1 , η (f ) i ), i ≥ 1, are i.i.d. under Q.
In particular, we have the following analogue of the many-to-one formula for H r :

(3.11) E x∈Hr g(V (x 1 ), • • • , V (x |x| )) = E Q exp(S H (S) r ) g(S 1 , • • • , S H (S) r ) .

The proof

Let us say a few words about the presentation of the proof of Theorem 1.1, which relies on a couple of lemmas, stated as Lemmas 4.1 and 4.2 below. Lemma 4.2, rather technical, consists of three estimates, namely, (4.10), (4.11) and (4.12). Here is how the proofs are organized: • Subsection 4.5: proof of Lemma 4.2, part (4.12).

•
Throughout the section, we assume (1.2) and (1.3). For any

x ∈ T ∪ { ← ∅}, let (4.1) T x := inf{n ≥ 0 : X n = x}, (inf ∅ := ∞)
which stands for the first hitting time of the vertex x by the biased walk. [In the special case x := ← ∅, (4.1) is in agreement with (2.7).] For r > 0, recall from (2.6) that

T Hr := inf{i ≥ 0 : X i ∈ H r },
where

H r := {x ∈ T : V (x) ≥ r, V ( ← x) < r} as in (2.4).
Our first preliminary result is as follows.

Lemma 4.1 Assume (1.2) and (1.3). We have

5 lim sup r→∞ 1 (2r) 1/2 log E[P ω (T Hr < T← ∅ )] ≤ -1 .
We need a second lemma, which is also the main technical result of the paper. In order to control the increments of the potential along the children of vertices in the spine, we introduce, for any vertex x ∈ T, the following quantity

(4.2) Λ(x) := y: ← y =x e -∆V (y) = y: ← y =x e -[V (y)-V (x)] . Let r > 0. Let χ ∈ ( 1 2 , 1). Let k := ⌊r 1-χ ⌋ , (4.3) h m := r k m , 0 ≤ m ≤ k , (4.4) λ m := (2r) 1/2 ( k -m + 1 k ) 1/2 , 1 ≤ m ≤ k . (4.5)
For any x ∈ T and any 0 ≤ s ≤ V (x) (for definition of V (x), see (2.5)), let

(4.6) H (x) s = inf i ≥ 0 : V (x i ) ≥ s, V (x j ) < s, ∀j ∈ [0, i) .
In words, H

is the generation of the oldest vertex in the path [[∅, x]] such that the value of the branching random walk V (•) is at least s.

For x ∈ H r := {x ∈ T : V (x) ≥ r, V ( ← x) < r}, we set 6 (4.7) a (x) i := λ m , if H (x) h m-1 ≤ i < H (x) hm for m ∈ [1, k] . Let c 1 > 0 be the constant in (3.2). Fix ε > 0, β ≥ 0, 0 < ε 1 < c 1 ε and θ ∈ ( 1 2 , χ). 7
We consider the following subset of H r :

H * r := x ∈ H r : max 1≤m<k ∆V (x H (x) hm ) ≤ r θ , V (x) ≥ -β, |x| < ⌊e ε 1 r 1/2 ⌋ , V (x j ) -V (x j ) ≤ a (x) j , ∀0 ≤ j < |x|, max 0≤j<|x| Λ(x j ) ≤ e εr 1/2 , (4.8)
where ∆V (y) := V (y) -V ( ← y ) as in (3.4), Λ(x) := y: ← y =x e -∆V (y) as in (4.2), and

V (y) := min z∈[[∅, y]] V (z) ,
for all y ∈ T. See Figure 1.

Define Z r = Z r (ε, ε 1 , β, θ, χ) by (4.9) Z r := x∈H * r 1 {Tx<T← ∅ } .
The reason for which we are interested in Z r is the obvious relation {T Hr < T← ∅ } ⊃ {Z r > 0}.

In the definition of Z r , everything depends only on the random potential V (•), except for T x and T← ∅ , both of which depend also on the movement of the biased random walk (X i ).

We summarize some moment properties of Z r in the next lemma. 6 As such, a

(x) i is well defined for all 0 ≤ i < H (x) r = |x| (for x ∈ H r ). The value of a (x) i for i = H (x) r
plays no role. [One can, for example, set a

(x) i := a (x) i-1 for i = H (S)
r .] 7 For Lemma 4.2, we can take any θ ∈ ( χ 2 , χ), but condition max 1≤m≤k ∆V (x

H (x) h m-1
) ≤ r θ is also exploited in Section 4.2 in the proof of Lemma 4.1, where θ needs to be greater than 1 2 . In order to avoid any possibility of confusion, we take θ ∈ ( 1 2 , χ) once for all.

0 i H (x) r H (x) hm H (x) hm-1 V (x j ) -V (x j ) ≤ λ m . For H (x) hm-1 ≤ j < H (x) hm , a (x) j = λ m , ≤ λ m h m r h m-1 V (x i ) Figure 1: The trajectory of (V (x i ), 0 ≤ i ≤ H (x) r ) when x ∈ H * r Lemma 4.2 Assume (1.2) and (1.3). For any 0 < ε 1 < c 1 ε, β ≥ 0 and 1 2 < θ < χ < 1, we have lim inf r→∞ 1 (2r) 1/2 log E[E ω (Z r )] ≥ -1 - ε 1 2 1/2 , (4.10) lim sup r→∞ 1 (2r) 1/2 log E[E ω (Z 2 r )] ≤ -1 + 2 1/2 (ε + ε 1 ) , (4.11) lim sup r→∞ 1 (2r) 1/2 log E[(E ω Z r ) 2 ] ≤ -2 + 2 1/2 ε . (4.12)
By admitting Lemmas 4.1 and 4.2 for the time being, we are ready to prove Theorem 1.1.

Proof of Theorem 1.1

We have seen in Section 2 that the proof of Theorem 1.1 consists of verifying (2.8), of which we recall the statement: under assumptions (1.2) and (1.3), P-almost surely on the set of non-extinction, (2.8) lim

r→∞ 1 (2r) 1/2 log P ω (T Hr < T← ∅ ) = -1 .
P * {P ω (T Hr < T← ∅ ) > e -(1-ε)(2r) 1/2 } ≤ e -c 3 (2r) 1/2 ,
for some c 3 = c 3 (ε) > 0 and all sufficiently large r. An application of the Borel-Cantelli lemma yields that with P * -probability 1, for all sufficiently large integer numbers r > 0, We now turn to the proof of the lower bound. Since E[P ω {Z r > 0}] = (P ⊗ P ω ){Z r > 0}, it follows from the Cauchy-Schwarz inequality that

P ω (T Hr < T← ∅ ) ≤ e -(1-ε)(2r)
E[P ω {Z r > 0}] ≥ {E[E ω (Z r )]} 2 E[E ω (Z 2 r )]
.

Applying
1 (2r) 1/2 log E[P ω {Z r > 0}] ≥ -1 -2 1/2 (ε + ε 1 ) -2 1/2 ε 1 .
On the other hand, by the Markov inequality, P ω {Z r > 0} ≤ E ω (Z r ), so it follows from (4.12) of Lemma 4.2 that

(4.14) lim sup r→∞ 1 (2r) 1/2 log E[(P ω {Z r > 0}) 2 ] ≤ -2 + 2 1/2 ε .
Recall (a special case of) the Paley-Zygmund inequality: for any non-negative random variable ξ, we have P{ξ

> 1 2 E(ξ)} ≥ 1 4 [E(ξ)] 2 E(ξ 2 )
. We apply it to ξ := P ω {Z r > 0}. In view of (4.13) and (4.14), we obtain: for any ε 2 > 6ε + 8ε 1 and all sufficiently large r,

P{P ω {Z r > 0} > e -(1+ε 2 )(2r) 1/2 } ≥ e -ε 2 r 1/2 .

Let (4.15)

γ r := P ω (T Hr < T← ∅ ).

Since {T Hr < T← ∅ } ⊃ {Z r > 0}, we have γ r ≥ P ω {Z r > 0}. Consequently, for all sufficiently large r > 0,

(4.16) P{γ r > e -(1+ε 2 )(2r) 1/2 } ≥ e -ε 2 r 1/2 .
As this stage, it is convenient to have the following preliminary estimate. Recall from

(2.5) that V (x) := max z∈[[∅, x]] V (z). Claim 4.3 Let c 4 > 0 be a constant satisfying (4.21) below. Let 0 < α < 1 2 . Let µ L := E x: |x|=L 1 {V (x)≥L α } 1 {V (x)<2L α } 1 { L-1 j=0 [1+Λ(x j )]≤e c 4 L } ,
where Λ(x) := y: ← y =x e -∆V (y) as in (4.2). Then lim L→∞ µ L = ∞.

Proof of Claim 4.3. By (3.5), we have

µ L = E Q e S L 1 {S L ≥L α } 1 {S L <2L α } 1 { L j=1 (1+η j )≤e c 4 L } ,
where (S j -S j-1 , η j ), j ≥ 1, are i.i.d. random vectors under Q, with η 1 := y: |y|=1 e -V (y) , and (4.17)

S j := max 0≤i≤j S i . j ≥ 0, Hence µ L ≥ e L α Q S L ≥ L α , S L < 2L α , L j=1 (1 + η j ) ≤ e c 4 L ≥ e L α Q{S L ≥ L α , S L < 2L α } -Q L j=1 (1 + η j ) > e c 4 L . (4.18)
We claim that for some constants c 5 > 0 and

c 6 > 0, lim inf L→∞ L 3 2 -2α Q{S L ≥ L α , S L < 2L α } ≥ c 5 , (4.19) lim sup L→∞ 1 L log Q L j=1 (1 + η j ) > e c 4 L ≤ -c 6 . (4.20)
It is clear that Claim 4.3 will follow from (4. [START_REF] Chang | Inequalities for the overshoot[END_REF]) and (4.20).

To check (4.19), we use [START_REF] Kozlov | The asymptotic behavior of the probability of non-extinction of critical branching processes in a random environment[END_REF]) that L 1/2 Q{S i ≥ 0, ∀1 ≤ i ≤ L} converges (when L → ∞) to a positive limit, whereas according to Caravenna [START_REF] Caravenna | A local limit theorem for random walks conditioned to stay positive[END_REF], lim inf

Q{S L ≥ L α , S L < 2L α } ≥ Q{L α ≤ S L < 2L α , S L-1 ≤ S L }. Since (S L -S L-i , 0 ≤ i ≤ L) is distributed as (S i , 0 ≤ i ≤ L), the latter probability is Q{L α ≤ S L < 2L α , S i ≥ 0, ∀1 ≤ i ≤ L}, which can be written as Q{S i ≥ 0, ∀1 ≤ i ≤ L} × Q{L α ≤ S L < 2L α | S i ≥ 0, ∀1 ≤ i ≤ L}. It is well known (Kozlov
L→∞ L 1-2α Q{L α ≤ S L < 2L α | S i ≥ 0, ∀1 ≤ i ≤ L} > 0. This yields (4.19).
The proof of (4.20) is also elementary. Let δ 1 ∈ (0, 1]. By the Markov inequality,

Q L j=1 (1 + η j ) > e c 4 L ≤ e -δ 1 c 4 E Q [(1 + η 1 ) δ 1 ] L ≤ e -δ 1 c 4 [1 + E Q (η δ 1 1 )] L . Note that E Q (η δ 1 1 ) = E Q [( |y|=1 e -V (y) ) δ 1 ] < ∞ if we choose δ 1 := min{c 1 , 1} (see (3.2)). So, as long as (4.21) c 4 > log[1 + E Q (η δ 1 1 )] δ 1 , we have e -δ 1 c 4 [1 + E Q (η δ 1 1 )] < 1, which yields (4.20). Claim 4.3 is proved.
We continue with our proof of Theorem 1.1, or more precisely, of the lower bound in (2.8). By Claim 4.3, we are entitled to choose and fix an integer L such that µ L > 1.

Let us construct a super-critical Galton-Watson G (L) which is a sub-tree of T. The vertices in G (L) 1 , the first generation of G (L) , are those x ∈ T with |x| = L such that

V (x) ≥ L α , V (x) < 2L α , L-1 j=0 [1 + Λ(x j )] ≤ e c 4 L ,
where Λ(x) := y: ← y =x e -∆V (y) as in (4.2). More generally, for any n ≥ 2, the vertices in

G (L) n , the n-th generation of G (L) , are those x ∈ T with |x| = nL such that V (x)-V (x * ) ≥ L α , that max (n-1)L≤i≤nL [V (x i )-V (x * )] < 2L α and that nL-1 j=(n-1)L [1+Λ(x j )] ≤ e c 4 L
, where

x * is the parent in G (L) n-1 of x (so x * = x (n-1)L as a matter of fact). Let c 4 > 0 be a constant satisfying (4.21). Let H s := {x ∈ T : V (x) ≥ s, V ( ← x) < s} as defined in (2.4). Let K s := x ∈ H s : |x|-1 j=0 [1 + Λ(x j )] ≤ e 2c 4 L 1-α s , |x| ≤ 2L 1-α s, V (x) ≤ 4s .
We need an elementary result.

Claim 4.4 For n ≥ 1 and s ∈ [2nL α , 2(n + 1)L α ], (4.22) #K s ≥ y∈G (L) n 1 {∃z∈G (L) 2n+2 : y<z} . Proof of Claim 4.4. Let y ∈ G (L) n be such that there exists z ∈ G (L) 2n+2 with y < z. By definition of G (L) , we have V (y) < 2nL α ≤ s and V (z) ≥ (2n + 2)L α ≥ s. So there exists x ∈ [[y, z]] such that x ∈ H s . Since x is a descendant of y, all we need is to check that x ∈ K s . Since z ∈ G (L) 2n+2 , we have, by definition of G (L) , |z|-1 j=0 [1 + Λ(z j )
] ≤ e c 4 (2n+2)L , and a fortiori (using

x ≤ z), |x|-1 j=0 [1 + Λ(x j )] ≤ e c 4 (2n+2)L ≤ e 4c 4 nL ≤ e 2c 4 L 1-α s . On the other hand, |x| ≤ |z| = (2n + 2)L ≤ 4nL ≤ 2L 1-α s. Finally, V (x) ≤ (2n + 2)2L α ≤ 8nL α ≤ 4s. As a conclusion, x ∈ K s .
We come back to the proof of the lower bound in (2.8). We use the trivial inequality

y∈G (L) n 1 {∃z∈G (L) 2n+2 : y<z} ≥ y∈G (L) n 1 {the sub-tree in G (L) rooted at y survives} .
Since G (L) is supercritical, there exist constants c 7 > 0 and c 8 > 0 such that for all sufficiently large n,

P y∈G (L) n 1 {∃z∈G (L) 2n+2 : y<z} ≥ e c 7 n ≥ c 8 .
Applying Claim 4.4, we see that there exists a constant c 9 > 0 such that for all sufficiently large s,

(4.23) P{#K s ≥ e c 9 s } ≥ c 8 .
Let r > 4s. We have

γ r := P ω (T Hr < T← ∅ ) ≥ x∈Ks P ω {T Hs < T← ∅ , X T Hs = x} γ (x) r-V (x) ,
where, conditionally on F Hs , (γ

(x)
t , t ≥ 0), for x ∈ K s , are independent copies of (γ t , t ≥ 0), and are independent of F Hs . [For x ∈ K s , we have V (x) ≤ 4s < r, so γ (x) r-V (x) is well defined.] For x ∈ K s , and with the notation Λ(x) := y: ← y =x e -∆V (y) from (4.2),

P ω {T Hs < T← ∅ , X T Hs = x} ≥ |x| j=1 ω(x j-1 , x j ) = e -V (x) |x|-1 j=0 [1 + Λ(x j )]
; on the other hand, by definition of K s , we have |x|-1 j=0 [1+Λ(x j )] ≤ e 2c 4 L 1-α s and V (x) ≤ 4s for x ∈ K s . Consequently, for x ∈ K s ,

P ω {T Hs < T← ∅ , X T Hs = x} ≥ e -(4+2c 4 L 1-α )s .
Hence, writing c 10 := 4 + 2c 4 L 1-α , we have Applying (4.16) to γ r-s implies that if r -s is sufficiently large,

P{γ r ≥ e -c 10 s e -(1+ε 2 )(2(r-s)) 1/2 } ≥ 1 -E{(1 -e -ε 2 (r-s) 1/2 ) #Ks } ≥ 1 -E{e -e -ε 2 (r-s) 1/2 #Ks } ≥ (1 -e -e -ε 2 (r-s) 1/2 e c 9 s ) P{#K s ≥ e c 9 s }.
By (4.23), P{#K s ≥ e c 9 s } ≥ c 8 if s is sufficiently large. As a consequence, for all sufficiently large s and r -s,

P{γ r ≥ e -c 10 s e -(1+ε 2 )(2(r-s)) 1/2 } ≥ c 8 [1 -e -e -ε 2 (r-s) 1/2 e c 9 s ].
We take s := 2 c 9 ε 2 r 1/2 , and see that for

ε 3 := (1 + 2 1/2 c 10 c 9
)ε 2 , there exists c 11 ∈ (0, 1) such that for all sufficiently large r, say r ≥ r 0 , (4.24)

P{γ r ≥ e -(1+ε 3 )(2r) 1/2 } ≥ c 11 .

Let J 1 be an integer such that (1 -c 11 ) J 1 < ε 3 . Let P * ( • ) := P( • | non-extinction) as before. Under P * , the system survives almost surely, so there exists an integer J 2 such that For |y| = J 2 with V (y) < r 1 , conditionally on V (y), P y ω {T Hr < T← ∅ } is distributed as γ r-V (y) , which is grater than or equal to γ r . It follows from (4.24) that for r ≥ max{r 1 , r 0 },

P * { |x|=J 2 1 > J 1 } > 1-ε 3 . Let r 1 be sufficiently large such that P * { |x|=J 2 1 {V (x)<r 1 } ≥ J 1 } ≥ 1 -ε 3 . We observe that for r ≥ r 1 , γ r ≥ max y: |y|=J 2 , V (
P{γ r ≥ c 12 (ω) e -(1+ε 3 )(2r) 1/2 } ≥ P max y: |y|=J 2 , V (y)<r 1 P y ω {T Hr < T← ∅ } ≥ e -(1+ε 3 )(2r) 1/2 ≥ (1 -(1 -c 11 ) J 1 )P |x|=J 2 1 {V (x)<r 1 } ≥ J 1 .
By definition of r 1 , we have

P{ |x|=J 2 1 {V (x)<r 1 } ≥ J 1 } ≥ (1 -ε 3 )(1 -q)
, where q := P{extinction} < 1. Therefore, for r ≥ max{r 1 , r 0 },

P{γ r ≥ c 12 (ω) e -(1+ε 3 )(2r) 1/2 } ≥ (1 -(1 -c 11 ) J 1 )(1 -ε 3 )(1 -q) ≥ (1 -ε 3 ) 2 (1 -q) ,
the last inequality following from the definition of J 1 . Since c 12 (ω) > 0 P-a.s., we have proved that

P * lim inf r→∞ log γ r (2r) 1/2 ≥ -1 -ε 3 ≥ (1 -ε 3 ) 2 .
Recall the definition

ε 3 := (1 + 2 1/2 c 10 c 9
)ε 2 , with ε 2 > 6ε + 8ε 1 , ε > 0 and ε 1 ∈ (0, c 1 ε); so ε 3 > 0 can be taken arbitrarily small. This yields the lower bound in (2.8), and thus completes the proof of Theorem 1.1 by admitting Lemmas 4.1 and 4.2.

The rest of the section is devoted to the proof of Lemmas 4.1 and 4.2.

Proof of Lemma 4.1

In the study of one-dimensional random walks, a frequent type of technical difficulties is to handle the overshoots. Such difficulties are, unfortunately, present throughout the proof of both Lemmas 4.1 and 4.2.

Let r > 0. Let χ ∈ (0, 1). Recall from (4.3)-(4.4) that

k := ⌊r 1-χ ⌋ , h m := r k m , 0 ≤ m ≤ k .
Recall from (2.4) that H r := {x ∈ T : V (x) ≥ r, V ( ← x) < r}. We distinguish the vertices x of H r according to whether there are some "large overshoots" of the random potential

V (•) along the path [[∅, x]]: let θ ∈ ( 1 2 , χ)
, and let

H r, + := x ∈ H r : max 1≤m<k ∆V (x H (x) hm ) > r θ , H r, -:= x ∈ H r : max 1≤m<k ∆V (x H (x) hm ) ≤ r θ ,
where, as before, ∆V (y) := V (y) -V ( ← y ) for any vertex y ∈ T\{∅}. Recall from (2.6) that

T Hr = inf x∈Hr T x = min inf x∈H r, + T x , inf x∈H r, - T x ,
where T x := inf{i ≥ 0 :

X i = x} as in (4.1). So (4.25) P ω (T Hr < T← ∅ ) ≤ x∈H r, + P ω (T x < T← ∅ ) + P ω inf x∈H r, - T x < T← ∅ .
We first bound x∈H r, + P ω (T x < T← ∅ ). By a one-dimensional argument (Zeitouni [START_REF] Zeitouni | Random Walks in Random Environment, École d' Été de Saint-Flour[END_REF], formula (2.1.4)), for any x, y ∈ T with y < x, (4.26)

P ω {T x < T← ∅ | X 0 = y} = u∈[[∅, y]] e V (u) u∈[[∅, x]] e V (u) .
In particular, for any x ∈ T\{∅}, (4.27)

P ω {T x < T← ∅ } = 1 u∈[[∅, x]] e V (u) ≤ e -V (x) .
Hence

x∈H r, + P ω (T x < T← ∅ ) ≤ x∈H r, + e -V (x) = x∈H r, + e -V (x) ,
the last identity following from the fact that V (x) = V (x) for all x ∈ H r, + . Taking expectation with respect to E on both sides, we obtain, by means of (3.11),

E x∈H r, + P ω (T x < T← ∅ ) ≤ Q max 1≤m<k ∆S H (S) hm > r θ ≤ k-1 m=1 Q ∆S H (S) hm > r θ .
We use (3.7) to see that for constant c 13 > 0,

E x∈H r, +
P ω (T x < T← ∅ ) ≤ c 13 (k -1) e -c 2 r θ = c 13 (⌊r 1-χ ⌋ -1) e -c 2 r θ .

Recall that θ > 1 2 . In view of (4.25), the proof of Lemma 4.1 is reduced to showing the following:

(4.28) lim sup r→∞ 1 (2r) 1/2 log E P ω inf x∈H r, - T x < T← ∅ ≤ -1 .
For any vertex x ∈ H r , let us recall a (x) j from (4.7), and define

τ x := inf{j : 1 ≤ j ≤ |x|, V (x j ) -V (x j ) ≥ a (x) j }. (inf ∅ := ∞)
For x ∈ H r , we have either τ x < |x| (with strict inequality), or τ x = ∞. We observe that inf x∈H r, -

T x = min inf x∈H r, -: τx<|x| T x , inf x∈H r, -: τx=∞ T x ≥ min inf x∈H r, -: τx<|x| T y(x) , inf x∈H r, -: τx=∞ T x ,
where y(x) := x τx . Hence

P ω inf x∈H r, - T x < T← ∅ ≤ P ω inf x∈H r, -: τx<|x| T y(x) < T← ∅ + x∈H r, -: τx=∞ P ω {T x < T← ∅ } =: Σ 1 + Σ 2 , (4.29)
with obvious notation. It is easy to get an upper bound for Σ 2 : by (4.27),

P ω {T x < T← ∅ } ≤ e -V (x) (which is e -V (x) for x ∈ H r, -), whereas τ x = ∞ implies V (x i ) -V (x i ) < a (x) i , ∀i < |x|, so (4.30) Σ 2 ≤ x∈Hr e -V (x) 1 {V (x i )-V (x i )<a (x) i , ∀i<|x|} k-1 m=1 1 {∆V (x H (x) hm
)≤r θ } .

To bound Σ 1 , we note that inf x∈H r, -: τx<|x|

T y(x) = inf{T y : ∃x ∈ H r, -, y = x τx , τ x < |x|} . Let y ∈ T with j := |y| ≥ 1 such that h m-1 ≤ V (y) < h m for some m ∈ [1, k]. We define a (y) i := λ ℓ , if H (y) h ℓ-1 ≤ i < H (y) h ℓ for ℓ ∈ [1, m) , λ m , if H (y) h m-1 ≤ i ≤ j .
Clearly, if y = x τx for some x ∈ H r, -satisfying τ x < |x|, then V (y i )-V (y i ) < a (y) i , ∀i < j, and V (y j ) -V (y j ) ≥ λ m , and moreover ∆V (y

H (y) h ℓ ) ≤ r θ , ∀1 ≤ ℓ < m. Accordingly, Σ 1 ≤ k m=1 ∞ j=1 |y|=j 1 {h m-1 ≤V (y)<hm} 1 {V (y i )-V (y i )<a (y) i , ∀i<j; V (y j )-V (y j )≥λm} × × m-1 ℓ=1 1 {∆V (y H (y) h ℓ
)≤r θ } P ω {T y < T← ∅ } .

Again, by (4.27), we have P ω {T y < T← ∅ } ≤ e -V (y) . This gives the analogue of (4.30) for Σ 1 .

We apply the many-to-one formula in (3.6). Recall from (3.9) that H (S) u := inf{i ≥ 0 :

S i ≥ u} (for u ≥ 0),
:= λ m , if H (S) h m-1 ≤ i < H (S)
hm and 1 ≤ m ≤ k .

By (3.6), E(Σ 1 ) ≤ k m=1 ∞ j=1 E Q e -(S j -S j ) 1 {h m-1 ≤S j <hm} 1 {S i -S i <a (S) i , ∀i<j; S j -S j ≥λm} × × m-1 ℓ=1 1 {∆S H (S) h ℓ ≤r θ } ≤ k m=1 ∞ j=1 e -λm E Q 1 {h m-1 ≤S j <hm} 1 {S i -S i <a (S) i , ∀i<j} m-1 ℓ=1 1 {∆S H (S) h ℓ ≤r θ } . (4.32)
Similarly, applying (3.11) in place of (3.6) to E(Σ 2 ), we obtain:

(4.33) E(Σ 2 ) ≤ Q S i -S i < a (S) i , ∀1 ≤ i < H (S) r ; max 1≤ℓ<k ∆S H (S) h ℓ ≤ r θ .
At this stage, we have two preliminary results.

Claim 4.5 For any integers 1 ≤ m 0 ≤ m < k and any s ∈ (-∞, h m 0 ), we define

(4.34) f m 0 ,m (s) := Q m+1 ℓ=m 0 +1 { max i∈[H (S) h ℓ-1 -s , H (S) h ℓ -s ) (S i -S i ) < λ ℓ } ∩ m ℓ=m 0 {∆S H (S) h ℓ -s ≤ r θ } .
Then, as r → ∞,

Q m+1 ℓ=1 { max i∈[H (S) h ℓ-1 , H (S) h ℓ ) (S i -S i ) < λ ℓ } ∩ m ℓ=1 {∆S H (S) h ℓ ≤ r θ } ≤ e -(1+o(1)) m+1 ℓ=1 r χ λ ℓ , uniformly in 1 ≤ m < k.
Claim 4.6 There exists a constant c 14 > 0 such that for r → ∞,

∞ j=1 E Q 1 {h m-1 ≤S j <hm} 1 {S i -S i <a (S) i , ∀i<j} m-1 ℓ=1 1 {∆S H (S) h ℓ ≤r θ } ≤ c 14 r exp -(1 + o(1)) m-1 ℓ=1 r χ λ ℓ , (4.37) uniformly in m ∈ [1, k].

Proof of Claim 4.5. Applying the strong Markov property successively at H

(S) hm-s , H (S) h m-1 -s , • • • , H (S)
hm 0 -s , we obtain:

f m 0 ,m (s) ≤ m+1 ℓ=m 0 +1 sup u∈[0, r θ ] Q max 0≤i<H (S) h ℓ -h ℓ-1 -u (S i -S i ) < λ ℓ .
By Lemma A.3, we arrive at the following estimate: when r → ∞,

f m 0 ,m (s) ≤ exp -(1 + o(1)) m+1 ℓ=m 0 +1 h ℓ -h ℓ-1 -r θ λ ℓ ≤ exp -(1 + o(1)) m+1 ℓ=m 0 +1 r χ λ ℓ ,
uniformly in s < h m 0 and in 1 ≤ m 0 ≤ m < k;8 this yields (4.35). The proof of (4.36 is along the same lines.

Proof of Claim 4.6. Let LHS (4.37) denote the sum on the left-hand side of (4.37). Then

LHS (4.37) = E Q m-1 ℓ=1 1 {∆S H (S) h ℓ ≤r θ } H (S) hm -1 j=H (S) h m-1 1 {S i -S i <a (S) i , ∀i<j} .
By definition of a (S) i in (4.31), this yields

LHS (4.37) = E Q H (S) hm -1 j=H (S) h m-1 1 {S i -S i <λm, ∀i∈[H (S) h m-1 , j)} × × m-1 ℓ=1 1 {max i∈[H (S) h ℓ-1 , H (S) h ℓ ) (S i -S i )<λ ℓ }∩{∆S H (S) h ℓ ≤r θ } .
We proceed to get rid of the sum over j on the right-hand side. Applying the strong

Markov property at time H (S)

h m-1 , we have

(4.38) LHS (4.37) ≤ E Q m-1 ℓ=1 1 {max i∈[H (S) h ℓ-1 , H (S) h ℓ ) (S i -S i )<λ ℓ }∩{∆S H (S) h ℓ ≤r θ } Ξ m ,
where

Ξ m := sup x∈[hm-h m-1 -r θ , hm-h m-1 ] E Q H (S)
x -1 j=0

1 {S i -S i <λm, ∀i∈[0, j)} ≤ E Q ∞ j=0 1 {S i -S i <λm, ∀i∈[0, j)} .
To estimate the expectation on the right-hand side, we write

∞ j=0 = ∞ n=1 nλ 2 m -1 j=(n-1)λ 2 m
(by implicitly treating λ 2 m as an integer; otherwise we replace λ m by ⌈λ m ⌉, and the next three paragraphs will still go through with obvious modifications), so that

Ξ m ≤ ∞ n=1 E Q nλ 2 m -1 j=(n-1)λ 2 m 1 {S i -S i <λm, ∀i∈[0, j)} ≤ ∞ n=1 λ 2 m Q max 0≤i<(n-1)λ 2 m (S i -S i ) < λ m .
By the Markov property,

Q{max 0≤i<(n-1)λ 2 m (S i -S i ) < λ m } ≤ [ Q{max 0≤i<λ 2 m (S i -S i ) < λ m }] n-1 . So Ξ m ≤ ∞ n=1 λ 2 m Q max 0≤i<λ 2 m (S i -S i ) < λ m n-1 . We let r → ∞ (so that λ m → ∞ uniformly in m ∈ [1, k])
. By Donsker's theorem,

Q{max 0≤i<λ 2 m (S i -S i ) < λ m } → P{sup s∈[0, 1] (W s -W s ) < 1 σ } < 1
, where (W s , s ≥ 0) under P is a standard Brownian motion, and W s := sup u∈[0, s] W u . So there exists a constant 0 < c 15 < 1 such that for all sufficiently large r and all m ∈

[1, k], Q{max 0≤i<λ 2 m (S i -S i ) < λ m } ≤ 1 -c 15 , which, in turn, yields Ξ m ≤ ∞ n=1 λ 2 m (1 -c 15 ) n-1 = λ 2 m c 15 ≤ 2r c 15 .
Going back to (4.38), this yields that for all sufficiently large r (writing c 16 := 2 c 15 ),

LHS (4.37) ≤ c 16 r Q m-1 ℓ=1 { max i∈[H (S) h ℓ-1 , H (S) h ℓ ) (S i -S i ) < λ ℓ } ∩ {∆S H (S) h ℓ ≤ r θ } .
This implies Claim 4.6 in case 2 ≤ m < k by means of (4.36), and trivially in case m = 1.

We continue with the proof of Lemma 4.1. By (4.32) and Claim 4.6, we have

E(Σ 1 ) ≤ c 14 r k m=1 exp -λ m -(1 + o(1)) m-1 ℓ=1 r χ λ ℓ .
By definition, k := ⌊r 1-χ ⌋ and λ m := (2r) 1/2 ( k-m+1 k ) 1/2 ; hence for r → ∞, (4.39)

m+1 ℓ=1 r χ λ ℓ = (2r χ ) 1/2 [k 1/2 -(k -m) 1/2 ] + o((2r) 1/2 ) , uniformly in 1 ≤ m 0 ≤ m < k. In particular, (4.40) k ℓ=1 r χ λ ℓ ∼ (2r) 1/2 . So uniformly in m ∈ [1, k], λ m + (2r χ ) 1/2 [k 1/2 -(k -m + 1) 1/2 ] ≥ (1 + o(1))(2r) 1/2 inf s∈[0, 1] (1 -s) 1/2 + [1 -(1 -s) 1/2 ] ,
and the infimum equals 1 because the function s → (1-s)

1/2 +[1-(1-s) 1/2 ] is identically 1 on [0, 1]. Therefore, E(Σ 1 ) ≤ c 14 rke -(1+o(1))(2r) 1/2 ≤ e -(1+o(1))(2r) 1/2 ,
the second inequality being a consequence of definition k := ⌊r 1-χ ⌋.

On the other hand, by (4.33) and (4.36) (applied to m := k -1), we have

E(Σ 2 ) ≤ e -(1+o(1)) k ℓ=1 r χ λ ℓ ≤ e -(1+o(1))(2r) 1/2 ,
the second inequality being a consequence of (4.39) (applied to m := k -1). Since

P ω (inf x∈H r, -T x < T← ∅ ) ≤ Σ 1 + Σ 2 (see (4. 29
)), this yields (4.28), and completes the proof of Lemma 4.1.

The rest of the section is devoted to the proof of Lemma 4.2, which is more technical.

For the sake of clarity, we prove the three parts -namely, (4.10), (4.11) and (4.12)separately.

Proof of Lemma 4.2: inequality (4.10)

Recall from (4.9) the definition

Z r := x∈H * r 1 {Tx<T← ∅ }
, where

H * r := x ∈ H r : max 1≤m<k ∆V (x H (x) hm ) ≤ r θ , V (x) ≥ -β, |x| < ⌊e ε 1 r 1/2 ⌋ , V (x j ) -V (x j ) ≤ a (x) j , ∀0 ≤ j < |x|, max 0≤ℓ<|x| Λ(x ℓ ) ≤ e εr 1/2 ,
with Λ(x) := y: ← y =x e -∆V (y) as in (4.2). For brevity, we write, in this subsection,

n = n(ε 1 , r) := ⌊e ε 1 r 1/2 ⌋ ; so |x| + 1 ≤ n for all x ∈ H * r .
Since only T x and T← ∅ depend on the biased walk (X i ), we have

(4.41) E ω (Z r ) = x∈H * r P ω {T x < T← ∅ } .
By the identity in (4.27), we have

P ω {T x < T← ∅ } ≥ 1 |x|+1 e -V (x) , which is ≥ 1 n e -V (x) =
1 n e -V (x) for all x ∈ H * r . Taking expectation with respect to E on both sides leads to:

E[E ω (Z r )] ≥ 1 n E x∈H * r e -V (x) = 1 n E x∈Hr e -V (x) 1 {V (x j )-V (x j )<a (x) j , ∀0≤j<|x|} 1 {V (x)≥-β} × ×1 {|x|<n} 1 {Λ(x ℓ )≤e εr 1/2 , ∀0≤ℓ<|x|} k-1 m=1 1 {∆V (x H (x) hm
)≤r θ } .

The expression on the right-hand side is, according to formula (3.10),

= 1 n Q H (S) r -1 j=0 {S j -S j < a (S) j , S j ≥ -β} ∩ ∩{H (S) r < n} ∩ H (S) r ℓ=1 {η ℓ ≤ e εr 1/2 } ∩ k-1 m=1 {∆S H (S) hm ≤ r θ } ,
where H (S) r := inf{i ≥ 0 : S i ≥ r} as in (3.9), S j := max 0≤i≤j S i as in (4.17), ∆S j := S j -S j-1 as before (with S 0 := 0), and η ℓ := y: ← y =w ℓ-1 e -∆V (y) . [In particular, η 1 := y: |y|=1 e -V (y) .] Recall from Section 3 that (∆S i , η i ), i ≥ 1, are i.i.d. random vectors under Q. Hence (4.42)

E[E ω (Z r )] ≥ 1 n [q 1 (r) -q 2 (r)] ,
where

q 1 (r) := Q H (S) r -1 j=0 {S j -S j < a (S) j , S j ≥ -β} ∩ {H (S) r < n} ∩ k-1 m=1 {∆S H (S) hm ≤ r θ } , q 2 (r) := Q H (S) r -1 j=0 {S j -S j < a (S) j } ∩ k-1 m=1 {∆S H (S) hm ≤ r θ } ∩ H (S) r ∧n ℓ=1 {η ℓ > e εr 1/2 } .
By definition of (a (S) j ) in (4.31) (with notation ∆S 0 := 0 for the term m = 1 below),

q 1 (r) = Q {H (S) r < n} ∩ ∩ k m=1 H (S) hm -1 j=H (S) h m-1 {S j -S j < λ m , S j ≥ -β} ∩ {∆S H (S) h m-1 ≤ r θ } . Since {H (S) r < n} ⊃ ∩ k m=1 {H (S) hm -H (S) h m-1 < ⌊ n k ⌋}, we have q 1 (r) ≥ Q k m=1 H (S) hm -1 j=H (S) h m-1 {S j -S j < λ m , S j ≥ -β} ∩ ∩{∆S H (S) h m-1 ≤ r θ , H (S) hm -H (S) h m-1 < ⌊ n k ⌋} ≥ Q k m=1 H (S) hm -1 j=H (S) h m-1 {S j -S j < λ m , S j -S H (S) h m-1 ≥ -β} ∩ ∩{∆S H (S) h m-1 ≤ r θ , H (S) hm -H (S) h m-1 < ⌊ n k ⌋} .
Recall that h m -h m-1 = h 1 . Applying the strong Markov property successively at times H (S)

h k-1 , H (S)
h k-2 , • • • , H (S)
h 1 , this gives that9

q 1 (r) ≥ k m=1 inf x∈(r θ , h 1 ] Q H (S) x -1 j=0 {S j -S j < λ m , S j ≥ -β} ∩ ∩{∆S H (S) x ≤ r θ , H (S) x < ⌊ n k ⌋} . (4.43) We let r → ∞. By Lemma A.2, uniformly in m ∈ [1, k] and x ∈ (r θ , h 1 ], Q H (S) x -1 j=0 {S j -S j < λ m , S j ≥ -β} ≥ exp -(1 + o(1)) x λ m ≥ exp -(1 + o(1)) r χ λ m .
On the other hand, (3.7) tells us that

c 17 := sup b>0 E Q [exp(c 2 ∆S H (S) b )] < ∞. By the Markov inequality, for r → ∞, uniformly in m ∈ [1, k] and x ∈ (r θ , h 1 ], Q{∆S H (S) x > r θ } ≤ c 17 e -c 2 r θ ≤ 1 3 exp -(1 + o(1)) r χ λ m .
[The last inequality, valid for all sufficiently large r, relies on the facts that θ > χ 2 and that λ m ≥ (2r χ ) 1/2 .] Also, for some constant c 18 > 0 and all sufficiently large r and Kozlov [26]), which is bounded by 1 3 exp[-(1 + o(1)) r χ λm ] as well for some constant ε 1 > 0 (for r → ∞;

all m ∈ [1, k], sup x∈(r θ , h 1 ] Q{H (S) x ≥ ⌊ n k ⌋} ≤ c 18 h 1 (⌊ n k ⌋) 1/2 (see Theorem A of
recalling that n := ⌊e ε 1 r 1/2 ⌋). [We use the fact that 1 2 > χ 2 .] As a consequence, for r → ∞, uniformly in m ∈ [1, k] and x ∈ (r θ , h 1 ], Q H (S) x -1 j=0 {S j -S j < λ m , S j ≥ -β} ∩ {∆S H (S) x ≤ r θ , H (S) x < ⌊ n k ⌋} ≥ Q H (S)
x -1

j=0 {S j -S j < λ m , S j ≥ -β} -Q{∆S H (S) x > r θ } -Q{H (S) x ≥ ⌊ n k ⌋} ≥ 1 3 exp -(1 + o(1)) r χ λ m , which is still exp[-(1 + o(1)) r χ λm ]
by changing the value of o(1). Going back to (4.43), we see that for r → ∞,

(4.44) q 1 (r) ≥ exp -(1 + o(1)) k m=1 r χ λ m = e -(1+o(1))(2r) 1/2 ,
the last identity following from the observation in (4.40) that k m=1 r χ λm ∼ (2r) 1/2 , r → ∞. We now estimate q 2 (r). By definition,

q 2 (r) ≤ n ℓ=1 Q H (S) r -1 j=0 {S j -S j < a (S) j }; max 1≤i<k ∆S H (S) h i ≤ r θ ; η ℓ > e εr 1/2 ; ℓ ≤ H (S) r = n ℓ=1 k m=1 q (ℓ, m) 2 (r) , (4.45)
where

q (ℓ, m) 2 (r) := Q H (S) r -1 j=0 {S j -S j < a (S) j }; max 1≤i<k ∆S H (S) h i ≤ r θ ; η ℓ > e εr 1/2 ; H (S) h m-1 < ℓ ≤ H (S) hm = Q k i=1 H (S) h i -1 j=H (S) h i-1 {S j -S j < λ i }; max 1≤i<k ∆S H (S) h i ≤ r θ ; η ℓ > e εr 1/2 ; H (S) h m-1 < ℓ ≤ H (S) hm ,
We apply the strong Markov property at H (S)

h k-1 , to see that, for 1 ≤ m < k, q (ℓ, m) 2 (r) ≤ Q k-1 i=1 H (S) h i -1 j=H (S) h i-1 {S j -S j < λ i }; max 1≤i<k ∆S H (S) h i ≤ r θ ; η ℓ > e εr 1/2 ; H (S) h m-1 < ℓ ≤ H (S) hm × sup x∈[h k-1 , h k-1 +r θ ] Q H (S) h k -x -1 j=0 {S j -S j < λ k } . Let r → ∞. By Lemma A.3, we have, uniformly in x ∈ [h k-1 , h k-1 + r θ ], Q H (S) h k -x -1 j=0 {S j -S j < λ k } ≤ exp -(1 + o(1)) h k -h k-1 -r θ λ k ≤ exp -(1 + o(1)) r χ λ k .
We iterate the argument and apply the strong Markov property successively at H (S)

h k-2 , H (S) h k-3 , • • • , H (S) hm , to see that q (ℓ, m) 2 (r) ≤ Q m i=1 H (S) h i -1 j=H (S) h i-1 {S j -S j < λ i }; max 1≤i≤m ∆S H (S) h i ≤ r θ ; η ℓ > e εr 1/2 ; H (S) h m-1 < ℓ ≤ H (S) hm × exp -(1 + o(1)) k i=m+1 r χ λ i ≤ Q m-1 i=1 H (S) h i -1 j=H (S) h i-1 {S j -S j < λ i }; max 1≤i≤m-2 ∆S H (S) h i ≤ r θ ; η ℓ > e εr 1/2 ; H (S) h m-1 < ℓ × exp -(1 + o(1)) k i=m+1 r χ λ i .
To bound the probability expression Q[• • • ] on the right-hand side, we note that under

Q, given H (S) h m-1 < ℓ, η ℓ is independent of everything concerning the potential V (•) until 29
H (S)
h m-1 , and has the law of η 1 . Consequently,

q (ℓ, m) 2 (r) ≤ Q m-1 i=1 H (S) h i -1 j=H (S) h i-1 {S j -S j < λ i }; max 1≤i≤m-2 ∆S H (S) h i ≤ r θ ; H (S) h m-1 < ℓ × ×Q(η 1 > e εr 1/2 ) × exp -(1 + o(1)) k i=m+1 r χ λ i ≤ Q m-1 i=1 H (S) h i -1 j=H (S) h i-1 {S j -S j < λ i }; max 1≤i≤m-2 ∆S H (S) h i ≤ r θ × ×Q(η 1 > e εr 1/2 ) × exp -(1 + o(1)) k i=m+1 r χ λ i .
Looking at the two probability expressions

Q[∩ m-1 i=1 • • • ] and Q(η 1 > e εr 1/
2 ) on the right-hand side. The first probability expression is, according to (4.36), bounded by exp

[-(1 + o(1)) m-1 ℓ=1 r χ λ ℓ ].
For the second probability expression, let us recall that η 1 = y: |y|=1 e -V (y) by definition; so by (3.2), there exists a constant c 19 > 0 such that Q(η 1 > e εr 1/2 ) ≤ c 19 e -c 1 εr 1/2 . We have thus proved that, for 1

≤ m ≤ k, q (ℓ, m) 2 (r) ≤ c 19 e -c 1 εr 1/2 exp -(1 + o(1)) i: 1≤i≤k, i =m r χ λ i ≤ c 19 e -c 1 εr 1/2 -(1+o(1))(2r) 1/2 . Since q 2 (r) ≤ n ℓ=1 k m=1 q (ℓ, m) 2
(r) (see (4.45)), and n := ⌊e ε 1 r 1/2 ⌋ ≤ e ε 1 r 1/2 , this yields

q 2 (r) ≤ c 19 k e -(c 1 ε-ε 1 )r 1/2 -(1+o(1))(2r) 1/2 .
Recall that E[E ω (Z r )] ≥ q 1 (r)-q 2 (r) n (see (4.42)) and that q 1 (r) ≥ e -(1+o(1))(2r) 1/2 (see (4.44)), we obtain, for r → ∞, 1))(2r) 1/2 does not play any role when taking the limit r → ∞ (recalling that k := ⌊r 1-χ ⌋). By definition, n := ⌊e ε 1 r 1/2 ⌋, this readily yields (4.10).

E[E ω (Z r )] ≥ 1 n e -(1+o(1))(2r) 1/2 -c 19 k e -(c 1 ε-ε 1 )r 1/2 -(1+o(1))(2r) 1/2 . Since ε 1 ∈ (0, c 1 ε), the term c 19 k e -(c 1 ε-ε 1 )r 1/2 -(1+o(

Proof of

H * r := x ∈ H r : max 1≤m<k ∆V (x H (x) hm ) ≤ r θ , V (x) ≥ -β, |x| < ⌊e ε 1 r 1/2 ⌋ , V (x j ) -V (x j ) ≤ a (x) j , ∀0 ≤ j < |x|, max 0≤j<|x| Λ(x j ) ≤ e εr 1/2 ,
with Λ(x) := y: ← y =x e -∆V (y) as in (4.2). By definition,

E ω (Z 2 r ) = x, y∈H * r P ω {T x < T← ∅ , T y < T← ∅ } = E ω (Z r ) + x =y∈H * r P ω {T x < T← ∅ , T y < T← ∅ } . (4.46)
By (4.27), P ω {T x < T← ∅ } ≤ e -V (x) . On the other hand, by the definition of H r , we have

V (x) = V (x) for x ∈ H * r ⊂ H r . So E ω (Z r ) ≤ x∈H * r e -V (x) ≤ x∈Hr e -V (x) 1 {max 1≤m<k ∆V (x H (x) hm )≤r θ } 1 {V (x j )-V (x j )≤a (x) j , ∀0≤j<|x|} .
Taking expectation on both sides, we obtain:

E[E ω (Z r )] ≤ E x∈Hr e -V (x)
(4.47) E[E ω (Z r )] ≤ e -(1+o(1))(2r) 1/2 .
Also, since V (x) ≥ r for x ∈ H * r , we have x∈H * r e -2V (x) ≤ e -r x∈H * r e -V (x) , so that for all sufficiently large r,

P ω {T x < T y < T← ∅ } ≤ P ω {T x∧y < T← ∅ }P x∧y ω {T x < T← ∅ }P x∧y ω {T y < T← ∅ },
where, for any vertex z, P z ω denotes the (quenched) probability under which the biased walk starts at z. By exchanging x and y, we also have

P ω {T y < T x < T← ∅ } ≤ P ω {T x∧y < T← ∅ }P x∧y ω {T y < T← ∅ }P x∧y ω {T x < T← ∅ }.
Hence

P ω {T x < T← ∅ , T y < T← ∅ } = P ω {T x < T y < T← ∅ } + P ω {T y < T x < T← ∅ } ≤ 2P ω {T x∧y < T← ∅ }P x∧y ω {T x < T← ∅ }P x∧y ω {T y < T← ∅ }.
[Although we have implicitly assumed x ∧ y is different from the root ∅, the last inequality remains trivially valid even if x ∧ y is the root.] By (4.27), P ω {T x∧y < T← ∅ } ≤ e -V (x∧y) .

More generally, we use (4.26) to see that

P x∧y ω {T x < T← ∅ } ≤ (|x ∧ y| + 1)e -[V (x)-V (x∧y)] .
We also have P x∧y ω {T y < T← ∅ } ≤ (|x ∧ y| + 1)e -[V (y)-V (x∧y)] by exchanging the roles of x and y. As a consequence,

P ω {T x < T← ∅ , T y < T← ∅ } ≤ 2(|x ∧ y| + 1) 2 e V (x∧y)-V (x)-V (y) ,
which is bounded by 2(|x ∧ y| + 1)e V (x∧y)-V (x)-V (y) . Moreover, for x ∈ H * r , we have |x ∧ y| + 1 ≤ |x| + 1 ≤ ⌊e ε 1 r 1/2 ⌋. Going back to (4.49), we obtain:

E[E ω (Z 2 r )] ≤ e -(1+o(1))(2r) 1/2 + 2e 2ε 1 r 1/2 E z: V (z)<r x, y∈H * r : x∧y=z e V (z)-V (x)-V (y) (4.50) = e -(1+o(1))(2r) 1/2 + 2e 2ε 1 r 1/2 E ∞ n=0 k m=1 Σ (n,m) 3 , (4.51)
where Σ

(n,m) 3

:= z: |z|=n e V (z) 1 {h m-1 ≤V (z)<hm}
x, y∈H * r : x∧y=z e -V (x)-V (y) .

For further use, we also see from the inequality E ω (Z r ) ≤

x∈H * r e -V (x) that, for all sufficiently large r,

(4.52) E[(E ω Z r ) 2 ] ≤ e -r + E z: V (z)<r 1 {V (z)≥-β} x, y∈H * r : x∧y=z e -V (x)-V (y) .
The term e -r comes from E( x∈H * r e -2V (x) ) and (4.48). The indicator function 1 {V (z)≥-β} was implicitly present in x ∈ H * r ; it is written explicitly here because it is going to play a crucial role later. We note that the expectation expressions on the right-hand side of (4.50) and (4.52) are very similar to each other, except that there is no V (z) term on the right-hand side of (4.52).

For each pair (n, m), we estimate E(Σ (n,m) 3

). By definition (recalling that x i is the ancestor of x in generation i for i ≤ |x|),

Σ (n,m) 3 = z: |z|=n e V (z) 1 {h m-1 ≤V (z)<hm} u =v, ← u =z= ← v e -V (u)-V (v) × × x∈H * r : x n+1 =u e -[V (x)-V (u)] y∈H * r : y n+1 =v e -[V (y)-V (v)] .
We first take expectation conditioning on F n+1 := σ{V (w) : |w| ≤ n + 1}, the σ-field generated by the random potential in the first n + 1 generations:

E(Σ (n,m) 3 | F n+1 ) ≤ z: |z|=n e V (z) 1 {h m-1 ≤V (z)<hm} 1 {V (z i )-V (z i )<a (z) i , ∀0≤i≤n} 1 {max 1≤ℓ<m ∆V (z H (z) h ℓ )≤r θ } × ×1 {Λ(z)≤e εr 1/2 } (u, v): u =v, ← u =z= ← v e -V (u)-V (v) f m (V (u))f m (V (v)), (4.53)
where Λ(x) := y: ← y =x e -∆V (y) as in (4.2), and for s < h m+1 ,

f m (s) := E x∈H r-s e -V (x) k-1 ℓ=m+1 1 {∆V (x H (x) h ℓ -s )≤r θ } k ℓ=m+2 H (x) h ℓ -s -1 i=H (x) h ℓ-1 -s 1 {V (x i )-V (x i )<λ ℓ } .
Some care needs to be taken in order to make (4.53) valid in all situations. On the righthand side of (4.53), V (u) < h m for most u with ← u = z (and V (u) < r for most v with ← v = z); however, there is a possible situation when V (u) ≥ h m : this is when u ∈ H hm (for some 1 ≤ m ≤ k), in which case we only have V (u) ≤ h m + r θ (which is strictly smaller than h m+1 ). In order to take care of this situation, only overshoots ∆V (x H (x)

h ℓ -s )
for ℓ > m are involved in the definition of f m (s). In particular, f k-1 (s) = 1 for s < r, and f k (s) should be defined as 1 for all s ∈ R.

By formula (3.11), this gives, for s < h m+1 ,

f m (s) = Q k-1 ℓ=m+1 1 {∆S H (S) h ℓ -s ≤r θ } ∩ k ℓ=m+2 H (S) h ℓ -s -1 i=H (S) h ℓ-1 -s {S i -S i < λ ℓ } ,
where H (S) t := inf{i ≥ 0 : S i ≥ t} (for any t ≥ 0) as in (3.9). By Claim 4.5, we arrive at the following estimate: when r → ∞,

f m (s) ≤ exp -(1 + o(1)) k ℓ=m+2 r χ λ ℓ ,
uniformly in s < h m+1 and m ∈ [1, k] (and in n ≥ 1). Let us go back to (4.53), and first look at the double sum (u, v): u =v, ← u =z= ← v on the right-hand side. Thanks to the upper bound for f m (s) we have just obtained that is valid uniformly in s ≥ 0, we get that, on the right-hand side of (4.53),

1 {Λ(z)≤e εr 1/2 } (u, v): u =v, ← u =z= ← v e -V (u)-V (v) f m (V (u))f m (V (v)) ≤ 1 {Λ(z)≤e εr 1/2 } e -(2+o(1)) k ℓ=m+2 r χ λ ℓ u: ← u =z e -V (u) 2 ≤ e -(2+o(1)) k ℓ=m+2 r χ λ ℓ e -V (z) e εr 1/2 2 ,
where, in the last inequality, we used the definition of Λ(z) := u: ← u =z e -[V (u)-V (z)] as in (4.2) to see that on the event {Λ(z) ≤ e εr 1/2 }, we have u: ← u =z e -V (u) = e -V (z) Λ(z) ≤ e -V (z) e εr 1/2 . Therefore, (4.53) yields

E(Σ (n,m) 3 | F n+1 ) ≤ e 2εr 1/2 -(2+o(1)) k ℓ=m+2 r χ λ ℓ z: |z|=n e V (z)-2V (z) 1 {h m-1 ≤V (z)<hm} × ×1 {V (z i )-V (z i )<a (z) i , ∀0≤i≤n} 1 {max 1≤ℓ<m ∆V (z H (z) h ℓ
)≤r θ } .

Taking expectation to get rid of the conditioning, and using the many-to-one formula (3.6), we obtain:

E(Σ (n,m) 3
) ≤ e

2εr 1/2 -(2+o(1)) k ℓ=m+2 r χ λ ℓ E Q e Sn-Sn 1 {h m-1 ≤Sn<hm} × ×1 {S i -S i <a (S) i , ∀0≤i≤n} 1 {max 1≤ℓ<m ∆S H (S) h ℓ ≤r θ } .
Going back to (4.51), this yields

E[E ω (Z 2 r )] ≤ e -(1+o(1))(2r) 1/2 + 2e 2ε 1 r 1/2 ∞ n=0 k m=1 e 2εr 1/2 -(2+o(1)) k ℓ=m+2 r χ λ ℓ × ×E Q e Sn-Sn 1 {h m-1 ≤Sn<hm} 1 {S i -S i <a (S) i , ∀0≤i≤n} 1 {max 1≤ℓ<m ∆S H (S) h ℓ ≤r θ } . (4.54)
Similarly, (4.52) leads to: for r → ∞,

E[(E ω Z r ) 2 ] ≤ e -r + ∞ n=0 k m=1 e 2εr 1/2 -(2+o(1)) k ℓ=m+2 r χ λ ℓ E Q e -Sn
:= λ ℓ if H (S) h ℓ-1 ≤ i < H (S) h ℓ . In particular, a (S) n = λ m on the event {h m-1 ≤ S n < h m }, so that e S n -Sn ≤ e λm on {h m-1 ≤ S n < h m } ∩ {S n -S n < a (S) n }. Consequently, E[E ω (Z 2 r )] ≤ e -(1+o(1))(2r) 1/2 + 2e 2ε 1 r 1/2 ∞ n=0 k m=1 e λm+2εr 1/2 -(2+o(1)) k ℓ=m+2 r χ λ ℓ × ×Q {h m-1 ≤ S n < h m } ∩ {S i -S i < a (S) i , ∀0 ≤ i ≤ n} ∩ { max 1≤ℓ<m ∆S H (S) h ℓ ≤ r θ } .
According to Claim 4.6, this yields

E[E ω (Z 2 r )] ≤ e -(1+o(1))(2r) 1/2 + +2e 2ε 1 r 1/2 k m=1 e λm+2εr 1/2 -(2+o(1)) k ℓ=m+2 r χ λ ℓ × c 14 r e -(1+o(1)) m-1 ℓ=1 r χ λ ℓ .
By definition, k := ⌊r 1-χ ⌋ and λ m := (2r)

1/2 ( k-m+1 k ) 1/2 . Hence λ m -2 k ℓ=m+2 r χ λ ℓ - m-1 ℓ=1 r χ λ ℓ ∼ -(2r) 1/2 .
This completes the proof of inequality (4.11) in Lemma 4.2.

4.5 Proof of Lemma 4.2: inequality (4.12)

We recall from (4.55) that

E[(E ω Z r ) 2 ] ≤ e -r + ∞ n=0 k m=1 e 2εr 1/2 -(2+o(1)) k ℓ=m+2 r χ λ ℓ E Q e -Sn 1 {min 0≤i≤n S i ≥-β} × ×1 {h m-1 ≤Sn<hm} 1 {S i -S i <a (S) i , ∀0≤i≤n} 1 {max 1≤ℓ<m ∆S H (S) h ℓ ≤r θ } .
On the right-hand side, we throw away

1 {max 1≤ℓ<m ∆S H (S) h ℓ
≤r θ } by saying that it is bounded by 1. On the event {h m-1 ≤ S n < h m }, we have a on the right-hand side, depending on whether m ≤ ⌈ε 5 k⌉ or not.

(S) n = λ m , so that 1 {S i -S i <a (S) i , ∀0≤i≤n} ≤ 1 {Sn-Sn<λm} . This leads to: E[(E ω Z r ) 2 ] ≤ e -r + k m=1 e 2εr 1/2 -(2+o(1)) k ℓ=m+2 r χ λ ℓ E Q ∞ n=0 e -Sn 1 {min 0≤i≤n S i ≥-β} × ×1 {h m-
First case: 1 ≤ m ≤ ⌈ε 5 k⌉. In this case, we simply use 1 {h m-1 ≤Sn<hm} ≤ 1 and 1 {Sn-Sn<λm} ≤ 1, to see that for large r,

Σ (m) 4 ≤ e 2εr 1/2 -(2+o(1)) k ℓ=m+2 r χ λ ℓ E Q ∞ n=0 e -Sn 1 {min 0≤i≤n S i ≥-β} .
According to Lemma B.2 of Aïdékon [START_REF] Aïdékon | Convergence in law of the minimum of a branching random walk[END_REF], for any b > 0, there exists a constant c 20 (b) > 0, whose value depends also on β, such that

(4.57) E Q ∞ j=1 e -b S j 1 {S i ≥-β, ∀i≤j} ≤ c 20 (b) .
Consequently, for all sufficiently large r, Σ

≤ c 20 (1) e 2εr Recall that k := ⌊r 1-χ ⌋. Since ε 5 > 0 can be as close to 0 as possible, this yields (4.12), and completes the proof of Lemma 4. [We do not need to worry about overshoots, because x → P x {H r k+1 < H - r k -λ } is nondecreasing for x ∈ [r k , ∞).]

r χ λ ℓ = k ℓ=1 r χ λ ℓ - m+1 ℓ=1 r χ λ ℓ = (1 + o(1))(2r) 1/2 -(2r χ ) 1/2 [k 1/2 -(k -⌈ε 5 k⌉) 1/2 ], which is (1 + o(1))(1 -ε 5 ) 1/2 (2r) 1/2 , r → ∞. Therefore, ( 4
Since P r k {H r k+1 < H - r k -λ } = P{H r k+1 -r k < H - -λ } = P{H y < H - -λ }, it follows from Lemma A.1 that (with λ sufficiently large such that λ > y + c 22 ) We choose λ ≥ 1 and r ≥ 1. We note that y+c The next lemma says that, under sufficient integrability conditions, the main term r λ within the exponential function in Lemma A.2 is, in some sense, optimal:

P r k {H r k+1 < H -
Lemma A.3 Assume E(e δS 1 ) < ∞ for some δ > 0. For any ε > 0, there exist constants c 30 > 0 and c 31 > 0 such that for all r ≥ 1 and λ ≥ c 30 , we have (A.5) P S j -S j < λ, ∀0 ≤ j ≤ H r ≤ c 31 exp -(1 -ε) r λ .

Proof. Let τ 0 := 0 and for any k ≥ 1, let τ k := inf{i > τ k-1 : S i ≥ S τ k-1 } be the k-th ascending ladder epoch. Let P (A.5) denote the probability expression on the left-hand side of (A.5). For any k 1, we have

P (A.5) ≤ P{S τ k ≥ r} + P S τ i-1 -min τ i-1 ≤j≤τ i S j < λ, ∀1 ≤ i ≤ k .
We now estimate the two probability expressions on the right-hand side.

For the first probability expression, we write S τ k = k i=1 (S τ i -S τ i-1 ), and observe that (S τ i -S τ i-1 , i ≥ 1) is a sequence of i.i.d. random variables, with E(e aSτ 1 ) < ∞ for all a < δ. So we take k = k(r, ε) := 1 -ε E(S τ 1 ) r ;

there exist constants c 32 > 0 and c 33 > 0, depending on ε, such that P{S τ k(r, ε) ≥ r} ≤ c 32 e -c 33 r for all r ≥ 1.

For the second probability expression (now with k := k(r, ε)), we use the fact that (S τ i-1 -min τ i-1 ≤j≤τ i S j , i ≥ 1) is also a sequence of i.i.d. random variables, having the same distribution as -min 0≤j≤τ 1 S j ; accordingly,

P S τ i-1 -min τ i-1 ≤j≤τ i S j < λ, ∀1 ≤ i ≤ k(r, ε) = P -min 0≤j≤τ 1 S j < λ k(r, ε)
.

Since τ 1 = H 0 and {-min 0≤j≤τ 1 S j < λ} = {H 0 < H - -λ }, we are entitled to apply (A.2) to see that for all sufficiently large λ (say λ ≥ λ 0 ), P{-min 0≤j≤τ 1 S j < λ} ≤ 1 -(1 -ε)

E(Sτ 1 )
λ . Hence for λ ≥ λ 0 , P S τ i-1 -min

τ i-1 ≤j≤τ i S j < λ, ∀1 ≤ i ≤ k(r, ε) ≤ 1 -(1 -ε) E(S τ 1 ) λ k(r, ε)
,

y

  is the parent of ← y , and ]]∅, x]] := [[∅, x]]\{∅}, with [[∅, x]] denoting the set of vertices on the unique shortest path connecting ∅ to x.

  Subsection 4.1: proof of Theorem 1.1, by admitting Lemmas 4.1 and 4.2. • Subsection 4.2: proof of Lemma 4.1. • Subsection 4.3: proof of Lemma 4.2, part (4.10). • Subsection 4.4: proof of Lemma 4.2, part (4.11).

Lemma 4 .

 4 1 is useful in the proof of the upper bound in (2.8), and Lemma 4.2 the lower bound. We start with the proof of the upper bound, by means of Lemma 4.1. Let P * ( • ) := P( • | non-extinction) . By Lemma 4.1 and the Markov inequality,

  γ r ≥ e -c 10 s x∈Ks γ (x) r-s ≥ e -c 10 s max x∈Ks γ

y)<r 1 P

 1 ω {T y < T← ∅ } P y ω {T Hr < T← ∅ } ≥ c 12 (ω) max y: |y|=J 2 , V (y)<r 1 P y ω {T Hr < T← ∅ } , where c 12 (ω) := min y: |y|=J 2 , V (y)<r 1 P ω {T y < T← ∅ } > 0 P-a.s. (notation: min ∅ := 1, max ∅ := 0).

uniformly in 1 ≤

 1 m 0 ≤ m < k. Furthermore,(4.36)

  (x) ≤ e -r . By (4.47) and (4.46), we have(4.49)E[E ω (Z 2 r )] ≤ e -(1+o(1))(2r) 1/2 + E x =y∈H * r P ω {T x < T← ∅ , T y < T← ∅ } .For any pair of distinct vertices x = y, let x∧y denote their youngest common ancestor;equivalently, x ∧ y is the unique vertex satisfying [[∅, x ∧ y]] = [[∅, x]] ∩ [[∅, y]]. Consider P ω {T x < T y < T← ∅ }.To realize T x < T y < T← ∅ , the biased walk first needs to hit x ∧ y before hitting ← ∅, then, starting from x ∧ y, it should hit x before hitting ← ∅, (and then, starting from x, it hits automatically x ∧ y before hitting ← ∅), and then, starting from x ∧ y, it should hit y before hitting ← ∅. Applying the strong Markov property, we obtain:

1 ≤Sn<hm} 1 Fix 0

 10 < ε 5 < 1. We use different estimates for Σ (m) 4

4 ≤ c 20 ( 1 ) 1 2- 1 2- 1 2) 4 ≤ 4 ≤(m) 4 (

 4201111444 ⌈ε 5 k⌉ e 2εr 1/2 -(2+o(1))(1-ε 5 ) 1/2 (2r) 1/2 . Second (and last) case:⌈ε 5 k⌉ < m ≤ k. Since m > ⌈ε 5 k⌉, we have h m-1 = (m -1) r k ≥ ε 5 r. So on the event {h m-1 ≤ S n < h m } ∩ {S n -S n < λ m }, we have S n > S n -λ m ≥ h m-1 -λ m ≥ ε 5 r-λ m , which is greater than or equal to ε 5 r-λ 1 = ε 5 r-(2r) 1/2 . Sn e -1 2 [ε 5 r-(2r) 1/2 ] 1 {min 0≤i≤n S i ≥-β} ≤ e 2εr 1/2 E Q ∞ n=0 e Sn e -1 2 [ε 5 r-(2r) 1/2 ] 1 {min 0≤i≤n S i ≥-β} = e 2εr 1/2 -1 2 [ε 5 r-(2r) 1/2 ] E Q ∞ n=0e Sn 1 {min 0≤i≤n S i ≥-β} .So by (4.57), we have Σ(mc 20 ( 1 2 ) e 2εr 1/2 -1 2 [ε 5 r-(2r) 1/2 ] for ⌈ε 5 k⌉ < m ≤ k. As a consequence, c 20 (1/2)k e 2εr 1/2 -1 2 [ε 5 r-(2r) 1/2 ] . Since E[(E ω Z r ) 2 ] ≤ e -r + k m=1 Σ see (4.56)), it follows from (4.58) and (4.59) that E[(E ω Z r ) 2 ] ≤ e -r + c 20 (1) ⌈ε 5 k⌉ e 2εr 1/2 -(2+o(1))(1-ε 5 ) 1/2 (2r) 1/2 + +c 20 (1/2)k e 2εr 1/2 -1 2 [ε 5 r-(2r) 1/2 ] .

2 .- c 26 r λ 3/ 2 . 22 28 = 1 k=0P 29 N - 1 k=0P

 2222281291 We let b → ∞. We have P{H - -b < H a } → 0 (by (A.1)), whereas sup b>0 E( |S H - -b+ b| 1+δ ) < ∞ and E[(S Ha ) 1+δ ) < ∞ (which is a consequence of the assumption E(|S 1 | 3+δ ) < ∞; see Mogulskii [37]). By Hölder's inequality, E{[ |S H - -b + b| + S Ha ] 1 {H - -b <Ha} ]} → 0. So (A.3) implies (A.2). Lemma A.2 Assume E(|S 1 | 3 ) < ∞.There exist constants c 24 > 0, c 25 > 0 and c 26 > 0 such that for all r ≥ 1 and λ ≥ c 24 , we have(A.4) P S j -S j < λ, S j ≥ 0, ∀0 ≤ j ≤ H r ≥ c 25 exp -r λProof. Let c 22 > 0 be the constant in Lemma A.1. Since E(S 1 ) = 0 and E(S 2 1 ) > 0, there exist c 27 > 0 and c 28 ∈ (0, 1) such that P{S 1 ≥ c 27 } ≥ c 28 , so thatP{H c 22 +1 < H - 0 } ≥ P S i -S i-1 ≥ c 27 , ∀1 ≤ i ≤ ⌈ c : c 29 > 0.Let y > 0 and let r k := (c 22 + 1) + yk, for 0≤ k ≤ N := ⌈ r y ⌉. Let E (A.4) := {S j -S j < λ, S j ≥ 0, ∀0 ≤ j ≤ H r }. Since r N ≥ r, E (A.4) will be realized if H r 0 < H - 0 and if for all 0 ≤ k ≤ N -1,the following is true: after hitting [r k , ∞) for the first time, the walk (S n ) hits [r k+1 , ∞) before hitting (-∞, r k -λ]. Applying the strong Markov property gives (P x being the probability under which the random walk starts at x; so P 0 = P) P(E (A.4) ) ≥ P{H r 0 < H - 0 } × Nr k {H r k+1 < H - r k -λ } ≥ c r k {H r k+1 < H - r k -λ } .

r k -λ } ≥ λ -c 22 y + λ = 1 - y + c 22 y + λ ≥ 1 22 λ-( y+c 22 λ ) 2 ] if y+c 22 λ ≤ 1 2 (

 11222222 y + c 22 λ ,which is greater than or equal to exp[-y+c by the elementary inequality that 1 -x ≥ e -x-x 2 for 0 ≤ x ≤ 1 2 ). Since N ≤ r y + 1 = r+y y , we obtain:P(E (A.4) ) ≥ c 29 exp -

22

 22

+ 1 + 2 λ 2 r+1y ≤ 4y 2 λ 2 2r y = 8ry λ 2 .

 12222 2c 22 r λy , and that if y ≥ c 22 , (y+c 22 ) So, taking y := λ 1/2 yields P(E (A.4) ) ≥ c 29 exp -

  1/2 . Since r → T Hr is non-decreasing, we can remove the condition that r be integer. As a consequence,

	lim sup r→∞	1 (2r) 1/2 log P

ω (T Hr < T← ∅ ) ≤ -1 , P * -a.s., which is the desired upper bound in (2.8).

  Lemma 4.2: inequality (4.11)

	Recall definition again from (4.9): Z r := x∈H * r 1 {Tx<T←

∅

} , where

  1 {max 1≤m<k ∆V (x

			H	(x) hm	)≤r θ } 1 {V (x j )-V (x j )≤a (x) j , ∀0≤j<|x|} ,
	which, by formula (3.11), is
	= Q max 1≤m<k	∆S H (S) hm	, S j -S j ≤ a (S) j , ∀0 ≤ j < H (S) r	.
	Applying (4.36), we get E[E ω (Z r )] ≤ e -(1+o(1)) k ℓ=1	r χ λ ℓ . Since	k ℓ=1	r χ λ ℓ ∼ (2r) 1/2 (see
	(4.40)), we arrive at:

  1 {min 0≤i≤n S i ≥-β} × ×1 {h m-1 ≤Sn<hm} 1 {S i -S i <a (S) i , ∀0≤i≤n} 1 {max 1≤ℓ<m ∆S

	(4.55)	H	h ℓ (S)	≤r θ } .
	(S) We proceed with (4.54). Recall from (4.31) that a i

Strictly speaking, the enlarged probability is a product space: the first coordinate concerns the branching random walk, and the second concerns the distinguished ray (= spine). In order to keep the notation as simple as possible, we choose to work formally on the same space, while bearing in mind that the spine (w n ) is not measurable with respect to the σ-field generated by the branching random walk.

More precisely, we apply the formula of Chang[START_REF] Chang | Inequalities for the overshoot[END_REF] to the ladder height of our mean-zero random walk via the Theorem on page 250 of Doney[START_REF] Doney | Moments of ladder heights in random walks[END_REF].

Of course, E[P ω (• • • )] is nothing else but E(• • • ).

Since h mh m-1 = r k (by (4.4)), it is here we use the condition θ < χ to ensure h mh m-1r θ > 0.

For the term m = k on the right-hand side, there is no need to consider {∆S H (S)x ≤ r θ }, whereas the m = 1 term has only the value x = h 1 . The current form of the inequality is used to give a compact expression for the lower bound.

A Appendix: Probability estimates for one-dimensional random walks

Let (Ω, F , P) be a probability space. Let S 0 := 0 and let (S i -S i-1 , i ≥ 1) be a sequence of i.i.d. real-valued random variables defined on (Ω, F , P) with E(S 1 ) = 0 and σ 2 := E(S 2 1 ) ∈ (0, ∞). We write

For any b ∈ R, let 10

Applying (2.6) of Borovkov and Foss [START_REF] Borovkov | Estimates for overshooting an arbitrary boundary by a random walk and their applications[END_REF] to the ladder heights, we immediately see that

the assumption E(S 2 1 ) < ∞ ensures that E(S H b ) < ∞ for all b ≥ 0, and that there exists

Then for any a ≥ 0,

Proof. We follow the same argument as in [START_REF] Aïdékon | The precise tail behavior of the total progeny of a killed branching random walk[END_REF].

This yields the second inequality in (A.1). Considering (-S n ) in place of (S n ) (and exchanging the roles of a and b) yields the first inequality.

(ii) Again, by the optional stopping theorem, 0 = E(S Ha∧H - -b