Pierre Andreoletti
email: pierre.andreoletti@univ-orleans.fr

Alexis Kagan
email: alexis.kagan@univ-orleans.fr

Generalized range of slow random walks on trees

Keywords: 60K37, 60J80 randomly biased random walks, branching random walks, range

In this work, we are interested in the set of visited vertices of a tree T by a randomly biased random walk X := (Xn, n ∈ N). The aim is to study a generalized range, that is to say the volume of the trace of X with both constraints on the trajectories of X and on the trajectories of the underlying branching random potential V := (V (x), x ∈ T). Focusing on slow regime's random walks (see [HS16b], [AC18]), we prove a general result and detail examples. These examples exhibit many different behaviors for a wide variety of ranges, showing the interactions between the trajectories of X and the ones of V.

Introduction

The construction of the process we are interested in starts with a supercritical Galton-Watson tree T with offspring distributed as a random variable ν such that E [ ν ] > 1. We adopt the following usual notations for tree-related quantities: the root of T is denoted by e, for any x ∈ T, ν x denotes the number of descendants of x, the parent of a vertex x is denoted by x * and its children by x i , 1 ≤ i ≤ ν x . For technical reasons, we add to the root e, a parent e * which is not considered as a vertex of the tree. We denote by |x| the generation of x, that is the length of the path from e to x and we write x < y when y is a descendant of x, also x ≤ y signifying that x can also be equal to y. Finally, we write T n for the tree truncated at generation n. We then introduce a real-valued branching random walk indexed by T: ( V (x), x ∈ T ). We suppose that V (e) = 0 and for any generation n, conditionally to E n = { T n , (V (x), x ∈ T n ) }, the vectors of increments ((V (x i ) -V (x), i ≤ ν x ), |x| = n) are assumed to be i.i.d. Finally, we denote by P the distribution of E = { T, ( V (x), x ∈ T ) } and P * , the probability conditioned on the survival set of the tree T.

We can now introduce the main process of this work which is a random walk (X n ) n∈N on T ∪ { e * } : for a given realization of the environment E , (X n ) n∈N is a Markov chain with transition probabilities given by

P E ( X n+1 = e|X n = e * ) = 1 , ∀x ∈ T { e * } , P E ( X n+1 = x * |X n = x ) =
e -V (x) e -V (x) + νx i=1 e -V (x i ) , ∀j ≤ ν x , P E X n+1 = x j |X n = x = e -V (x j ) e -V (x) + νx i=1 e -V (x i ) .

The measure P E is usually referred to as the quenched distribution of the walk (X n ) n∈N in contrast to the annealed distribution P which is the measure P E integrated with respect to the law of E :

P( • ) = P E ( • ) P( dE ) .
Similarly, P * is the annealed probability conditioned on the survival set of the tree T (defined by replacing P by P * in the above probability). For x ∈ T ∪ { e * }, we use the notation P E

x for the conditional probability P E (•|X 0 = x); when there is no subscript, the walk is supposed to start at the root e. Recurrent criteria for these walks is determined from the fluctuations of log-Laplace transform ψ(s) := log E |z|=1 e -sV (z) , s > 0.

(1)

If inf 0≤s≤1 ψ(s) > 0 then (X n , n) is P almost surely transient and recurrent otherwise. It turns out that recurrent cases can be themselves classified, this can be found in the works of G. Faraud [START_REF] Faraud | A central limit theorem for random walk in a random environment on marked galton-watson trees[END_REF] and equivalently for transient cases in E. Aidekon [START_REF] Aïdékon | Transient random walks in random environment on a galton-watson tree[END_REF].

Here we consider recurrent cases and more particularly the regime where the random walk is particularly slow (see [START_REF] Hu | The slow regime of randomly biased walks on trees[END_REF]), that is to say we put ourselves in the boundary case for which ψ(1) = ψ (1) = 0.

(2)

In this paper, we are interested in the trace of X which is the set of vertices visited by this random walk until a given instant. The literature on the subject initially started with the study of the range, that is to say the volume of the trace of the simple random walk on Z d , where d ≥ 2 is the dimension. In particular P. Erdös and S. Taylor [START_REF] Erdös | Some problems concerning the structure of random walk paths[END_REF] prove that the asymptotic in time of the trace depends on the dimension d. If we put ourselves in the present context of random walk in random environment on trees then the trace naturally depends on the hypothesis on the environment E , see for example [START_REF] Andreoletti | Range and critical generations of a random walk on Galton-Watson trees[END_REF], [START_REF] Aïdékon | Scaling limit of the recurrent biased random walk on a galton-watson tree[END_REF] and [dR22]. A first step in the extension of the notion of the range is to count, for example, the number of vertices visited a large number of time (instead of at least one time). This aspect has been studied for the simple random walk in [START_REF] Rosen | A random walk proof of the erdös-taylor conjecture[END_REF] and in our context by [START_REF] Andreoletti | The heavy range of randomly biased walks on trees[END_REF] and [START_REF] Chen | Heavy range of the randomly biased walk on galton-watson trees in the slow movement regime[END_REF], about which we will give some details later in the paper. A second step in the study of the trace, especially in the case of random walk in random environment, is to select certain vertices not only with criteria on the trajectory of the walk but also on the underlying potential V . With this in mind we introduce a generalization of the range : for any n, let f n = {f n,k : R k → R + ; k ∈ N * } be a collection of bounded functions. Also, let g n : R + → R be a positive function. Then, the generalized range R n (g n , f n ) is given by

R n (g n , f n ) := x∈T g n (L n x )f n,|x| (V (x 1 ), V (x 2 ), • • • , V (x)), with (3)
L n x := n k=1
1 {X k =x} , (x i , i ≤ |x|) being the sequence of vertices of the unique path from the root (excluded) to vertex x and L n x is the usual local time of the walk at x before the instant n. As we may see, R n (g n , f n ) is quite general and can not be treated in this form, at once for every of these functions g n and f n , so additional assumptions (involving f n , g n and distribution P) will be introduced in Section 1.3. The aim of studying this extended range is twofold, first it allows to understand the interactions between the trajectories of the main process X and of the underlying branching potential V, second we develop a general tool allowing to treat many examples (for chosen f n and g n ). Note that if we take, for example, f n,k = 1 and g n = 1 [1,∞) for any integer n and k, then we get the regular range (treated in [START_REF] Andreoletti | Range and critical generations of a random walk on Galton-Watson trees[END_REF]), and if g n = 1 [n b ,∞) with 0 < b < 1, then we get the heavy range (see [START_REF] Andreoletti | The heavy range of randomly biased walks on trees[END_REF] and [START_REF] Chen | Heavy range of the randomly biased walk on galton-watson trees in the slow movement regime[END_REF]). The presentation of the results is divided into three subsections. In the first one below, we detail and comment particular examples showing a large variety of behaviors for the range for different f n and g n . In a second subsection, we present an informal statement of the general result, the aim of which is to give the main ideas without introducing too much technical material. Finally, in the last section, we introduce assumptions which leads to the full statement of the main theorem.

First results : examples

The first two theorems (Theorems 1.1 and 1.2) we present in this section derive from three other works : in the first one [START_REF] Hu | The potential energy of biased random walks on trees[END_REF], it is proved that, during its first n steps, the walk can reach height of potential of order (log n) 2 . More precisely, it is proved that the random variable ( max 1≤k≤n V (X k ) /(log n) 2 ) n≥2 converges almost surely to one half. Note that this behavior can be quite disappointing if we have in mind the intuitive behavior of Sinai's one dimensional random walk in random environment [START_REF] Ya | The limit behaviour of a one-dimensional random walk in a random medium[END_REF] for which the highest height of potential reached by the walk is of order log n. Of course the fact that the walk evolves on a tree instead of a one dimensional lattice changes the deal but at the same time it is also proved in [START_REF] Hu | The slow regime of randomly biased walks on trees[END_REF] that this walk has a similar behavior than Sinai's one (they are both at a distance of order (log n) 2 from the origin at a given instant n). In both cases, the potential plays a crucial role. In the two other papers ( [START_REF] Andreoletti | Range and critical generations of a random walk on Galton-Watson trees[END_REF] and [START_REF] Andreoletti | The heavy range of randomly biased walks on trees[END_REF]), the range is studied : in [START_REF] Andreoletti | Range and critical generations of a random walk on Galton-Watson trees[END_REF], it is proved that regular range (the number of visited vertices up to the instant n) is of order n /log n, whereas in [START_REF] Andreoletti | The heavy range of randomly biased walks on trees[END_REF], it is proved that the number of edges visited more than n b (with 0 < b < 1) times is typically of order n 1-b (this particular range is called «heavy range»in that paper, see also [START_REF] Chen | Heavy range of the randomly biased walk on galton-watson trees in the slow movement regime[END_REF] for a refinement of this work). Our first theorem below mixes the two approaches, showing the influence of a strong constraint on the trajectories of V on both regular or heavy range. What we mean by strong constraint here is a condition of the form V ≥ (log n) α with 1 < α < 2, that is to say when the potential is larger than what we can call regular height of potential for this walk (in the slow regime, a regular height is of order log n since it can be proved that ( V (Xn) /log n) n≥2 converges weakly, see [START_REF] Hu | The slow regime of randomly biased walks on trees[END_REF]) but smaller than the extreme value (log n) 2 of [START_REF] Hu | The potential energy of biased random walks on trees[END_REF]. Before stating this result, let us introduce the following hypothesis on the distribution of the branching random walk : there exists θ > 0 and δ 1 ∈ (0, 1/2) such that

E |z|=1 e -(1+θ)V (z) + E |z|=1 e θV (z) <∞, (4)
E |z|=1 (1 + |V (z)|)e -V (z) 2 + E |z|=1 e -(1-δ1)V (z) 2 <∞, (5)
these are common hypothesis used for example in [START_REF] Andreoletti | Range and critical generations of a random walk on Galton-Watson trees[END_REF].

Theorem 1.1. Assume (2), (4) and (5) hold. If for any n and k, f n,k (t 1 , t 2 , • • • , t k ) = 1 {t k ≥(log n) α } with α ∈ (1, 2) and if g n (t) = 1 {t≥n b } with b ∈ [0, 1), then

log + Rn(gn,f n )-(1-b) log n (log n) α-1
n≥2 converges in P * -probability to -1, where log + x = log(max(1, x)).

This result shows that the number of vertices with high potential visited at least once (resp. strongly visited, with b > 0) is of the same order, though smaller, than the regular range (resp. heavy-range). So visiting high potential is not just an accident appearing a couple of times on very specific paths of the tree. Far from that in fact, as the constraint of high potential creates a decrease of order e -(log n) α-1 +o(1) and therefore appears as a second order correction comparing to ranges without constraint on the environment. In the second theorem below, we add a slight different constraint which force the random walk to reach a high level of potential far from the ultimate visited vertices of given paths: Theorem 1.2. Assume (2), (4) and (5) hold. If for any n and k, f n,k (t 1 , t 2 , • • • , t k ) = 1 {t k/β ≥(log n) α } with β > 1, α ∈ (1, 2) ( x stands for the integer part of x) and for any b ∈ [0, 1),

g n (t) = 1 {t≥n b } then log + Rn(gn,f n )-(1-b) log n (log n) α-1
) n≥2 converges in P * -probability to -1 -π 2 √ β -1 + ρ (β -1) π 2 4 , where for any c > 0,

ρ(c) := cσ √ 2π +∞ 0 e -cσ 2 2 u 2 u 1/2 P(m 1 > 1/ √ uσ 2 ) - 1 2 +∞ u 1 y 3/2 P(m 1 > 1/ yσ 2 )dy du,
and m is a Brownian meander, m 1 := sup s≤1 m s and σ

2 := E[ |x|=1 V 2 (x)e -V (x) ].
As we may see, a slight change in function f n (comparing to previous theorem) makes appear something new, as the constant in the limit is very different than in Theorem 1.1. Note that ρ can be explicitly calculated : for any c > 0

ρ(c) = 2 √ c 1 -e - sinh( √ c) -2 √ c -log((e √ c + 1)/2) , (6)
so we clearly obtain continuity when β converges to 1, getting back to the previous theorem. At this point, we also would like to discuss the appearance of the Brownian meander distribution in ρ. First, note that a Brownian meander appears in the asymptotic distribution of the (correctly normalized) generation of X n (see [START_REF] Hu | The slow regime of randomly biased walks on trees[END_REF]) which is the consequence of the positivity of V (see Fact 4 below, page 11) together with an induced constraint on the largest downfall of V (we call maximal downfall, for a given x ∈ T, the quantity max y≤x (V (y)-V (y)), where V (y) := max z≤y V (z)) visited by the walk before the instant n. Also in [START_REF] Andreoletti | Range and critical generations of a random walk on Galton-Watson trees[END_REF], the distribution of two independent Brownian meanders (m 1 and m 2 ) appears in the result for the regular range R n (that is when f n,k = 1 and

g n = 1 [1,∞) ) : in P * -probability lim n→+∞ R n log n n = C(D m 1 , D m 2 ), (7)
one of these Brownian meanders also coming from the positivity of V and the other one coming from the fact that for a given visited vertex x, the maximum of V (on the unique path from the root to x) is attained pretty near the generation of x.

Here, the Brownian meander appears as we ask a visited vertex x to have reached a high level of potential in an early generation before the one of x and it turns out that the constraint of low downfall of V appearing in [START_REF] Hu | The slow regime of randomly biased walks on trees[END_REF] (max y≤x (V (y)-V (y) ≤ log n) along this kind of path produces this appearance of the Brownian meander. However, contrarily to (7), the Brownian meander is involved in the correction of the main fluctuation (e -C(Dm)(log n) α-1 ) and not just in the constant of the limit (C(D m 1 , D m 2 )).

In the third example below, we choose f n,k in such a way that an interaction appears between the trajectory of X and the downfalls of V , which have an important role in the behavior of these walks. More particularly, let us introduce, for a given t = (t 1 , t 2 , • • • , t k ) with k a positive integer, the following quantity

H k (t) := k j=1 e tj -t k ,
then we call sum of exponential downfalls of V at x ∈ T with |x| = k the quantity

H |x| (V x ) := H |x| (V (x 1 ), • • • , V (x k )) = |x| i=1 e V (xi)-V (x k ) . (8)
In order to simplify the notation and when there is no possible confusion, we will simply write H x instead of H |x| (V x ) in the sequel.

Theorem 1.3. Assume (2), ( 4) and (5) hold.

For any n and

k let f n,k (t 1 , t 2 , • • • , t k ) = 1 {t k ≥a(log n) α } ( k j=1 H j (t)) -d with α ∈ [1, 2), a ∈ R, d ∈ {0, 1} and g n (t) = 1 {t≥n b } with b ≥ 0. If b ∈ [0, 1/(1 + d)) and α = 1 (with a > 1/δ 1 when d = 1) then log + Rn(gn,f n ) log n n≥2 converges in P * -probability to 1 -(1 + d)b, otherwise if a = 1, b = 0, d = 1 and 1 < α < 2 log + Rn(gn,f n )-log n (log n) α/2 n≥2 converges in P * -probability to -2, finally if a = 1, 0 < b < 1/2, d = 1 and 1 < α < 2 log + Rn(gn,f n )-(1-2b) log n (log n) α-1
n≥2 converges in P * -probability to -1/b. For the first limit (when α = 1, implying that we have set a common height of potential -see Fact 1), by taking d = 0, we obtain the limit (1 -b) of the usual heavy range of [START_REF] Andreoletti | The heavy range of randomly biased walks on trees[END_REF]. Otherwise, if we add the penalization with the cumulative exponential downfalls ( y≤x H y ), that is when d = 1, then an extra cost d * b = b appears. The second case (with b = 0 but 1 < α < 2) has two constraints on the environment so the normalization (log n) α/2 appears as a compromise between the fact that high level of potential is asked (1 {t k ≥(log n) α } ), which alone yields by Theorem 1.1 a normalization (log n) α-1 , and the fact that cumulative exponential downfall fluctuations ( m≤k H m (t)) can not be two large as it appears in the denominator of the range. This yields the (log n) α/2 (note that as α < 2, α/2 > α -1). For the last case (0 < b < 1/2 and 1 < α < 2), the range is of order n 1-2b e -(log n) α-1 /b comparing to ne -2(log n) α/2 when b = 0 of the previous case. In particular, the parameter b of the heavy range appears in both the main normalization n 1-2b and in the correction e -(log n) α-1 /b . This can be intuitively understood as follows : first n 1-2b = n * n -b * n -b , one n -b is classical from the heavy range when asking for a local time to be larger than n b (which already appears in the first part of the Theorem), the second n -b comes from the fact that a local time at a given vertex x can be larger than n b only if |x| j=1 e V (xj )-V (x) ≥ n b and as this quantity appears in the normalization of the range (via f n,k (t 1 , t 2 , • • • , t k )) this produced this second n -b . So this part (n 1-2b ) appears as a first interaction between the constraints on the trajectory of X and the one of V. Let us now discuss about e -(log n) α-1 /b = e -(log n) α /(b log n) . For this term, we see intuitively the constrains for the walk to reach height of potential of order (log n) α but a the same time, in order to keep the denominator j≤k H j (t) as low as possible, the maximal downfall has to remain smaller than b log n, thus producing the ratio (log n) α /(b log n).

In the ultimate example below, we ask similar constraints for the environment than above but only in the early visited generations : Theorem 1.4. Assume (2), (4) and (5) hold. Let β > 1. For any n and k, let

f n,k (t 1 , t 2 , • • • , t k ) = 1 {t k/β ≥(log n) α } ( k/β j=1 H j (t)) -1 , α ∈ (1, 2) and if g n (t) = 1 {t≥n b } with b ∈ (0, 1), then log + Rn(gn,f n )-(1-b) log n (log n) α/2
n≥2 converges in P * -probability to -2.

This last theorem just prove that if the factor ( k/β j=1 H j (t)) -1 only concerns the beginning of the trajectory, that is the sites at a distance |x|/β of the root (if x is a visited vertex), then things go back to normal: there is no more multiple interactions between X and V.

We can imagine more examples like the ones we present above (by acting more on the function g n as we did for example) but for now, let us introduce a more general result with general hypothesis on g n and f n .

A general result (informal statement)

In this section, we present an informal statement for the asymptotic in n of R n (g n , f n ) for general g n and f n (including, in particular, the results of the preceding section). The aim, in a first step, is to introduce the result and the main ideas but to minimize the technical materials. First recall the expression of the generalized range (3)

R n (g n , f n ) = x∈T g n (L n x )f n,|x| (V (x 1 ), V (x 2 ), • • • , V (x)),
with L n x the local time of X at x before the instant n. We assume that g n can be written as the product of an indicator function and a function ϕ which is positive non-decreasing: for any b ≥ 0 and t ≥ 1, g n (t) := 1 {t≥n b } ϕ(t). The indicator function is here to include all types of range (regular or heavy). Also, we ask the function t → ϕ(t)/t to be non-increasing, so that ϕ(L n x ) remains reasonable (at most of the order of the local time itself). Let us introduce the branching object Ψ as follows : let 0 ∨ λ < λ be two real numbers and k ≥ 1 an integer, also let φ : R k -→ R be a bounded function. Ψ k λ,λ (φ) is then defined as a mean of φ along the trajectory of V (with constraints) until generation k, that is

Ψ k λ,λ (φ) := E |x|=k e -V (x) φ (V (x 1 ) , . . . , V (x)) 1 O λ,λ (x) , (9)
where O λ,λ is the set of (λ, λ )-regular lines

O λ,λ := x ∈ T; max j≤|x| H xj ≤ λ, H x > λ , with H xj = j i=1 e V (xi)-V (xj ) , (10)
also we denote

O λ := x ∈ T; max j≤|x| H xj ≤ λ , and Ψ k λ (φ) := E |x|=k e -V (x) φ (V (x 1 ) , . . . , V (x)) 1 O λ (x) . Note that since H x ≥ 1 (H x > 1 when |x| > 1), we have, for all λ < 1, O λ,λ = O λ and Ψ k λ,λ (φ) = Ψ k λ (φ).
The appearance of this set of regular lines O λ,λ is partly inspired from the works of [START_REF] Hu | The slow regime of randomly biased walks on trees[END_REF] (λ representing extreme exponential downfalls of V related to a reflecting barrier for the walk (X k , k ≤ n)), and also (for λ ) from the constraint on the local time appearing in the function g n . It turns out indeed that constraints on the value of the local time at a site x imply constraints on H x . In other words, there are constraints on the branching potential V induced by constraints on the random walk X and sometimes, these constraints have a major impact on the range. We call this type of contribution «contribution of type one», that is of order n θ where θ ∈ (0, 1] (this actually appears for example in Theorem 1.3). To be more specific, let us introduce the following notations: first

C ∞ := C ∞ ({f n ; n ≥ 1}) stands for the supremum of {f n ; n ≥ 1} that is C ∞ := sup m, f m, ∞ .
Then, define the set

U b := κ ∈ [0, 1]; for all k ≥ 1, t ∈ R k , n ≥ 1 : 1 {H k (t)>n b } f n,k (t) ≤ C ∞ n -κ , (11)
note that U b = ∅ because 0 ∈ U b and as the supremum is attained, let

κ b =: max U b . (12)
When κ b > 0, we say that a mixing between the constraints on trajectories of the random walk X and on those of the branching potential V produce a contribution of type one.

To introduce a second type of contribution, which can be seen as the second order comparing to the contribution of type one, we present an important quantity which is the sum over all the generations of Ψ

• n,n b (f n,• ) : k≥1 Ψ k n,n b (f n,k
). First, let us give an heuristic about the way it appears in the asymptotic of the range. For any k ≥ 1, introduce the k th return time T k := inf{k > T k-1 , X k = e} to e and take T 0 = 0. Recall the definition of V before (7) and let

R T n (g n , f n ) := x∈T g n (L T n x )f n,|x| (V x )1 {V (x)≥A log n} with A > 0 . R T n (g n , f n
) is a version of the generalized range where we have replaced the instant n by T n and we have made appear the additional constraint V (x) ≥ A log n. Note that it is known (following Lemma 2.1 in [START_REF] Andreoletti | Range and critical generations of a random walk on Galton-Watson trees[END_REF] and its proof at the beginning of Section 4.2) that this additional condition 1 {V (x)≥A log n} has no effect on the normalization of the range, that is Fact 1: There exists 0 < c 1 = c 1 (A) ≤ 1 such that lim n→+∞ P * R T n R T n = c 1 = 1. So here, we typically consider collections of functions

f n such that R T n (g n , f n )/R T n (g n , f n ) → Cte > 0.
One of the main gain of this consideration is the fact that relatively high potential yields interesting quasi-independence in the trajectory of (X n , n). With this fact, we have (see Section 3.1) something like

R T n (g n , f n ) nE E [R T 1 (g n , f n )]
in probability and thanks to the fact that ϕ is non-decreasing and to the expression of the quenched mean of R T 1 (g n , f n ), in probability, for large n

R T n (g n , f n ) nE E [R T 1 (g n , f n )] ϕ(n b ) n b n k≥1 Ψ k n,n b (f n,k ), which makes appear k≥1 Ψ k n,n b (f n,k
). It turns out that this lower bound is exactly the good quantity which leads to our main result. The following assumption ensures that k≥1 Ψ k n,n b (f n,k ) is not too small, which would correspond to an exaggerate penalization on the potential V : Assumption 1.

For all b ∈ [0, 1), ε > 0 and n large enough

k≥1 Ψ k n,n b (f n,k ) ≥ 1 n (κ b +ε)∧1 . (A1)
The second type of contribution that we call «contribution of type two» strongly involves the term

n κ b k≥1 Ψ k n,n b (f n,k ).
It is negligible with respect to n ε for all ε > 0 and comes also from a mixing between the constraints on X and the constraints on V. So finally introduce (h n , n) which is certainly the most important sequence of the paper : for any n ≥ 2

h n :=    log n κ b k≥1 Ψ k n,n b (f n,k ) if ∃ γ ∈ (0, 1) : (log n) γ log n κ b k≥1 Ψ k n,n b (f n,k ) → 0 log n otherwise . (13)
Let us start by a discussion about (h n , n) with the following remark in which we note that either

h n = o(log n) or h n = log n.
Remark 1. By definition of κ b ,

n κ b k≥1 Ψ k n,n b (f n,k ) ≤ C ∞ k≥1 Ψ k n (1) = C ∞ E x∈T e -V (x) 1 {x∈On} ≤ C ∞ (log n) 3 ,
where the last inequality is a quite elementary fact that will be proved later (see Remark 2). This implies, in particular, that if there exists 0 < γ < 0 such that

(log n) γ /log n κ b k≥1 Ψ k n,n b (f n,k ) → 0, then necessarily log(n κ b k≥1 Ψ k n,n b (f n,k )) < 0 and lim n→+∞ log(n κ b k≥1 Ψ k n,n b (f n,k )) = -∞.
Moreover, in this case, there exists 0 < γ < 1 such that h n ≥ (log n) γ . Also assumption (A1) above ensures that

log(n κ b k≥1 Ψ k n,n b (f n,k )) ≥ log n κ b n (κ b +ε)∧1 ≥ -((κ b + ε) ∧ 1 -κ b ) log n ≥ -ε log n, overall, definition of h n implies, under (A1), that (log n) γ ≤ h n ≤ log n.
The sequence (h n , n) is the quantity which gives the contribution of type two and produces the second order in our result. It is important to note that we carefully assign an expression to h n depending on whether constraints are penalizing or not. According to the asymptotic behavior of the term

n κ b k≥1 Ψ k n,n b (f n,k ), we assign h n two possible expressions : if (log n) γ is negligible with respect to | log(n κ b k≥1 Ψ k n,n b (f n,k
))| for some γ ∈ (0, 1) (which then remains smaller than ε log n by Remark 1), constraints are considered penalizing and we set

h n := | log(n κ b k≥1 Ψ k n,n b (f n,k
))|, see Theorem 1.1 for example. Otherwise, constraints are not penalizing enough and we set h n := log n, see Theorem 1.3 with α = 1 for instance. In this latter case, the choice is significant since log n is the right order for the logarithm of the regular range, that is to say the range without any constraint on the trajectories of the branching random potential V. We are now almost ready to state a result. But first introduce two last values : L (with L = ±∞ possibly) and ξ ∈ {-1, 0} defined as follows

L := lim inf n→∞ h -1 n log n 1-b-κ b ϕ(n b ) , and (14)
ξ := lim n→∞ h -1 n log n κ b k≥1 Ψ k n,n b (f n,k ) , (15)
and note that, following Remark 1, ξ necessarily exists. The full statement of our main result below need additional quite complex assumptions, involving f n in particular, they are described precisely in the next section (see (A2), (A3) and (A4)). The interesting point is the fact that all of these assumptions concern k≥1 Ψ k . And more than that, we can resume the actions of (A2), (A3) and (A4) by saying that Ψ has to be stable for small perturbations of its parameters. In the informal statement below, we will say that Ψ should have controlled fluctuations.

Theorem 1.5 (Informal statement). Assume (2), (4) and (5) hold, b ∈ [0, 1), assume also that (A1) is satisfied and Ψ has controlled fluctuations. If L ∈ (-ξ, +∞], then in P * -probability

h -1 n log + R n (g n , f n ) -log(n 1-b-κ b ϕ(n b )) -→ n→∞ ξ, if L = -ξ, with ∆ n := h -1 n log(n 1-b-κ b ϕ(n b ))-inf ≥n h -1 log( 1-b-κ b ϕ( b )), then in P * -probability h -1 n log + R n (g n , f n ) -∆ n -→ n→∞ 0, otherwise L ∈ [-∞, -ξ[ and in P * -probability R n (g n , f n ) -→ →∞ 0,
for some increasing sequence (n ) of positive integers. Note that when lim h

-1 n log(n 1-b-κ b ϕ(n b )) = L, n = .
We now present particular examples which lead to different values of L and ξ. First, note that all theorems presented in the previous section satisfy L = +∞ and ξ = -1, corresponding, from our point of view, to the most interesting case. Let us take, for example,

g n (t) = 1 {t≥n b } and f n,k (t 1 , t 2 , • • • , t k ) = 1 {t k ≥a(log n) α } ( l≤k H l (t)) -1 as in Theorem 1.3, with a > 0, α ∈ [1, 2), but b ∈ [1/2, 1).
When α > 1 and b > 1/2, we can prove that h n ∼ a(log n) α-1 /b (with the usual notation t n ∼ s n if and only if t n /s n → 1) and n 1-b-κ b ϕ(n b ) = n 1-2b so we obtain lim h -1 n log(n 1-b-κ b ϕ(n b )) = L = -∞. However, when α = 1 and a > 1/δ 1 , we can prove that for all b ∈ [1/2, 1), κ b = b and h n = log n thus giving L = 1 -2b and ξ = 0. In other words, L ∈ (-∞, -ξ] (with L = -ξ if and only if b = 1/2). Let us finally take the simple example g n (t) = t1 {t≥n b } and f n,k = 1. We can prove that for all b ∈ (0, 1), h n = log n, ξ = 0 and n

1-b-κ b ϕ(n b ) = n so lim h -1 n log(n 1-b-κ b ϕ(n b
)) = L = 1 and we are in the case L ∈ (-ξ, +∞). To finish, we present an example for which f n,k is quite general but with a simple form. Assume

• f n,k = 1 A n,k with A n,k ⊂ R k and A n,k b := A n,k ∩ {t ∈ R k ; max 1≤j≤k H j (t) ≤ n, H k (t) > n b }; • (A n,k b × R k -k ) ∩ A n,k b = ∅ for all k < k ; • κ b = 0.
We obtain the following simple expression for

n κ b k≥1 Ψ k n,n b (f n,k ) = P(∪ k≥1 {(S 1 , . . . , S k ) ∈ A n,k b })
, where (S i , i) is a sum of i.i.d random variables with mean 0 and variance ψ (1) (this comes from the so-called many-to-one Lemma, see Lemma 2.1). So

log(n κ b k≥1 Ψ k n,n b (f n,k )) = -log P(∪ k≥1 {(S 1 , . . . , S k ) ∈ A n,k b }).
Consequently, if the probability P(∪ k≥1 {(S 1 , . . . , S k ) ∈ A n,k b }) is small enough, that is to say such that (log n) γ is negligible comparing to -log P(∪ k≥1 {(S 1 , . . . , S k ) ∈ A n,k b }) for a certain γ ∈ (0, 1), then the constraint is penalizing enough and h n = -log P(∪ k≥1 {(S 1 , . . . , S k ) ∈ A n,k b }). Otherwise, h n = log n. For example, take A n,k = {t ∈ R k ; inf{j ≤ k; t j ≥ (log n) α } = k} which leads to an example similar to Theorem 1.1.

A general result (full statement)

In this section, we explain precisely what «Ψ has controlled fluctuations» means. For that, we present the assumptions (A2), (A3) and (A4) mentioned in the previous section. We start with (A2), and then state a preliminary result (Proposition 1) of the main theorem (Theorem 1.5). This proposition is quite technical especially in its statement. However, it stresses on the fact that all the expressions involved depend deeply on k Ψ k .,. (f n,k ) and therefore justify the last two Assumptions (A3) and (A4) which leads to the formal statement of Theorem 1.5. Assumption 2. Assumption (A2) below is an upper bound for a conditional version of k≥1 Ψ k n,n b (f n,k ) actually requiring in order to be introduced two facts and additional notations. Fact 2 : By Lemma 2.3 in [START_REF] Andreoletti | The heavy range of randomly biased walks on trees[END_REF], there exists two real numbers c 2 , c2 > 0 such that for any h > 0

P * max |w|≤ h/c2 |V (w)| > h ≤ he -c2h . (16)
This fact, that will be useful when cutting on early generations of the tree, justifies the introduction of the following notation : for any n and k, f n,k h is the function defined by

f n,k h (t 1 , . . . , t k ) := inf s∈[-h,h] m f n,k+m (s 1 , . . . , s m , t 1 + s m , . . . , t k + s m ) , (17)
with m = h/c 2 and s = (s 1 , . . . , s m ) ∈ R m . The second fact is about the largest generation visited by the walk before the instant n or before n excursions to the vertex e. Fact 3 : Let ( n = (log n) 3 , n ≥ 2), by Lemma 3.2 in [START_REF] Andreoletti | The heavy range of randomly biased walks on trees[END_REF], there exists A > 0 such that :

lim n→+∞ P( max k≤T n |X k | ≤ A n ) = 1.
This fact is here essentially to justify the introduction of the sequence ( n , n) which appears in our second assumption and all along the paper. Note that a very precise result on the largest generation visited by the walk before the instant n can be found in [START_REF] Faraud | Almost sure convergence for stochastically biased random walks on trees[END_REF] .

A last notation we need to introduce is a conditional and translated version of Ψ k λ,λ (F ) for a given bounded function

F . For all k ∈ N * , l ∈ N * , F : R l+k -→ R bounded and t = (t 1 , . . . , t l ) ∈ R l Ψ k λ,λ (F |t) := E |x|=k e -V (x) F (t 1 , . . . , t l , V (x 1 ) + t l , . . . , V (x) + t l )1 O λ,λ (x) , ( 18
)
where |x|=k is the sum over all the individuals x of generation k. Otherwise, if l = 0, then Ψ k λ,λ (F |t) := Ψ k λ,λ (F ). We are now ready to introduce the second assumption : for all δ, ε, A, B > 0 and b ∈ [0, 1), there exists n 0 ∈ N * such that for any n ≥ n 0 , l ≤ A n and any t = (t 1 , . . . , t l ) ∈ R l with t l ≥ -B and

H l (t) ≤ n k≥1 Ψ k n,n b -H l (t) f n,l+k εhn |t ≤ e δt l + ε A hn k≥1 Ψ k n,n b (f n,k ). ( A2
)
Let us comment this inequality which plays two roles. A first one ensures that the fluctuations of V in the early generations of the tree have minor influence, this yields the presence of e ε A hn . The second point is technical and aims to show that

E E [R T 1 (g n , f n )] n -b ϕ(n b ) k≥1 Ψ k n,n b (f n,k
) in probability. For that, the second moment of

Z n := x∈O n,n b e -V (x) f n,k εhn (V x )1 {V (x)≥A log n,V (x)≥-B,V (x)=V (x)}
has to be controlled, with V x := (V (x 1 ), . . . , V (x)) and V (x) := min v≤x V (v). We first observe that

Z 2 n ≈ z∈T x,y>z u∈{x,y} 1 {u∈O n,n b } e -V (u) f n,|u| εhn (V u )1 {V (u)≥A log n,V (u)≥-B,V (u)=V (u)} .
Then taking the expectation of Z 2 n , k≥1 Ψ k n,n b -H l (t) (f n,l+k εhn |t) in (A2) actually appears as the conditional expectation of a well chosen function of the translated potential (V z (u (v) . Hence, for all δ ∈ (0, 1/2), by independence of the increments of the branching random walk (T, V (u); u ∈ T)

) := V (u) - V (z)) u>z . Indeed, note that u ∈ O n,n b together with V (u) = V (u) implies that u ∈ O z n,n b -Hz := {u > z : max z<v≤u H z,v ≤ n, H z,u > n b -H z } with H z,v := z<w≤v e Vz(w)-Vz
E[Z 2 n ] e (1-2δ)B E z∈On e -V (z)
x,y>z u∈{x,y}

1 {u∈O z n,n b -Hz } e -Vz(u) F n,|u| Vz (V z (u |z|+1 ), . . . , V z (u)) ≈ e (1-2δ)B E z∈On e -V (z) e δV (z) k≥1 Ψ k n,n b -Hz (f n,l+k |V z ) 2 ,
where, for |z| = l and any t = (t 1 , . . . , t l ) ∈ R l F n,|u| t (V z (u l+1 ), . . . , V z (u)) := e δt l f n,|u| εhn (t 1 , . . . , t l , V z (u l+1 ) + t l , . . . , V z (u) + t l ).

Assumption (A2) finally allows to say that E[Z 2 n ] e εhn ( k≥1 Ψ k n,n b (f n,k )) 2 for all ε > 0 and n large enough. We are now almost ready to state an intermediate result which is a proposition giving a lower and an upper bound for the generalized range stopped at T n . This proposition is followed by the theorem, much easier to read, but requiring extra assumptions. First, let us introduce for any z > 0

H k z := (t 1 , . . . , t k ) ∈ R k ; t k ≥ z , H k B,z := {(t 1 , . . . , t k ) ∈ R k ; t k ≥ z, min 1≤i≤k t i ≥ -B}, (19)
respectively the set of vectors such that its last coordinate is larger than z and additionally with all coordinates larger than -B. The introduction of these last two objects is justified by Fact 4 : for any ε > 0, there exists a > 0 such that (see [START_REF] Aïdékon | Convergence in law of the minimum of a branching random walk[END_REF])

P(min u∈T V (u) ≥ -a) ≥ 1 -ε,
and Fact 1 we have already talked about saying that, in P * -probability, 1/3 n is a height of potential usually reached by the walk.

Proposition 1. Recall (12), let ε b := min(b + 1 {b=0} , 1 -b)/13 and W := |z|=1 e -V (z) . Assume (2), (4) and (5) hold as well as (A1) and (A2). Lower bound: there exists c 5 > 0 such that for all b ∈ [0, 1), ε ∈ (0, ε b ), B > 0 and n large enough

P R T n (g n , f n ) n 1-b ϕ(n b )u 1,n < e -5εhn ≤ e -c5εhn (u 1,n ) 2 k≥1 Ψ k n,n b (f n,k εhn ) 2 + h n e -εc2hn + e -min(ε log n,3hn) (n κ b u 1,n ) 2 , ( 20
)
with

u 1,n = u 1,n (ε) := k≥1 Ψ k λn/2,n b f n,k εhn 1 Υ k n , Υ k n := {t ∈ R k ; H k (t) ≤ n b e εhn } ∩ H k B,2 1/3 n /δ1
and λ n = ne -min(10ε log n,5hn) .

Upper bound: for any ε > 0 and n large enough

P R T n (g n , f n ) n 1-b ϕ(n b )u 2,n > e εhn ≤ e -ε 2 hn + o(1) (21)
with

u 2,n := k≥1 Ψ k n f n,k 1 R k \H k 1/3 n /δ 1 + Ψ k n,n b /(log n) 2 (f n,k ) + E W Ψ k n,n b /(W (log n) 2 ) (f n,k ) .
Note that (20) and (21) remain true replacing

R T n (g n , f n ) by R T kn (g n , f n ) with k n = n/(log n) p , p > 0.
This proposition is technical and difficult to read, we present it here however because it shows that all the estimations depend deeply on Ψ . .,. (f ) and g n , recall indeed that the key sequence (h n , n) defined in (13) depends both on Ψ .

.,. (f ) and κ b (with b coming from the function g n ). This also means that without any more information on Ψ .

.,. (f ), it is difficult to state a more explicit result. Finally, note that the exact role of (A1) and (A2) will appear clearly in the proof of the lower bound (Section 3.2).

We now present two new assumptions (A3) and (A4) which lead to the formal statement of the result. These assumptions tell essentially that quantities u 1,n and u 2,n , which appear in the previous proposition, are actually very similar. Now introduce (A3) and (A4) :

Assumption 3 : for all b ∈ [0, 1), ε ∈ (0, ε b ), ε 1 ∈ (0, ε) and n large enough

u 1,n ≥ e -ε1hn k≥1 Ψ k n,n b (f n,k ). ( A3
)
Assumption 4 : for all ε 1 > 0, b ∈ [0, 1) and n large enough

u 2,n ≤ e ε1hn k≥1 Ψ k n,n b (f n,k ). (A4)
The full statement of Theorem 1.5 then writes as follows:

Theorem 1.5 (Full statement). Assume (2), (4) and (5) hold, b ∈ [0, 1) and (A1), (A2), (A3) and (A4) are satisfied. If L ∈ (-ξ, +∞], then in P * -probability

h -1 n log + R n (g n , f n ) -log(n 1-b-κ b ϕ(n b )) -→ n→∞ ξ, if L = -ξ, with ∆ n := h -1 n log(n 1-b-κ b ϕ(n b ))-inf ≥n h -1 log( 1-b-κ b ϕ( b )), then in P * -probability h -1 n log + R n (g n , f n ) -∆ n -→ n→∞ 0, otherwise L ∈ [-∞, -ξ[ and in P * -probability R n (g n , f n ) -→ →∞ 0,
for some increasing sequence (n ) of positive integers. Note that when lim h

-1 n log(n 1-b-κ b ϕ(n b )) = L, n = .
The rest of the paper is decomposed as follows: in Section 2, after short preliminaries (Section 2.1), we prove the theorems of Section 1.1. For these proofs (Section 2.2), we check that the four assumptions (A1-A4) of Theorem 1.5 are realized, obtaining simultaneously the asymptotic of h n . In section 2.3, we prove Theorem 1.5 : essentially, Proposition 1 is assumed to be true and we only check that if Assumptions (A3) and (A4) are true then the theorem comes. We prove Proposition 1 in section 3, this is the most technical part of the paper which can be read independently of the other parts : in Section 3.1, we summarize usual facts, in a second sub-section we prove a lower bound for stopped generalized range R T n (g n , f n ) and finally in a last one an upper bound.

In section 4 we present some estimates on sums of i.i.d. random variables useful for the proof of the examples of Section 1.1. Finally, we resume in a last section (page 56) the notations which are transversal along the paper.

Proof of the theorems

This section is decomposed in three parts: in the first section below, one can find preliminaries that are useful all along the rest of the paper. In the second sub-section, we prove the four theorems presented as examples. Finally, the last section is devoted to the proof of Theorem 1.5.

Preliminary material

We recall the many-to-one formula (see [START_REF] Shi | Branching random walks. École d'été de Probabilités[END_REF] Chapter 1, and [FHS11] equation 2.1) which will be used several times in the paper to compute expectations related to the environment. Note that the identity below comes from a change of probability measure (see references above), however we still keep P and E for simplicity.

Lemma 2.1 (Many-to-one Lemma). Recall the definition of ψ in (1). For any t > 0,

E |x|=m f (V (x i ), 1 ≤ i ≤ m) = E(e tSm+ψ(t)m f (S i , 1 ≤ i ≤ m)),
where (S n ) n∈N is the random walk starting at 0, such that the increments ( S n+1 -S n ) n∈N are i.i.d. and for any measurable function h : R m → [0, ∞),

E[h(S 1 )] = e -ψ(t) E( |x|=1 e -tV (x) h(V (x))).
A second very useful fact is contained in the following remark, it tells essentially that, in probability, the e -V (x) -weighted number of vertices x such that x ∈ O n (recall (10)) can be found in a quite small quantity when |x| ≤ A n and can not be found when |x| > A n . This remark is not precise at all but will be enough for our purpose.

Remark 2. There exists c 3 ∈ (0, 1) such that for any A > 0 and n large enough

E |x|> A n e -V (x) 1 {x∈On} ≤ n -Ac3 and E |x|≤ A n e -V (x) 1 {x∈On} ≤ n /2, which implies E x∈T e -V (x) 1 {x∈On} ≤ n .
Proof. We give a proof here which essentially use technical Lemma 4.6 (for the second inequality below), indeed by Lemma 2.1 above

E |x|> A n e -V (x) 1 {x∈On} ≤ k> A n P(sup i≤k (S i -S i ) ≤ log n) ≤ k> A n exp(- kπ 2 σ 2 (1 -ε) 8 log n ) ≤ n -Ac3 .
A similar computation gives the second fact and both of them the last one.

Proofs of Theorems 1.1 to 1.4

The pattern of the proofs of each theorem is the following : we first prove two facts (an upper and a lower bound) about the sum k≥1 Ψ k •,• (F ) with specific F , depending on the considered function f n,k and on a slightly different version of the latter whether we are looking for an upper or a lower bound. Then we use this two facts to prove that (A1), (A2), (A3) and (A4) are satisfied. In these proofs, we use several times the notation

ε b = min(b + 1 {b=0} , 1 -b)/13 which was introduced in Proposition 1. Proof of Theorem 1.1. Recall that f n,k (t 1 , t 2 , • • • , t k ) = 1 {t k ≥(log n) α } , α ∈ (1, 2
) and see (10) for the definition of O λ,λ . All along the proof, we assume that B, δ > 0, ε ∈ (0, ε b ), n is large enough and t ≥ -B. Let us start with the proof of the following two facts:

E x∈On e -V (x) 1 {V (x)≥(log n) α -t} ≤ e δt-(log n) α-1 (1-ε) , (22)
and for any 0

≤ m ≤ log n E x∈O λn,n b e -V (x) 1 {V (x)≥(log n) α +m, Hx≤n b e ε(log n) α-1 , V (x)≥-B} ≥ e -(log n) α-1 (1+ε) , (23)
with λ n = ne -6(log n) α-1 and recall V (x) = min u≤x V (u). We first deal with the upper bound (22).

Recall n = (log n) 3 , E x∈On e -V (x) 1 {V (x)≥(log n) α -t} ≤ k≤ A n E |x|=k e -V (x) 1 {V (x)≥(log n) α -t} 1 {x∈On} + E |x|> A n e -V (x) 1 {x∈On} ,
where

A > 0 is chosen such that E[ |x|> A n e -V (x) 1 {x∈On} ] ≤ 1/n (see Remark 2). This yields, as α ∈ (1, 2), E[ |x|> A n e -V (x) 1 {x∈On} ] ≤ e δ(t+B) 1 n ≤ 1 2 e δt-(log n) α-1 (1-ε)
for n large enough and any t ≥ -B. Thanks to many-to-one Lemma 2.1, the first sum in the above inequality is smaller than

k≤ A n P S k ≥ (log n) α -t, max j≤k S j -S j ≤ log n ≤ A n P max j≤τ (log n) α -t S j -S j ≤ log n , with τ r = inf{i ≥ 1; S i ≥ r}.
Then, thanks to Lemma A.3 in [START_REF] Hu | The potential energy of biased random walks on trees[END_REF], and as t ≥ -B

A n P max j≤τ (log n) α -t S j -S j ≤ log n ≤ A n e t log n -(log n) α-1 (1-ε 2 ) ≤ A n e t+B log n -(log n) α-1 (1-ε 2 ) ≤ e δt+δB-(log n) α-1 (1-ε 2 ) ≤ 1 2 e δt-(log n) α-1 (1-ε) ,
so we get exactly (22). We now turn to the lower bound (23). Let n = (log n) 4 and α n = (log n) α + log n. By the manyto-one Lemma, for any m ≤ log n, the expectation in ( 23) is larger than

k≥1 P S k ≥ α n , max j≤k H S j ≤ λ n , n b < H S k ≤ n b e ε(log n) α-1 , S k ≥ -B ,
with H S j := j i=1 e Si-Sj . For any b ∈ (0, 1), by Lemma 4.3 (77

) (with = (log n) 2 , t = α n , q = 1, a b = a = 6, d = (α -1)/2 and c = ε), above sum is larger than e -(log n) α-1 (1+ε) . Other- wise, if b = 0, observe that for all k ≤ n , S k = S k implies H S k ≤ k ≤ n so the sum is larger than k≤ n P S k ≥ α n , max j≤k H S j ≤ λ n , S k = S k , S k ≥ -B . Lemma 4.5 (with = (log n) 2 , t = α n , d = 1/2, a = 6 and d = (α -1)/2) leads to (23) also for b = 0.
We are now ready to prove that f n satisfies assumptions (A1), (A2), (A3) and (A4). Recall that

Ψ k n,n b (f n,k ) = E |x|=k e -V (x) f n,k (V (x 1 ), . . . , V (x))1 {x∈O n,n b } where x ∈ O n,n b if and only if max j≤|x| H xj ≤ n and H x > n b , also U b = {κ ∈ [0, 1]; for all k ≥ 1, t ∈ R k , n ≥ 1 : 1 {H k (t)>n b } f n,k (t) ≤ C ∞ n -κ } with C ∞ = sup n, f n, ∞ .
• Check of (A1) and asymptotic of h n . We obtain from (23) with m = 0 that for any ε ∈ (0, ε b ) and n large enough,

E[ x∈O n,n b e -V (x) 1 {V (x)≥(log n) α } ] is larger than (as λ n ≤ n) E x∈O λn,n b e -V (x) 1 {V (x)≥(log n) α } 1 {Hx≤n b e ε(log n) α-1 ,V (x)≥-B} ≥ e -(log n) α-1 (1+ε) .
Note that above inequality implies that for all b ∈ [0, 1), κ b = max U b = 0. Indeed, if we had κ b > 0, then this should imply that for any x ∈ T

e -V (x) 1 {x∈O n,n b } f n,k (V (x 1 ), . . . , V (x)) ≤ C ∞ n -κ b e -V (x) 1 {x∈O n,n b } , which gives that E[ x∈O n,n b e -V (x) 1 {V (x)≥(log n) α } 1 {Hx≤n b e ε(log n) α-1 ,V (x)≥-B} ] is smaller than C ∞ n -κ b E[ x∈On e -V (x) ] ≤ C ∞ n n -κ b by Remark 2, but this contradicts the above lower bound (23) as α ∈ (1, 2). Then, by definition of Ψ k n,n b , k≥1 Ψ k n,n b (f n,k ) = E x∈O n,n b e -V (x) 1 {V (x)≥(log n) α } ≥ e -(log n) α-1 (1+ε) ,
and additionally with (22) (taking t = 0), asymptotic of h n is given by

h n = n κ b log k≥1 Ψ k n,n b (f n,k ) = log E x∈O n,n b e -V (x) 1 {V (x)≥(log n) α } ∼ (log n) α-1 .
We also deduce from the previous lower bound that (A1) is satisfied, indeed, as α ∈ (1, 2),

k≥1 Ψ k n,n b (f n,k ) ≥ n -(κ b +ε1)∧1
for any ε 1 > 0 and n large enough. • For (A2), recalling m n = εh n /c 2 (see ( 16)), then by definition f n,j εhn (t 1 , . . . , t j ) = inf s∈[-εhn,εhn] mn f n,mn+j (s 1 , . . . , s mn , t 1 + s mn , . . . , t j + s mn ) = inf

sm n ∈[-εhn,εhn] 1 {tj +sm≥(log n) α } = 1 {tj ≥(log n) α +εhn} .
Observe that for A > 0, n large enough, any l ∈ N and t = (t 1 , . . . , t l ), by definition of

Ψ k n (F |t) (see (18)) and (22) with ε/3A instead of ε k≥1 Ψ k n,n b -H l (t) f n,l+k εhn |t = E x∈On e -V (x) 1 {V (x)+t l ≥(log n) α +εhn} 1 {Hx>n b -H l (t)} ≤ E x∈On e -V (x) 1 {V (x)≥(log n) α -t l } ≤ e δt l -(log n) α-1 (1-ε 3A ) . Moreover, e -(log n) α-1 (1-ε 3A ) = e 2ε 3A (log n) α-1 e -(log n) α-1 (1+ ε 3A ) ≤ e ε A hn k≥1 Ψ k n,n b (f n,k
), the last inequality coming from the fact that h n ∼ (log n) α-1 and ( 23) with m = 0 and as above ε 3A instead of ε. So (A2) is satisfied.

We are left to prove that technical assumptions (A3) and (A4) are realized.

• For (A3), recall first, from Proposition 1, that for all b ∈ [0, 1), Υ k n is the set {t = (t 1 , . . . , t k ) ∈ R k ; H k (t) ≤ n b e εhn , t k ≥ 2 1/3 n /δ 1 , min j≤k t j ≥ -B},
with λ n = ne min(10ε log n,-5hn) = ne -5hn for large n. Let 0 < ε 1 < ε, note that λ n /2 ≥ λ n = ne -6(log n) α-1 so for n large enough

u 1,n = k≥1 Ψ k λn/2,n b (f n,k εhn 1 Υ k n ) = E x∈O λn /2,n b e -V (x) 1 {V (x)≥(log n) α +εhn,Hx≤n b e εhn ,V (x)≥-B} ≥ E x∈O λn ,n b e -V (x) 1 {V (x)≥(log n) α +hn,Hx≤n b e ε 1 3 (log n) α-1 ,V (x)≥-B} ≥ e -(log n) α-1 (1+ ε 1 3 ) ,
where we use that (log n) α > 2 1/3 n /δ 1 for the second equality and the last inequality comes from (23), with m = h n and

ε 1 /3 instead of ε. Moreover, e -(log n) α-1 (1+ ε 1 3 ) = e -2ε 1 3 (log n) α-1 e -(log n) α-1 (1-ε 1 3 ) ≥ e -ε1hn k≥1 Ψ k n,n b (f n,k ) which comes from the fact that h n ∼ (log n) α-1 and (22) with t = 0, ε1 3 instead of ε. • Finally for (A4), recall the definition of u 2,n just below (21). First observe that as α ∈ (1, 2), for n large enough, (log n) α > 1/3 n /δ 1 so for any k Ψ k n (f n,k 1 R\H k 1/3 n /δ 1 ) = E |x|=k e -V (x) 1 {V (x)≥(log n) α ,V (x)< 1/3 n /δ1} 1 {x∈On} = 0. Recall that E[W ] = e ψ(1) = 1 so k≥1 Ψ k n,n b /(log n) 2 (f n,k ) + E W Ψ k n,n b /(W (log n) 2 ) (f n,k ) ≤ k≥1 Ψ k n (f n,k ) + E W Ψ k n (f n,k ) = 2 k≥1 Ψ k n (f n,k ), 2 k≥1 Ψ k n (f n,k ) = 2E[ x∈On e -V (x) 1 {V (x)≥(log n) α } ] ≤ 2e -(log n) α-1 (1-ε 1 6 ) ≤ e -(log n) α-1 (1-ε 1 3 ) thanks to (22) with t = 0, ε 1 /6 instead of ε. Moreover, e -(log n) α-1 (1-ε 1 3 ) = e 2ε 1 3 (log n) α-1 e -(log n) α-1 (1+ ε 1 3 ) ≤ e ε1hn k≥1 Ψ k n,n b (f n,k
). The last inequality comes from the fact that h n ∼ (log n) α-1 and ( 23) with m = 0 and ε1

3 instead of ε. Proof of Theorem 1.2. Here f n,k (t 1 , t 2 , • • • , t k ) = 1 {t k/β ≥(log n) α } with β > 1 and α ∈ (1, 2), let us start with the proof of the two following facts, for all B, δ > 0, ε ∈ (0, ε b ), n large enough, any t ≥ -B and i ∈ N E x, (|x|+i)/β >i e -V (x) 1 {V (x (|x|+i)/β -i )≥(log n) α -t} 1 {x∈On} ≤ e δt-c β (log n) α-1 (1-ε) , (24)
and for any m ≤ log n

E x, (|x|+i)/β >i e -V (x) 1 {V (x (|x|+i)/β -i )≥(log n) α +m} 1 {x∈Υn∩O λn ,n b } ≥ e -c β (log n) α-1 (1+ε) , ( 25
)
with

λ n = ne -6c β (log n) α-1 , for any a > 1 δ1 Υ n = Υ n (ε) := {x ∈ T; H x ≤ n b e εc β (log n) α-1 , V (x) ≥ a log n, V (x) ≥ -B},
and

c β = -1 -π √ β -1/2 + ρ((β -1)π 2 /4) (for ρ see (6)). Recall n = (log n) 3 and introduce L n := (log n) 2+εα with ε α ∈ (0, α -1). Proof of (24) : first note that if t > (log n) α /2, (24) is obviously satisfied, indeed E x, (|x|+i)/β >i e -V (x) 1 {V (x ( (|x|+i)/β -i) )≥(log n) α -t} 1 {x∈On} ≤ E x∈On e -V (x) ,
and by Remark 2, E[ x∈On e -V (x) ] = E[ x∈On e -V (x) ]e δt-δt ≤ n e δt-δ 2 (log n) α ≤ e δt-c β (log n) α-1 for n large enough. Now assume t ≤ (log n) α /2. The expectation in (24) is smaller than

k≤ A n p≥1 1 {p= k+i β -i} E |x|=k e -V (x) 1 {V (xp)≥(log n) α -t} 1 {x∈On} + E |x|> A n e -V (x) 1 {x∈On} ,
with A > 0 such that the last term is smaller than 1/n (Remark 2). Note that p = k+i β -i implies k ≥ βp and as k≤ A n 1 {p= k+i β -i} ≤ β for any p ≥ 1, the above sum is smaller, by the many-to-one Lemma, than

β p≤ A n P S p ≥ (log n) α -t, max j≤ pβ H S j ≤ n + 1 n ≤β A n p=Ln P S p ≥ (log n) α -t, max j≤ pβ H S j ≤ n (26) + β p<Ln P S p ≥ (log n) α -t + 1 n .
For the second sum in (26), by the exponential Markov inequality, for n large enough, all p < L n and t ≥ -B

P S p ≥ (log n) α -t ≤ e δnt-δn(log n) α +pψ(1-δn) ≤ e δn(t+B)- (log n) 2α 2σ 2 Ln +Lnψ(1-δn) ≤ e δt-(1-ε) (log n) 2α 2σ 2 Ln ,
with δ n := (log n) α /σ 2 L n , and we have used that ψ(1 -δ n ) ∈ R + for the second inequality and that δ n → 0 (α ∈ (1, 2)) together with ψ(1) = ψ (1) = 0 and ψ (1) = σ 2 for the last one.

For the first sum in (26), which gives the main contribution, by the Markov property at time p, P S p ≥ (log n) α -t, max j≤ βp H S j ≤ n is smaller than P S p ≥ (log n) α -t, max j≤p H S j ≤ n P max j≤ (β-1)p H S j ≤ n . Then thanks to Lemma 4.6 (79) (with = (log n) 2 , (β -1)p and ε/2 in place of, respectively, k and ε), for n large enough and any p ∈ {L n , . . . , A n } P max

j≤ (β-1)p H S j ≤ n ≤ e -p π 2 σ 2 (β-1) 8(log n) 2 (1-ε 2 ) = e -p π 2 σ 2 (β-1) 8((1-ε/2) -1/2 log n) 2 .
Hence, as log n ≤ (1 -ε/2) -1/2 log n,

A n p=Ln P S p ≥ (log n) α -t, max j≤ pβ H S j ≤ n is smaller than A n p=Ln E 1 {τ (log n) α -t ≤p, max j≤k Sj -Sj ≤(1-ε/2) -1/2 log n} e -p π 2 σ 2 (β-1) 8((1-ε/2) -1/2 log n) 2 ≤ A n E 1 {max j≤τ (log n) α -t Sj -Sj ≤(1-ε/2) -1/2 log n} e -τ (log n) α -t π 2 σ 2 (β-1) 8((1-ε/2) -1/2 log n) 2 ≤ A n e √ 1-ε 2 c β t log n -c β (log n) α-1 (1-ε 2 ) ≤ A n e c β (t+B) log n -c β (log n) α-1 (1-ε 2 ) ≤ 1 3 e δt-c β (log n) α-1 (1-ε) ,
where Lemma 4.1 (with = ((1

-ε/2) -1/2 log n) 2 , r( ) = (log n) α -t, c = π 2 (β -1)/4 and 1 -1 -ε/2 instead of ε)
provides the second inequality. Finally collecting all the upper bounds of the three sums in (26), for n large enough

E x; (|x|+i)/β >i e -V (x) 1 {V (x ( (|x|+i)/β -i) )≥(log n) α -t} 1 {x∈On} ≤ 1 3 e δt-c β (log n) α-1 (1-ε) + βe δt-(1-ε) (log n) 2α 2σ 2 Ln + 1 n ≤ 2 3 e δt-c β (log n) α-1 (1-ε) + e δ(t+B) n ,
which is smaller than e δt-c β (log n) α-1 (1-ε) (we have used that (log n) 2α /L n ≥ (log n) 2(α-1)-εα and (log n) α-1 = o((log n) 2(α-1)-εα )). This yields the upper bound in (24). Proof of (25). Let α n := (log n) α + log n. For all m ≤ log n, by the many-to-one Lemma, the expectation in (25) is larger than p,k≥1

1 {p= (k+i)/β -i} P S p ≥ α n , n b < H S k ≤ n b e εc β (log n) α-1 , max j≤k H S j ≤ λ n , S k ≥ 2 1 3 n δ 1 , S k ≥ -B .
The above probability is larger than (as α n > a log n for all a > 1 δ1 )

P S p ≥ α n , S p ≥ -B, S p = S p , n b < H S k ≤ n b e εc β (log n) α-1 , max j≤k H S j ≤ λ n , min p<j≤k S j ≥ S p .
Recall that H S j = j i=1 e Si-Sj so we have, for any p < j ≤ k, H S j = e Sp-Sj H S p + H S p,j where H S p,j = j i=p+1 e Si-Sj . Note that S p = S p and min p<j≤k S j ≥ S p implies H S j ≤ p + H S p,j so the previous probability is larger than

P S p ≥ α n , S p ≥ -B, S p = S p , max j≤p H S j ≤ λ n , n b < H S p,k ≤n b e εc β (log n) α-1 -p , max p<j≤k H S p,j ≤ λ n -p, min p<j≤k S j ≥ S p ,
which, thanks to the Markov property at time p, is nothing but the product of

P S p ≥ α n , S p ≥ -B, S p = S p , max j≤p H S j ≤ λ n and P n b < H S k-p ≤ n b e εc β (log n) α-1 -p, max j≤k-p H S j ≤ λ n -p = ne -6(log n) α-1 -p, S k-p ≥ 0 . From now, let p ∈ {L n , . . . , n = (log n) 4 }.
We first deal with the second probability. Observe that for all i ≥ 0,

p = (k + i)/β -i implies k -p ≥ (β -1)L n . It follows that for all ε ∈ (0, ε b ), n large enough, for all L n ≤ p ≤ n , k ≥ 1, i ≥ 0 such that p = (k + i)/β -i, P n b < H S k-p ≤ n b e εc β (log n) α-1 -p, max j≤k-p H S j ≤ λ n -p, S k-p ≥ 0 is larger than (as λ n -p ≥ λ n -n ≥ ne -7c β (log n) α-1 ) P n b < H S k-p ≤ n b e ε 2 c β (log n) α-1 , max j≤k-p H S j ≤ ne -7c β (log n) α-1 , S k-p ≥ 0 ≥ e -π 2 σ 2 8 (k-p) (log λ n ) 2 ,
with λ n := n (1+ε/2) -1/2 . The last inequality comes from Lemma 4.6 (80

) (with = (log n) 2 , a = 7, c = εc β 2 , d = α-1
2 , k -p and ε/2 instead respectively of k and ε). The equality p = (k + i)/β -i also implies, for any 0 ≤ i ≤ log n that k -p ≤ (p + log n)(β -1) + β so it follows that the above probability is larger than C exp( π 2 σ 2 (β-1) 8(log λ n ) 2 p) for some positive constant C ∈ (0, 1). Collecting the previous inequalities together with Lemma 4.4 gives, as k≥1 1 {p= (k+i)/β -i} ≥ 1, that for n large enough, the mean in (25) is larger than

C n p=Ln E e - π 2 σ 2 (β-1) 8(log λ n ) 2 p 1 {Sp≥αn,S p ≥-B,Sp=Sp,max j≤p H S j ≤ne -7c β (log n) α-1 } k≥1 1 {p= (k+i)/β -i} ≥ CP(S n ≥ 0) 2 E e - π 2 σ 2 (β-1) 8(log λ n ) 2 τα n 1 {Ln≤τα n ≤ n ,∀j≤τα n :Sj -Sj ≤log λ n } ≥ CP(S n ≥ 0) 2 P(S n ≥ α n )E e - π 2 σ 2 (β-1) 8(log λ n ) 2 τα n 1 {∀j≤τα n :Sj -Sj ≤log λ n } -P(S Ln ≥ α n ).
Note that thanks to (69) and the fact that α ∈ (1, 2), we can find a constant

c (1.2) > 0 such that CP S n ≥ 0 2 P S n ≥ α n ≥ c (1.2) ( n ) -1 ≥ 2e -ε 2 (log n) α-1 . Then applying Lemma 4.1 (with = log λ n , r = α n , c = π 2 (β -1)/4 and 1 + ε/2 -1 instead of ε), for n large enough E e - π 2 σ 2 (β-1) 8(log λ n ) 2 τα n 1 {∀j≤τα n :Sj -Sj ≤log λ n } ≥ e -c β (log n) α-1 (1+ ε 2 ) .
Finally, by Markov inequality, 1+ε) . Collecting the different estimates yields (25).

P(S Ln ≥ α n ) ≤ L n e -c (1.2) α 2 n /Ln for some constant c (1.2) > 0. Since α 2 n /L n ≥ (log n) 2(α-1)-εα and (log n) α-1 = o((log n) 2(α-1)-εα ), we get that P(S Ln ≥ α n ) ≤ e -c β (log n) α-1 (
We are ready to prove that f n satisfies assumptions (A1), (A2), (A3) and (A4). Recall that

Ψ k n,n b (f n,k ) = E |x|=k e -V (x) f n,k (V (x 1 ), . . . , V (x))1 {x∈O n,n b } where x ∈ O n,n b if and only if max j≤|x| H xj ≤ n and H x > n b , U b = {κ ∈ [0, 1]; for all k ≥ 1, t ∈ R k , n ≥ 1 : 1 {H k (t)>n b } f n,k (t) ≤ C ∞ n -κ } with C ∞ = sup n, f n, ∞ .
• Check of (A1) and asymptotic of h n . We obtain from (25) with i = m = 0 and n large enough

E x∈O n,n b e -V (x) 1 {V (x |x|/β )≥(log n) α } ≥ E x∈T e -V (x) 1 {V (x |x|/β )≥(log n) α } 1 {x∈Υn∩O λn ,n b } ≥ e -c β (log n) α-1 (1+ε) .
This implies that for all b ∈ [0, 1), κ b = max U b = 0 (we use a similar argument than in the proof of Theorem 1.1) and additionally with (24), gives, taking i = t = 0

h n = n κ b log k≥1 Ψ k n,n b (f n,k ) = log E x∈O n,n b e -V (x) 1 {V (x |x|/β )≥(log n) α } ∼ c β (log n) α-1 .
We also deduce from the previous lower bound that (A1) is satisfied.

• For (A2), recalling m n = εh n /c 2 (c 2 is defined in ( 16)), by definition, for any j > 0 f n,j εhn (t 1 , . . . , t j ) = inf s∈[-εhn,εhn] mn f n,mn+j (s 1 , . . . , s mn , t 1 + s mn , . . . , t j + s mn ) = inf

sm n ∈[-εhn,εhn] 1 {t (mn+j)/β -mn ≥(log n) α -sm n } = 1 { (mn+j)/β >mn} 1 t (mn+j)/β -mn ≥(log n) α +εhn .
Then for any l ∈ N * and all t = (t 1 , . . . , t l ) ∈ R l , f n,l+k εhn (t 1 , . . . , t l , V (x 1 ) + t l , . . . , V (x) + t l ), with |x| = k, is equal to

1 {mn< (k+i)/β ≤i} 1 {t (k+i)/β -mn ≥(log n) α +εhn} + 1 { (k+i)/β >i} 1 {V (x ( (k+i)/β -i) )+t l ≥(log n) α +εhn} , with i = m n + l. Recall the definition of Ψ . .,. (F |t) in (18), we have k≥1 Ψ k n,n b -H l (t) f n,l+k εhn |t ≤ E x∈On e -V (x) f n,l+k εhn (t 1 , . . . , t l , V (x 1 ) + t l , . . . , V (x) + t l ) ≤ k≥1 1 {mn< (i+k)/β ≤i} 1 {t (i+k)/β -mn ≥(log n) α } Ψ k n (1) + E x; (|x|+i)/β >i e -V (x) 1 {V (x ( (|x|+i)/β -i) )≥(log n) α -t l } 1 {x∈On} . k≥1 1 {mn< (i+k)/β ≤i} 1 {t (i+k)/β -mn ≥(log n) α } Ψ k n (1) is equal to l p=1 1 {tp≥(log n) α } k≥1 Ψ k n (1)1 {p= i+k β -mn} ≤ β l p=1 1 {tp≥(log n) α } ,
where we have used that k≥1

Ψ k n (1)1 {p= i+k β -mn} ≤ e ψ(1) k≥1 1 {p= i+k β -mn} ≤ β. Also by (24) with i = m n + l, t = t l and ε 4A instead of ε, E x; (|x|+i)/β >i e -V (x) 1 {V (x ( (|x|+i)/β -i) )≥(log n) α -t l } 1 {x∈On} ≤ e δt l -c β (log n) α-1 (1-ε 4A ) , so k≥1 Ψ k n,n b -H l (t) f n,l+k εhn |t ≤ β l p=1 1 {tp≥(log n) α } + 1 2 e δt l -c β (log n) α-1 (1-ε 3A ) .
Note that β l p=1 1 {tp≥(log n) α } is very small for n large enough, any l < A n and H l (t) ≤ n. Indeed,

l p=1 e δ(tp-t l ) ≤ lH l (t) δ ≤ A n n δ so β l p=1 1 {tp≥(log n) α } = e δt l β l p=1 e δ(tp-t l ) e -δtp 1 {tp≥(log n) α } ≤ e δt l βA n n δ e -δ(log n) α , which, as α ∈ (1, 2), is smaller than 1 2 e δt l -c β (log n) α-1 (1-ε 3A ) . Finally observe that e -c β (log n) α-1 (1-ε 3A ) = e c β (log n) α-1 2ε 3A e -c β (log n) α-1 (1+ ε 3A ) ≤ e ε A hn k≥1 Ψ k n,n b (f n,k ),
where we have used that h n ∼ c β (log n) α-1 and (25) with i = m = 0.

We are left to prove that the technical assumptions (A3) and (A4) are realized. The ideas are very similar to those of the proof of these two assumptions in the previous theorem, we give details here however to keep the proofs independent from one another.

• For (A3), recall that Υ k n is the set

{t = (t 1 , . . . , t k ) ∈ R k ; H k (t) ≤ n b e εhn , t k ≥ 2 1/3 n /δ 1 , min j≤k t j ≥ -B}. Let 0 < ε 1 < ε and recall that λ n = ne -5hn . Note that λ n /2 ≥ λ n = ne -6(log n) α-1 so the sum k≥1 Ψ k λn/2,n b (f n,k εhn 1 Υ k n ) is larger than k≥1 Ψ k λn,n b (f n,k εhn 1 Υ k n ) which is nothing but E x∈O λn ,n b e -V (x) 1 { |x|+mn β >mn} 1 {V (x (|x|+mn)/β -mn )≥(log n) α +εhn,Hx≤n b e εhn ,V (x)≥ 2 δ 1 1 3 n ,V (x)≥-B} ≥ E x, (|x|+mn)/β >mn e -V (x) 1 {V (x (|x|+mn )/β -mn )≥(log n) α +hn} 1 {x∈Υn( ε 1 3 )∩O λn ,n b } ≥ e -c β (log n) α-1 (1+ ε 1 3 ) ,
where this last inequality comes from (25) with i = m = m n and ε 1 /3 instead of ε. Moreover,

e -c β (log n) α-1 (1+ ε 1 3 ) = e -2ε 1 3 c β (log n) α-1 e -c β (log n) α-1 (1-ε 1 3 ) ≥ e -ε1hn k≥1 Ψ k n,n b (f n,k
), the last inequality comes from the fact that h n ∼ c β (log n) α-1 and (24) with i = t = 0.

• For (A4), first observe that for all k ∈ N * and α ∈ (1, 2), (log n) α -

1/3 n /δ 1 > log n for n large enough so Ψ k n (f n,k 1 R\H k 1/3 n /δ 1 ) = E |x|=k e -V (x) 1 {V (x |x|/β )≥(log n) α ,V (x)< 1/3 n /δ1} 1 {x∈On} ≤ E |x|=k e -V (x) 1 {V (x)≥(log n) α ,V (x)< 1/3 n /δ1} 1 {V (x)-V (x)≤log n} = 0. Recall that W = |z|=1 e -V (z) and k≥1 Ψ k n,n b /(log n) 2 (f n,k ) + E W Ψ k n,n b /(W (log n) 2 ) (f n,k ) ≤ k≥1 Ψ k n (f n,k ) + E W Ψ k n (f n,k ) , which is equal to 2 k≥1 Ψ k n (f n,k ) since E[W ] = e ψ(1)
= 1 and thanks to (24) with i = t = 0 and ε1 4 in place of ε

2 k≥1 Ψ k n (f n,k ) = 2E x∈On e -V (x) 1 {V (x |x|/β )≥(log n) α } ≤ 2e -c β (log n) α-1 (1-ε 1 4 ) ≤ e -c β (log n) α-1 (1-ε 1 3 ) . Moreover, e -c β (log n) α-1 (1-ε 1 3 ) = e 2ε 1 3 c β (log n) α-1 e -c β (log n) α-1 (1+ ε 1 3 ) ≤ e ε1hn k≥1 Ψ k n,n b (f n,k
), the last inequality comes from the fact that h n ∼ c β (log n) α-1 and (25) with i = m = 0.

Proof of Theorem 1.3. Assume first that a = d = 1 and α ∈ (1, 2) which corresponds to the second and third case of the theorem. Let us start with the proof of the two facts, note that we distinguish whether b = 0 or b ∈ (0, 1/2). Facts for the case b = 0 : for all B, δ > 0, ε ∈ (0, ε b ) and n large enough, for any t ≥ -B,

E x∈On e -V (x) j≤|x| H xj 1 {V (x)≥(log n) α -t} ≤ e δt-2(log n) α/2 (1-ε) , (27)
and for all 0

≤ m ≤ log n, 0 ≤ M ≤ e (log n) α/2 E x∈T e -V (x) 1 {x∈Υn,1∩O λ n,1 } M |x| + j≤|x| H xj 1 {V (x)≥(log n) α +m} ≥ e -2(log n) α/2 (1+ε) , ( 28
) with λ n,1 = ne -12(log n) α/2 and Υ n,1 = Υ n,1 (ε) := {x ∈ T; H x ≤ e 2ε(log n) α/2 , V (x) ≥ -B}.
We first deal with the upper bound (27

). Note that if t > (log n) α /2, then (27) is obviously satisfied. Indeed, ( j≤|x| H xj ) -1 1 {V (x)≥(log n) α -t} ≤ 1 so for n large enough E x∈On e -V (x) j≤|x| H xj 1 {V (x)≥(log n) α -t} ≤ E x∈On e -V (x) e -δt e δt ≤ n e δt-δ 2 (log n) α ≤ e δt-2(log n) α/2 (1-ε) ,
where we have used Remark 2. Now assume t ≤ (log n) α /2, by the many-to-one Lemma, the expectation in ( 27) is smaller than

k≤ A n E 1 k j=1 H S j 1 {τ (log n) α -t ≤k, max j≤k H S j ≤n} + E |x|> A n e -V (x) 1 {x∈On} , (29)
the second sum is treated as usual : Remark 2 with a chosen A, together with the fact that α ∈ (1, 2)

and t ≥ -B implies that E |x|> A n e -V (x) 1 {x∈On} ≤ 1/n ≤ 1 2 e δt-2(log n) α/2 (1-ε) . Also using that ( k j=1 H S j ) -1 ≤ e -max j≤k Sj -Sj leads to k≤ A n E 1 k j=1 H S j 1 {τ (log n) α -t ≤k, max j≤k H S j ≤n} ≤ A n E e -max j≤τ (log n) α -t Sj -Sj . Since t < (log n) α /2, (log n) α -t > (log n) α /2 so by Lemma 4.2 with ε 2 instead of ε and any t ≥ -B E e -max j≤τ (log n) α -t Sj -Sj ≤ e -2(1-ε 2 ) √ (log n) α -t ≤ e -2(1-ε 2 ) (log n) α -(t+B) √ (log n) α +B ≤ 1 2 e δt-2(log n) α/2 (1-ε) .
This treats the first sum in (29) and yields (27).

We now turn to the lower bound (28). Recall n = (log n) 4 , using that

k j=1 H S j ≤ k max j≤k H S j
and the fact that m ≤ log n, 0 ≤ M ≤ e (log n) α/2 and λ n,1 > e (log n) α/2 , we obtain thanks to the many-to-one Lemma

E x∈T e -V (x) 1 {x∈Υn,1∩O λ n,1 } M |x| + j≤|x| H xj 1 {V (x)≥(log n) α +m} ≥ k≤ n E 1 2ke (log n) α/2 1 {S k ≥αn, max j≤k H S j ≤e (log n) α/2 , S k ≥-B, S k =S k } ≥ e -(log n) α/2 2 n k≤ n P S k ≥ α n , max j≤k H S j ≤ e (log n) α/2 , S k ≥ -B, S k = S k ,
where α n = (log n) α + log n. By Lemma 4.5 (with = (log n) 2 , t = α n , d = α/4 and a = 0), the previous probability is larger than e -(log n) α/2 (1+ ε 2 ) . Finally collecting the inequalities, we get (28). Facts for the case b ∈ (0, 1/2) : for any t ≥ -B, r ≥ 0 and w > 0

E x∈On e -V (x) 1 {r+Hx>n b /(w(log n) 2 )} r + j≤|x| H xj 1 {V (x)≥(log n) α -t} ≤ (w + 1)n -b e δt-1-ε b (log n) α-1 . ( 30
) Also for all 0 ≤ m ≤ log n, 0 ≤ M ≤ n b E x∈T e -V (x) 1 {x∈Υn,2∩O λ n,2 ,n b } M |x| + j≤|x| H xj 1 {V (x)≥(log n) α +m} ≥ n -b e -1+ε b (log n) α-1 , (31)
with λ n,2 = ne -6 b (log n) α-1 and Υ n,2 = Υ n,2 (ε) := {x ∈ T; H x ≤ n b e ε b (log n) α-1 , V (x) ≥ -B}.
We first deal with the upper bound (30). We split the sum according to the generation of x: when |x| > A n , we use that 1 {r+Hx>n b /(w(log n) 2 ),V (x)≥(log n) α -t} (r + j≤|x| H xj ) -1 ≤ 1 so the expectation in (30) is smaller than

E |x|> A n e -V (x) 1 {x∈On} + E |x|≤ A n e -V (x) 1 {r+Hx>n b /(w(log n) 2 )} r + j≤|x| H xj 1 {V (x)≥(log n) α -t} 1 {x∈On} .
Then, when |x| ≤ A n , we again split the sum but this time according to max j≤|x| H xj : when

max j≤|x| H xj > n b e 1 b (log n) α-1 , we use that 1 {r+Hx>n b /(w(log n) 2 ),V (x)≥(log n) α -t} (r+ j≤|x| H xj ) -1 ≤ (max j≤|x| H xj ) -1 ≤ n -b e -1 b (log n) α-1 . Otherwise, one can observe that 1 {r+Hx>n b /(w(log n) 2 )} (r + j≤|x| H xj ) -1 ≤ 1 {r+Hx>n b /(w(log n) 2 )} (r + H x ) -1 ≤ wn -b (log n) 2 .
Therefore, the expectation in (30) is smaller than

E |x|> A n e -V (x) 1 {x∈On} + E |x|≤ A n e -V (x) 1 {x∈On} n -b e -1 b (log n) α-1 + wn -b (log n) 2 E |x|≤ A n e -V (x) 1 {V (x)≥(log n) α -t, max j≤|x| Hx j ≤n b e 1 b (log n) α-1 } ,
which, by Remark 2 and the many-to-one Lemma, is smaller, for n large enough, than

1 n + n n -b e -1 b (log n) α-1 + wn -b (log n) 2 k≤ A n P S k ≥ (log n) α -t, max j≤k H S j ≤ n b e 1 b (log n) α-1 . Also, k≤ A n P S k ≥ (log n) α -t, max j≤k H S j ≤ n b e -1 b (log n) α-1 is smaller than A n P max j≤τ (log n) α -t S j -S j ≤ b log n + 1 b (log n) α-1 ≤ e t log n -1 b (log n) α-1 (1-ε 2 ) ,
where Lemma A.3 in [START_REF] Hu | The potential energy of biased random walks on trees[END_REF] provides us the last inequality for n large enough and any t. Finally, note that for any δ > 0, n large enough, any w > 0 and any t ≥ -B,

1/n ≤ 1 3 n -b e -δB-1-ε b (log n) α-1 ≤ w+1 3 n -b e δt-1-ε b (log n) α-1 , n n -b e -1 b (log n) α-1 ≤ 1 3 n -b e -δB-1-ε b (log n) α-1 ≤ w+1 3 n -b e δt-1-ε b (log n) α-1 , wn -b (log n) 2 e t log n -1 b (log n) α-1 (1-ε 2 ) ≤ w+1 n b (log n) 2 e t+B log n -1 b (log n) α-1 (1-ε 2 ) ≤ w+1 3n b e δt-1-ε b (log n) α-1
and this finish the proof of the first fact. We now turn to the lower bound (31). By the many-toone Lemma, for any m ≤ log n, 0 ≤ M ≤ n b and A > 0, the mean in (31) is larger than (as

λ n,2 > n b e ε 3b (log n) α-1 ) k≤ A n E 1 kn b + k j=1 H S j 1 {S k ≥αn,max 1≤j≤k H S j ≤n b e ε 3b (log n) α-1 ,H S k >n b ,S k ≥-B} ≥ n -b 2A n e -ε 3b (log n) α-1 k≤ A n P S k ≥ α n , max 1≤j≤k H S j ≤ n b e ε 3b (log n) α-1 , H S k > n b , S k ≥ -B , with α n := (log n) α + log n. By Lemma 4.3 (77) (with = (log n) 2 , t = α n , q = b, a b = -a = -ε 3b , d = α-1 2 and c = ε 3b ) the above sum is larger, for n large enough, than e -1 b (log n) α-1 (1+ ε 2 ) ≥ 2A n e -1 b (log n) α-1 (1+ε)
, which completes the proof of the upper bound.

We are ready to prove that f n satisfies assumptions (A1), (A2), (A3) and (A4).

• Check of (A1) and asymptotic of h n . (28) with m = M = 0 implies, for b = 0 and n large enough

k≥1 Ψ k n (f n,k ) ≥ E x∈T e -V (x) j≤|x| H xj 1 {V (x)≥(log n) α } 1 {x∈Υn,1∩O λ n,1 } ≥ e -2(log n) α/2 (1+ε) .
This implies that κ 0 = max U 0 = 0 (see the part concerning κ b in the proof of Theorem 1.1 for details) and additionally with (27) and t = 0

h n = n κ b log k≥1 Ψ k n,n b (f n,k ) ∼ 2(log n) α/2 .
We also deduce from the previous lower bound that (A1) is satisfied. From (30) with r = t = 0, w = 1 and ε 2 instead of ε, we get for all b ∈ (0, 1) and n large enough

k≥1 Ψ k n,n b (f n,k ) ≤ E x∈On e -V (x) 1 {Hx>n b /(log n) 2 } j≤|x| H xj 1 {V (x)≥(log n) α } ≤ n -b e -1-ε b (log n) α-1
.

This implies that for all b ∈ (0, 1), κ b ≥ b. From (31) with m = M = 0, we get that for all b ∈ (0, 1)

k≥1 Ψ k n,n b (f n,k ) ≥ E x∈T e -V (x) j≤|x| H xj 1 {V (x)≥(log n) α } 1 {x∈Υn,2∩O λ n,2 ,n b } ≥ n -b e -1+ε b (log n) α-1
.

This implies that for all b ∈ (0, 1/2), κ b ≤ b. Finally, for any b ∈ (0, 1/2), κ b = b and

h n = n κ b log k≥1 Ψ k n,n b (f n,k ) ∼ 1 b (log n) α-1 .
We also deduce from the previous lower bound that (A1) is satisfied.

• For (A2), recalling m n = εh n /c 2 (see ( 16)) and for all s = (s 1 , . . . , s mn ) ∈ R mn , t = (t 1 , . . . , t k ) ∈ R k , with u = (s 1 , . . . , s mn , t 1 + s mn , . . . , t k + s mn )

f n,mn+k (s 1 , . . . , s mn , t 1 + s mn , . . . , t k + s mn ) =

1 {t k +sm n ≥(log n) α } 1 mn+k j=1 H j (u) . ( 32
)
Note that mn+k j=1

H j (u) = mn j=1 H j (s) + k j=1 e -tj H mn (s) + H j (t)) ≥ k j=1 H j (t so f n,k εhn (t 1 , . . . , t k ) = inf s∈[-εhn,εhn] mn f n,mn+k (s 1 , . . . , s mn , t 1 + s mn , . . . , t k + s mn ) ≤ inf sm n ∈[-εhn,εhn] 1 {t k +sm n ≥(log n) α } 1 k j=1 H j (t) = 1 {t k ≥(log n) α +εhn} k j=1 H j (t)
.

It follows that f n,k εhn (t 1 , . . . , t k ) ≤ 1 {t k ≥(log n) α } k j=1 H j (t j ) -1 and for |x| = k with u x = (t 1 , . . . , t l , V (x 1 ) + t l , . . . , V (x) + t l ) f n,l+k εhn (t 1 , . . . , t l , V (x 1 ) + t l , . . . , V (x) + t l ) ≤ 1 {V (x)≥(log n) α -t l } 1 l+k j=1 (u x ) . Assume b = 0. Observe again that l+k j=1 (u x ) = l j=1 H j (t) + k j=1 e -V (xj ) H l (t) + H xj ≥ j≤k H xj . Then, by definition of Ψ k n F |t (see (18)), for all A, B, ε, δ > 0, n large enough, for any l ∈ N * and all t = (t 1 , . . . , t l ) ∈ R l with t l ≥ -B k≥1 Ψ k n,n b -H l (t) f n,l+k εhn |t ≤ E x∈On e -V (x) f n,l+k εhn (t 1 , . . . , t l , V (x 1 ) + t l , . . . , V (x) + t l ) ≤ E x∈On e -V (x) 1 {V (x)≥(log n) α -t l } 1 j≤k H xj ≤ e δt l -2(log n) α/2 (1-ε 3A ) ,
where we have used (27) with t = t l and replaced ε by ε 3A for the last inequality. Finally, observe that

e -2(log n) α/2 (1-ε 3A ) = e 4ε 3A (log n) α/2 e -2(log n) α/2 (1+ ε 3A ) ≤ e ε A hn k≥1 Ψ k n,n b (f n,k ),
where we have used that h n ∼ 2(log n) α/2 and (28

) with m = M = 0. Assume b ∈ (0, 1/2). Note that l+k j=1 H j (u x ) ≥ H l (t) + j≤k H xj .
Then for all A, B, ε, δ > 0, n large enough, for any l ∈ N * and all t = (t 1 , . . . ,

t l ) ∈ R l with t l ≥ -B k≥1 Ψ k n,n b -H l (t) f n,l+k εhn |t ≤ E x∈On e -V (x) 1 {V (x)≥(log n) α -t l } H l (t) + j≤|x| H xj 1 {H l (t)+Hx>n b /(log n) 2 } ≤ 2n -b e δt l -1 b (log n) α-1 (1-ε 4A ) ≤ n -b e δt l -1 b (log n) α-1 (1-ε 3A ) ,
where we have used (30) with r = H l (t), w = 1, t = t l and ε 4A instead of ε for the last inequality. Finally, observe that

n -b e δt l -1 b (log n) α-1 (1-ε 3A ) = e 2ε 3bA (log n) α-1 n -b e -1 b (log n) α-1 (1+ ε 3A ) ≤ e ε A hn k≥1 Ψ k n,n b (f n,k ),
where we have used that h n ∼ 1 b (log n) α-1 and (31) with m = M = 0.

We are left to prove that technical assumptions (A3) and (A4) are realized.

• For (A3), recall that

Υ k n = {t = (t 1 , . . . , t k ) ∈ R k ; H k (t) ≤ n b e εhn , V (x) ≥ 2 1/3
n /δ 1 , t k ≥ -B}. By (32), for |x| = k with v x = (s 1 , . . . , s mn , V (x 1 ) + s mn , . . . , V (x) + s mn )

f n,k εhn (V (x 1 ), . . . , V (x)) = inf s∈[-εhn,εhn] mn 1 {V (x)+sm n ≥(log n) α } 1 mn+k j=1 H j (v x )
, and recall that mn+k j=1

H j (v x ) = mn j=1 H j (s) + k j=1 e -V (xj ) H mn (s) + H xj . For |x| = k such that V (x) ≥ -B, observe, as s ∈ [-εh n , εh n ] mn , that mn+k j=1 H j (v x ) ≤ m n e 2εhn + km 2 n e 2εhn+B + k j=1 H xj . Also recall, by definition, that h n ≥ (log n) γ for γ ∈ (0, 1) so mn+k j=1 H j (v x ) ≤ 2km 2 n e 2εhn+B + k j=1 H xj ≤ ke 3εhn + k j=1 H xj . It follows that f n,k εhn (V (x 1 ), . . . , V (x)) ≥ 1 {V (x)≥(log n) α +εhn} ke 3εhn + k j=1 H xj -1 . Let 0 < ε 1 < ε and recall λ n = ne -5hn ≥ 2λ n,i , i ∈ {1, 2}.
Thanks to the previous inequality and the fact that (log n) α > 2

1/3 n /δ 1 , we have k≥1 Ψ k λn/2,n b (f n,k εhn 1 Υ k n ) ≥ E x∈O λ n,i ,n b e -V (x) 1 {V (x)≥(log n) α +εhn} |x|e 3εhn + j≤|x| H xj 1 {Hx≤n b e εhn ,V (x)≥-B} .
Assume b = 0. By (28) with m = h n , M = e (log n) α/2 and ε1 3 instead of ε, together with the fact that h n ∼ 2(log n) α/2 , for n large enough k≥1

Ψ k λn/2 (f n,k εhn 1 Υ k n ) ≥ E x∈T e -V (x) 1 {V (x)≥(log n) α +hn} |x|e (log n) α/2 + j≤|x| H xj 1 {x∈Υn,1( ε 1 3 )∩O λ n,1 } ≥ e -2(log n) α/2 (1+ ε 1 3 ) . Moreover, e -2(log n) α/2 (1+ ε 1 3 ) = e -4ε 1 3 (log n) α/2 e -2(log n) α/2 (1-ε 1 3 ) ≥ e -ε1hn k≥1 Ψ k n,n b (f n,k
), the last inequality comes from the fact that h n ∼ 2(log n) α/2 and (27) with t = 0. Assume b ∈ (0, 1/2). By (31) with m = h n and M = n b , together with the fact that

h n ∼ 1 b (log n) α-1 , for n large enough k≥1 Ψ k λn/2,n b (f n,k εhn 1 Υ k n ) ≥ E x∈T e -V (x) 1 {V (x)≥(log n) α +hn} |x|n b + j≤|x| H xj 1 {x∈Υn,2( ε 1 3 )∩O λ n,2 } ≥ n -b e -1 b (log n) α-1 (1+ ε 1 3 ) . Moreover, e -1 b (log n) α-1 (1+ ε 1 3 ) = e -2ε 1 3b (log n) α-1 e -1 b (log n) α-1 (1- ε 1 3 ) ≥ n b e -ε1hn k≥1 Ψ k n,n b (f n,k
), the last inequality comes from the fact that h n ∼ 1 b (log n) α-1 and (30) with r = t = 0, w = 1 and we have used that n b (log n) -2 < n b .

• Finally for (A4), we first observe that for all k ∈ N * and α ∈ (1, 2), (log

n) α > 2 1/3 n /δ 1 for n large enough so Ψ k n (f n,k 1 R\H k 1/3 n /δ 1 ) = E |x|=k e -V (x) k j=1 H xj 1 {V (x)≥(log n) α ,V (x)< 1/3 n /δ1} 1 {x∈On} = 0.
Recall that W = |z|=1 e -V (z) and E[W ] = e ψ(1) = 1 so when b = 0

k≥1 Ψ k n,n b /(log n) 2 (f n,k ) + E W Ψ k n,n b /(W (log n) 2 ) (f n,k ) ≤ k≥1 Ψ k n (f n,k ) + E W Ψ k n (f n,k ) = 2 k≥1 Ψ k n (f n,k ),
and thanks to (27) for n large enough with t = 0

2 k≥1 Ψ k n (f n,k ) = 2E x∈On e -V (x) j≤|x| H xj 1 {V (x)≥(log n) α } ≤ 2e -2(log n) α/2 (1-ε 1 4 ) ≤ e -2(log n) α/2 (1-ε 1 3 ) .
Moreover, e -2(log n) α/2 (1-

ε 1 3 ) = e 4ε 1 3 (log n) α/2 e -2(log n) α/2 (1+ ε 1 3 ) ≤ e ε1hn k≥1 Ψ k n,n b (f n,k
), the last inequality comes from the fact that h n ∼ 2(log n) α/2 and (28) with m = M = 0. Otherwise, b ∈ (0, 1/2) and thanks to (30) for n large enough with r = t = 0, w = 1 and ε1

4 instead of ε k≥1 Ψ k n,n b /(log n) 2 (f n,k ) = x∈On e -V (x) 1 {Hx>n b /(log n) 2 } r + j≤|x| H xj 1 {V (x)≥(log n) α } ≤ 1 n b e -1 b (log n) α-1 (1- ε 1
3 ) , and we also get from (30) with r = t = 0 and w = W that for n large enough

Ψ k n,n b /(W (log n) 2 ) (f n,k ) = E x∈On e -V (x) 1 {Hx>n b /(W (log n) 2 )} r + j≤|x| H xj 1 {V (x)≥(log n) α } ≤ W + 1 n b e -1 b (log n) α-1 (1- ε 1 4 ) . By (5), telling that E[W 2 ] < ∞, we have C 4 := E[W (W + 1) + 1] = E[W 2 + 2] < ∞ and then k≥1 Ψ k n,n b /(log n) 2 (f n,k ) + E W Ψ k n,n b /(W (log n) 2 ) (f n,k ) ≤ C 4 n b e -1 b (log n) α-1 (1- ε 1 4 ) ≤ 1 2n b e -1 b (log n) α-1 (1- ε 1 3 ) . Moreover, e -1 b (log n) α-1 (1- ε 1 3 ) = e ε 1 3b (log n) α-1 e -1 b (log n) α-1 (1+ ε 1 3 ) ≤ n b e ε1hn k≥1 Ψ k n,n b (f n,k
), the last inequality comes from the fact that h n ∼ 1 b (log n) α-1 and (31) with m = M = 0. This completes the proof for these two cases. Assume now α = 1 and a ∈ R (with a > 1/δ 1 when d = 1), which corresponds to the first case of the theorem. As usual, let us first state the following two facts: for all b ∈ [0, 1/(d + 1)), B, δ > 0, ε ∈ (0, ε b ) and n large enough, for any t ≥ -B, r ≥ 0 and w > 0

E x∈On e -V (x) 1 {r+Hx>n b /(w(log n) 2 )} r + j≤|x| H xj d 1 {V (x)≥a log n-t} ≤ (w + 1) 2 n e δt n -bd , (33)
For any 0 ≤ M ≤ n b , ε < b/3 (when b > 0)

E x∈T e -V (x) 1 {x∈Υn∩O λn,n b } M |x| + j≤|x| H xj d 1 {V (x)≥a log n} ≥ 1 2 n n -bd , (34)
with λ n = n 1-11ε and for any a > 1/δ 1

Υ n = Υ n (ε) := {x ∈ T; H x ≤ n b+ε , V (x) ≥ a log n, V (x) ≥ -B}.
These facts ensure that f n satisfies assumptions (A1), (A2), (A3) and (A4) for b ∈ (0, 1/(d + 1)). (A3) does not hold exactly when b = 0 so we use (38) (which appears in the proof of Theorem 1.5) together with the result when b > 0 to conclude this case.

• Check of (A1) and asymptotic of h n . We get from (34) that κ b = max U b ≤ bd and (33) gives κ b ≥ bd. It follows that for all b ∈ [0, 1/(d + 1)), κ b = bd and for any n ≥ 2, h n = log n. Indeed, on the one hand, (33) with r = t = 0 and w = 1 gives, for n large enough

n κ b k≥1 Ψ k n,n b (f n,k ) = n bd E x∈O n,n b e -V (x) k j=1 H xj d 1 {V (x)≥a log n} ≤ 2 d 2 n ,
and on the other hand, we get from (34), for n large enough that

n κ b k≥1 Ψ k n,n b (f n,k ) ≥ 1 2 n .
From these inequalities, we get that for any γ ∈ (0, 1),

| log(n κ b k≥1 Ψ k n,n b (f n,k ))| ≤ 3 log n = o((log n) γ
). Then h n = log n and we also deduce that (A1) is satisfied.

• For (A2), let |x| = k and observe that f n,l+k εhn (t 1 , . . . , t l , V (x 1 ), . . . , V (x)) ≤ (H l (t) + H x ) -d so it follows, for all ε ∈ (0, ε b ), A, δ, B > 0, n large enough, any l ∈ N * , t = (t 1 , . . . , t l ) ∈ R l and t l ≥ -B, by (33) with r = H l (t), t = t l and w = 1

k≥1 Ψ k n,n b -H l (t) f n,l+k εhn |t ≤ 2 d 2 n e δt l n -bd ≤ e δt l + ε A hn k≥1 Ψ k n,n b (f n,k ),
where the last inequality comes from (34).

• For (A3), recall that

Υ k n = {t = (t 1 , . . . , t k ) ∈ R k ; H k (t) ≤ n b+ε , V (x) ≥ 2 1/3 n /δ 1 , t k ≥ -B}. For |x| = k, we have f n,k εhn (V (x 1 ), . . . , V (x)) ≥ 1 {V (x)≥(a+ε)(log n)} kn 3ε + k j=1 H xj -d
, and thanks to (34

) with M = n b , b ∈ (0, 1/(d + 1)) k≥1 Ψ k λn/2,n b (f n,k εhn 1 Υ k n ) ≥ E x∈T e -V (x) 1 {Υn∩O λn,n b } (|x|n b + j≤|x| H xj ) d ≥ 1 2 n n -bd ≥ e -ε1hn k≥1 Ψ k n,n b (f n,k ),
where we recall λ n = n 1-10ε .

• Finally, for (A4) with d = 1 (and then a > 1/δ 1 )

Ψ k n (f n,k 1 R\H k 1/3 n /δ 1 ) = E |x|=k e -V (x) 1 {x∈On} k j=1 H xj d 1 {V (x)≥a log n,V (x)< 1/3 n /δ1} = 0.
Otherwise, d = 0 and for any a ∈ R, thanks to Remark 2

k≥1 Ψ k n (f n,k 1 R\H k 1/3 n /δ 1 ) = E x∈On e -V (x) 1 {V (x)≥a log n,V (x)< 1/3 n /δ1} ≤ E x∈On e -V (x) ≤ n ,
which, thanks to (34), is smaller than e ε1hn k≥1 Ψ k n,n b (f n,k ) for all ε 1 > 0. We get from (33) with r = t = 0 and w = W that for n large enough

Ψ k n,n b /(W (log n) 2 ) (f n,k ) = E x∈On e -V (x) 1 {Hx>n b /(W (log n) 2 )} ( j≤|x| H xj ) d 1 {V (x)≥a log n} ≤ (W + 1) 2 n n -bd . By (5), telling that E[W 2 ] < ∞, we have C 4 := E[W (W + 1) + 1] = E[W 2 + 2] < ∞ and then k≥1 Ψ k n,n b /(log n) 2 (f n,k ) + E W Ψ k n,n b /(W (log n) 2 ) (f n,k ) ≤ 2C 4 n -bd ≤ e ε1hn k≥1 Ψ k n,n b (f n,k ),
where, again, the last inequality comes from (34). This finishes the proof of the result of the theorem for b ∈ (0, 1/(d + 1)). Now assume b = 0 and let ε > 0. Using the result of the theorem with b ε = ε/(2 + d) and the fact that

R n (1 [n bε ,∞) , f n ) ≤ R n (1 [1,∞) , f n ), we get the following lower bound for R n (1 [1,∞) , f n ): P(log + R n (1 [1,∞) , f n ) < (1 -ε) log n) is smaller than P log + R n (1 [n bε ,∞) , f n ) < (1 -(1 + d)b ε -ε/(2 + d)) log n → 0,
where we have used the case b > 0. For the upper bound, we use an intermediate result in the proof of Theorem 1.5: recall that κ 0 = 0 and h n = log n.

Also recall ξ = lim n→∞ h -1 n log(n κ b k≥1 Ψ k n,n b (f n,k )).
It's easy to see that ξ = 0 and by ( 38)

P(log + R n (1 [1,∞) , f n ) > (1 + ε) log n) ≤ P 1 n R n (1 [1,∞) , f n ) > e εhn → 0,
this ends the proof of the theorem for all b ∈ [0, 1/(d + 1)).

Proof of Theorem 1.4.

Here f n,k (t 1 , t 2 , • • • , t k ) = 1 {t k/β ≥(log n) α } ( k/β
j=1 H j (t)) -1 with β > 1 and α ∈ (1, 2). We state the following facts: for all B, δ > 0, ε ∈ (0, ε b ), n large enough, any t ≥ -B and i ∈ N

E x; |x|+i/β >i e -V (x) 1 {x∈On} |x|/β j=1 H xj 1 {V (x (|x|+i)/β -i )≥(log n) α -t} ≤ e δt-2(log n) α/2 (1-ε) , (35)
and for all 0

≤ i, m ≤ log n, 0 ≤ M ≤ e (log n) α/2 E x; |x|+i/β >i e -V (x) 1 {x∈Υn∩O λn } M |x| + |x|/β j=1 H xj 1 {V (x (|x|+i)/β -i )≥(log n) α +m} ≥ e -2(log n) α/2 (1+ε) , (36)
with λ n = ne -12(log n) α/2 and for any a > 1 δ1

Υ n = Υ n (ε) := {x ∈ T; H x ≤ e 2ε(log n) α/2 , V (x) ≥ a log n, V (x) ≥ -B}.
Using these two facts, we follow the same lines as in the previous theorem to prove that h n ∼ 2(log n) α/2 and that (A1) to (A4) are satisfied.

Proof of Theorem 1.5

First, note that Remark 1 implies that ξ = lim n→∞ h -1 n log(n κ b k≥1 Ψ k n,n b (f n,k )) well exists. To prove Theorem 1.5, we first show that Assumptions (A3) and (A4) yield a simpler statement for both lower and upper bound of Proposition 1. This implies a convergence in probability for stopped ranges R T kn with k n = n/(log n) 3/2 and R T n . Then, we use a result of [HS16b] (Proposition 2.4) implying that T n /(n log n) converges in probability to a positive limit in order to obtain the result for R n . Let us start with the Lower bound : Recalling the expression of 20)), together with (A3) choosing ε 1 = min(1, c 5 ) ε 4 (see Proposition 1 for c 5 ), we get

u 1,n = k≥1 Ψ k λn/2,n b (f n,k εhn 1 Υ k n ) (see below (
u 1,n ≥ e -min(1,c5) ε 4 k≥1 Ψ k n,n b f n,k .
This, together with the fact that, by definition of ξ, n

κ b k≥1 Ψ k n,n b (f n,k
) > e (ξ-ε)hn for n large enough, implies

P R T kn (g n , f n ) n 1-b-κ b ϕ(n b ) < e (ξ-7ε)hn ≤ P R T kn (g n , f n ) n 1-b ϕ(n b ) k≥1 Ψ k n,n b (f n,k ) < e -6εhn ≤ P R T kn (g n , f n ) n 1-b ϕ(n b )u 1,n < e -5εhn .
Also considering (20), P

R T kn (gn,f n ) n 1-b ϕ(n b )u1,n < e -5εhn
is smaller than e (-c5+ min(1,c 5 )

2

)εhn + h n e -εhn + e -min(ε log n,3hn)+min(1,c5) ε 2 hn

n κ b k≥1 Ψ k n,n b (f n,k ) 2 ≤ e -εc 5 2 hn + h n e -εhn + e -min(ε log n,3hn)+ ε 2 hn+2| log(n κ b k≥1 Ψ k n,n b (f n,k ))| .
Now, thanks to Remark 1, for n large enough, | log(n

κ b k≥1 Ψ k n,n b (f n,k ))| is smaller than ε 8 log n ≤ -min(-ε 8 log n, -h n ) and ε 2 h n is smaller than ≤ -1 2 min(-ε log n, -h n ) so -min(ε log n, 3h n ) + ε 2 h n + 2| log(n κ b k≥1 Ψ k n,n b (f n,k ))| is smaller than -1 2 min(ε log n, h n ).
Finally, for all ε ∈ (0, ε b ) and n large enough

P R T kn (g n , f n ) n 1-b-κ b ϕ(n b
) < e (ξ-7ε)hn ≤ e -εc 5 2 hn + h n e -εc2hn + e -1 4 min(ε log n,hn) , then switching ε by ε/7 in the above probability, we obtain as h n → +∞, the desired expression : for all ε ∈ (0, 7ε b )

lim n→∞ P R T kn (g n , f n ) n 1-b-κ b ϕ(n b ) < e (ξ-ε)hn = 0.
We are now ready to move from R T kn to R n . First note that

P R n (g n , f n ) n 1-b-κ b ϕ(n b ) < e (ξ-ε)hn ≤ P R n (g n , f n ) n 1-b-κ b ϕ(n b ) < e (ξ-ε)hn , T kn ≤ n + P(T kn > n), recalling that R n (g n , f n ) = x∈T g n (L n x )f n,|x| (V (x 1 ), V (x 2 ), • • • , V (x)
) and g n (t) = ϕ(t)1 {t≥n b } with b ∈ [0, 1). Then, as ϕ is non-decreasing and positive, so is g n , hence

T kn ≤ n implies g n (L T kn x ) ≤ g n (L n x ) and therefore R T kn (g n , f n ) ≤ R n (g n , f n ) since f n,k ≥ 0. It follows that P R n (g n , f n ) n 1-b-κ b ϕ(n b ) < e (ξ-ε)hn ≤ P R T kn (g n , f n ) n 1-b-κ b ϕ(n b ) < e (ξ-ε)hn + P(T kn > n),
and thanks to the above convergence, together with the fact that (T n /(n log n)) n convergences in P-probability to an almost surely finite and positive random variable, we obtain the desired expression: for all ε ∈ (0, 7ε b ):

lim n→∞ P R n (g n , f n ) n 1-b-κ b ϕ(n b ) < e (ξ-ε)hn = 0. ( 37
)
Upper bound : we prove the following statement, for all ε > 0

lim n→∞ P R n (g n , f n ) n 1-b-κ b ϕ(n b ) > e (ξ+ε)hn = 0. ( 38
) Recall that u 2,n = k≥1 (Ψ k n (f n,k 1 R k \H k 1/3 n /δ 1 )+Ψ k n,n b /(log n) 2 (f n,k )+E[W Ψ k n,n b /(W (log n) 2 ) (f n,k )]). Assumption (A4) with ε 1 = ε 4 gives that u 2,n ≤ e ε 4 hn k≥1 Ψ k n,n b (f n,k ), so for n large enough, as n κ b k≥1 Ψ k n,n b (f n,k ) ≤ e (ξ+ ε 2 )hn and T n ≥ n P R n (g n , f n ) n 1-b-κ b ϕ(n b ) > e (ξ+ε)hn ≤ P R T n (g n , f n ) n 1-b-κ b ϕ(n b ) > e (ξ+ε)hn ≤ P R T n (g n , f n ) n 1-b ϕ(n b ) k≥1 Ψ k n,n b (f n,k ) > e ε 2 hn ≤ P R T n (g n , f n ) n 1-b ϕ(n b )u 2,n > e ε 4 hn ≤ e -ε 8 hn + o(1),
where the last inequality comes from (21) replacing ε by ε 4 . Then, taking the limit, we get (38). We are now ready to prove the theorem. We split this proof in three parts depending on the values of (recall

) L = lim inf n→∞ h -1 n log n 1-b-κ b ϕ(n b ) . • Assume L ∈ (-ξ, +∞].
For any t ∈ R, e log + t = e log(t∨1) ≥ t so for any ε ∈ (0, ε b ) and n large enough,

P log + R n (g n , f n ) -log(n 1-b-κ b ϕ(n b )) < (ξ -ε)h n is smaller than P e log + Rn(gn,f n ) < n 1-b-κ b ϕ(n b )e (ξ-ε)hn ≤ P R n (g n , f n ) n 1-b-κ b ϕ(n b ) < e (ξ-ε)hn → 0,
where the limit comes from (37). Note that this lower bound remains true even when L ∈ (-ξ, +∞]. However, we need that L ∈ (-ξ, +∞] for the upper bound. Indeed, in this case, for n large enough, n 1-b-κ b ϕ(n b ) > e -ξhn and for any ε > 0, n 1-b-κ b ϕ(n b )e (ξ+ε)hn > e εhn > 1 so for n large enough

P(log + R n (g n , f n ) -log(n 1-b-κ b ϕ(n b )) > (ξ + ε)h n ) = P(log + R n (g n , f n ) > log(n 1-b-κ b ϕ(n b )e (ξ+ε)hn ), R n (g n , f n ) > 1). Moreover, when R n (g n , f n ) > 1, log + R n (g n , f n ) = log R n (g n , f n ) so the previous probability is equal to P log R n (g n , f n ) > log(n 1-b-κ b ϕ(n b )e (ξ+ε)hn ), R n (g n , f n ) > 1 ≤ P R n (g n , f n ) n 1-b-κ b ϕ(n b )
> e (ξ+ε)hn .

Then, taking the limit, we get the result thanks to (38).

• Assume L = -ξ. Recall that ∆ n = h -1 n log(n 1-b-κ b ϕ(n b ))-inf ≥n h -1 log( 1-b-κ b ϕ( b )). L = -ξ implies that for any ε ∈ (0, ε b ) and n large enough, inf ≥n h -1 log( 1-b-κ b ϕ( b )) > -ξ -ε 2 so h n ∆ n < log(n 1-b-κ b ϕ(n b )) + (ξ + ε 2 )h n and as e log + t ≥ t P h -1 n log + R n (g n , f n ) < -ε + ∆ n ≤ P R n (g n , f n ) < e -εhn+hn∆ n ≤ P R n (g n , f n ) n 1-b-κ b ϕ(n b ) < e (ξ-ε 2 )hn → 0,
where the limit comes from (37). Also, L = -ξ implies that for any ε ∈ (0, ε b ) and n large enough, inf ≥n h

-1 log( 1-b-κ b ϕ( b )) < -ξ + ε 2 so h n ∆ n > log(n 1-b-κ b ϕ(n b )) + (ξ -ε 2 )h n and as h n (ε+∆ n ) > 0, P(h -1 n log + R n (g n , f n ) > ε+∆ n ) = P(log R n (g n , f n ) > h n (ε+∆ n ), R n (g n , f n ) > 1) which is smaller than P R n (g n , f n ) > e εhn+hn∆ n ≤ P R n (g n , f n ) n 1-b-κ b ϕ(n b ) > e (ξ+ ε 2 )hn → 0,
where the limit comes from (38).

• Assume L ∈ [-∞, -ξ). In this case, there exists an increasing sequence (n ) of positive integers (with n = when lim ξ+2ε L )hn and for any ε > 0

h -1 n log(n 1-b-κ b ϕ(n b )) = L) and ε L > 0 such that for any ∈ N * , n 1-b-κ b ϕ(n b ) < e -(
P R n (g n , f n ) > ε ≤ P R n (g n , f n ) > e -ε L hn ≤ P R n (g n , f n ) n 1-b-κ b ϕ(n b ) > e (ξ+ε L )hn → 0,
where the limit comes from (38) with ε = ε L , which ends the proof.

Proof of Proposition 1

The proof of Proposition 1 is decomposed as follows. In the first short section below, we present the expression of the generating function with constraint of edge local time. In a second sub-section, we prove the lower bound (20), this section is itself decomposed in different steps treating successively the random walk at fixed environment and then an important quantity of the environment. Finally, in a third section, we obtain the upper bound (21). Note that the fact that the upper and the lower bounds are robust when replacing T n by T kn with k n = n/(log n) p , with p > 0, does not need extra arguments than the ones that follow.

Preliminary

We first introduce the edge local time N n x of a vertex x ∈ T, that is the number of times the random walk X visits the edge (x * , x) before the instant n:

N n x := n i=1 1 {Xi-1=x * , Xi=x} , (39)
the law of N T 1 x (recall that T 1 is the instant of the first return to the root e) and y;y * =x N T 1 y at fixed environment, that is under P E , are given by Lemma 3.1. Let x ∈ T, and

T x := inf{k > 0, X k = x}, then P E (T x < T 1 ) = e -V (x) /H x and for any i ∈ N * , s ∈ [0, 1] and ν ≥ 0, i) The distribution of N T 1 x under P E x (•) = P E (•|X 0 = x) is geometrical on N with mean H x -1 = 1≤j<|x| e V (xj )-V (x) .
In particular

E E s νN T 1 x 1 {N T 1 x ≥i} = e -V (x) H 2 x 1 - 1 H x i-1 s iν 1 -s ν (1 -1 Hx )
.

ii) For any z ∈ T such that z * = x, the distribution of y;y * =x N T 1 y under P E z is geometrical on N with mean Hx := H x y;y * =x e -Vx(y) with V x (y) = V (y) -V (x) . In particular

E E s ν y;y * =x N T 1 y 1 { y;y * =x N T 1 y ≥i} = e -V (x) H x Hx (1 + Hx ) 2 1 - 1 1 + Hx i-1 s iν 1 -s ν (1 -1 1+ Hx
) .

Proof. The fact that P E (T x < T 1 ) = e -V (x) /H x comes from a standard result for one-dimensional random walks in random environment, see for example [START_REF] Golosov | Localization of random walks in one-dimensional random environments[END_REF]. The proofs of points i) and ii) are very similar and elements for the first one can be found in [AD20] so we will only deal with the second one.

For any x ∈ T, min y;y * =x T y is the first hitting time of the set {y ∈ T; y * = x} of children of x and let β x := P E x (min y;y * =x T y < T 1 ) be the quenched probability, starting from x, to reach a children of x before hitting the root e. Hence, y;y * =x N T 1 y is the number of times the random walk X visits the «edge» (x, {y ∈ T; y * = x}) before the instant T 1 . It follows, thanks to the strong Markov property, that for all z ∈ T such that x * = z and k ∈ N

P E z y;y * =x N T 1 y = k = β k x (1 -β x ). ( 40
)
Note that the right part above does not depend on z. We now compute β x . On the one hand, thanks to (40), we have

E E z [ y;y * =x N T 1 y ] = β x /(1 -β x )
and on the other hand, thanks to the first point,

E E z [ y;y * =x N T 1 y ] = y;y * =x E E z [N T 1 y ] = y;y * =x (H y -1) = H x y;y * =x e -Vx(y) = Hx .
N T 1 y = k = α x β k-1 x (1 -β x ) and P E y;y * =x N T 1 y = 0 = 1 -α x ,
so on the one hand, E E [ y;y * =x N T 1 y ] = α x /(1-β x ) and on the other hand, thanks to the first point, y) . It follows that α x = y;y * =x e -V (y) /(1+ Hx ) and the result is proved.

E E [ y;y * =x N T 1 y ] = y;y * =x E E [N T 1 y ] = y;y * =x e -V (

Lower bound for R

T n (g n , f n ) Let us first introduce two key random variables denoted R T n (f n ) and R(f n ). R T n (f n ) is a simplified version of R T n (g n , f n )
which does not depend on the function g n and with a constraint on V : recall λ n = ne -min(10ε log n,5hn) and H k zn = {(t 1 , . . . , t k ) ∈ R k ; t k ≥ z n } where we set for convenience

z n := 1/3 n /δ 1 with n = (log n) 3 and δ 1 ∈ (0, 1/2) (see (5)), then R T n (f n ) := n i=1 x∈O λn ,n b 1 {N T i x -N T i-1 x ≥n b } 1 {∀j =i:N T j x -N T j-1 x =0} f n,|x| 1 H |x| zn (V x ),
where we use the notation

F (V x ) = F (V (x 1 ), • • • , V (x)). Note that the local time until T n which appears in R T n (g n , f n ) is replaced in R T n (f n
) by edge local times excursion by excursion. Also, visited vertices are restricted to some V -regular lines O λn,n b . R T n (g n , f n ) and R T n (f n ) are related as follows, first since ϕ is non-decreasing

R T n (g n , f n ) ≥ ϕ(n b ) x∈T 1 {L T n x ≥n b } f n,|x| 1 H |x| zn (V x ). Then, introduce E n x = n i=1 1 {L T i x -L T i-1 x ≥1}
, the number of excursions to the root where the walk hits vertex x. Notice that E n x = 1 if and only if there exists i ∈ {1, . . . , n} such that

L T i x -L T i-1
x ≥ 1 and for any j ∈ {1, . . . , n}, j = i,

L T j x -L T j-1 x = 0 that is N T j x -N T j-1 x = 0. Thus x∈T 1 {L T n x ≥n b } f n,|x| 1 H |x| zn (V x ) ≥ x∈O λn,n b 1 {L T n x ≥n b ,E n x =1} f n,|x| 1 H |x| zn (V x ) ≥ n i=1 x∈O λn ,n b 1 {L T i x -L T i-1 x ≥n b } 1 {∀j =i: N T i x -N T i-1 x =0} f n,|x| 1 H |x| zn (V x ),
so finally, as

L T i x -L T i-1 x ≥ N T i x -N T i-1
x , we have the following relation

R T n (g n , f n ) ≥ ϕ(n b )R T n (f n ). ( 41
)
The second random variable R(f n ) depends only on the environment :

R(f n ) := x∈O λn ,n b e -V (x) 1 H x 1 - 1 H x n b -1 f n,|x| 1 H |x| zn (V x ),
it can be related to the quenched mean of R T n (f n ) as follows

1 ≤ nR(f n ) E E [R T n (f n )] ≤ (1 -e -zn ) -(n-1) . ( 42
)
Indeed, the random variables

N T i x -N T i-1
x , i ∈ {1, . . . , n}, are i.i.d under P E so,

E E [R T n (f n )] = n x∈O λn ,n b P E (N T 1 x ≥ n b )P E (N T 1 x = 0) n-1 f n,|x| 1 H |x| zn (V x ).
Moreover, on the event {V (x) ≥ z n }, thanks to Lemma 3.1,

P E (N T 1 x = 0) n-1 = P E (T x > T 1 ) n-1 = (1 -e -V (x) /H x ) n-1 ≥ (1 -e -V (x) ) n-1 ≥ (1 -e -zn ) n-1 since H x ≥ 1, and thanks to Lemma 3.1 i) with ν = 0, P E (N T 1 x ≥ n b ) = e -V (x) (1 -1/H x ) n b -1 /H
x which gives (42). We are now ready to obtain a relation between a lower bound for R T n (g n , f n ) and a lower bound for R(f n ). Lemma 3.2. Recall ε b = min(b + 1 {b=0} , 1 -b)/13 and let (a n ) be a sequence of positive numbers. For all ε ∈ (0, ε b ) and n large enough

P * R T n (g n , f n ) < nϕ(n b )a n /4n b ≤ P * R(f n ) < a n /n b + ne -min(9ε log n,4hn) n 2κ b a 2 n . ( 43
)
Proof. Note that thanks to (42), for n large enough, nR(

f n ) ≤ 2E E [R T n (f n )], so by (41), on the event {R(f n ) ≥ a n /n b } P E R T n (g n , f n ) < nϕ(n b )a n /4n b ≤ P E R T n (f n ) < E E [R T n (f n )]/2 .
Using Bienaymé-Tchebychev inequality and the fact that

N T i x -N T i-1
x , i ∈ {1, . . . , n}, are i.i.d under P E implies, on the event

{R(f n ) ≥ a n /n b } P E (R T n (f n ) < E E [R T n (f n )] /2) ≤ 4 E E [R T n (f n )] 2 nVar E (R T 1 (f n )) ≤ 16n 2b a 2 n n
x,y∈O λn,n b

P E (N T 1 x ∧ N T 1 y ≥ n b )f n,|x| 1 H |x| zn (V x )f n,|y| 1 H |y| zn (V y ). ( 44
)
The last inequality coming from the fact that, on

{R(f n ) ≥ a n /n b }, thanks to (42) E E [R T n (f n )] 2 ≥ n 2 R(f n ) 2 /4 ≥ n 2 a 2 n /4n 2b . Markov inequality in (44) yields P E (N T 1 x ∧N T 1 y ≥ n b ) ≤ E E [N T 1 x N T 1 y ]/n 2b , so finally, on the event {R(f n ) ≥ a n /n b } P E (R T n (g n , f n ) < nϕ(n b )a n /4n b ) ≤ 16 na 2 n x,y∈O λn,n b E E [N T 1 x N T 1 y ]f n,|x| 1 H |x| zn (V x )f n,|y| 1 H |y| zn (V y ). ( 45
)
To treat the above sum, we first make a simplification by using the uniform upper bound of the set U b , see (11)

x,y∈O λn,n b

E E [N T 1 x N T 1 y ]f n,|x| 1 H |x| zn (V x )f n,|y| 1 H |y| zn (V y ) ≤ C 2 ∞ n 2κ b x,y∈O λn E E [N T 1 x N T 1 y ]. ( 46
)
We then split the computations in two distinct steps: the first step is dedicated to the cases x ≤ y or y ≤ x and the second one to the cases nor x ≤ y neither y ≤ x. The key here is to take into account that we are only interested in vertices belonging to λ n -regular lines O λn with λ n = ne -min(10ε log n,5hn) for ε ∈ (0, ε b ).

We start with the cases x ≤ y and y ≤ x and as they are symmetrical, we only deal with the first one. First note that as

E E N T 1 x N T 1 y ≤ 2e -V (y) H x = 2H x e -V (x) e -Vx(y) (see [AD20] Lemma 3.6) E x≤y x,y∈O λn E E [N T 1 x N T 1 y ] ≤ 2E x∈O λn e -V (x) H x y≥x y∈O x λn e -Vx(y) ≤ 2E x∈O λn e -V (x) 2 λ n ≤ 2 2 n λ n ,
where for all λ > 0, O x λ is translated set of λ-regular lines

O x λ = y ∈ T, y > x; max |x|<j≤|y| H x,yj ≤ λ , H x,yj = x<w≤yj e Vx(w)-Vx(yj ) ,
also, the second inequality is obtained thanks to the regular line which yields H x 1 O λn (x) ≤ λ n and the last one comes from Remark 2. We then move to the second case, neither x ≤ y nor y ≤ x, that we denote x ∼ y. In this case,

E E N T 1 x N T 1 y = 2H x∧y e V (x∧y)-V (x)-V (y) (see [AD20] Lemma 3.6). Thus E E [N T 1 x N T 1 y ] ≤ 2λ n l≥1 |z|=l e -V (z) 1 {z∈O λn } u =v u * =v * =z e -Vz(u) e -Vz(v) x≥u x∈O u λn e -Vu(x) y≥v y∈O v λn e -Vv(y) ,
where we have used again the regular line O λn which gives an upper bound for H x∧y . Finally, independence of the increments of V conditionally to (T, V (w); w ∈ T, |w| ≤ l + 1) and Remark 2 yields

E x ∼y x,y∈O λn E E [N T 1 x N T 1 y ] ≤ 2λ n E |u|=1 e -V (u) 2 E z∈O λn e -V (z) 3 ≤ 2λ n E |u|=1 e -V (u) 2 ( n ) 3 ,
and thanks to (5), the second moment above is finite. Collecting the upper bounds for the two cases and moving back to (46), we get for n large enough

E x,y∈O λn ,n b E E [N T 1 x N T 1 y ]f n,|x| 1 H |x| zn (V x )f n,|y| 1 H |y| zn (V y ) ≤ ( n ) 4 λ n n 2κ b ≤ ne -min(9ε log n,4hn) n 2κ b , (47)
the last inequality is justified by the fact (see Remark 1) that ( n ) 4 = o(e hn ) and ( n ) 4 = o(e ε log n ).

We are now ready to conclude the proof of the lemma :

P * R T n (g n , f n ) < nϕ(n b )a n /4n b is smaller than P * (R(f n ) < a n /n b ) + P * R T n (g n , f n ) < nϕ(n b )a n /4n b , R(f n ) ≥ a n /n b ,
then, as the second term in the above inequality is nothing but

E * P E R T n (g n , f n ) < nϕ(n b )a n /4n b 1 {R(f n )≥an/n b } ,
the proof ends thanks to (45) and (47).

Lower bound for R(f n )

This is the most technical part of the proof of Proposition 1. For any n ≥ 2 and ε ∈ (0, ε b ), recall that λ n = ne -min(10ε log n,5hn) and z n = 1/3 n /δ 1 , δ 1 ∈ (0, 1/2) (see ( 5)) with n = (log n) 3 . For any ε > 0, let us choose (a n ) as follows

a n := e -4εhn k≥1 Ψ k λn/2,n b f n,k εhn 1 Υ k n (48) with Υ k n = {t ∈ R k ; H k (t) ≤ n b e εhn } ∩ H k B,2zn . Recall that Ψ k λ,λ , h n , H k B,2zn
and f n,k εhn can be found respectively in (9), ( 13), ( 19) and (17).

Lemma 3.3. There exists c 4 > 0 such that for any ε ∈ (0, ε b ) and n large enough

P * R(f n ) < a n /n b ≤ e -ε c 4 c 2 hn E[Z 2 n ] k≥1 Ψ k λn/2,n b f n,k εhn 1 Υ k n 2 + h n e -εc2hn , (49)
with, recall, m n = εh n /c 2 (see (16)).

Proof. Recall the expression of R(f n ):

R(f n ) = x∈O λn,n b e -V (x) 1 H x 1 - 1 H x n b -1 f n,|x| 1 H |x| zn (V (x 1 ), • • • , V (x)),
with H x and H |x| zn respectively defined in (8) and ( 19). The main idea here is to cut the tree at the generation m n to introduce independence between generations. First note that

R(f n ) ≥ |u|=mn k≥1 |x|=k+mn x>u; x∈O λn ,n b e -V (x) H x 1 - 1 H x n b f n,k+mn 1 H k+mn zn (V (x 1 ), . . . , V (x)),
from here we would like to make a translation to decompose the trajectories of V before and after the generation m n and to do that, we have in particular to re-write H xj for j ≤ |x|. Let u < x with |u| = m n . For all m n < j ≤ |x|, we have H xj = H u e -Vu(xj ) + H u,xj where, for any z < v, H z,v := z<w≤v e Vz(w)-Vz (v) . So on the events

{max |w|≤mn |V (w)| ≤ εh n } and {V u (x):= min u<w≤x (V (w) -V (u)) ≥ -B}, for any B > 0 : ∀i ≤ m n : H xi ≤ m n e 2εhn and ∀ m n < j ≤ |x| : H xj ≤ m n e 2εhn+B + H u,xj . Assume n b < H u,x ≤ n b e εhn . Then, H x > n b and for n large enough (recall h n ≤ log n for n large enough, h n → ∞ and ε ∈ (0, ε b )) 1 H x 1 - 1 H x n b ≥ (1 -1/n b ) n b m n e 2εhn+B + H u,x ≥ (1 -1/n b ) n b m n e 2εhn+B + n b e εhn ≥ e -3εhn n b .
Now introduce the translated (λ, λ )-regular lines

O v λ,λ := y ∈ T, y > v; max |v|<j≤|y| H v,yj ≤ λ, H v,y > λ .
Note that for n large enough,

O u λn/2,n b ⊂ O λn,n b . Indeed, if |u| = m n and m n < j ≤ |x|, then H xj ≤ m n e 2εhn+B + H u,xj . Moreover, m n e 2εhn+B ≤ e 3εhn ≤ λ n /2 for n large since ε ∈ (0, 1/13), so H u,xj ≤ λ n /2 implies H xj ≤ λ n .
For f n,mn+k , we simply write (still on the event { max

|w|≤mn |V (w)| ≤ εh n }) f n,mn+k (V (x 1 ), . . . , V (x)) ≥ f n,k εhn (V u (x mn+1 ), . . . , V u (x)),
where we recall that

f n,k h (t 1 , . . . , t k ) = inf s∈[-h,h] m f n,m+k (s 1 , . . . , s m , t 1 + s m , . . . , t k + s m ) with m = h/c 2 . In the same way, if |V (u)| ≤ εh n then 1 {V (x)≥zn} ≥ 1 {Vu(x)≥2zn} since ε < 1 and h n ≤ 1/3
n . We finally obtain, for n large enough (independently of the environment) on

{max |w|≤mn |V (w)| ≤ εh n } that R(f n ) is larger than e -3εhn n b |u|=mn e -V (u) k≥1 |x|=k+mn x>u; x∈O u λn /2,n b e -Vu(x) 1 {Hu,x≤n b e εhn } f n,k εhn 1 H k B,2zn (V u (x mn+1 ), . . . , V u (x)) ≥ e -4εhn n b |u|=mn k≥1 |x|=k+mn x>u; x∈O u λn /2,n b e -Vu(x) f n,k εhn 1 Υ k n (V u (x mn+1 ), . . . , V u (x)). (50)
Now, introduce the random variable

Z u n Z u n := k≥1 |x|=k+mn x>u; x∈O u λn /2,n b e -Vu(x) f n,k εhn 1 Υ k n (V u (x mn+1 ), . . . , V u (x)), we obtain P R(f n ) < e -4εhn E[Z n ]/n b , max |w|≤mn |V (w)| ≤ εh n ≤ P |u|=mn Z u n < E[Z n ] ,
with

Z n := x∈O λn/2,n b e -V (x) f n,|x| εhn 1 Υ |x| n (V (x 1 ), . . . , V (x)). (51)
Hence, by Lemma 2.4 in [START_REF] Andreoletti | The heavy range of randomly biased walks on trees[END_REF], there exists c 4 > 0 such that for n large enough

P * R(f n ) < e -4εhn E[Z n ]/n b , max |w|≤mn |V (w)| ≤ εh n ≤ e -c4mn E[Z 2 n ] E[Z n ] 2 , (52)
and finally, (48) yields

P * R(f n ) < a n /n b , max |w|≤mn |V (w)| ≤ εh n ≤ e -ε c 4 c 2 hn E[Z 2 n ] k≥1 Ψ k λn/2,n b f n,k εhn 1 Υ k n 2 , we have used that E[Z n ] = k≥1 Ψ k λn/2,n b f n,k εhn 1 Υ k n
and m n = εh n /c 2 . Finally, (16) finishes the proof.

The next step is to give a lower bound for E[Z 2

n ], we do that in the dedicated section below.

Control of the second moment E[Z 2 n ]

In this section we prove the following lemma, Lemma 3.4. Assume (A1) and (A2) hold. For all ε ∈ (0, ε b ), A > 2/c 3 and n large enough

E[Z 2 n ] ≤ e 6ε A hn k≥1 Ψ k n,n b (f n,k ) 2 ,
recall also that c 3 comes from Remark 2.

Proof. The expression of Z 2 n is given by x,y∈O λn /2,n b e -V (x)-V (y) f

n,|x| εhn 1 Υ |x| n (V x )f n,|y| εhn 1 Υ |y| n (V y ) (see (51)) and λ n ≤ n so Z 2 n ≤ x,y∈O n,n b e -V (x) e -V (y) f n,|x| εhn 1 H |x| B,2zn (V x )f n,|y| εhn 1 H |y| B,2zn (V y ), (53)
with (recall) F (V w ) = F (V (w 1 ), . . . , V (w)). Let us split the computations of the upper bound of the mean of Z 2 n into two main cases : the first one is when x and y in the sum (53) are directly related in the tree and the second one when it is not: 5)). For this case, we simply use the fact that f n,i εhn ≤ C ∞ and e -2V (w) 1 {V (w)≥2zn} ≤ e -V (w) /n 2 so by symmetry

Cases 1 (x ≤ y or y ≤ x) : recall z n = 1/3 n /δ 1 with n = (log n) 3 , δ 1 ∈ (0, 1/2) (see (
E x≤y or y≤x x,y∈O n,n b e -V (x)-V (y) 1 {V (x)≥2zn} ≤ 2E x∈On e -2V (x) 1 {V (x)≥2zn} y≥x y∈O x n e -Vx(y) ≤ 2 n 2 E x∈On e -V (x) y≥x y∈O x n e -Vx(y) ,
which is equal, by using that the increments of V are conditionally independent and stationary, to 2E[ x∈On e -V (x) ] 2 /n 2 . Then, thanks to Remark 2 and the fact that

h n ≥ (log n) γ with 0 < γ ≤ 1, 2E[ x∈On e -V (x)
] 2 ≤ n ≤ e εhn/A . In addition with assumption (A1), the part {x ≤ y or y ≤ x} in the sum (53) is smaller than

e ε A hn k≥1 Ψ k n,n b (f n,k ) 2 .
Cases 2 (x ∼ y) : recall that x ∼ y if and only if neither x ≤ y nor y ≤ x. First let Σ 0 (z) :=

x ∼y x,y∈O n,n b

1 {x∧y=z} e -V (x) e -V (y) f n,|x| εhn 1 H |x| B,2zn (V x )f n,|y| εhn 1 H |y| B,2zn (V y ).
We decompose Σ 0 (z) as follows: for all A > 2/c 3 z∈T

Σ 0 (z) = |z|≥ A n Σ 0 (z) + |z|< A n (Σ 1 (z) + Σ 2 (z)), (54)
and for any i ∈ {1, 2}, Σ i (z) :=

x ∼y x,y∈O n,n b

1 {x∧y=z} e -V (x) e -V (y) f n,|x| εhn 1 H |x| B,2zn (V x )f n,|y| εhn 1 H |y| B,2zn (V y )1 {(x,y)∈Ci,z} ,
with C 1,z := {(x, y) ∈ T 2 ; x * > z and y * > z} and C 2,z := {(x, y) ∈ T 2 ; x * = z or y * = z}.

Let us start with the easiest part: |z|≥

A n Σ 0 (z). Observe that |z|≥ A n Σ 0 (z) ≤ C 2 ∞ l≥ A n |z|=l 1 {V (z)≥-B, z∈On} u =v u * =v * =z x≥u x∈On e -V (x)
y≥v y∈On e -V (y) .

By conditional independence of the increments of V and Remark 2, for any n large enough

E |z|≥ A n Σ 0 (z) ≤ C 2 ∞ e B E |u|=1 e -V (u) 2 E x∈On e -V (x) 2 l≥ A n E |z|=l e -V (z) 1 {z∈On} ≤ C 2 ∞ e B E |u|=1 e -V (u) 2 2 n n -2 ≤ k≥1 Ψ k n,n b (f n,k ), (55)
where we have used (A1) and (5) for the last inequality.

For Σ 1 (z), |z| < A n , we decompose according to the value of V (w) with w ∈ {u, v}:

Σ 1 (z) = Σ 1,1 (z) + Σ 1,2 (z) with Σ 1,1 (z) := u =v u * =v * =z 1 {V (u)∨V (v)<2zn} x>u x∈O n,n b e -V (x) f n,|x| εhn 1 H |x| B,2zn (V x ) y>v y∈O n,n b e -V (y) f n,|y| εhn 1 H |y| B,2zn (V y ), and Σ 1,2 (z) := u =v u * =v * =z 1 {V (u)∨V (v)≥2zn} x>u x∈O n,n b e -V (x) f n,|x| εhn 1 H |x| B,2zn (V x ) y>v y∈O n,n b e -V (y) f n,|y| εhn 1 H |y| B,2zn (V y ). We first deal with Σ 1,1 (z). Observe that x ∈ O n,n b (resp. y ∈ O n,n b ) means H u ≤ n (resp. H v ≤ n), x ∈ O u n (resp. y ∈ O v n ) and n b -H u e -Vu(x) < H u,x (resp. n b -H v e -Vv(y) < H v,y ). Besides, V (u) < 2z n and V (x) > 2z n (resp. V (v) < 2z n and V (y) > 2z n ) implies V u (x) > 0 (resp. V v (y) > 0) that is n b -H u < H u,x (resp. n b -H v < H v,y ), so Σ 1,1 (z) is smaller than u =v u * =v * =z 1 {V (u)∧V (v)≥-B,Hu∨Hv≤n} x>u x∈O u n,n b -Hu e -V (x) f n,|x| εhn (V x ) y>v y∈O v n,n b -Hv e -V (y) f n,|y| εhn (V y ). (56) We now move to Σ 1,2 (z). Note that {V (u) ∨ V (v) ≥ 2z n } = {V (u) ≥ 2z n , V (v) < 2z n } ∪ {V (v) ≥ 2z n , V (u) < 2z n } ∪ {V (u) ∧ V (v) ≥ 2z n }. By symmetry, Σ 1,2 (z) is equal to 2 u =v u * =v * =z 1 {V (u)≥2zn,V (v)<2zn} x>u x∈O n,n b e -V (x) f n,|x| εhn 1 H |x| B,2zn (V x ) y>v y∈O n,n b e -V (y) f n,|y| εhn 1 H |y| B,2zn (V y ) + u =v u * =v * =z 1 {V (u)∧V (v)≥2zn} x>u x∈O n,n b e -V (x) f n,|x| εhn 1 H |x| B,2zn (V x ) y>v y∈O n,n b e -V (y) f n,|y| εhn 1 H |y| B,2zn (V y ).
The same decomposition of H y we used for Σ 1,1 (z) also works for the part {V (v) < 2z n } in the above sum, so as in (56) and first using that on {V (u) ≥ 2z n }∩{V (y) ≥ -B} ,V (u) ≥ (1-δ 1 )V (u)+2 log n and δ 1 V (v) ≥ -δ 1 B, then using that on

{V (u) ∧ V (v) ≥ 2z n }, V (u) + V (v) ≥ (1 -δ 1 )(V (u) + V (v)) + 4 log n, Σ 1,2 (z) is smaller than 1 {V (z)≥-B,z∈On} 2e δ1B C 2 ∞ n 2 u =v u * =v * =z e -(1-δ1)(V (u)+V (v)) x>u x∈O u n e -Vu(x) y>v y∈O v n e -Vv(y) + 1 {V (z)≥-B,z∈On} C 2 ∞ n 4 u =v u * =v * =z e -(1-δ1)(V (u)+V (v)) x>u x∈O u n e -Vu(x) y>v y∈O v n e -Vv(y) ≤ 1 {V (z)≥-B,z∈On} 3e δ1B C 2 ∞ n 2 u =v u * =v * =z e -(1-δ1)(V (u)+V (v)) x>u x∈O u n e -Vu(x) y>v y∈O v n e -Vv(y) .
Note that the genealogical common line between x and y is the common line of individuals before u and v so for any p ≤ |z|, x p = y p = u p = v p and

f n,|x| εhn (V x ) = f n,|x| εhn (V (u 1 ), • • • , V (u), V u (x |u|+1 ) + V (u), • • • , V u (x) + V (u)), and
f n,|y| εhn (V y ) = f n,|y| εhn (V (v 1 ), • • • , V (v), V v (y |v|+1 ) + V (v), • • • , V v (y) + V (v)).
Recall that for all q ≥ 1 and t q = (t 1 , . . . , t q ) ∈ R q ,

Ψ k n (F |t p ) = E |x|=k e -V (x) F (t 1 , . . . , t p , V (x 1 ) + t p , . . . , V (x) + t p )1 On (x) .
We naturally note Ψ k n (F |V w ) when we evaluate the function Ψ k n (F |•) at (V (w 1 ), . . . , V (w)). By conditional independence of the increments of

V , E[ |z|=l Σ 1 (z)] = E[ |z|=l Σ 1,1 (z) + Σ 1,2 (z)] is smaller, for n large enough with l < A n , than E |z|=l u =v u * =v * =z 1 {V (u)∧V (v)≥-B,Hu∨Hv≤n} i,j≥1 (k,w)∈{(i,u);(j,v)} e -V (w) Ψ k n,n b -Hw f n,|w|+k εhn |V w + 3e δ1B 2 n C 2 ∞ n 2 E |z|=l 1 {V (z)≥-B,z∈On} u =v u * =v * =z e -(1-δ1)(V (u)+V (v)) ,
where we have used that E[ x∈On e -V (x) ] ≤ n . Then, by assumption (A2) with δ = δ 1 (see (5) for the definition of δ 1 ), for all l < A n (|u| = |v| = l + 1) and n large enough, on the event

{V (u) ∧ V (v) ≥ -B, H u ∨ H v ≤ n} i,j≥1 (k,w)∈{(i,u);(j,v)} Ψ k n,n b -Hw f n,|w|+k εhn |V w ≤ e δ1V (u)+δ1V (v)+ 2ε A hn k≥1 Ψ k n,n b (f n,k ) 2 . Hence, E[ |z|< A n Σ 1 ] is smaller, for n large enough, than e 2ε A hn E |w|=1 e -(1-δ1)V (w) 2 E |z|< A n e -V (z)-(1-2δ1)V (z) 1 {V (z)≥-B} k≥1 Ψ k n,n b (f n,k ) 2 + 3e δ1B 2 n C 2 ∞ n 2 E |w|=1 e -(1-δ1)V (w) 2 E z∈On e -V (z)-(1-2δ1)V (z) 1 {V (z)≥-B} .
Finally, thanks to assumption (A1), (5) and by Remark 2, for n large enough

E |z|< A n Σ 1 (z) ≤ e 5ε A hn k≥1 Ψ k n,n b (f n,k ) 2 . ( 57
)
We now turn to Σ 2 (z), that is the sum

x ∼y x,y∈O n,n b 1 {x∧y=z} e -V (x) e -V (y) f n,|x| εhn 1 H |x| B,2zn (V x )f n,|y| εhn 1 H |y| B,2zn (V y )1 {(x,y)∈C2,z} ,
with C 2,z := {(x, y) ∈ T 2 ; x * = z or y * = z}. The first step is to split the set {x * = z or y * = z} into three disjoint sets: {x * = z and y * > z}, {x * > z and y * = z} and {x * = z and y * = z}. By symmetry, the previous sum is equal to

2 x =v x * =v * =z 1 {x∈O n,n b } e -V (x) f n,|x| εhn 1 H |x| B,2zn (V x ) y>v y∈O n,n b e -V (y) f n,|y| εhn 1 H |y| B,2zn (V y ) + x =y x * =y * =z e -V (x) e -V (y) 1 {x,y∈O n,n b } f n,|x| εhn 1 H |x| B,2zn (V x )f n,|y| εhn 1 H |y| B,2zn (V y ).
We then use a similar approach as the one we used for Σ 1 (z) to obtain

|z|=l Σ 2 (z) ≤ 2C 2 ∞ n 2 |z|=l x =v x * =v * =z e -(1-δ1)V (x) 1 {V (v)≥-B} y>v y∈O v n e -V (y) + C 2 ∞ n 4 |z|=l 1 {V (z)≥-B} x =y x * =y * =z e -(1-δ1)(V (x)+V (y)) .
Hence, by using conditional independence of the increments of V , E[ |z|=l Σ 2 (z)] is smaller, for n large enough, than

2e δ1B n C 2 ∞ n 2 E |z|=l 1 {V (z)≥-B} x =v x * =v * =z e -(1-δ1)(V (x)+V (v)) + C 2 ∞ n 4 E |z|=l 1 {V (z)≥-B} x =v x * =y * =z e -(1-δ1)(V (x)+V (y)) ,
where we used as usual E[ x∈On e -V (x) ] ≤ n . Hence, thanks to assumption (A1) and ( 5), for n large enough

E |z|< A n Σ 2 (z) ≤ e 3ε A hn k≥1 Ψ k n,n b (f n,k ) 2 . (58)
Collecting Case 1, Case 2 ((54), inequalities (55), ( 57) and ( 58)) and considering (53) give the lemma.

We are now ready to prove the lower bound of

R T n (g n , f n ) in Proposition 1. Recall u 1,n = k≥1 Ψ k λn/2,n b f n,k εhn 1 Υ k n where Υ k n = {t ∈ R k ; H k (t) ≤ n b e εhn } ∩ H k B,2zn , H k B,2zn
is defined in (19) and z n = 2 1/3 n /δ 1 . Thanks to Lemmata 3.2, 3.3 and the expression of a n (48), for n large enough, as e -εhn ≤ 1 4 , the probability

P(R T n (g n , f n ) < n 1-b ϕ(n b )e -5εhn u 1,n ) is smaller than P R T n (g n , f n ) < nϕ(n b )e -4εhn u 1,n /4n b ≤ e -ε c 4 c 2 hn E[Z 2 n ] u 2 1,n + h n e -εc2hn + e 8εhn-min(9ε log n,4hn) n 2κ b u 2 1,n .
Then, Lemma 3.4 provides the upper bound of

E[Z 2 n ] so P R T n (g n , f n ) < nϕ(n b )e -4εhn u 1,n /4n b is smaller, for n large enough, than (recall that h n ≤ log n) e -( c 4 c 2 -6 A )εhn k≥1 Ψ k n,n b (f n,k )/u 1,n 2 + h n e -εc2hn + e -min(ε log n,3hn) n 2κ b u 2 1,n
, which yields the lower bound of Proposition 1.

Upper bound for

R T n (g n , f n )
For all n ≥ 1 and x ∈ T, recall that E n x is the number of excursions, among the first n excursions to the root, for which the edge (x * , x) is reached. In a similar way, Ẽn

x is the number of excursions such that the vertex x is reached more often from above than from below :

E n x = n i=1 1 {N T i x -N T i-1 x ≥1} and Ẽn x := n i=1 1 { y;y * =x N T i y -N T i-1 y >N T i x -N T i-1 x } .
Also introduce the event A n such that all vertices of the trace of {X k , k ≤ T n } have exponential downfall fluctuation lower than n, potential larger than z n = 1/3 n /δ 1 and which are visited during a single excursion to the root

A n := ∀ j ≤ T n , X j ∈ O n , x∈On (1 {E n x ≥2} + 1 { Ẽn x ≥2} )1 H |x| zn (V x ) = 0 . ( 59
)
Note that lim n→∞ P(A n ) = 1. Indeed, Ẽn x ≥ 2 implies E n x ≥ 2 so

1 -P(A n ) ≤ P(∃ j ≤ T n : X j ∈ O n ) + P x∈On 1 {E n x ≥2} 1 H |x| zn (V x ) > 0 . By [AC18] (equation 2.2), P(∃ j ≤ T n : X j ∈ O n ) → 0. Moreover, P( x∈On 1 {E n x ≥2} 1 H |x| zn (V x ) > 0) is smaller than E x∈On P E (E n x ≥ 2)1 H |x| zn (V x ) = E x∈On P E (E n x ≥ 1) -P E (E n x = 1) 1 H |x| zn (V x ) .
Thanks to the strong Markov property,

N T i x -N T i-1
x , i ∈ {1, . . . , n}, are i.i.d under

P E so P E (E n x ≥ 1) -P E (E n x = 1) ≤ E E [E n x ] -P E (E n x = 1) = nP E (N T 1 x ≥ 1)(1 -P E (N T 1 x = 0) n-1 ) ≤ n 2 P E (N T 1
x ≥ 1) 2 and by Lemma 3.1, for all x with V (x) ≥ z n , n 2 P E (N T 1

x ≥ 1) 2 ≤ n 2 e -2V (x) ≤ n 2-1/δ1 e -V (x) / 1/δ1 n . δ 1 ∈ (0, 1/2), hence, by Remark 2

P x∈On 1 {E n x ≥2} 1 H |x| zn (V x ) > 0 ≤ n 2-1/δ1 1/δ1 n E x∈On e -V (x) ≤ n 2-1/δ1 1/δ1-1 n → 0.
Lemma 3.5. Let (u n , n) be a sequence of positive numbers, then

P E (R T n (g n , f n ) > u n , A n ) ≤ 2n 1-b ϕ(n b ) u n (X 1,n + X 2,n + X 3,n ),
where

X 1,n := x∈On 1 {V (x)<zn} e -V (x) + y;y * =x e -V (y) f n,|x| (V x ), (60)
X 2,n := x∈On 1 {V (x)≥zn} e -V (x) H x 1 - 1 H x n b /2 -1 (n b + H x )f n,|x| (V x ), (61)
and

X 3,n := x∈On 1 {V (x)≥zn} e -V (x) H x Hx 1 + Hx 1 - 1 1 + Hx n b /2 -1 (n b + 1 + Hx )f n,|x| (V x ), ( 62
)
recall the definition of Hx in Lemma 3.1.

Proof. Since g n (0) = 0, we have, by Markov inequality, that

P E (R T n (g n , f n ) > u n , A n ) is smaller than 2 u n x∈On 1 {V (x)<zn} E E g n L T n x f n,|x| (V x ) + x∈On 1 {V (x)≥zn} E E g n L T n x 1 {E n x , Ẽn x ∈{0,1}} f n,|x| (V x ) .
The first part in the above sum is the easiest to deal with. Indeed, the application t ∈ [1, ∞) → ϕ(t)/t is non-increasing so g n (t) ≤ tn -b ϕ(n b ) and we have

x∈On 1 {V (x)<zn} E E g n L T n x f n,|x| (V x ) ≤ n 1-b ϕ(n b ) x∈On 1 {V (x)<zn} E E L T 1 x f n,|x| (V x ) = n 1-b ϕ(n b )X 1,n .
We have used that for all 1 ≤ i ≤ n,

L T i x -L T i-1
x is distributed as L T 1

x under P E with mean e -V (x) + y;y * =x e -V (y) by Lemma 3.1.

We then move to the high potential part. Assume E n

x ∈ {0, 1} and Ẽn x ∈ {0, 1}. If E n x = 0, then the vertex x is never visited during any of the first n excursions and Ẽn x = 0. Thus,

g n L T n x = g n (0) = 0. If E n
x = 1 and Ẽn x = 0, then there exists i ∈ {1, . . . , n} such that

N T i x -N T i-1
x ≥ 1 and ∀j = i, N T j

x -N T j-1

x = 0 and ∀m ∈ {1, . . . , n}, y;y

* =x N T m y -N T m-1 y ≤ N T m x -N T m-1
x . In particular, since, starting from the root e,

L T n x = n j=1 N T j x -N T j-1 x + y;y * =x N T j y -N T j-1 y , we have, on {E n x = 1, Ẽn x = 0} L T n x = N T i x -N T i-1 x + y;y * =x N T i y -N T i-1 y ≤ 2 N T i x -N T i-1 x . (63)
Otherwise, if E n x = 1 and Ẽn x = 1, then there exists i ∈ {1, . . . , n} such that N T i x -N T i-1

x ≥ 1 and ∀j = i, N T j

x -N T j-1 x = 0 and ∃m ∈ {1, . . . , n} such that y;y

* =x N T m y -N T m -1 y > N T m x -N T m -1 x and ∀m = m , y;y * =x N T m y -N T m-1 y ≤ N T m x -N T m-1
x . So we have necessarily m = i and, on

{E n x = 1, Ẽn x = 1} L T n x = N T i x -N T i-1 x + y;y * =x N T i y -N T i-1 y ≤ 2 y;y * =x N T i y -N T i-1 y . ( 64
)
g n is non-decreasing so (63) and (64) give, when E n x ∈ {0, 1} and Ẽn x ∈ {0, 1}

g n L T n x ≤ n i=1 g n 2 N T i x -N T i-1 x + n i=1 g n 2 y;y * =x N T i y -N T i-1 y .
From this inequality, it follows that

E E g n L T n x 1 {E n x , Ẽn
x ∈{0,1}} is smaller than

nE E g n 2N T 1 x + nE E g n 2 y;y * =x N T 1 ≤n 1-b ϕ(n b )E E N T 1 x 1 {N T 1 x ≥ n b /2 } + n 1-b ϕ(n b )E E y;y * =x N T 1 y 1 { y;y * =x N T 1 y ≥ n b /2 } .
We have used that for all 1

≤ i ≤ n, N T i x -N T i-1 x (resp. y;y * =x N T i y -N T i-1 y ) is distributed as N T 1
x (resp. y;y * =x N T 1 y ) under P E and the fact that the application t ∈ [1, ∞) → ϕ(t)/t is non-increasing. Then, by Lemma 3.1

E E N T 1 x 1 {N T 1 x ≥ n b /2 } ≤ e -V (x) H x 1 - 1 H x n b /2 -1 (n b + H x ),
and

E E y;y * =x N T 1 y 1 { y;y * =x N T 1 y ≥ n b /2 } ≤ e -V (x) H x Hx 1 + Hx 1 - 1 1 + Hx n b /2 -1 (n b + 1 + Hx ),
which ends the proof.

Lemma 3.6. Let b ∈ [0, 1). For n large enough

E[X 1,n + X 2,n + X 3,n ] ≤ 3(log n) 2 u 2,n .
where we recall u

2,n = k≥1 Ψ k n f n,k 1 R k \H k zn +Ψ k n,n b /(log n) 2 (f n,k )+E[W Ψ k n,n b /(W (log n) 2 ) (f n,k )] , with W = |z|=1 e -V (z) .
Proof. We start with the easiest part, that is the expression of E[X 1,n ]. Thanks to hypothesis (2)

E[X 1,n ] = E x∈On 1 {V (x)<zn} e -V (x) + e -V (x) y;y * =x e -Vx(y) f n,|x| (V x ) = 2E x∈On 1 {V (x)<zn} e -V (x) f n,|x| (V x ) = 2 k≥1 Ψ k n f n,k 1 R k \H k zn . Let λn := n b /2 -1 log q n with q n := 4C ∞ n n b k≥1 Ψ k n,n b /(log n) 2 f n,k ,
and let us find an upper bound for E[X 2,n ]. For that, we decompose X 2,n into two parts according to the value of H x :

X 2,n ≤ x∈On (1 {Hx≤ λn} + 1 {Hx> λn} ) e -V (x) H x 1 - 1 H x n b /2 -1 (n b + H x )f n,|x| (V x ) ≤ C ∞ n b + λn 1 - 1 λn n b /2 -1 x∈On e -V (x) + 1 + n b λn x∈O n, λn e -V (x) f n,|x| (V x ).
By definition of λn and q n (see above), (1 -1/ λn ) n b /2 -1 ≤ 1/q n . Moreover, by Remark 2,

E[ x∈On e -V (x) ] ≤ n and E[ k≥1 Ψ k n,n b f n,k ] ≤ C ∞ E[ x∈On e -V (x) ] ≤ C ∞ n so for n large enough (q n ≥ 4n b implying λn ≤ n b ), we obtain E[X 2,n ] ≤ 1 2 k≥1 Ψ k n,n b /(log n) 2 f n,k + 1 + n b λn k≥1 Ψ k n, λn f n,k .
For E[X 3,n ], we decompose X 3,n into two parts according to the value of Hx : X 3,n is smaller than

x∈On (1 {1+ Hx≤ λn} + 1 {1+ Hx> λn} ) e -V (x) H x Hx 1 + Hx 1 - 1 1 + Hx n b /2 -1 (n b + 1 + Hx )f n,|x| (V x ) ≤ C ∞ n b + λn 1 - 1 λn n b /2 -1 x∈On e -V (x) + 1 + n b λn x∈On e -V (x) 1 {1+ Hx> λn} × y;y * =x e -Vx(y) f n,|x| (V x ).
Then, as above,

C ∞ n b + λn 1 -1/ λn n b /2 -1 ≤ k≥1 Ψ k n,n b /(log n) 2 f n,k /2
, also recall that Hx = H x y;y * =x e -Vx(y) so by conditional independence of H x and y;y * =x e -Vx(y) together with the fact that this random variable has the same law as W = |x|=1 e -V (x) ,

E x∈On e -V (x) 1 {1+ Hx> λn} y;y * =x e -Vx(y) f n,|x| (V x ) = k≥1 E W Ψ k n,( λn-1)/W (f n,k ) . Hence E[X 3,n ] ≤ 1 2 k≥1 Ψ k n,n b /(log n) 2 f n,k + 1 + n b λn k≥1 E W Ψ k n,( λn-1)/W (f n,k ) . Finally, note that Ψ k n,n b (f n,k ) ≤ Ψ k n,n b /(log n) 2 f n,
k so using assumption (A1), we get q n ≤ 4C ∞ n n 1+b thus giving λn -1 ≥ n b (log n) -2 for all b ∈ (0, 1) and n large enough. Hence, for all b ∈ [0, 1) and n large enough, (1

+ n b / λn ) ≤ 2(log n) 2 and Ψ k n,( λn-1)/W (f n,k ) (resp. Ψ k n, λn (f n,k )) is smaller than Ψ k n,n b /(W (log n) 2 ) (f n,k ) (resp. Ψ k n,n b /(log n) 2 (f n,k
)) so we obtain the result. We are now ready to prove the upper bound in Proposition 1. Recall (59) and let ε > 0

P R T n (g n , f n ) n 1-b ϕ(n b )u 2,n > e εhn ≤ P R T n (g n , f n ) n 1-b ϕ(n b )u 2,n > e εhn , A n + 1 -P(A n ),
where

u 2,n = k≥1 (Ψ k n f n,k 1 R k \H k zn + Ψ k n,n b /(log n) 2 (f n,k ) + E W Ψ k n,n b /(W (log n) 2 ) (f n,k ) )
. By Lemma 3.5 with u n = e εhn n 1-b ϕ(n b )u 2,n and Lemma 3.6, for n large enough

P R T n (g n , f n ) n 1-b ϕ(n b )u 2,n > e εhn , A n ≤ 2e -εhn u 2,n E[X 1,n + X 2,n + X 3,n ] ≤ 6(log n) 2 e -εhn ,
and then for n large enough

P R T n (g n , f n ) n 1-b ϕ(n b )u 2,n > e εhn ≤ 6(log n) 2 e -εhn + 1 -P(A n ).
Finally, observe (see Remark 1) that (log n) 2 = o(e εhn ) and we complete the proof of the upper bound recalling (see below (59)) that 1 -P(A n ) = o(1).

Technical estimates for one-dimensional random walk

In this section, we prove some technical expressions involving sums of i.i.d. random variables introduced via the many-to-one Lemma at the beginning of Section 2. Recall that (S i -S i-1 , i ≥ 1) is a sequence of i.i.d. random variables such that E(S 1 ) = 0, there exists η > 0 for which E(e ηS1 ) < +∞. Also we denote σ 2 = ψ (1) = E(S 2 1 ). We also use the following notations : for any a, τ a := inf{k > 0, S k ≥ a}, τ - a := inf{k > 0, S k ≤ a} and τ S-S a := inf{k > 0, S k -S k ≥ a} with S k := max 1≤m≤k S m and H S j := j i=1 e Si-Sj .

Two Laplace transforms

In this section, we deal with Laplace transforms which appear when we study the range with underlying constraint on V .

Lemma 4.1. Let r := r( ) such that lim →+∞ r( )/ = +∞, then for any ε > 0

e -(1+ √ c-ρ(c)) r (1+ε) ≤ E e -cσ 2 2 2 τr 1 τr≤τ S-S ≤ e -(1+ √ c-ρ(c)) r (1-ε) , with ρ(c) = cσ √ 2π +∞ 0 e -cσ 2 2 u f (u)du, and f (u) = 2 u 1/2 P(m 1 > 1/ √ uσ 2 ) -1 2 +∞ u 1 y 3/2 P(m 1 > 1/ yσ 2 )dy.
Note that ρ can be explicitly calculated : for any c > 0

ρ(c) = 2 √ c 1 -e - √ c sinh( √ c) -2 √ c -log((e √ c + 1)/2) .
Proof. We start with the upper bound.

Let us introduce the usual strict ladder epoch sequence (

T k := inf{i > T k-1 , S i > S T k-1 }, k; T 0 = 0). Then for any k E e -cσ 2 2 2 τr 1 τr≤τ S-S ≤ E e -cσ 2 2 2 τr 1 S T k <r 1 τr≤τ S-S + P(S T k ≥ r) ≤ E e -cσ 2 2 2 τ0 1 τ0≤τ - - k + P(S T k ≥ r), (65)
where the last equality comes from the strong Markov property and equality T 1 = τ 0 := inf{m > 0, S m > 0}. From here we need the asymptotic in of E e -cσ 2 2 2 τ0 1 τ0≤τ - -. First we use following identity

E e -λ 2 τ0 1 τ0≤τ - - = E[e -λ 2 τ0 ] -P(τ 0 > τ - -) + E (1 -e -λ 2 τ0 )1 τ0>τ -, (66)
and then give an upper bound for each of the three terms. Lemma 2.2 in [START_REF] Aïdékon | Tail asymptotics for the total progeny of the critical killed branching random walk[END_REF] gives for m large enough

P(τ 0 > τ - -) = E(S τ0 ) + o 1 , (67)
Both of the other terms can be obtained with a Tauberian theorem, we give here some details for the third one which is more delicate. Let dH (u) the measure defined by

P(τ 0 > z 2 , τ 0 > τ - -) = ∞ z dH (u), integration by part gives E (1 -e -λ 2 τ0 )1 τ0>τ - - = +∞ 0 (1 -e -λu )dH (u) = λ +∞ 0
e -λu P(τ 0 > u 2 , τ 0 > τ - -)du. So we need an asymptotic in of the tail probability P(τ 0 > u 2 , τ 0 > τ - -). Let us decompose this probability as follows

P(τ 0 > z 2 , τ 0 < τ - -) = P(τ 0 > τ - -> z 2 ) + P(τ 0 > z 2 , τ - -≤ z 2 ) = P(τ - 0 > τ > z 2 ) + P(τ 0 > z 2 , τ ≤ z 2 ) =: P 1 + P 2 . ( 68
)
where τ - 0 := inf{k > 0, S k < 0} with for any k, S k = -S k and similarly τ := inf{k > 0, S k ≥ }. For P 2 , we just use Donsker's theorem for conditioned random walk to remain positive obtain in [START_REF] Bolthausen | On a functional central limit theorem for random walks conditioned to stay positive[END_REF] which gives lim →+∞ P(τ ≤ z 2 |τ 0 > z 2 ) = P(m 1 > 1/σ √ z), where m is the Brownian meander and m 1 = sup s≤1 m s . Also we know from Feller [START_REF] Feller | An Introduction to Probability Theory[END_REF] (see the first equivalence page 514 of Caravenna [START_REF] Caravenna | A local limit theorem for random walks conditioned to stay positive[END_REF] for the expression we use here) that for any z > 0 :

lim →∞ P(τ 0 > z 2 ) = 2 π E(S τ0 ) √ zσ 2 , ( 69
) so lim →∞ P 2 = 2 π E(S τ0 ) √ zσ 2 P(m 1 > 1/σ √ z). (70)
For P 1 we use a similar strategy, for any A > x, ε > 0 and large enough

P 1 ≤ P(z 2 ≤ τ ≤ A 2 , τ 0 > τ ) + P(τ 0 > A 2 ) ≤ A 2 k=z 2 P(S k-1 ≤ , S k > | τ 0 > k)P(τ 0 > k) + P(τ 0 > A 2 ) ≤ (1 + ε) 2 π E(S τ0 ) σ A 2 k=z 2 P(S k-1 ≤ , S k > | τ 0 > k) k 1/2 + C A 1/2 ,
where we have used (69) for the last inequality and C > 0 is a constant. Also functional limit theorem [START_REF] Bolthausen | On a functional central limit theorem for random walks conditioned to stay positive[END_REF] implies that lim →+∞

A 2 k=z 2 P(S k-1 ≤ , S k > | τ 0 > k) k 1/2 = - A z 1 y 1/2 dP(m 1 > 1/ yσ 2 ).
We deduce from that, taking limits A → +∞ and ε → 0, lim

→∞ * P 1 ≤ - 2 π E(S τ0 ) σ +∞ z 1 y 1/2 dP(m 1 > 1/ yσ 2 ) = 2 π E(S τ0 ) σ 1 z 1/2 P(m 1 > 1/ √ zσ 2 ) - 1 2 +∞ z 1 y 3/2 P(m 1 > 1/ yσ 2 )dy .
Note that just by noticing that P 1 ≥ P(z 2 ≤ τ ≤ A 2 , τ 0 > τ ), above expression is also a lower bound for lim →∞ * P 1 . Considering this, (70) and (68), we obtain

lim →∞ P(τ 0 > z 2 , τ 0 > τ - -) = 2 π E(S τ0 ) σ f (z) ( 71
)
where f is the function given in the statement of the Lemma. Note that this convergence is uniform on any compact set in (0, ∞) by monotonicity of z → P(τ 0 > z 2 , τ 0 < τ - -), continuity of the limit and Dini's theorem. From here we follow the same lines of the proof of a Tauberian theorem (Feller [Fel68]) for completion we recall the main lines for our particular case. For any ε > 0, by the uniform convergence we have talked about just above,

lim →+∞ 1/ε ε e -λu P(τ 0 > u 2 , τ 0 > τ - -)du = 2 π E(S τ0 ) σ 1/ε ε e -λu f (u)du.
By (69), we also have for any and z > 0, P(τ 0 > z 2 , τ 0 > τ - -) ≤ Const z 1/2 and as +∞ 0

e -λu u -1/2 du < +∞, we get lim ε→0 lim →+∞ ε 0 e -λu P(τ 0 / 2 > u) = 0.

Similarly lim ε→0 lim →+∞ +∞ 1/ε e -λu P(τ 0 / 2 > u, τ 0 > τ - -)du = 0. Finally lim

→+∞ +∞ 0 (1 -e -λu )dH (u) = lim →+∞ E (1 -e -λ 2 τ0 )1 τ0>τ - = λ 2 π E(S τ0 ) σ +∞ 0 e -λu f (u)du. ( 72
)
Note also that just by using (69) we also have lim

→+∞ E[1 -e -λ 2 τ0 ] = √ 2λE(S τ0 )σ -1
. Then collecting (66), ( 67) and (72) and taking λ = cσ 2 /2 we obtain for large enough

E e -cσ 2 2 2 τ0 1 τ0≤τ - - = 1 - E(S τ0 ) 1 + √ c - cσ √ 2π +∞ 0 e -cσ 2 u 2 f (u)du + o 1 . (73)
To obtain an explicit expression for the above integral, we integrate by parts

+∞ 0 e -λu f (u)du = 2 +∞ 0 e -λu u 1/2 P(m 1 > 1/ √ uσ 2 )du - 1 2λ +∞ 0 u 3/2 (1 -e -λu )P(m 1 > 1/ √ uσ 2 )du,
then using the expression of P(m 1 > u) := -2 k=1 (-1) k exp(-(ku) 2 /2), ∀u > 0, and elementary computations

+∞ 0 e -λu f (u)du = 2 π λ 1 sinh( √ 2λ/σ) - e - √ 2λ/σ sinh( √ 2λ/σ) - σ √ 2π λ √ 2λ σ -log((e √ 2λ/σ + 1)/2) . (74)
Now we deal with the probability P(S T k ≥ r) in the same way as [START_REF] Hu | The potential energy of biased random walks on trees[END_REF]. As T k can be written as a sum of i.i.d random variables with common law given by τ 0 , the exponential Markov property gives for any η > 0, P(S T k ≥ r) ≤ e -ηr (E(e ηSτ 0 )) k . Taking k = (1 -ε)r/E(S τ0 ) we can find constants c and c" such that P(S T k ≥ r) ≤ c e -c"r for any r ≥ 1. So replacing this and (73) in (65), we finally get for any m large enough

E e -cσ 2 2 2 τr 1 τr≤τ S-S ≤ E e -cσ 2 2 2 τ0 1 τ0≤τ - k + P(S T k ≥ r) ≤ 1 - E(S τ0 ) 1 + √ c - cσ √ 2π +∞ 0 e -cσ 2 2 u f (u)du (1-ε)r/E(Sτ 0 )
+ c e -c"r , which gives the upper bound.

For the lower bound the very beginning starts with the same spirit as the proof of Lemma A.2 in [START_REF] Hu | The potential energy of biased random walks on trees[END_REF] : let r k = a * k for 0 ≤ k ≤ N := r a and a > 0 (chosen later) then

∩ N k=0 {inf{i > τ r k , S i ≥ r k+1 } < inf{i > τ r k , S i ≤ r k -}} ⊂ {τ r ≤ τ S-S }, then, the strong Markov property gives E e -cσ 2 2 2 τr 1 τr≤τ S-S ≥ Π N k=0 E r k e -cσ 2 2 2 τr k+1 1 τr k+1 <τ - r k - = Π N k=0 E e -cσ 2 2 2 τr k+1 -r k 1 τr k+1 -r k <τ - - = E e -cσ 2 2 2 τa 1 τa<τ - - N +1
.

So we only need a lower bound for Laplace transform of the form E(e -hτa 1 τa<τ - -), with h = h( ) → 0. From here we follow the same lines as for the upper bound with following differences, τ 0 (resp. τ - 0 ) is replaced by τ a (resp. by τ - -a ), also estimation (69) should be replaced by following one that can be found in [START_REF] Aidekon | The Seneta-Heyde scaling for the branching random walk[END_REF] : there exists 0 < θ < +∞ such that uniformly in a ∈ [0, a ] with a = o( 1/2 )

P(τ - -a ≥ z 2 ) ∼ θR(a) √ z ,
for large , where R the usual renewal function (see (2.3) in [START_REF] Aidekon | The Seneta-Heyde scaling for the branching random walk[END_REF]) with following property (see (2.6) together with Lemma 2.1 in [START_REF] Aidekon | The Seneta-Heyde scaling for the branching random walk[END_REF])

lim a→∞ R(a) a = 1 θ 2 πσ 2 1/2 . ( 75
)
Now considering (68), with the change we have just talked above, as for any a > 0, lim

→+∞ P(τ ≤ z 2 |τ - -a > z 2 ) = P(m 1 > 1/σ √ z), we obtain lim m→∞ P 2 = lim →∞ P(τ - -a > z 2 , τ ≤ z 2 ) = θR(a) √ z P(m 1 > 1/σ √ z),
similarly for P 1 = P(τ - a > τ > z 2 ), for large enough and then taking the limit A → +∞

P 1 ≥ (1 -ε) θR(a) A 2 k=z 2 P(S k-1 ≤ , S k > | τ - a > k) k 1/2 ≥ (1 -2ε) θR(a) +∞ z 1 y 1/2 dP(m 1 > 1/ yσ 2 ).
We then obtain the equivalent of (71), that is lim →∞ P(τ a > z 2 , τ a > τ - -) = θR(a)f (z) from which we deduce following lower bound for associated Laplace transform :

lim →+∞ mE (1 -e -λ 2 τa )1 τa>τ -= λθR(a) +∞ 0 e -λu f (u)du.
In the same spirit lim →+∞ E[1 -e -λ 2 τ-a ] = √ λπθR(a). Also first Lemma 2.2 in [START_REF] Aïdékon | Tail asymptotics for the total progeny of the critical killed branching random walk[END_REF] gives for any a > 0 and any large P(τ -a > τ - -) = P -a (τ 0 > τ - --a ) ∼ E(-S τ-a )/ . So finally collecting these estimates and taking λ = σ 2 c/2, for any ε > 0 and large enough

E e -cσ 2 2 2 τr 1 τr≤τ S-S ≥ 1 - E(-S τ-a ) + θR(a) π 2 σ √ c - cσ 2 2 +∞ 0 e -cσ 2 2 u f (u)du (1 + ε) N +1
. Now recall that N = r/a, so let us take a large enough in such a way that (using (75)) R(a)/a ≤ 1 θ 2 πσ 2 1/2 (1 + ε). Also for large a, E(-S τ-a )/a ≤ (1 + ε) (this can be seen easily, noticing that undershoot S τ-a -a has a second moment). This finishes the proof. Lemma 4.2. For any ε > 0, β > 0, any r large enough uniformly in t = t(r) with lim r→+∞ r -t = +∞, E e -max 1≤j≤τ r-t Sj -Sj ≤ e -2 √ r-t(1-ε) .

Proof. Like in the proof of Lemma 4.1 we use strict ladder epoch sequence (T k := inf{s > T k-1 , S s > S T k-1 }, k; T 0 = 0), also let us introduce random variable Y k := max T k-1 ≤j≤T k S j -S j for any k ≥ 1. Let m a positive integer to be chosen later, by the strong Markov property

E e -max 1≤k≤m Y k = m k=1 E(e -Y k 1 Y k >max i≤k-1 Yi, Y k ≥max k+1≤i≤m Yi ) ≤ mE(e -Y2 (1 -P(Y 1 > Y 2 |Y 2 )) m-1 ).
At this point we need an asymptotic in y of M (y) := P(Y 1 > y) = P(max 0≤s≤T0 S s < -y) = P(τ 0 > τ -y ), for that we use following equality (see for example [START_REF] Aïdékon | Tail asymptotics for the total progeny of the critical killed branching random walk[END_REF] Lemma 2.2) : for large y, P(τ 0 > τ -y ) = E(S τ0 )/y + o(1/y). So for any large A, and ε > 0

e -Y2 (1 -P(Y 1 > Y 2 |Y 2 )) m-1 =e -Y2 (1 -P(Y 1 > Y 2 |Y 2 )) m-1 1 Y2>A + e -Y2 (1 -P(Y 1 > Y 2 |Y 2 )) m-1 1 Y2≤A ≤e -Y2 1 -E(S τ0 )(1 -ε)(Y 2 ) -1 m-1 1 Y2>A + (1 -P(Y 1 > A)) m-1 ,
For the second term above we can find constant c = c(A) such that (1 -P(Y 1 > A)) m-1 ≤ e -cm . For the first term , let us introduce measure dM defined as M (x) = +∞ x dM (z)dz, then integrating by parts

E(e -Y2 1 -E(S τ0 )(1 -ε)(Y 2 ) -1 m-1 1 Y2>A ) = - +∞ A e -x 1 - E(S τ0 )(1 -ε) x m-1 dR(x) ≤ e -A 1 - E(S τ0 )(1 -ε) A m-1 - +∞ A e -x 1 - E(S τ0 )(1 -ε) x m-1 R(x)dx -(m -1)S τ0 (1 -ε) +∞ A e -x x 2 1 - E(S τ0 )(1 -ε) x m-2 R(x)dx ≤ e -2(1-4ε) √ E(Sτ 0 )m ,
the last inequality is definitely not optimal but enough for what we need, we can obtain it easily decomposing the interval (A, +∞) on the intervals (A, E(S τ0 )m(1 -ε)), ( E(S τ0 )m(1ε), E(S τ0 )m(1 + ε)) and ( E(S τ0 )m(1 + ε), +∞). Collecting the above inequalities, we obtain that for any ε > 0 and m large enough

E e -max 1≤k≤m Y k ≤ 2me -2(1-4ε) √ E(Sτ 0 )m .
To finish the proof we follow the same lines as the end of the proof of Lemma 4.1 (below (74)),

that is saying that E e -max 1≤j≤τ r-t Sj -Sj ≤ E e -max 1≤k≤m Y k + P(S T k ≥ r -t) then taking k = (1 -ε)(r -t)/E(S τ0 ).

Additional technical estimates

Lemma 4.3. Let (t ) a positive increasing sequence such that t -1/2 → +∞ but t -1 → 0. For any B > 0 and large enough

P(τ S-S 1/2 ∨ τ - -B > τ t ) ≥ e - t √ (1+o(1)) . (76)
Let A > 0 large, d ∈ (0, 1/2), a > 0, 0 < b < 1, q ∈ [b, 1], a b := a(21 q>b -1) and c > 0

j≤A 3/2 P S j ≥ t , sup m≤j H S m ≤ e q √ -a b d , e b √ ≤ H S j ≤ e b √ +c d , S j ≥ -B ≥ e - t q √ (1+o(1)) . (77)
Proof. The proof of (76) follows the same lines as the proof of Lemma A.2 in [START_REF] Hu | The potential energy of biased random walks on trees[END_REF]. For (77), as j ≤ A 3/2 , for any (d, e) and any m ≤ j, A

H S m ≤ e q * √ -a b d , S j ≥ -B ≥ P S j ≥ t , b √ ≤ S j -S j ≤ b √ + c d , sup m≤j S m -S m ≤ q √ -a d , S j ≥ -B
with c = c/2 and a = a b + 1. To obtain a lower bound for the above probability, the idea is to say that maximum of S is obtained at a certain instant k ≤ j and that this maximum is larger than t + b √ + c d + r for a certain r > 0 to be chosen latter, then above probability is larger than :

k≤j P(S k-1 < S k , S k ≥ t + b √ + c d + r, sup m≤k S m -S m ≤ √ -a d , S k ≥ -B; S j -S k ≥ t -S k , b √ ≤ S k -S j ≤ b √ + c d , ∀m ≥ k + 1, S m ≤ S k , S k -S m ≤ √ -a d , S m -S k ≥ -B -S k ).
Now, the events {S m -S k ≥ -B -x}, as well as {S j -S k ≥ t -x} increases in x and as S k ≥ t + b √ + c d + r so we can replace, in the two events of the above probability, «-S k » by -(t + b √ + c d + r). This makes appear two independent events, so above probability is larger than ) is smaller, thanks to Proposition 3.1 in [START_REF] Faraud | Almost sure convergence for stochastically biased random walks on trees[END_REF], to e -π 2 σ 2 j/4 this implies that k>A 3/2 P(sup m≤k S m -S m ≤ √ ) ≤ e -π 2 σ 2 A 1/2 /2 . Now if we apply (76) to the first probability above as b √ + c d = o(t ), this finishes the proof.

P(S k-1 < S k , S k ≥ t + b √ + c d + r, sup m≤k S m -S m ≤ √ -a d , S k ≥ -B)× P(S j -S k ≥ -b √ -c d -r, b √ ≤ S k -S j ≤ b √ + c d , ∀m ≥ k + 1, -B -t -b √ + c d -r ≤ S m -S k ≤ 0, S m -S k ≥ - √ + a d ) =: p 1 (k) * p 2 (k, j). ( 78
Lemma below is a simple extension of FKG inequality.

In the following, a function F : R k -→ R is said to be non-decreasing if: for all s = (s 1 , . . . , s k ) ∈ R k and t = (t 1 , . . . , t k ) ∈ R k , s ≤ k t implies F (s) ≤ F (t) where s ≤ k t if and only if s j ≤ t j for all j ∈ {1, . . . , k}.

Lemma 4.4. Let r > 0, k ∈ N * , f 1 , f 2 : R k -→ R + . For any i ∈ {1, 2}, introduce fi (u 1 , . . . , u k ) := f i (u 1 , u 1 + u 2 , . . . , u 1 + u 2 + . . . + u k ). If f1 and f2 are non-decreasing then E f 1 (S 1 , S 2 , . . . , S k )f 2 (S 1 , S 2 , . . . , S k ) ≥ E f 1 (S 1 , S 2 , . . . , S k ) E f 2 (S 1 , S 2 , . . . , S k ) .

Proof. When R k is a totally order set, the first inequality above is the well known regular FKG inequality. Here, we can easily extend it to the partial order ≤ k . Indeed, since fi is non-decreasing for any i ∈ {1, 2}, we have, by independence of increments of S i∈{1,2}

E f i (S 1 , S 2 , . . . , S k ) = i∈{1,2}

E fi (S 1 , S 2 -S 1 , . . . , S k -S k-1 ) = E[F 1 (S 1 )]E[F 2 (S 1 )],

with F i (u 1 ) := E fi (u 1 , S 2 -S 1 , . . . , S k -S k-1 ) for any i ∈ {1, 2}. Since fi is non-decreasing, F i is also non-decreasing so thanks to the regular FKG inequality, E[F 1 (S 1 )]E[F 2 (S 1 )] ≤ E[F 1 F 2 (S 1 )]. Again, using that the increments of S are independent and stationary, the result follows by induction.

Lemma 4.5. Let (t ) a sequence of positive numbers such that t / → 0. For all d ∈ (0, 1/2] such that t / d → +∞ and all ε, B > 0, a ≥ 0 and 0 ≤ d < d for n large enough Proof. Recall that τ r = inf{i ≥ 1; S i ≥ r}. First, observe that for all j ≤ k ≤ 2 , H S j ≤ 2 e Sj -Sj so with for all i ∈ {1, 2}, f i := 1 A i , f 1 f 2 (u) = f 1 (u)f 2 (u) and

k≤ 2 P S k ≥ t ,
A 1 := u = (u 1 , . . . , u k ) ∈ R k ; ∃ j ≤ 2 : u j ≥ t ,
and

A 2 := u = (u 1 , . . . , u k ) ∈ R k ; ∀ j ≤ τ k ,t t , ∀i < j : u j -u i ≥ -d + a d + 2 log , u j ≥ -B .
Then, it is easy to see that for all i ∈ {1, 2}, fi (see Lemma 4.4 for the definition) is non-decreasing according to the partial order ≤ k defined above. Then, thanks to Lemma 4.4, E[f 1 f 2 (S 1 , S 2 , . . . , S k )] is larger than ≥ P (S 1 , S 2 , . . . , S kn ) ∈ A 1 P (S 1 , S 2 , . . . , S k ) ∈ A 2 ≥ P(S 2 ≥ t )P ∀j ≤ τ k t : S j -S j ≤ d -a d -2 log , S j ≥ -B, τ t ≤ k .

Again, on {τ t ≤ k }, τ k t = τ t and thanks to [START_REF] Kozlov | On the asymptotic behavior of the probability of non-extinction for critical branching processes in a random environment[END_REF] (Theorem A), there exists C K > 0 such that for large enough P ∀j ≤ τ k t : S j -S j ≤ d -a d -2 log , S j ≥ -B, τ t ≤ k ≥ P ∀j ≤ τ t : S j -S j ≤ d -a d -2 log , S j ≥ -B -P(τ t > k ) ≥ P ∀j ≤ τ t : S j -S j ≤ d -a d -2 log , S j ≥ -B -C K e -. Moreover, t / → 0 so P(S 2 ≥ t ) → 1. Finally, by (76) together with the fact that d ∼ da d -2 log (as d > d ) for large enough, P ∀j ≤ τ t : S j -S j ≤ d -a d -2 log , S j ≥ -B ≥ 2e -t -d (1+ε) and since t n / d = o( ), C K e -≤ e -t -d (1+ε) , the result follows. , S k ≥ 0 . We need independence to compute this probability so for all k ∈ N * , L < k ≤ 2 , we say that S k = S k-≥ λ which gives that for all k -< j ≤ k, S j ≤ S k-and then, max k-<j≤k S k--S j ≤ λ implies that S j ≥ S k--λ n ≥ 0 for all k -< j ≤ k. Hence

√ + c 2 d ] ,
which is larger than C/ for large enough (see Lemma 4.3).

We then deal with P(A k, ). Thanks to Lemma 4.4, this probability is larger than P max j≤k-S j -S j ≤ λ P S k-≥ λ P S k-≥ 0 2 , and again, using [START_REF] Kozlov | On the asymptotic behavior of the probability of non-extinction for critical branching processes in a random environment[END_REF] together with the fact that P(S L ≥ λ ) → 1, there exists C > 0 such that for large enough and any k ∈ {L , . . . , 2 },

P S k-≥ √ P S k-≥ 0 ≥ P S L ≥ √ P S 2 ≥ 0 2 ≥ C 2 .
We now turn to the most important part: P max j≤k-S j -S j ≤ λ . We follow the same lines as the proof of (79): for any k ∈ {L , . . . , 2 }, k -> L -so max j≤L -S j -S j ≤ λ together with S L -= S L -≤ S j and max L -<i≤j S i -S j ≤ λ for all L -< j ≤ k -implies that max j≤k-S j -S j ≤ λ . It follows that P max j≤k-S j -S j ≤ λ is larger than for some C > 0. Then, thanks to [START_REF] Faraud | Almost sure convergence for stochastically biased random walks on trees[END_REF], for all ε > 0 and large enough P(max j≤L -S j -S j ≤ λ ) ≥ e -(1+ ε 4 )

P max
π 2 σ 2 (L -) 8

(λ ) -2 so for large enough and any k ∈ {L , . . . , 2 }, P max j≤k-S j -S j ≤ λ is larger than is smaller than 1 η for any η, η > 0. Collecting previous inequalities, we obtain

C √ L - e -(1+ ε
P(A k, ) ≥ C 2 e -(k-)(1+ ε 2 ) π 2 σ 2 8(λ ) 2 .
Finally, observe that λ ∼ √ and then for any k ∈ {L , . . . , 2 } P(A k, ) ≥ e -kπ 2 σ 2 8 (1+ε) , which completes the proof.

Notations

In this section, we have summarized the transversal notations, give a short description of them when it is possible and the page or equation where they are introduced.

Sequences and constants in the statement of the main theorem κ b (equation ( 12)), critical exponent. h n (equation ( 13)), resume the constraint on V and second order for R n (g n , f n ). L (equation ( 14)).

ξ (equation ( 15)).

Different form of the cumulative exponential drop of V H x (below (8)), variable appearing in the distribution under P E of the edge local time at x before the instant T 1 . Hx (Lemma 3.1), variable appearing in the distribution under P E of the sum of edge local times of the descendants of x before the instant T 1 . H S (page 15) version of above H after the many to one Lemma is applied. Elementary random variables related to the random walk X N n x Edge local time at (x * , x) before n (equation ( 39)). T n (page 7) n-th instant of return to the root e. E n x , Ẽn x (above 59).

Different ranges R n (g n , f n ) the generalized range (equation (3)) with g n function of constraints on the trajectory of (X n , n), f n function of constraints on the potential V . R T n (g n , f n ) variant of R T n (g n , f n ) with additional condition on V (page 7).

y;y * =x N T 1 y

 1 is finally geometrical on N under P E z with mean Hx and β x = Hx /(1 + Hx ). Introduce α x := P E (min y;y * =x T y < T 1 ), the quenched probability to reach the set {y ∈ T; y * = x} during the first excursion. Thanks to (40), we have for all k ∈ N * P E y;y * =x

)

  Probability p 2 can be easily simplified, indeed as lim →+∞ t / √ = +∞ and large, -B -tb √ + c d -r ≤ -√ and by taking r = c d , p 2 is smaller thanP(-b √ -c d ≤ S j -S k ≤ -b √ , ∀m ≥ k + 1, -√ + a d ≤ S m -S k ≤ 0) =P(∀m ≤ j -k, -√ + a d ≤ S m ≤ 0, -b √ -c d ≤ S j-k ≤ -b √ ) =P(∀m ≤ j -k, S m ≤ √ -a d |S j-k ≥ 0, S j-k ∈ [b √ , b √ + c d ])× P(S j-k ≥ 0, S j-k ∈ [b √ , b √ + c d ]),with S m = -S m for any m. For the conditional probability we can use a similar result proved by Caravenna and Chaumont[START_REF] Caravenna | An invariance principle for random walk bridges conditioned to stay positive[END_REF] telling that the distributionP x (•|∀m ≤ n, S m ≥ 0, S n ∈ [0, h))converges. Note that they need in their work additional hypothesis on the distribution of S 1 (more especially absolute continuity of the distribution of S 1 ) which is not necessary here as the size of interval[b √ , b √ + c d ] equals c d → +∞. So as a d = o( √ ) lim →+∞ P(∀m ≤ , S m ≤ c √ -a d |S ≥ 0, S ∈ [b √ , b √ + c d ]) = Cte > 0.Moreover another work of Caravenna ([Car05] Theorem 1) gives for large ,P(S ≥ 0, S ∈ [b √ , b √ + c d ) ≥ b/ .So finally when j -k is of the order of , there exists a constante Cte > 0 such that p 2 (k, j) ≥ Cte * -1 . Turning back to (78) and summing over k and j, we obtainj≤A 3/2 k≤j p 1 (k)p 2 (k, j) k-1 < S k , S k ≥ t + b(1 + 2ε )check that above sum k>A 3/2 • • • as a negligible contribution, indeed the probability P(sup m≤k S m -S m ≤ √

k≤ 2 P

 2 S k ≥ t , max j≤k H S j ≤ e d -a d , S k ≥ -B, S k = S k ≥ e -t d(1+ε) .

Lemma 4. 6 .,kπ 2 σ 2 8 .√

 68 Let α ∈ (1, 2) and ε α ∈ [0, α -1) and introduce L := χ 1+ εα 2 , χ > 0. For all ε > 0, large enough and any k ∈ {L , . . . , and for any a, d, c > 0, b ∈ (0, 1), large enough and any k ∈ {L , . . . ,2 } P max j≤k H S j ≤ e √ -a d , e b √ < H S k ≤ e b √ +c d , S k ≥ 0 ≥ e -kπ 2 σ 2 8 (1+ε) . (80)Proof. Let us start with the upper bound. Thanks to the Markov property, for any k ∈ N, k > L and thanks to[START_REF] Faraud | Almost sure convergence for stochastically biased random walks on trees[END_REF], for large enough, P max j≤L S j -S j ≤ √ ≤ e -π 2 σ 2 L8(1-ε 2 ) , so for any ε, large enough and any k > L For the lower bound, observe that for any k ≤ 2 , P max j≤k H S j+c d , S k ≥ 0 is larger than P max j≤k S j -S j ≤ λ , b √ < S k -S k ≤ b √ +c d -log 2 , S k ≥ 0 , where λ := √ -a d -log 2 . As c 2 d ≥ log 2 (d > 0), the previous probability is larger thanP max j≤k S j -S j ≤ λ , b √ < S k -S k ≤ b √ + c 2 d

P≥ 0 ×

 0 max j≤k S j -S j ≤ λ , b √ < S k -S k ≤ b √ + c 2 d , S k ≥ 0 ≥ P(A k, ∩ B k, ) = P(A k, )P(B k, ), with A k, := max j≤k-S j -S j ≤ λ , S k-≥ 0, S k-= S k-≥ λ ,andB k, := ∀ k -< j ≤ k, S k--S j ≤ λ , S j ≤ S k-, b √ < S k--S k ≤ b √ + c 2 d .Let S := -S. P(B k, ) is nothing butP S ≤ λ , S ≥ 0, S ∈ (b P S ≤ λ |S > 0, S ∈ (b √ , b

  j≤L -S j -S j ≤ λ , S L -= S L -, maxL -<i≤j S i -S j ≤ λ , S j ≥ S L -∀ L -< j ≤ k -= P max j≤L -S j -S j ≤ λ , S L -= S L -P max j≤k--(L -) S j -S j ≤ λ , S k--(L -) ≥ 0 .Moreover, by Lemma 4.4,P max j≤k--(L -) S j -S j ≤ λ , S k--(L -) ≥ 0 is larger than P(max j≤k--(L -) S j -S j ≤ λ )P(S k--(L -) ≥ 0). By induction, we get that P max j≤k-S j -S j ≤ λ is larger thanP max j≤L -S j -S j ≤ λ , S L -= S L - L (k) i≤L (k) P S k--i(L -) ≥ 0 with L (k) := (k -)/(L -) .Again, by Lemma 4.4, P(max j≤L -S j -S j ≤ λ , S L -= S L -≥ P max j≤L -S j -S j ≤ λ )P(S L -≥ 0) and as k ≤ 2 , P(S k--i(L -) ≥ 0) ≥ P S k ≥ 0 ≥ P S 2 ≥ 0 . Hence, by[START_REF] Kozlov | On the asymptotic behavior of the probability of non-extinction for critical branching processes in a random environment[END_REF] P max j≤k-S j -S j ≤ λ ≥ C √ L -P max j≤L -S j -S j ≤ λ L (k)

  where we have used for the first inequality that e -η π 2 σ 2 (L -) 8(λ ) 2

  The regular lines and their possible parameters : O λ,λ := x ∈ T; max j≤|x|H xj ≤ λ, H x > λ λ = λ n (above 21), λ = λ n (below (23)), λ = λ n,1 and λ = λ n,2 (in the proof of Theorem 1.3), λ = λn in the proof of Lemma 3.6. All along the paper λ is typically of order n b .Secondary constraints on the environment :H k B,z = {(t 1 , . . . , t k ) ∈ R k ; t k ≥ z, min i≤k t i ≥ -B} z = z n = 1/3 n /δ 1 (beginning of Section 3.2). Υ . . (Proposition 1) : various intersections of conditions on H and H k B,. . The branching function Ψ Ψ k λ,λ (equation (9)), k is a generation, λ an upper bound for H, λ a lower bound for H. Ψ k λ,λ (•|•) (equation (18)) a conditional version of Ψ k λ,λ .

  3/2 exp(S m -S m ) ≤ e d

					√	+e d implies H S m ≤ e d	√	+e d
	then
	P S j ≥ t , e b	√	≤ H S j ≤ e b √	+c d	, sup m≤j

  max which is equal to P S 2 ≥ t , ∀j ≤ τ t : S j -S j ≤ d -a d -2 log , S j ≥ -B . Now let k = (e t ) 2 + 2 . First note that, since 2 ≤ k , we have, on{S 2 ≥ t }, τ t = τ k t with τ k t := k ∧ inf{i ≤ k ; S i ≥ t } so P S 2 ≥ t , ∀j ≤ τ t : S j -S j ≤ d -a d -2 log , S j ≥ -B = P S 2 ≥ t , ∀j ≤ τ k t : S j -S j ≤ d -a d -2 log , S j ≥ -B .For any k ∈ N * and r > 0, let t= (t 1 , . . . , t k ) ∈ R k and define the t-version τ k,t ∧ inf i ≤ k; t i ≥ r ,with the usual convention inf ∅ = +∞. ThenP S 2 ≥ t n , ∀j ≤ τ k t : S j -S j ≤ d -a d -2 log , S j ≥ -B = E f 1 f 2 (S 1 , S 2 , . . . , S k ) ,

		r	of τ k r that is
	τ k,t r	:= k
	j≤k	H S j ≤ e

d -a d , S k ≥ -B, S k = S k ≥ k≤ 2 P k = τ t , max j≤k S j -S j ≤ d -a d -2 log , S k ≥ -B ,