Elie Aidékon

Large deviations for transient random walks in random

Keywords: Random walk in random environment, law of large numbers, large deviations, Galton-Watson tree AMS subject classifications. 60K37, 60J80, 60F15, 60F10

published or not. The documents may come

Large deviations for random walks in random

environment on a Galton-Watson tree

Introduction

We consider a super-critical Galton-Watson tree T of root e and offspring distribution (q k , k ≥ 0) with finite mean m := k≥0 kq k > 1. For any vertex x of T, we call |x| the generation of x, (|e| = 0) and ν(x) the number of children of x; we denote these children by x i , 1 ≤ i ≤ ν(x). We let ν min be the minimal integer such that q ν min > 0 and we suppose that ν min ≥ 1 (thus q 0 = 0). In particular, the tree survives almost surely. Following Pemantle and Peres [START_REF] Pemantle | Critical random walk in random environment on trees[END_REF], on each vertex x, we pick independently and with the same distribution a random variable A(x), and we define

• ω(x, x i ) := A(x i ) 1+ ν(x) i=1 A(x i ) , ∀ 1 ≤ i ≤ ν(x), • ω(x, ← x) := 1 1+ b i=1 A(x i ) .
To deal with the case x = e, we add a parent ← e to the root and we set ω( ← e , e) = 1. Once the environment built, we define the random walk (X n , n ≥ 0) starting from y ∈ T by

P y ω (X 0 = y) = 1, P y ω (X n+1 = z | X n = x) = ω(x, z) .
The walk (X n , n ≥ 0) is a T-valued Random Walk in Random Environment (RWRE). To determine the transience or recurrence of the random walk, Lyons and Pemantle [START_REF] Lyons | Random walk in a random environment and first-passage percolation on trees[END_REF] provides us with the following criterion. Let A be a generic random variable having the distribution of A(e).

Theorem A (Lyons and Pemantle [START_REF] Lyons | Random walk in a random environment and first-passage percolation on trees[END_REF]) The walk

(X n ) is transient if inf [0,1] E[A t ] > 1 m
, and is recurrent otherwise. We make the hypothesis that 0 < i ≤ s < ∞. Under this assumption, we gave a criterion in [START_REF] Aidékon | Transient random walks in random environment on a Galton-Watson tree[END_REF] for the positivity of the speed v. Let

Λ := Leb t ∈ R : E[A t ] ≤ 1 q 1 (Λ = ∞ if q 1 = 0). (1.1) Theorem B ([1]) Assume inf [0,1] E[A t ] > 1
m , and let Λ be as in (1.1). (a) If Λ < 1, the walk has zero speed.

(b) If Λ > 1, the walk has positive speed.

2

When the speed is positive, we would like to have information on how hard it is for the walk to have atypical behaviours, which means to go a little faster or slower than its natural pace. Such questions have been discussed in the setting of biased random walks on Galton-Watson trees, by Dembo et al. in [START_REF] Dembo | Large deviations for random walks on Galton-Watson trees: averaging and uncertainty[END_REF]. The authors exhibit a large deviation principle both in quenched and annealed cases. Besides, an uncertainty principle allows them to obtain the equality of the two rate functions. For the RWRE in dimensions one or more, we refer to Zeitouni [START_REF] Zeitouni | Random walks in random environment[END_REF] for a review of the subject. In our case, we consider a random walk which always avoids the parent ← e of the root, and we obtain a large deviation principle, which, following [START_REF] Dembo | Large deviations for random walks on Galton-Watson trees: averaging and uncertainty[END_REF], has been divided into two parts.

We suppose in the rest of the paper that inf

[0,1] E[A t ] > 1 m , (1.2) Λ > 1 , (1.3)
which ensures that the walk is transient with positive speed. Before the statement of the results, let us introduce some notation. Define for any n ≥ 0 and x ∈ T,

τ n := inf {k ≥ 0 : |X k | = n} , D(x) := inf k ≥ 1 : X k-1 = x, X k = ← x , (inf ∅ := ∞) .
Let P denote the distribution of the environment ω conditionally on T, and Q := P(•)GW (dT). Similarly, we denote by P x the distribution defined by P x (•) := P x ω (•)P(dω) and by Q x the distribution Q x (•) := P x (•)GW (dT) . Besides, if i > ν -1 min , then I a and I q are strictly increasing on [1/v, +∞[. When i ≤ ν -1 min , we have I a = I q = 0 on the interval.

As pointed by an anonymous referee, it would be interesting to know when I a and I q coincide. We do not know the answer in general. However, the computation of the value of the rate functions at b = 1 reveals situations where the rate functions differ. Let

I q (1) = -inf ]0,1] 1 θ ψ(θ) . (1.9)
In particular, I a (1) = I q (1) if and only if ψ ′ (1) ≤ ψ [START_REF] Aidékon | Transient random walks in random environment on a Galton-Watson tree[END_REF]. Otherwise I a (1) < I q (1).

Quite surprisingly, we can exhibit elliptic environments on a regular tree for which the rate functions differ. This could hint that the uncertainty of the location of the first passage in [START_REF] Dembo | Large deviations for random walks on Galton-Watson trees: averaging and uncertainty[END_REF] does not hold anymore for a random environment. Here is an explicit example. Consider a binary tree (q 2 = 1). Let A equal 0.01 with probability 0.8 and 500 with probability 0.2. Then we check that the walk is transient, but ψ ′ (1) > ψ(1) so that I a (1) = I q (1) on such an environment. Theorem 1.2 exhibits a subexponential regime in the slowdown case when i ≤ ν -1 min . The following theorem details this regime. Let

S e (•) := Q e (. | D(e) = ∞) .
Theorem 1. [START_REF] Comets | Majorizing multiplicative cascades for directed polymers in random media[END_REF] We place ourself in the case i < ν -1 min . (i) Suppose that either "i < ν -1 min and q 1 = 0" or "i < ν -1 min and s < 1" . There exist constants d 1 , d 2 ∈ (0, 1) such that for any a > 1/v and n large enough, e -n d 1 < S e (τ n > an) < e -n d 2 .

(1.10) (ii) If q 1 > 0 and s > 1 (id est when Λ < ∞), the regime is polynomial and we have for any

a > 1/v, lim n→∞ 1 ln(n) ln (S e (τ n > an)) = 1 -Λ . (1.11)
We mention that in one dimension, which can be seen as a critical state of our model where q 1 = 1, such a polynomial regime is proved by Dembo et al. [START_REF] Dembo | Tail estimates for one-dimensional random walk in random environment[END_REF], our parameter Λ taking the place of the well-known κ of Kesten, Kozlov, Spitzer [START_REF] Kesten | A limit law for random walk in a random environment[END_REF]. We did not deal with the critical case i = ν -1 min . Furthermore, we do not have any conjecture on the optimal values of d 1 and d 2 and do not know if the two values are equal.

The rest of the paper is organized as follows. Section 2 describes the tail distribution of the first regeneration time, which is a preparatory step for the proof of the different theorems. Then we prove Theorems 1.1 and 1.2 in Section 3, which includes also the computation of the rate functions at speed 1 presented in Proposition 1.3. Section 4 is devoted to the subexponential regime with the proof of Theorem 1.4.

Moments of the first regeneration time

We define the first regeneration time

Γ 1 := inf k > 0 : ν(X k ) ≥ 2, D(X k ) = ∞, k = τ |X k |
as the first time when the walk reaches a generation by a vertex having more than two children and never returns to its parent. We propose in this section to give information on the tail distribution of Γ 1 under S e . We first introduce some notation used throughout the paper. For any x ∈ T, let

N(x) := k≥0 1I {X k =x} , (2.1)
T x := inf {k ≥ 0 : X k = x} , T * x := inf{k ≥ 1 : X k = x} .
This permits to define

β(x) := P x ω (T← x = ∞) , γ(x) := P x ω (T← x = T * x = ∞) . (2.2)
The following fact can be found in [START_REF] Dembo | Large deviations for random walks on Galton-Watson trees: averaging and uncertainty[END_REF] (Lemma 4.2) in the case of biased random walks, and is directly adaptable in our setting.

Fact A The first regeneration height |X Γ 1 | admits exponential moments under the measure S e (•).

The case i > ν -1 min

This section is devoted to the case i > ν -1 min , where Γ 1 is proved to have exponential moments.

Proposition 2.1 Suppose that i > ν -1 min . There exists θ > 0 such that E S e e θΓ 1 < ∞.

Proof. The proof follows the strategy of Proposition 1 of Piau [START_REF] Piau | Théorème central limite fonctionnel pour une marche au hasard en environment aléatoire[END_REF]. We couple the distance of our RWRE to the root (|X n |) n≥0 with a biased random walk (Y n ) n≥0 on Z as follows.

Let p := iν min 1+iν min , and let u n , n ≥ 0, be a family of i.i.d. uniformly distributed [0,1] random variables. We set X 0 = e and Y 0 = 0. If X k and Y k are known, we construct

X k+1 = x i if i-1 ℓ=1 ω(x, x ℓ ) ≤ u k < i ℓ=1 ω(x, x ℓ ) , X k+1 = ← x otherwise , Y k+1 = y + 21I {u k ≤p} -1 ,
where x := X k ∈ T and y := Y k ∈ Z. Then (X n ) n≥0 has the distribution of our T-RWRE indeed, and (Y n ) n≥0 is a random walk on Z which increases of one unit with probability p > 1/2 and decreases of the same value with probability 1p. Notice also that on the event {D(e) = ∞}, we have

|X k+1 | -|X k | ≥ Y k+1 -Y k .
It implies that the first regeneration time R 1 of (Y n ) n≥0 defined by

R 1 := inf {k > 0 : Y ℓ < Y k ∀ℓ < k , Y m ≥ Y k ∀m > k}
is necessarily a regeneration time for (X n , n ≥ 0), which proves in turn that

S e (Γ 1 > n) ≤ Q e (R 1 > n) .
To complete the proof, we must ensure that Q e (R 1 > n) is exponentially small, which is done in [START_REF] Dembo | Tail estimates for one-dimensional random walk in random environment[END_REF] Lemma 5.1.

2.2

The cases "i < ν -1 min , q 1 = 0" and " i < ν -1 min , s < 1"

When i < ν -1 min , if we assume also that q 1 = 0 or s < 1, we prove that Γ 1 has a subexponential tail. This situation covers, in particular, the case of RWRE on a regular tree. Proposition 2.2 Suppose that i < ν -1 min and q 1 = 0, then there exist

1 > α 1 > α 2 > 0 such that for n large enough, e -n α 1 < S e (Γ 1 > n) < e -n α 2 . (2.3)
The same relation holds with some 1 > α 3 > α 4 > 0 in the case "i < ν -1 min and s < 1".

Proof of Proposition 2.2: lower bound. We only suppose that i < ν -1 min , which allows us to deal with both cases of the lemma. Define for some p ′ ∈ (0, 1/2) and b ∈ N,

w + := Q ν i=1 A(e i ) ≥ 1 -p ′ p ′ , ν(e) ≤ b , w -:= Q ν i=1 A(e i ) ≤ p ′ 1 -p ′ , ν(e) ≤ b . By (1.2), E Q ν(e) i=1 A(e i ) > 1 and therefore Q ν(e) i=1 A(e i ) > 1 > 0. Since ess inf A < ν -1 min , it guarantees that Q ν(e)
i=1 A(e i ) < 1 > 0. Consequently, by choosing p ′ close enough of 1/2 and b large, we can take w + and w -positive. Let c := 1 6 ln(b) , and define h n := ⌊c ln(n)⌋. A tree T is said to be n-good if

• any vertex x of the h n first generations verifies ν(x) ≤ b and ν(x) i=1 A(x i ) ≥ 1-p ′ p ′ ,
• any vertex x of the h n following generations verifies ν(x) ≤ b and ν 1) which is stretched exponential, i.e. behaving like e -n r+o (1) for some r ∈ (0, 1). Define the events Suppose that the tree is n-good. Since A is supposed bounded, there exists a constant c 1 > 0 such that for any x neighbour of y, we have

(x) i=1 A(x i ) ≤ p ′ 1-p ′ . We observe that Q(T is n-good) ≥ w hnb hn + w hnb 2hn - ≥ e -n 1/3+o(
E 1 := {at
ω(x, y) ≥ c 1 ν(x) . (2.4)
It yields that P e ω (E 1 ) -1 = O(n K ) for some K > 0 (where O(n K ) means that the function is bounded by a factor of n → n K ). Combine (2.4) with the strong Markov property at time τ hn to see that

P e ω (E 3 | E 1 ∩ E 2 ) -1 = O(n K ) ,
where K is taken large enough. We emphasize that the functions O(n K ) are deterministic. Still by Markov property,

P e ω (E 1 ∩ E 2 ∩ E 3 ∩ E 4 ) = E e ω [1I E 1 ∩E 2 ∩E 3 β(X τ 2hn )] . (2.5) Let (Y ′ n ) n≥0
be the random walk on Z starting from zero with

P ω (Y ′ n+1 = k + 1 | Y ′ n = k) = 1 -P ω (Y ′ n+1 = k -1 | Y ′ n = k) = p ′ .
We introduce T ′ i := inf{k ≥ 0 : Y k = i}, and p ′ n the probability that (Y ′ n ) n≥0 visits h n before -1:

p ′ n := P ω (T ′ -1 < T ′ hn ) .
By a coupling argument similar to that encountered in the proof of Proposition 2.1, we show that in an n-good tree,

P e ω (E 1 ∩ E 2 ) ≥ P e ω (E 1 )(p ′ n ) n = O(n K ) -1 (p ′ n ) n , (2.6)
which gives

P e ω (E 1 ∩ E 2 ∩ E 3 ) ≥ O(n K ) -1 (p ′ n ) n . (2.7) Observing that Q e (Γ 1 > n, D(e) = ∞) ≥ E Q 1I {T is n-good} 1I E 1 ∩E 2 ∩E 3 ∩E 4 , we obtain by (2.5) Q e (Γ 1 > n, D(e) = ∞) ≥ E Q e 1I {T is n-good} 1I E 1 ∩E 2 ∩E 3 β(X τ 2hn ) = E Q e 1I {T is n-good} P e ω (E 1 ∩ E 2 ∩ E 3 ) E Q [β] ,
by independence. By (2.7),

Q e (Γ 1 > n, D(e) = ∞) ≥ O(n K ) -1 Q (T is n-good) (p ′ n ) n .
We already know that Q (T is n-good) has a stretched exponential lower bound, and it remains to observe that the same holds for (p ′ n ) n . But the method of gambler's ruin shows that p

′ n ≥ 1 -p ′ 1-p ′ hn
, which gives the required lower bound by our choice of h n .

Let us turn to the upper bound. We divide the proof in two, depending on which case we deal with.

Proof of Proposition 2.2: upper bound in the case q 1 = 0. Assume that q 1 = 0 (the condition i < ν -1 min is not required in the proof). The proof of the following lemma is deferred. Recall the notation introduced in (2.2), γ(e) := P e ω (T← e = T * e = ∞) ≤ β(e).

Lemma 2.3 When q 1 = 0, there exists a constant c 2 ∈ (0, 1) such that for large n,

E Q [(1 -γ(e)) n ] ≤ e -n c 2 .
Denote by π k the k-th distinct site visited by the walk (X n , n ≥ 0). We observe that

Q e (Γ 1 > n 3 ) ≤ Q e (Γ 1 > τ n ) + Q e ( more than n 2 distinct sites are visited before τ n ) + Q e (∃ k ≤ n 2 : N(π k ) > n). (2.8) Since Q e (Γ 1 > τ n ) = Q e (|X Γ 1 | > n), it follows from Fact A that Q e (Γ 1 > τ n ) decays
exponentially. For the second term of the right-hand side, beware that Q e ( more than n 2 distinct sites are visited before τ n )

≤ n k=1
Q e (more than n distinct sites are visited at level k) .

If we denote by t k

i the first time when the i-th distinct site of level k is visited, we have, by the strong Markov property, P e ω (more than n sites are visited at level k

) = P e ω t k n < ∞ ≤ P e ω t k n-1 < ∞, D X t k n-1 < ∞ = E e ω 1I {t k n-1 <∞} 1 -β(X t k n-1 ) .
The independence of the environments entails that

E Q e 1I {t k n-1 <∞} 1 -β(X t k n-1 ) = Q e t k n-1 < ∞ E Q [1 -β] .
Consequently,

Q e t k n < ∞ ≤ Q e t k n-1 < ∞ E Q [1 -β] ≤ (E Q [1 -β]) n-1 , (2.9)
which leads to Q e more than n 2 sites are visited before

τ n ≤ n (E Q [1 -β]) n-1 , (2.10)
which is exponentially small. We remark, for later use, that equation (2.9) holds without the assumption q 1 = 0. For the last term of equation (2.8), we write

Q e ∃ k ≤ n 2 : N(π k ) > n ≤ n 2 k=1 Q e (N(π k ) > n) .
Let U := n≥0 (N * ) n be the set of words, where (N) 0 := {∅}. Each vertex x of T is naturally associated with a word of U, and T is then a subset of U (see [START_REF] Neveu | Arbres et processus de Galton-Watson[END_REF] for a more complete description). For any k ≥ 1,

Q e (N(π k ) > n) = x∈U Q e (x ∈ T, N(x) > n, x = π k ) ≤ x∈U E Q 1I {x∈T} P e ω (x = π k )(1 -γ(x)) n ,
with the notation of (2.2). By independence,

Q e (N(π k ) > n) ≤ x∈U E Q 1I {x∈T} P e ω (x = π k ) E Q [(1 -γ(e)) n ] = E Q [(1 -γ(e)) n ] .
Apply Lemma 2.3 to complete the proof.

Proof of Lemma 2.3. Let µ > 0 be such that q := Q(β(e) > µ) > 0, and write

R := inf{k ≥ 1 : ∃|x| = k, β(x) ≥ µ} .
Let x R be such that |x R | = R and β(x R ) ≥ µ and we suppose for simplicity that x R is a descendant of e 1 . We see that γ(e) ≥ ω(e, e 1 )β(e 1 ) ≥ c 1 ν(e) β(e 1 ) by equation (2.4). In turn, equation (2.1) of [START_REF] Aidékon | Transient random walks in random environment on a Galton-Watson tree[END_REF] implies that for any vertex x, we have

1 β(x) = 1 + 1 ν(x) i=1 A(x i )β(x i ) ≤ 1 + 1 ess inf A 1 β(x i ) ,
for any 1 ≤ i ≤ ν(x). By recurrence on the path from e 1 to x R , this leads to

1 β(e 1 ) ≤ 1 + 1 ess inf A + . . . + 1 ess inf A R-1 1 µ .
We deduce the existence of constants c 4 , c 5 > 0 such that (1) .

γ(e) ≥ c 4 ν(e) e -c 5 R . (2.11) It yields that E Q (1 -γ(e)) n 1I {ν(e)< √ n} ≤ Q R > 1 4c 5 ln(n) + e -n 1/4+o
We observe that

Q R > 1 4c 5 ln(n) ≤ Q ∀|x| = 1 4c 5 ln(n), β(x) > µ .
By assumption, q 1 = 0; thus #{x ∈ T : |x| = 1 4c 5 ln(n)} ≥ 2 1/4c 5 ln(n) =: n c 6 . As a consequence, Q ∀|x| = 1 4c 5 ln(n), β(x) > µ ≤ q n c 6 . Hence, the proof of our lemma is reduced to find a stretched exponential bound for E Q (1γ(e)) n 1I {ν(e)≥ √ n} . For any x ∈ T, denote by V µ

x the number of children

x i of x such that β(x i ) > µ. For ε ∈ (0, Q(β(e) > µ)), E Q (1 -γ(e)) n 1I {ν(e)≥ √ n} ≤ Q e ν(e) ≥ √ n, V µ e < εν(e) + E Q (1 -γ(e)) n 1I {V µ e ≥εν(e)} .
We apply Cramér's Theorem to handle with the first term on the right-hand side. Turning to the second one, the bound is clear once we observe the general inequality,

γ(e) = ν(e) k=1 ω(e, e k )β(e k ) ≥ c 1 ν(e) ν(e) k=1 β(e k ) ≥ c 1 µ ν(e)
V µ e , (2.12) which is greater than c 1 µε on {V µ e ≥ εν(e)}.

Remark 2.3. As a by-product, we obtain that E Q (1γ(e)) n 1I {ν(e)≥ √ n} ≤ e -n c 3 without the assumption q 1 = 0.

Proof of Proposition 2.2 : upper bound in the case s < 1. We follow the strategy of the case "q 1 = 0". The proof boils down to the estimate of

Q e (N(π k ) > n, D(e) = ∞) = Q e (N(π k ) > n, ν(π k ) < √ n, D(e) = ∞) + Q e (N(π k ) > n, ν(π k ) ≥ √ n, D(e) = ∞) .
Let x ∈ T and consider the RWRE (X n , n ≥ 0) when starting from ←

x. Inspired by Lyons et al. [START_REF] Lyons | Biased random walks on Galton-Watson trees[END_REF], we propose to couple it with a random walk (Y ′′ n , n ≥ 0) on Z. We first define X ′′ n as the restriction of X n on the path [[ ← e , x]]. Beware that X ′′ n exists only up to a time T , which corresponds to the time when the walk (X n , n ≥ 0) escapes the path [[ ← e , x]], id est leaves the path and never comes back to it. After this time, we set X ′′ n = ∆ for some ∆ in some space

E. Then (X ′′ n ) n≥0 is a random walk on [[ ← e , x]] ∪ {∆}, whose transition probabilities are, if y / ∈ { ← e , x, ∆}, P ← x ω (X ′′ n+1 = y + | X ′′ n = y) = ω(y, y + ) ω(y, y + ) + ω(y, ← y ) + y k =y + ω(y, y k )β(y k ) , P ← x ω (X ′′ n+1 = ← y | X ′′ n = y) = ω(y, ← y ) ω(y, y + ) + ω(y, ← y ) + y k =y + ω(y, y k )β(y k ) , P ← x ω (X ′′ n+1 = ∆ | X ′′ n = y) = ν(y) k=1 ω(y, y k )β(y k ) ω(y, y + ) + ω(y, ← y ) + y k =y + ω(y, y k )β(y k ) ,
where y + is the child of y which lies on the path [[

← e , x]].
Besides, the walk is absorbed on ∆ and reflected on ← e and x. We recall that s := ess sup A. We construct the adequate coupling with a biased random walk (Y ′′ n ) n≥0 on Z, starting from |x| -1, increasing with probability s/(1 + s), decreasing otherwise and such that

Y ′′ n ≥ |X ′′ n | as long as X ′′ n = ∆ (which is always possible since P ω (X ′′ n+1 = y + | X ′′ n = y) ≤ s 1+s
). After time T , we let Y n move independently. By coupling and then by gambler's ruin method, it leads to

P ← x ω (T x < T← e ) ≤ P |x|-1 ω ( ∃ n ≥ 0 : Y ′′ n = |x| ) = s .
It follows that

1 -P x ω (T * x < T← e ) ≥ ω(x, ← x) 1 -P ← x ω (T x < T← e ) ≥ c 1 (1 -s) ν(x) ,
by equation (2.4). Hence,

Q e (N(π k ) > n, ν(π k ) ≤ √ n, D(e) = ∞) = x∈U E Q 1I {ν(x)≤ √ n} P e ω (x = π k , D(e) > T x ) P x ω (N(x) > n, D(e) = ∞) ≤ x∈U E Q P e ω (x = π k ) 1 - c 1 (1 -s) √ n n = 1 - c 1 (1 -s) √ n n ,
which decays stretched exponentially. On the other hand,

Q e (N(π k ) > n, ν(π k ) ≥ √ n, D(e) = ∞) ≤ Q e ν(π k ) ≥ √ n, V µ π k < εν(π k ) + Q e N(π k ) > n, V µ π k ≥ εν(π k ) .
with the notation introduced in the proof of Lemma 2.3. We have

Q e ν(π k ) ≥ √ n, V µ π k < εν(π k ) = Q ν(e) ≥ √ n, V µ e < εν(e) ,
which is stretched exponential by Cramér's Theorem. We also observe that

Q e N(π k ) > n, V µ π k ≥ εν(π k ) ≤ E Q e 1I {V µ π k ≥εν(x)} (1 -γ(π k )) n = E Q 1I {V µ e ≥εν(x)} (1 -γ(e)) n ≤ (1 -cµε) n ,
by equation (2.12). This completes the proof.

The case Λ < ∞

In this part, we suppose that Λ < ∞, where Λ is defined by

Λ := Leb t ∈ R : E[A t ] ≤ 1 q 1 .
We prove that the tail distribution of Γ 1 is polynomial.

Proposition 2.4 If Λ < ∞, then lim n→∞ 1 ln(n) ln (S e (Γ 1 > n)) = -Λ . (2.13) Proof of Proposition 2.4. Lemma 3.3 of [1] already gives lim inf n→∞ 1 ln(n) ln (S e (Γ 1 > n)) ≥ -Λ.
Hence, the lower bound of (2.13) is known. The rest of the section is dedicated to the proof of the upper bound.

We start with three preliminary lemmas. We first prove an estimate for one-dimensional RWRE, that will be useful later on. Denote by (R n , n ≥ 0) a generic RWRE on Z such that the random variables A(i), i ≥ 0 are independent and have the distribution of A, when we set for i ≥ 0,

A(i) := ω R (i, i + 1) ω R (i, i -1)
with ω R (y, z) the quenched probability to jump from y to z. We denote by P k ω,R the quenched distribution associated with (R n , n ≥ 0) when starting from k, and by P R the distribution of the environment ω R . Let c 7 ∈ (0, 1) be a constant whose value will be given later on. For any k ≥ ℓ ≥ 0 and n ≥ 0, we introduce the notation

p(ℓ, k, n) := E P R (1 -c 7 P ℓ ω,R (T * ℓ > T 0 ∧ T k )) n . (2.14) Lemma 2.5 Let 0 < r < 1, and Λ r := Leb t ∈ R : E[A t ] ≤ 1
r . Then, for any ε > 0, we have for n large enough,

k≥ℓ≥0 r k p(ℓ, k, n) ≤ n -Λr+ε .
Proof. The method used is very similar to that of Lemma 5.1 in [START_REF] Aidékon | Transient random walks in random environment on a Galton-Watson tree[END_REF]. We feel free to present a sketch of the proof. We consider the one-dimensional RWRE (R n ) n≥0 . We introduce for k ≥ ℓ ≥ 0, the potential V (0) = 0 and

V (ℓ) = - ℓ-1 i=0 ln(A(i)) , H 1 (ℓ) = max 0≤i≤ℓ V (i) -V (ℓ) , H 2 (ℓ, k) = max ℓ≤i≤k V (i) -V (ℓ) .
We know (e.g. [START_REF] Zeitouni | Random walks in random environment[END_REF]) that

e -H 2 (ℓ+1,k) k + 1 ≤ P ℓ+1 ω,R (T k < T ℓ ) ≤ e -H 2 (ℓ+1,k) , (2.15) e -H 1 (ℓ) k + 1 ≤ P ℓ-1 ω,R (T -1 < T ℓ ) ≤ e -H 1 (ℓ) . (2.16) It yields that P ℓ ω,R (T * ℓ > T 0 ∧ T k ) ≥ e -H 1 (ℓ)∧H 2 (ℓ,k)+O(ln k) ,
where O(ln k) is a deterministic function. Let η ∈ (0, 1).

p(ℓ, k, n) ≤ (1 -c 7 n -1+η ) n + P R (H 1 (ℓ) ∧ H 2 (ℓ, k) -O(ln k) ≥ (1 -η) ln(n)) ≤ e -c 8 n η + P R (H 1 (ℓ) ∧ H 2 (ℓ, k) -O(ln k) ≥ (1 -η) ln(n)) .
In Section 8.1 of [START_REF] Aidékon | Transient random walks in random environment on a Galton-Watson tree[END_REF], we proved that for any s ∈ (0, 1),

E P R e Λs(H 1 (ℓ)∧H 2 (ℓ,k)) ≤ e k ln(1/s)+os(k) ,
where o s (k) is such that o s (k)/k tends to 0 at infinity. This implies that, defining o s (k

) := o s (k) -Λ s O(ln k), s k P R (H 1 (ℓ) ∧ H 2 (ℓ, k) -O(ln k) ≥ (1 -η) ln(n)) ≤ s k 1 ∧ e k ln(1/s)-Λs(1-η) ln(n)+ os(k) ≤ n -Λs(1-η) exp ((k ln(s) + Λ s (1 -η) ln(n)) ∧ o s (k)) .
Observe that there exists M s such that for any k and any n, we have (k ln(s

) + Λ s (1 - η) ln(n)) ∧ o s (k) ≤ sup i≤Ms ln(n) o(i) + η ln n,
and notice that sup i≤Ms ln(n) o s (i) is negligible towards ln(n). This leads to, for n large enough,

s k p(ℓ, k, n) ≤ s k e -c 8 n η + n -Λs(1-η)+2η .
Let r ∈ (0, 1) and s > r. We have

r k p(ℓ, k, n) ≤ r k e -c 8 n η + r s k n -Λs(1-η)+2η .
Lemma 2.5 follows by choosing η small enough and s close enough to r.

Let Z n represent the size of the n-th generation of the tree T. We have the following result.

Lemma 2.6 There exists a constant c 9 > 0 such that for any H > 0, B > 0 and n large enough,

E Q (1 -γ(e)) n 1I {Z H >B} ≤ n -c 9 B .
Proof. We have √ n e -c 5 R , with R := inf{k ≥ 1 : ∃|x| = k, β(x) ≥ µ} as before (µ > 0 is such that q := Q(β(e) > µ) > 0). Thus, (1) .

E Q (1 -γ(e)) n 1I {Z H >B} ≤ E Q (1 -γ(e)) n 1I {ν(e)≥ √ n} + E Q (1 -γ(e)) n 1I {Z H >B, ν(e)≤ √ n} ≤ e -n c 3 + E Q (1 -γ(e)) n 1I {Z H >B, ν(e)≤ √
E Q (1 -γ(e)) n 1I {Z H >B, ν(e)≤ √ n} ≤ Q R > 1 4c 5 ln(n) + H, Z H > B + e -n 1/4+o
By considering the Z H subtrees rooted at each of the individuals in generation H, we see that

Q (R > c 10 ln(n) + H, Z H > B) = E GW Q(R > c 10 ln(n)) Z H 1I {Z H >B} ≤ Q(R > c 10 ln(n)) B .
If R > c 10 ln(n), we have in particular β(x) < µ for each |x| = c 10 ln(n) which implies that

Q (R > c 10 ln(n) + H, Z H > B) ≤ E GW q Z c 10 ln(n) B .
Let t ∈ (q 1 , 1). For n large enough, E GW q Z c 10 ln(n) ≤ t c 10 ln(n) = n c 10 ln(t) , (E GW [q Zn ]/q n 1 has a positive limit by Corollary 1 page 40 of [START_REF] Athreya | Branching processes[END_REF]). The lemma follows.

Let r ∈ (q 1 , 1), ε > 0, B be such that and H large enough so that

c 9 Bε > 2Λ (2.
GW (Z H ≤ B) < r H 1 B < 1. (2.18) In particular, c 11 := GW (Z H > B) > 0.
Let ν(x, k) denote for any x ∈ T the number of descendants of x at generation |x| + k (ν(x, 1) = ν(x)), and let

S H := {x ∈ T : ν(x, H) > B} . (2.19)
For any x ∈ T, we call F (x) the youngest ancestor of x which lies in S H , and G(x) an oldest descendant of x in S H . For any x, y ∈ T, we write x ≤ y if y is a descendant of x and x < y if besides x = y. We define for any x ∈ T, W (x) as the set of descendants y of x such that there exists no vertex z with x < z ≤ y and ν(z, H) > B. In other words, W (x) = {y : y ≥ x, F (y) ≤ x}. We define also

• W (x) := W (x)\{x} , ∂W (x) := {y : ← y ∈ W (x), ν(y, H) > B} .
Finally, let W j (e) := {x : |x| = j, x ∈ W (e)}.

Lemma 2.7 Recall that m := E GW [ν(e)] and r is a real belonging to (q 1 , 1). We also recall that H and B verify GW (Z H ≤ B) < r H 1 B . We have for any j ≥ 0,

E GW [W j (e)] < m r j-1 .
Proof. We construct the subtree T H of the tree T by retaining only the generations kH, k ≥ 0 of the tree T. Let

W = W(T) := {x ∈ T H : ∀y ∈ T H , (y < x) ⇒ ν(y, H) ≤ B} . (2.20)
The tree W is a Galton-Watson tree whose offspring distribution is of mean (2.18). Then for each child e i of e (in the original tree T), let W i := W(T e i ) where T e i is the subtree rooted at e i . We conclude by observing that

E GW [Z H 1I {Z H ≤B} ] ≤ B × GW (Z H ≤ B) ≤ r H by
W j (e) ≤ ν(e) i=1 #{x ∈ W i : |x| = 1 + ⌈(j -1)/H⌉ × H} hence E GW [W j (e)] ≤ E GW [ν(e)]r j-1 .
We still have r ∈ (q 1 , 1) and ε > 0. We prove that for n large enough, and r and ε close enough to q 1 and 0, we have

Q e (Γ 1 > n, D(e) = ∞) ≤ c 12 n -(1-2ε)Λr+3ε , (2.21) where Λ r := Leb{t ∈ R : E[A t ] ≤ 1
r } as in Lemma 2.5. This suffices to prove Proposition 2.4 since ε and Λ r can be arbitrarily close to 0 and Λ, respectively. We recall that we defined B, H and S H in (2.17),(2.18) and (2.19).

The strategy is to divide the tree in subtrees in which vertices are constrained to have a small number of children (at most B children at generation H). With B = H = 1, we would have literally pipes. In general, the traps constructed are slightly larger than pipes. We then evaluate the time spent in such traps by comparison with a one-dimensional random walk. We define π s k as the k-th distinct site visited in the set S H . We observe that 4 (n) distinct sites are visited before τ ln 2 (n)

Q e (Γ 1 > n, D(e) = ∞) (2.22) ≤ Q e Γ 1 > τ ln 2 (n) + Q e more than ln
+ Q e ∃ k ≤ ln 4 (n), ∃ x ∈ W (π s k ), N(x) > n/ ln 4 (n) + Q e ∃ x ∈ W (e), N(x) > n/ ln 4 (n), D(e) = ∞, Z H ≤ B .
The first term on the right-hand side decays like e -ln 2 (n) by Fact A, and so does the second term by equation (2.9). We proceed to estimate the third term on the right-hand side of (2.22). Since

Q e ∃k ≤ ln 4 (n), ∃x ∈ W (π s k ), N(x) > n/ ln 4 (n) ≤ ln 4 (n) k=1 Q e ∃x ∈ W (π s k ), N(x) > n/ ln 4 (n)
we look at the rate of decay of Q e ∃ x ∈ W (π s k ), N(x) > n/ ln 4 (n) for any k ≥ 1. We first show that the time spent at the frontier of W (π s k ) will be negligible. Precisely, we show

Q e (N(π s k ) > n ε ) ≤ c 14 n -2Λ , (2.23) Q e (∃ z ∈ ∂W (π s k ), N(z) > n ε ) ≤ c 15 n -2Λ . (2.

24)

As P y ω (N(y) > n ε ) ≤ (1γ(y)) n ε for any y ∈ T, we have,

Q e (N(π s k ) > n ε ) = E Q y∈ S H P e ω (π s k = y)P y ω (N(y) > n ε ) ≤ E Q y∈ S H P e ω (π s k = y)(1 -γ(y)) n ε . (2.25)
We would like to split the expectation E Q P e ω (π s k = y)(1γ(y)) n ε in two. However the random variable P e ω (π s k = y) depends on the structure of the first H generations of the subtree rooted at y. Nevertheless, we are going to show that, for some c 14 > 0,

E Q P e ω (π s k = y)(1 -γ(y)) n ε ≤ c 14 E Q [P e ω (π s k = y)] E Q (1 -γ(y)) n ε |ν(y, H) > B .
Let U := n≥0 (N * ) n be, as before, the set of words. We have seen that U allows us to label the vertices of any tree (see [START_REF] Neveu | Arbres et processus de Galton-Watson[END_REF]). Let y ∈ U and let ω y represent the restriction of the environment ω to the outside of the subtree rooted at y (when y belongs to the tree). For 1 ≤ L ≤ H, we denote by y L the ancestor of y such that |y L | = |y| -L. We attach to each y L the variable ζ(y L ) := 1I {ν(y L ,H)>B} . We notice that there exists a measurable function f such that P e ω (π

s k = y) = f (ω y , ζ)1I {ν(y,H)>B} where ζ := (ζ(y L )) 1≤L≤H . Let E(ω y ) := {e ∈ {0, 1} H : Q(ζ = e | ω y ) > 0}. We have E Q [f (ω y , ζ) | ω y ] ≥ max e ∈ E(ωy) f (ω y , e)Q (ζ = e | ω y ) .
We claim that there exists a constant c 13 > 0 such that for almost every ω and any e ∈ E(ω y ),

Q (ζ = e | ω y ) ≥ c 13 .
Let us prove the claim. If ω y is such that ν( B}. We observe that, for any e ∈ E(ω y ), we necessarily have e L = 1 for h < L ≤ H. We are reduced to the study of

Q (ζ = e | ω y ) = Q 1 ≤ L ≤ h {ζ(y L ) = e L } ω y .
For any tree T , we denote by T j the restriction to the j first generations. Let also T y h designate the subtree rooted at y h in T. Since ν(y h , h) ≤ B, we observe that T h y h belongs almost surely to a finite (deterministic) set in the space of all trees. We construct the set Ψ(T h y h , e) := {tree T :

T h = T h y h , GW (T h+H ) > 0, ∀|x| ≤ 2H, ν T (x) ≤ B ∀ 1 ≤ L ≤ h, ν T (y L , h) > B if and only if e L = 1} .
We observe that Ψ(T K y K , e) = ∅ as soon as e ∈ E(ω y ). Let Ψ(T K y K , e) := {T h+H , T ∈ Ψ(T h y h , e)} be the same set but where the trees are restricted to the first h + H generations. Since Ψ(T K y K , e) is again included in a finite deterministic set in the space of trees, we deduce that there exists c 13 > 0 such that, almost surely,

inf{GW (T h+H | T h ), T ∈ Ψ(T h y h , e), e ∈ E(ω y )} ≥ c 13 .
Consequently,

Q (ζ = e | ω y ) ≥ Q(T h+H y h ∈ Ψ(T h y h , e) | ω y ) ≥ c 13 ,
as required. We get

E Q [f (ω y , ζ) | ω y ] ≥ c 13 max e ∈ E(ωy) f (ω y , e) ≥ c 13 f (ω y , ζ) .
Finally we obtain, with c 14 := 1 c 13 ,

f (ω y , ζ) ≤ c 14 E Q [f (ω y , ζ) | ω y ] .
By (2.25), it entails that

Q e (N(π s k ) > n ε ) ≤ c 14 y∈U E Q 1I {ν(y,H)>B} E Q [f (ω y , ζ) | ω y ] (1 -γ(y)) n ε = c 14 y∈U E Q [f (ω y , ζ)] E Q 1I {ν(e,H)>B} (1 -γ(e)) n ε = c 14 y∈U E Q [P e ω (π s k = y)] E Q (1 -γ(e)) n ε | ν(e, H) > B .
It implies that

Q e (N(π s k ) > n ε ) ≤ c 14 E Q (1 -γ(e)) n ε | Z H > B ≤ c 14 n -c 9 εB
, by Lemma 2.6. Since c 9 εB > 2Λ, this leads to, for n large,

Q e (N(π s k ) > n ε ) ≤ c 14 n -2Λ
which is equation (2.23). Similarly, recalling that ∂W (y) designates the set of vertices z such that ← z ∈ W (y) and ν(z, H) > B, we have that

Q e (∃ y ∈ ∂W (π s k ), N(y) > n ε ) ≤ E Q   y∈S H P e ω (π s k = y) z∈∂W (y) (1 -γ(z)) n ε   ≤ c 14 E Q y∈S H P e ω (π s k = y) E GW [∂W (e)] E Q (1 -γ(e)) n ε | Z H > B = c 14 E GW [∂W (e)] E Q (1 -γ(e)) n ε | Z H > B .
We notice that

E GW [∂W ] ≤ E GW x∈W (e) ν(x) = mE GW [W (e)
] which is finite by Lemma 2.7. It yields, by Lemma 2.6,

Q e (∃ x ∈ W (π s k ), N(G(x)) > n ε ) ≤ c 15 n -2Λ
thus proving (2.24). Our next step is then to find an upper bound to the probability to spend most of our time at a vertex x belonging to some • W (y). To this end, recall that G(x) is an oldest descendant of x such that ν(x, H) > B. We have just proved that the time spent at y(= F (x)) or G(x) is negligible. Therefore, starting from x, the probability to spend much time in x is not far from the probability to spend the same time without reaching y neither G(x). Then, this probability is bound by coupling with a one-dimensional random walk.

Define T (ℓ) x as the ℓ-th time the walk visits x after visiting either F (x) or G(x), id est T

(1)

x = T x and, T (ℓ) x := inf{k > T (ℓ-1)

x :

X k = x, ∃ i ∈ ( T (ℓ-1) x , k), X i = F (x) or G(x)} .
Let also

N (ℓ) (x) = T (ℓ+1) (x)-1
k= T (ℓ) (x) 1I {X k =x} be the time spent at x between T (ℓ) and T (ℓ+1) . We observe that, for any k ≥ 1,

Q e ∃ x ∈ W (π s k ), N(x) > n/ ln 4 (n) ≤ Q e (N(π s k ) > n ε ) + Q e (∃ x ∈ W (π s k ), N(G(x)) > n ε ) + Q e ∃ x ∈ • W (π s k ), ∃ ℓ ≤ 2n ε , N (ℓ) (x) > n 1-2ε ≤ (c 14 + c 15 )n -2Λ + ℓ≤2n ε Q e ∃ x ∈ • W (π s k ), N (ℓ) (x) > n 1-2ε . (2.26) Since Q e (∃ x ∈ W (π s k ), N (ℓ) (x) > n 1-2ε ) ≤ E Q    y∈S H P e ω (π s k = y) x∈ • W (y) P x ω (N (ℓ) (x) > n 1-2ε )    ,
and by the strong Markov property at T (ℓ)

x , where as before y + represents the child of y on the path. We let ( X n ) n≥0 be the random walk on [[e, G(x)]] with the transition probabilities ω and we denote by P ω,x (•) the probability distribution of ( X n , n ≥ 0). By Lemma 4.4 of [START_REF] Aidékon | Transient random walks in random environment on a Galton-Watson tree[END_REF], we have the following comparisons:

P x ω N (ℓ) (x) > n 1-2ε = P x ω T (ℓ) x < ∞ P x ω N (1) (x) > n 1-2ε ≤ P x ω (N (1) (x) > n 1-2ε ) , this yields Q e (∃ x ∈ W (π s k ), N (ℓ) (x) > n 1-2ε ) ≤ E Q    y∈S H P e ω (π s k = y) x∈ • W (y) P x ω (N (1) (x) > n 1-2ε )    ≤ c 14 E Q y∈S H P e ω (π s k = y) E Q    x∈ • W (e) P x ω (N (1) (x) > n 1-2ε ) Z H > B    = c 14 E Q    x∈ • W (e) P x ω (N (1) (x) > n 1-2ε ) Z H > B    . (2.
P ← x ω (T x < T e ) ≤ P ← x ω,x (T x < T e ) , P x + ω (T G(x) < T x ) ≤ P x + ω,x (T G(x) < T x ) .
Therefore,

P x ω (T * x < T e ∧ T G(x) ) = ω(x, ← x)P ← x ω (T x < T e ) + ω(x, x + )P x + ω (T x < T G(x) ) + i≤ν(x):x i =x + ω(x, x i )(1 -β(x i )) ≤ ω(x, ← x) P ← x ω,x (T x < T e ) + ω(x, x + ) P x + ω,x (T x < T G(x) ) + i≤ν(x):x i =x + ω(x, x i ) = 1 -ω(x, ← x) + ω(x, x + ) P x ω,x (T * x > T e ∧ T G(x) ) . Since ν(x) ≤ B (for x ∈ • W (e))
, we find by (2.4) a constant c 16 ∈ (0, 1) such that ω(x,

← x) + ω(x, x + ) ≥ c 16 . It yields that P x ω (T * x < T e ∧ T G(x) ) ≤ 1 -c 16 P x ω,x (T * x > T e ∧ T G(x) ) .
We observe that, for any x ∈ W (e), with the notation of (2.14) and taking c 7 := c 16 ,

E P 1 -c 16 P x ω,x (T * x > T e ∧ T G(x) ) n = p(|x|, |G(x)|, n) .
It follows that

E GW    x∈ • W (e) P x (N (1) (x) > n 1-2ε )    ≤ E GW    x∈ • W (e) p(|x|, |G(x)|, n 1-2ε )    .
On the other hand, x∈W (e) p(|x|, |G(x)|, n 1-2ε ) ≤ y∈∂W (e) x≤y p(|x|, |y|, n 1-2ε ). It implies that

E GW    x∈ • W (e) P x (N (1) (x) > n 1-2ε )    ≤ j≥0 E GW [#{y ∈ ∂W (e), |y| = j}] i≤j p(i, j, n 1-2ε ) ≤ m j≥0 E GW [W j-1 (e)] i≤j p(i, j, n 1-2ε ) .
By Lemmas 2.5 and 2.7, for n large enough,

E GW    x∈ • W (e) P x (N (1) (x) > n 1-2ε )    ≤ m 2 j≥0 r j-2 i≤j p(i, j, n 1-2ε ) ≤ n -(1-2ε)Λr +ε .
(2.28) Supposing r and ε close enough to q 1 and 0, equation (2.28) combined with (2.26) and (2.27),

shows that, for any k ≥ 1,

Q e ∃ x ∈ W (π s k ), N(x) > n/ ln 4 (n) ≤ c 17 n -(1-2ε)Λr +2ε .
We arrive at

Q e ∃ k ≤ ln 4 (n), ∃ x ∈ W (π s k ), N(x) > n/ ln 4 (n) ≤ c 18 n -(1-2ε)Λr+3ε . (2.29) Finally, the estimate of Q e ∃ x ∈ W (e), N(x) > n/ ln 4 (n), D(e) = ∞, Z H ≤ B in (2.22) is similar. Indeed, Q e ∃ x ∈ W (e), N(x) > n/ ln 4 (n), D(e) = ∞, Z H ≤ B ≤ Q e (N(e) > n ε , D(e) = ∞, ν(e) ≤ B) + Q e (∃ x ∈ W (e), N(G(x)) > n ε ) + Q e ∃ x ∈ W (e), ∃ ℓ ≤ 2n ε , N (ℓ) (x) > n 1-2ε .
We have

Q e (N(e) > n ε , D(e) = ∞, ν(e) ≤ B) ≤ E Q (1 -ω(e, ← e )) n ε 1I {ν(e)≤B} ≤ (1 -c 1 /B) n ε , by (2.4). By equation (2.24), Q e (∃ x ∈ W (π s k ), N(G(x)) > n ε ) ≤ c 15 n -2Λ .
Finally,

Q e ∃ x ∈ • W (e), ∃ ℓ ≤ 2n ε , N (ℓ) (x) > n 1-2ε ≤ ℓ≤2n ε Q e ∃ x ∈ • W (e), N (ℓ) (x) > n 1-2ε ≤ 2n ε Q e ∃ x ∈ • W (e), N (1) (x) > n 1-2ε ≤ 2n ε E GW    x∈ • W (e) P x (N (1) (x) > n 1-2ε )    ≤ c 17 n -(1-2ε)Λr +2ε ,
by (2.28). We deduce that, for n large enough,

Q e ∃ x ∈ W (e), N(x) > n/ ln 4 (n), D(e) = ∞, Z H ≤ B ≤ n -(1-2ε

Large deviations principles

We recall the definition of the first regeneration time

Γ 1 := inf k > 0 : ν(X k ) ≥ 2, D(X k ) = ∞, k = τ |X k | .
We define by iteration

Γ n := inf k > Γ n-1 : ν(X k ) ≥ 2, D(X k ) = ∞, k = τ |X k |
for any n ≥ 2. We have the following fact (points (i) to (iii) are already discussed in [START_REF] Aidékon | Transient random walks in random environment on a Galton-Watson tree[END_REF]; point (iv) is shown in [START_REF] Gross | Marche aléatoire en milieu aléatoire sur un arbre[END_REF] in the case of regular trees and in [START_REF] Lyons | Biased random walks on Galton-Watson trees[END_REF] in the case of biased random walks, and is easily adaptable to our case).

Fact B

(i) For any n ≥ 1, Γ n < ∞ Q e -a.s.

(ii) Under Q e , (Γ n+1 -Γ n , |X Γ n+1 | -|X Γn |), n ≥ 1 are independent and distributed as (Γ 1 , |X Γ 1 |) under the distribution S e . (iii) We have E S e [ |X Γ 1 | ] < ∞. (iv) The speed v verifies v = E S e [ |X Γ 1 | ] E S e [ Γ 1 ] .
The rest of the section is devoted to the proof of Theorems 1.1 and 1.2. It is in fact easier to prove them when conditioning on never returning to the root. Our theorems become Theorem 3.1 (Speed-up case) There exist two continuous, convex and strictly decreasing functions

I a ≤ I q from [1, 1/v] to R + , such that I a (1/v) = I q (1/v) = 0 and for a < b, b ∈ [1, 1/v], lim n→∞ 1 n ln Q e τ n n ∈]a, b] D(e) = ∞ = -I a (b) , (3.1) lim n→∞ 1 n ln P e ω τ n n ∈]a, b] D(e) = ∞ = -I q (b) . (3.2)
If ess inf A =: i > ν -1
min , then I a and I q are strictly increasing on [1/v, +∞[. If i ≤ ν -1 min , then I a = I q = 0. Theorems 1.1 and 1.2 follow from Theorems 3.1 and 3.2 and the following proposition.

Proposition 3.3 We have, for a < b ≤ 1/v, lim n→∞ 1 n ln Q e ( τ n n ∈]a, b]) = lim n→∞ 1 n ln Q e ( τ n n ∈]a, b] | D(e) = ∞) , (3.5) lim n→∞ 1 n ln P e ω ( τ n n ∈]a, b]) = lim n→∞ 1 n ln P e ω ( τ n n ∈]a, b] | D(e) = ∞) . (3.6)
Similarly, in the slowdown case, we have for 1/v ≤ a < b, Proof. Let x ≤ y be two vertices of T with |x| = n and |y| = n + m. We observe that

lim n→∞ 1 n ln Q e ( τ n n ∈ [a, b[) = lim n→∞ 1 n ln Q e ( τ n n ∈ [a, b[ | D(e) = ∞) , (3.7) lim n→∞ 1 n ln P e ω ( τ n n ∈ [a, b[) = lim
A(h, b, y) ⊃ A(h, b, x) ∩ {ω : P x ω (τ n+m = T y , τ n+m ≤ bm, T← x > τ n+m ) ≥ e -hm } =: A(h, b, x) ∩ A x (h, b, y).

It yields that

e n+m (h, b) ≥ E Q   |x|=n 1I A(h,b,x) |y|=n+m,y≥x 1I Ax(h,b,y)   = E Q   |x|=n 1I A(h,b,x)   E Q   |x|=m 1I A(h,b,x)   = e n (h, b)e m (h, b) . (3.9)
Let h > h c and p be such that e p (h c , b) > 0, where we write h c for h c (b). Then e np (h c , b) > 0 for any n ≥ 1. We want to show that e k (h, b) > 0 for k large enough. By (2.4), ω(e, e 1 ) ≥ c 1 if ν(e) = 1 so that e k (-ln(c 1 ), b) ≥ q k 1 . Let n c be such that e -hcnc c 1 ≥ e -hnc . We check as before that for any n ≥ n c , and any r ≤ p, we have indeed

e np+r (h, b) ≥ e np (h c , b)e r (-ln(c 1 ), b) ≥ e np (h c , b)q r 1 > 0 .
Thus (3.9) implies that lim Proof. Let M := inf{h : e(h, b) > 1}. We claim that if h < M, then e(h, b) < 1. Indeed, suppose that there exists h 0 < M such that e(h 0 , b) ≥ 1. Then e(h 0 , b) = 1 by definition of M, so that e(h, b) is constant equal to 1 on [h 0 , M[. By concavity, ln(e(h, b)) is equal to 0 on [h 0 , +∞[, which is impossible since it tends to ln(m) at infinity. The corollary follows.

e n (th 1 + (1 -t)h 2 , tb 1 + (1 -t)b 2 ) ≥ e nt (h 1 , b 1 )e n(1-t) (h 2 , b 2 ) ,
We have the tools to prove Theorem 1.1.

Proof of Theorem 1.1. For b ∈ [1, +∞[, let J a (b) := -sup{-h + ln(e(h, b)) , h ≥ 0} , J q (b) := -sup{-h + ln(e(h, b)) , h ∈ S} .

Define then for any

b ≤ 1/v, I a (b) = J a (b) , I q (b) = J q (b) .
We immediately see that I a ≤ I q . The convexity of J a and J q stems from the convexity of the function hln(e(h, b)). Indeed, let J represent either J a or J q and let 1 ≤ b 1 ≤ b 2 and t ∈ [0, 1]. Denote by h 1 , h 2 , b and h the reals that verify

J(b 1 ) = h 1 -ln(e(h 1 , b 1 )) , J(b 2 ) = h 2 -ln(e(h 2 , b 2 )) , h := th 1 + (1 -t)h 2 , b := tb 1 + (1 -t)b 2 .
We observe that

J(b) ≤ h -ln(e(h, b)) ≤ t(h 1 -ln(e(h 1 , b 1 ))) + (1 -t)(h 2 -ln(e(h 2 , b 2 ))) = tJ(b 1 ) + (1 -t)J(b 2 )
which proves the convexity. We show now that, for any b ≥ 1,

lim n→∞ 1 n ln Q e τ n < T← e , τ n ≤ bn = -J a (b) , (3.11) lim n→∞ 1 n ln P e ω τ n < T← e , τ n ≤ bn = -J q (b) . (3.12)
We first prove (3.11). Since Q e τ n < T← e , τ n ≤ bn ≥ e -hn e n (h, b) for any h ≥ 0, we have lim inf

n→∞ 1 n ln Q e (τ n < T← e , τ n ≤ bn) ≥ -I a (b).
Turning to the upper bound, take a positive integer k. We observe that

Q e τ n < T← e , τ n ≤ bn ≤ k-1 ℓ=0 e -nℓ/k e n ((ℓ + 1)/k, b) ≤ ke n/k sup{e -hn e n (h, b), h ≥ 0} . Therefore, lim sup n→∞ 1 n ln Q e τ n < T← e , τ n ≤ bn ≤ 1 k -J a (b) .
Letting k tend to infinity gives the upper bound of (3.11).

To prove equation (3.12), let k be still a positive integer and h ∈ S. Denote by V pk (T) the set of vertices |x| = pk such that P

x ℓ-1 ω τ ℓk < T← x ℓ-1 , τ ℓk = T x ℓ ≤ bk ≥ e -hk
for any ℓ ≤ p, where x ℓ represents the ancestor of x at generation ℓk. Call V (T) := ∪ p≥0 V pk (T) the subtree thus obtained. We observe that V is a Galton-Watson tree of mean offspring e k (h, b). Let T k,h := {T : V (T) is infinite} .

Take T ∈ T k,h . For any x ∈ V pk , we have

P e ω τ pk < T← e , τ pk = T x ≤ bpk ≥ P e ω τ k < T← e , τ k = T x 1 ≤ bk . . . P x k-1 ω τ pk < T← x k-1 , τ pk = T x ≤ bk ≥ e -hpk .
It implies that

P e ω τ pk < T← e , τ pk ≤ bpk ≥ e -hpk #V pk (T) .
By the Seneta-Heyde Theorem (see [START_REF] Athreya | Branching processes[END_REF] page 30 Theorem 3),

lim p→∞ 1 p ln (#V pk (T)) = ln(e k (h, b)) Q -a.s.
It follows that, as long as

T ∈ T k,h , lim inf p→∞ 1 pk ln P e ω τ pk < T← e , τ pk ≤ bpk ≥ -h + 1 k ln(e k (h, b)) .

29

Notice that P e ω τ n < T← e , τ n ≤ bn ≥ P e ω τ pk < T← e , τ pk ≤ bpk

min |x|=pk P x ω τ n < T← x , τ n ≤ b(n -pk)
where p := ⌊ n k ⌋. Since A is bounded, there exists c 17 > 0 such that ν(y) i=1 ω(y, y i ) ≥ c 17 ∀y ∈ T. It yields that

min |x|=pk P x ω τ n < T← x , τ n = (n -pk) ≥ c k 17 .
Hence,

lim inf n→∞ 1 n ln P e ω τ n < T← e , τ n ≤ bn ≥ -h + 1 k ln(e k (h, b)) . (3.13)
Take now a general tree T. Notice that since h ∈ S, Q (T k,h ) > 0 for k large enough, and there exists almost surely a vertex z ∈ T such that the subtree rooted at it belongs to T k,h . It implies that for large k, (3.13) holds almost surely. Then letting k tend to infinity and taking the supremum over all h ∈ S leads to lim inf n→∞ 1 n ln P e ω τ n < T← e , τ n ≤ bn ≥ -J q (b) .

For the upper bound in (3.12), we observe that, for any integer k,

P e ω (τ n < T← e , τ n ≤ bn) ≤ k-1 ℓ=0 e -ℓn/k |x|=n 1I A((ℓ+1)/k,b,x) .
By Markov's inequality, we have A(h,b,x) ≤ (e(h,b) + 1/k) n for all but a finite number of n, Q-a.s. In particular, if e(h, b)+1/k < 1, then |x|=n 1I A(h,b,x) = 0 for n large enough. Consequently, for n large,

Q   |x|=n 1I A(h,b,x) > (e(h, b) + 1/k) n   ≤ e n (h, b) (e(h, b) + 1/k) n ≤ e(h, b) e(h, b) + 1/k n , by (3.

10). An application of the Borel-Cantelli lemma proves that |x|=n 1I

P e ω (τ n < T← e , τ n ≤ bn) ≤ e n/k k sup{e -hn (e(h, b) + 1/k) n , h : e(h, b) + 1/k ≥ 1} .
We find that lim sup

n→∞ 1 n ln(P e ω (τ n < T← e , τ n ≤ bn)) ≤ 1/k + sup{-h + ln(e(h, b) + 1/k), h : e(h, b) + 1/k ≥ 1} .
Let k tend to infinity and use Corollary 3.5 to complete the proof of (3.12).

We observe that P e ω (τ n < T← e , τ n ≤ bn) -P e ω (τ n < T← e < ∞, τ n ≤ bn) ≤ P e ω (T← e = ∞, τ n ≤ bn) ≤ P e ω (τ n < T← e , τ n ≤ bn) .

But P e ω (τ n < T← e < ∞, τ n ≤ bn) ≤ P e ω (τ n < T← e , τ n ≤ bn) max i=1,...,ν(e) (1β(e i )). Since max i=1,...,ν(e) (1β(e i )) < 1 almost surely, we obtain that lim We can now finish the proof of the theorem. The continuity has to be proved only at b = 1 (since J a and J q are convex on [1, +∞[), which is directly done with the arguments of [START_REF] Dembo | Large deviations for random walks on Galton-Watson trees: averaging and uncertainty[END_REF] Section 4. We let b < 1/v = E S e [Γ 1 ]/E S e [|X Γ 1 |] and we observe that for any constant c 18 > 0, S e (τ n ≤ bn) ≤ S e (τ n < Γ c 18 n ) + S e (Γ c 18 n ≤ bn) .

Choose c 18 such that b (E S e [Γ 1 ]) -1 < c 18 < (E S e [|X Γ 1 |]) -1 . Use Cramér's Theorem with Facts A and B to see that S e (τ n < Γ c 18 n ) and S e (Γ c 18 n ≤ bn) decrease exponentially. Then, S e (τ n ≤ bn) has an exponential decay and, by (3.15), I a (b) > 0 which leads to I q (b) > 0 since I a ≤ I q . We deduce in particular that I a and I q are strictly decreasing. Furthermore, P e ω (τ n ≤ bn | D(e) = ∞) tends to 1 almost surely when b > 1/v, which in virtue of (3.14), implies that J q (b) = 0. By continuity, I q (1/v) = 0 and therefore

I a (1/v) = 0. Finally, let a < b, b ∈ [1, 1/v]. P e ω (an < τ n ≤ bn | D(e) = ∞) = P e ω (τ n ≤ bn | D(e) = ∞) -P e ω (τ n ≤ an | D(e) = ∞) .
Equation (3.2) follows since I q is strictly decreasing. The same argument proves (3.1).

Proof of Theorem 3.2

The proof is the same as before by taking for b ≥ 1, We verify that I a ≤ I q and both functions are convex. We have then for any b ≥ 1, We have J a = J q = 0 on [1, 1/v]. In the case i > ν -1 min , the positivity of I a and I q on ]1/v, +∞[ comes from Proposition 2.1 and Cramér's Theorem, which implies that they are strictly increasing. Equations (3.3) and (3.4) follow in that case. In the case i ≤ ν -1 min , we follow the strategy of [START_REF] Dembo | Large deviations for random walks on Galton-Watson trees: averaging and uncertainty[END_REF]. Let η > 0. As in the proof of Proposition 2.2, we set h n := ⌊ln(n)/(6 ln(b))⌋, and for some b ∈ N,

A(h
lim n→∞ 1 n ln Q e T← e > τ n ≥ bn = -J a (b) , (3.16)
w + := Q ν i=1 A(e i ) ≥ 1 + η, ν(e) ≤ b , w -:= Q ν i=1 A(e i ) ≤ 1 1 + η , ν(e) ≤ b .
Taking b large enough, we have w + > 0 and w -> 0. We say that T is a n-good tree if

• any vertex x of the h n first generations verifies ν(x) ≤ b and ν(x) i=1 A(x i ) ≥ 1 + η ,

• any vertex x of the h n following generations verifies ν(x) ≤ b and ν(x) i=1 A(x i ) ≤ 1 1+η .

Then we know that Q n := Q(T is n-good) ≥ exp(-n 1/3+o (1) ). Let Y ′ be a random walk starting from zero which increases (resp. decreases) of 1 with probability 1+η 2+η (resp. 1 2+η ). We define p ′ n as the probability that Y ′ reaches -1 before h n . We show that (2.6) is still true (by the exactly same arguments), so that there exists a constant K > 0 and a deterministic function O(n K ) bounded by a factor of n → n K , such that

P e ω (T← e > τ 2hn ≥ n) ≥ O(n K ) -1 (p ′ n ) n , (3.18)
We have, by gambler's ruin formula,

p ′ n = 1 - 1 1 + 1 1+η + . . . + 1 1+η hn ≥ 1 1 + η . Let k n := ⌊n d ⌋ with d ∈ (1/3, 1/2) and let f ∈ (d, 1 -d).
We call an n-slow tree a tree in which we can find a vertex |x| = k n such that T x is n-good (where T x is the subtree rooted at x), and for any y ≤ x, we have ν(y) ≤ exp(n f ). We observe that if a tree is not n-slow, then either there exists a vertex before generation k n with more than exp(n f ) children, or any subtree rooted at generation k n is not n-good. This leads to

Q(T is not n-slow) ≤ kn ℓ=1 E GW [Z ℓ ]GW (ν > e n f ) + E GW (1 -Q n ) Z kn ≤ k n m kn me -n f + (1 -Q n ) (1+ε) kn + GW (Z kn ≤ (1 + ε) kn ) .
We notice that (1 1) ). Moreover,

-Q n ) (1+ε) kn ≤ exp(-(1 + ε) n d+o(
GW (Z kn ≤ (1 + ε) kn ) ≤ (1 + ε) kn E GW 1 Z kn
Observe that for any k ≥ 0, E GW 1

Z k+1 ≤ q 1 E GW 1 Z k +(1-q 1 )E GW 1 X 1 +X 2
where X 1 and X 2 are independent and distributed as Z k . We then verify E GW 1

X 1 +X 2 ≤ (u/2) ∧ v where u := E GW [min(X 1 , X 2 ) -1 ] and v := E GW [max(X 1 , X 2 ) -1 ]. Since u + v = E GW 2 Z k , we de- duce that E GW 1 X 1 +X 2 ≤ 2 3 E GW 1 Z k , leading to E GW 1 Z k+1 ≤ (q 1 + 2 3 (1 -q 1 ))E GW 1 Z k ≤ (q 1 + 2 3 (1 -q 1 )) k+1 . We get GW (Z kn ≤ (1 + ε) kn ) ≤ (1 + ε)(q 1 + 2 3 (1 -q 1 )) kn ,
and, taking ε small enough, 1) ) . Let

Q(T is not n-slow) ≤ exp(-n d+o(
n 1 := n -k n -2h n , δ > 0, and G k := {|x| = k s.t. T x is n-slow}. We have τ n n ∈ [a, b[, τ← e > τ n ⊂ E 5 ∩ E 6 ∩ E 7 , with
E 5 := T← e > τ n 1 , τ n 1 n 1 ∈ 1 v -δ, 1 v + δ , E 6 := X τn 1 ∈ G n 1 , E 7 := D(X τn 1 ) > τ n , τ n n ∈ a - 1 v + δ, b - 1 v -δ .
We look at the probability of the event E 7 conditioned on E 5 and E 6 . Therefore, we suppose that u := X τn 1 is known, and that the subtree T u rooted at u is a n-slow tree. There exists x n at generation n 1 + k n such that T xn is a n-good tree and ν(y) ≤ e n f for any u ≤ y < x n .

Let also n be large enough so that k n ≤ δn. It implies that

P u ω D(u) > τ n , τ n n ∈ (a - 1 v + δ, b - 1 v -δ) ≥ P u ω (D(u) > T xn = k n ) P xn ω D(x n ) > τ n , τ n n ∈ (a - 1 v + δ, b - 1 v -2δ) ≥ exp(-c 21 n c 22 )P xn ω D(x n ) > τ n , τ n n ∈ (a - 1 v + δ, b - 1 v -2δ) ,
for some c 22 ∈ (0, 1). By definition of a n-good tree, any vertex x descendant of x n and such that |x| ≤ n verifies ν(x) ≤ b. Therefore there exists a constant c 23 > 0 such that P y ω (τ n ≤ 2h n ) ≥ c 2hn 23 for any y ≥ x n , |y| < n. By the strong Markov property,

P xn ω D(x n ) > τ n , τ n n ∈ (a - 1 v + δ, b - 1 v -2δ) ≥ P xn ω D(x n ) > τ n , τ n n ≥ a - 1 v + δ c 2hn 23 .
Let L := a -1 v + δ. By equation (3.18),

P xn ω D(x n ) > τ n , τ n n ≥ a - 1 v + δ ≥ O(n K ) -1 1 1 + η Ln .
Hence, by the strong Markov property, lim inf

n→∞ 1 n ln P e ω (E 7 | E 5 ∩ E 6 ) = lim inf n→∞ 1 n ln P u ω D(u) > τ n , τ n n ∈ (a - 1 v + δ, b - 1 v -δ) ≥ -L(1 + η) .
This implies that lim Notice that

E Q [P e ω (E 5 ∩ E c 6 )] = E Q [P e ω (E 5 ) -P e ω (E 5 ∩ E 6 )] = Q(E 5 )(1 -Q(T is n-slow)) ≤ Q(E 5 ) exp(-n d+o(1)
) , by equation (3.19). By Markov's inequality, (1) .

Q(P e ω (E 5 ∩ E c 6 ) ≥ 1 n 2 ) ≤ n 2 Q(E 5 )e -n d+o
The Borel-Cantelli lemma implies that almost surely, for n large enough,

P e ω (E 5 ∩ E 6 ) ≥ P e ω (E 5 ) - 1 n 2 .
We observe that P e ω (E 5 ) → P e ω (T← e = ∞) when n goes to infinity. Therefore , equation (3.22) becomes lim

Proof of Proposition 3.3

The speed-up case is quite immediate. Indeed, reasoning on the last visit to the root, we have

Q e (τ n ≤ bn, D(e) = ∞) ≤ Q e (τ n ≤ bn) ≤ bnQ e (τ n ≤ bn, D(e) = ∞) .
Therefore, by Theorem 3.1,

lim n→∞ 1 n ln Q e (τ n ≤ bn) = lim n→∞ 1 n ln Q e (τ n ≤ bn | D(e) = ∞) .
It already gives (3.5) since I a is strictly decreasing on [1, 1/v]. We do exactly the same for the quenched inequality. Therefore, let us turn to the slowdown case, beginning with the annealed inequality (3.7). We follow the arguments of [START_REF] Dembo | Large deviations for random walks on Galton-Watson trees: averaging and uncertainty[END_REF]. We still write i = ess inf A. For technical reasons, we need to distinguish the cases where P(A = i) is null or positive. We feel free to deal only with the case P(A = i) = 0, the other one following with nearly any change. Moreover, we suppose without loss of generality that i > ν -1 min , since the two sides are equal to zero when i ≤ ν -1 min . Let k ≥ 1. We write ℓ = k [START_REF] Athreya | Branching processes[END_REF] to say that ℓ and k have the same parity. Following [START_REF] Dembo | Large deviations for random walks on Galton-Watson trees: averaging and uncertainty[END_REF], we write for b > a > 1/v,

P e ω (bn > τ n ≥ an) = ℓ=k[2] |x|=k P e ω (bn > τ n ≥ an, τ n > ℓ, X ℓ = x, |X i | > k, ∀ i = ℓ + 1 . . . , τ n ) = ℓ=k[2] |x|=k P e ω (τ n > ℓ, X ℓ = x)P x ω (bn -ℓ > τ n > an -ℓ, D(x) > τ n ) .
By coupling, we have, for p := ν min i > 1,

sup |x|=k P e ω (τ n > ℓ, X ℓ = x) ≤ P e ω (|X ℓ | ≤ k) ≤ P (S p ℓ ≤ k) ,
where S p ℓ stands for a reflected biased random walk on the half line, which moves of +1 with probability p/1 + p and of -1 with probability 1/1 + p. From (and with the notation of) Lemma 5.2 of [START_REF] Dembo | Large deviations for random walks on Galton-Watson trees: averaging and uncertainty[END_REF], we know that for all ℓ of the same parity as k,

P (S p ℓ ≤ k) ≤ c k (1 + δ k ) ℓ P (S p ℓ = k, 1 ≤ S i ≤ k -1, i = 1, . . . , ℓ -1)
where c k < ∞ and δ = (δ k ) is a sequence independent of all the parameters and tending to zero. In particular, we stress that δ do not depend on p. Hence, P e ω (bn > τ n ≥ an) is smaller than

c k (1 + δ k ) bn ℓ=k[2] |x|=k P (S p ℓ = k, 1 ≤ S i ≤ k -1, i = 1, . . . , ℓ -1)W n (x, ℓ) where W n (x, ℓ) := P x ω (bn -ℓ > τ n ≥ an -ℓ, D(x) > τ n ) .
We deduce that

P e ω (bn > τ n ≥ an) ≤ c k (1 + δ k ) bn ℓ=k[2] |x|=k P e ωp (τ k = ℓ, D(e) > ℓ)W n (x, ℓ) = ν k min c k (1 + δ k ) bn ℓ=k[2] |x|=k P e ωp (τ k = ℓ, D(e) > ℓ, X ℓ = x)W n (x, ℓ) , (3.23)
where ω p represents the environment of the biased random walk on the ν min -ary tree such that for any vertex x, P x ωp (X 1 = x i ) = This proves (1.8). For the quenched case, we have that

P e ω (τ n = n) = |x|=n n-1 k=0 ω(x k , x k+1 ) ,
where x k is the ancestor of the vertex x at generation k. We observe that we are reduced to the study of a generalized multiplicative cascade, as studied in [START_REF] Liu | On generalized multiplicative cascades[END_REF]. The following lemma is well-known in the case of a regular tree (see [START_REF] Franchi | Chaos multiplicatif: un traitement simple et complet de la fonction de partition[END_REF] and [START_REF] Comets | Majorizing multiplicative cascades for directed polymers in random media[END_REF]). We extend it easily to a Galton-Watson tree. Proof. When ψ ′ (1) < ψ(1), Biggins [START_REF] Biggins | Martingale convergence in the branching random walk[END_REF] shows that lim n→∞ We see that (still by [START_REF] Biggins | Martingale convergence in the branching random walk[END_REF]) lim n→∞

  In the transient case, let v denote the speed of the walk, which is the deterministic real v ≥ 0 such that lim n→∞ |X n | n = v, a.s. Define i := ess inf A , s := ess sup A .

Theorem 1 . 1 ( 1 n 1 n

 1111 Speed-up case) There exist two continuous, convex and strictly decreasing functionsI a ≤ I q from [1, 1/v] to R + , such that I a (1/v) = I q (1/v) = 0 and for a < b, b ∈ [1, 1/v], lim n→∞ ln Q e τ n n ∈]a, b] = -I a (b) , , b] = -I q (b) . (1.5)Theorem 1.2 (Slowdown case) There exist two continuous, convex functionsI a ≤ I q from [1/v, +∞[ to R + , such that I a (1/v) = I q (1/v) =0 and for any 1/v ≤ a < b, lim n→∞ ln Q e τ n n ∈ [a, b[ = -I a (a) , ∈ [a, b[ = -I q (a) . (1.7)

  Then ψ(0) = ln(m) and ψ(1) = ln E Q ν(e)i=1 ω(e, e i ) . Proposition 1.3 We have I a (1) = -ψ (1) , (1.8)

  [START_REF] Zeitouni | Random walks in random environment[END_REF]

  )

  ← y ) > B, then E(ω y ) = {(1, . . . , 1)} and Q (ζ = e | ω y ) = 1. Therefore suppose ν( ← y ) ≤ B and let h := max{1 ≤ L ≤ H : ν(y L , L) ≤

  27) For any x ∈ W (e), define, for any y ∈ [[e, G(x)]], ω(y, y + ) := ω(y, y + ) ω(y, y + ) + ω(y, , y + ) + ω(y, ← y ) ,

Theorem 3 . 2 (

 32 Slowdown case) There exist two continuous, convex functionsI a ≤ I q from [1/v, +∞[ to R + , such that I a (1/v) = I q (1/v) =0 and for any 1/v ≤ a < b, lim n→∞ 1 n ln Q e τ n n ∈ [a, b[ D(e) = ∞ = -I a (a) , , b[ D(e) = ∞ = -I q (a) . (3.4)

  , b[ | D(e) = ∞) . (3.8) Theorems 3.1 and 3.2 are proved in two distinct parts for sake of clarity. Proposition 3.3 is proved in subsection 3.3.

3. 1 We define also for any b ≥ 1 hLemma 3 . 4 1 n

 11341 Proof of Theorem 3.1 For any real numbers h ≥ 0 and b ≥ 1, any integer n ∈ N and any vertex x ∈ T with |x| = n, define A(h, b, x) := {ω : P e ω τ n = T x , τ n ≤ bn, T← e > τ n ≥ e -hn } , e n (h, b) := E Q c (b) := inf{h ≥ 0 : ∃ p ∈ N, e p (h, b) > 0} . There exists for any b ≥ 1 and h > h c (b), a real e(h, b) > 0 such that lim n→∞ ln(e n (h, b)) = ln(e(h, b)) . Moreover, the function (h, b) → ln(e(h, b)) from {(h, b) ∈ R + × [1, +∞[ : h > h c (b)} to R is concave, is nondecreasing in h and in b, and lim h→∞ ln(e(h, b)) = ln(m) .

n→∞ 1 n

 1 ln(e n (h, b)) = sup 1 k ln(e k (h, b)), k ≥ 1 =: ln(e(h, b)) , (3.10) with e(h, b) > 0. Similarly, we can check that

  which leads to ln(e(th 1 + (1t)h 2 , tb 1 + (1t)b 2 )) ≥ t ln(e(h 1 , b 1 )) + (1t) ln(e(h 2 , b 2 )) , hence the concavity of (h, b) → ln(e(h, b)). The fact that e(h, b) is nondecreasing in h and in b is direct. Finally, lim sup h→∞ ln(e(h, b)) ≤ ln(m) and lim inf h→∞ ln(e(h, b)) ≥ lim inf h→∞ ln(e 1 (h, b)) = ln(m) by dominated convergence. In the rest of the section, we extend e(h, b) to R + × [1, +∞[ by taking e(h, b) = 0 for h ≤ h c (b).

Corollary 3 . 5

 35 Let S := {h ≥ 0 : e(h, b) > 1} and S ′ := {h ≥ 0 : e(h, b) ≥ 1}. We have sup{e -h e(h, b), h ∈ S} = sup{e -h e(h, b), h ∈ S ′ } .

  e ω (τ n ≤ bn) | D(e) = ∞) = -J q (b) . (3.14)In the annealed case, notice that S e (τ n < T← e < ∞, τ n ≤ bn) = S e (τ n < T← e , τ n ≤ bn)E P[1 -β] which leads similarly to lim n→∞ 1 n ln(S e (τ n ≤ bn)) = -J a (b) . (3.15)

  , b, x) := {ω : P e ω τ n = T x , T← e > τ n ≥ bn ≥ e -hn } , e n (h, b) := E Q {h : e(h, b) > 1} . Define also for any b ≥ 1, J a (b) := -sup{-h + ln( e(h, b)) , h ≥ 0} , J q (b) := -sup{-h + ln( e(h, b)) , h ∈ S} , and for any b ≥ 1/v, I a (b) := J a (b) , I q (b) := J q (b) .

lim n→∞ 1 n

 1 ln P e ω T← e > τ n ≥ bn = -J q (b) . (3.17) As before, we obtain lim n→∞ 1 n ln (S e (τ n ≥ bn)) = -J a (b) , lim n→∞ 1 n ln (P e ω (τ n ≥ bn | D(e) = ∞)) = -J q (b) .

  v ≤ a < b. We want to show that (under the hypothesis i ≤ ν -1 min ), lim inf n→∞ ln P e ω ( τ n n ∈ [a, b[, D(e) > τ n ) = 0 . (3.20) If this is proved, the Jensen's inequality gives lim inf n→∞ ln Q e ( τ n n [a, b[, D(e) > τ n ) = 0 . (3.21) Equations (3.4) and (3.3) follow. Therefore, we focus on the proof of (3.20).

1 n ln P e ω (E 5 ∩ E 6 ∩ E 7 ) ≥ lim inf n→∞ 1 n

 15671 , b[, D(e) > τ n ≥ lim inf n→ ln P e ω (E 5 ∩ E 6 ) -L ln(1 + η) . (3.22)

pνN

  min(1+p) for each child x i , and P x ω (X 1 = ← x) = 1 1+p . Taking the expectations yields that Q e (bn > τ n ≥ an) ≤ ν k min c k (1 + δ k ) bn ℓ=k[START_REF] Athreya | Branching processes[END_REF] |x|=kP e ωp (τ k = ℓ, D(e) > ℓ, X ℓ = x)E Q [W n (x, ℓ)] .(3.24)Moreover, define for any |x| = k,S + k,ℓ (T, x) = {s i } ℓ i=0 : |s i+1 | -|s i | = 1, s 0 = 0, k -1 ≥ |s i | > 0, s ℓ = xthe set of paths on T which ends at x in ℓ steps and stays between generation 1 and k -1 before. We notice that, for any environment ω,P e ω (τ k = ℓ, D(e) > ℓ, X ℓ = x) = {s}∈S + k,ℓ (T,x) y∈T ω(y, ← y ) N (y, ← y ) ν(y) i=1 ω(y, y i ) N (y,y i ) (3.25)where for each path {s i }, N(z, y) stands for the number of passage from z to y. Let ε > 0, and G k denote for any k the set of trees such that any vertex x of generation less than k verifies ν(x) = ν min and A(x) ≤ ess inf A + ε. Let p ′ := ν min (ess inf A + ε). We observe thatP e ωp (τ k = ℓ, D(e) > ℓ, X ℓ = x) = {s}∈S + k,ℓ (T,x) (y,y i )Therefore, if T belongs to G k , we have by equation(3.25),P e ωp (τ k = ℓ, D(e) > ℓ, X ℓ = x) ≤ 1 + p ′ 1 + p ℓ P e ω (τ k = ℓ, D(e) > ℓ, X ℓ = k) .It entails that1I {T∈G k } ℓ=k[2] |x|=k P e ωp (τ k = ℓ, D(e) > ℓ, X ℓ = x)W n (x, ℓ) ≤ 1I {T∈G k } 1 + p ′ 1 + p bn ℓ=k[2] |x|=k P e ω (τ k = ℓ, D(e) > ℓ, X ℓ = x)W n (x, ℓ) = 1I {T∈G k } 1 + p ′ 1 + p bn P e ω (bn > τ n ≥ an, D(e) > τ n ) ≤ 1 + p ′ 1 + p bn P e ω (bn > τ n ≥ an, D(e) > τ n ) . (3.26)Taking expectations givesQ(T ∈ G k ) ℓ=k[2] |x|=k P e ωp (τ k = ℓ, X ℓ = x)E Q [W n (x, ℓ)] ≤ 1 + p ′ 1 + p bn Q e (bn > τ n ≥ an, D(e) > τ n ) . (3.27) As before, Q e (bn > τ n ≥ an, D(e) = ∞) + Q e (bn > τ n ≥ an, ∞ > D(e) > τ n ) = Q e (bn > τ n ≥ an, D(e) > τ n ) ≥ Q e (bn > τ n ≥ an, D(e) = ∞) . Since Q e (bn > τ n ≥ an, ∞ > D(e) > τ n ) ≤ Q e (bn > τ n ≥ an, D(e) > τ n )E Q [1β], we get lim n→∞ 1 n ln Q e (bn > τ n ≥ an, D(e) > τ n ) = lim n→∞ 1 n ln Q e (bn > τ n ≥ an | D(e) = ∞) .

Consequently, we have by ( 3 .

 3 24) and (3.27) lim sup n→∞ Q e (bn > τ n ≥ an) ≤ b ln 1 + p ′ 1 + p (1 + δ k ) + lim n→∞ 1 n ln Q e (bn > τ n ≥ an | D(e) = ∞) . Since Q e (cn > τ n > bn) ≥ Q e (cn > τ n > bn, D(e) = ∞), we prove equation (3.7) by taking p ′ arbitrarily close to p, and letting k tend to infinity. We prove now the quenched equality (3.8). For any environment ω, construct the environment f p (ω) by setting A(x) = i (:= ess inf A) for any |x| ≤ k. We construct also for p ′ > p, an environment f p ′ (ω) by picking independently A(x) in [i, p ′ /ν min ] for any x ≤ k, such that A(x) has the distribution of A conditioned on A ∈ [i, p ′ /ν min ]. By equation (3.23), we have almost surely lim sup n→∞ 1 n ln P e ω (bn > τ n ≥ an) ≤ lim sup n→∞ 1 n P e fp(ω) (bn > τ n ≥ an, D(e) > τ n ) + b ln(1 + δ k ) . Equation (3.26) applied to the environment f p ′ (ω), together with Theorem 3.2 shows that lim sup n→∞ 1 n ln P e fp(ω) (bn > τ n ≥ an, D(e) > τ n ) ≤ -I q (b) + b ln 1 + p ′ 1 + p . Let p ′ tend to p to get that almost surely, lim sup n→∞ 1 n ln P fp(ω) (bn > τ n ≥ an, D(e) > τ n ) ≤ -I q (b) . ω (bn > τ n ≥ an) ≤ -I q (b) + b ln(1 + δ k ) . When k goes to infinity, we obtain lim sup n→∞ 1 n ln P e ω (bn > τ n > an) ≤ -I q (b) , which gives equation (3.8).

3. 4 3

 43 Proof of Proposition 1.Recall that, for any θ ∈ R,

Lemma 3 . 6 1 n

 361 We have lim n→∞ ln( |x|=nn-1 k=0 ω(x k , x k+1 )) = inf ]0,1] 1 θ ψ(θ) .

1 n ln( |x|=n n- 1 k=0

 11 ω(x k , x k+1 )) = ψ(1) = inf ]0,1] 1 θ ψ(θ). Therefore let us assume that ψ ′ (1) ≥ ψ[START_REF] Aidékon | Transient random walks in random environment on a Galton-Watson tree[END_REF]. By the argument of[START_REF] Franchi | Chaos multiplicatif: un traitement simple et complet de la fonction de partition[END_REF]

Finally, let 1 θ

 1 θ ∈]0, θ c [ where ψ(θ c ) = inf ]0,1] ψ(θ). Since ( i a i ) θ ≤ i a θ i for any (a i ) i with a i ≥ 0, it yields that lim sup k , x k+1 ) θ   .

1 n ln( |x|=n n- 1 k=0

 11 ω(x k , x k+1 ) θ ) = ψ(θ). It remains to let θ tend to θ c .4 The subexponential regime : Theorem 1.4We prove (1.10) and (1.11) separately. We recall that the speed v of the walk verifiesv = E S e [|XΓ 1 |] E S e [Γ 1 ] .

  time τ hn we can't find an edge of level smaller than h n crossed only once} ∩ {D(e) > τ hn } , E 2 := {the walk visits the level h n n times before reaching the root or the level 2h n } , E 3 := {after the n-th visit of level h n , the walk reaches level 2h n before level h n } , E 4 := {after time τ 2hn the walk never comes back to level 2h n -1} .

Acknowledgements: I am very grateful of Zhan Shi for his guidance in the redaction of this work. I thank also the anonymous referee for suggesting me several improvements.

Proof of Theorem 1.4 : equation (1.10). Suppose that either "i < ν -1 min and q 1 = 0" or "i < ν -1 min and s < 1" . Let a > 1/v and c 24 > 0 such that c 24 < (E S e [X Γ 1 ]) -1 . We have S e (τ n ≥ an) ≥ S e (Γ nc 24 ≥ an) -S e (Γ nc 24 > τ n ) .

The second term on the right-hand side decays exponentially by Cramér's Theorem applied to the random walk (|X Γn |, n ≥ 0) (recall that |X Γ 1 | has exponential moments by Fact A).

The simple inequality S e (Γ nc 24 ≥ an) ≥ S e (Γ 1 ≥ an) thus implies by Proposition 2.2 the lower bound of (1.10). Hence, we turn to the upper bound of (1.10). Part (i) of Lemma 6.3

of [START_REF] Dembo | Large deviations for random walks on Galton-Watson trees: averaging and uncertainty[END_REF] states: Lemma A (Dembo et al. [START_REF] Dembo | Large deviations for random walks on Galton-Watson trees: averaging and uncertainty[END_REF])

By Proposition 2.2, Y 1 = Γ 1 meets the conditions of the lemma. Therefore, take in lemma A, Y i = Γ i -Γ i-1 and t = a/c 25 where c 25 is such that

In particular, we have t > E S e We finish with the case "Λ < ∞". Proof of Theorem 1.4 : equation (1.11). Suppose that Λ < ∞ and let a, c 24 and c 25 be as before. We write

By Proposition 2.4, S e (Γ 1 ≥ an) = n -Λ+o (1) . Therefore S e (Γ 1 < an) nc 24 -1 tends to 1 (since Λ > 1). Consequently, S e (Γ nc 24 ≥ an) ≥ n 1-Λ+o (1) , which gives the lower bound of (1.11), by the inequality S e (τ n ≥ an) ≥ S e (Γ nc 24 ≥ an) -S e (Γ nc 24 > τ n ). Turning, to the upper bound, write as before S e (τ n ≥ an) ≤ S e (Γ nc 25 ≥ an)+ S e |X Γnc 25 | ≤ n . We already know that S e |X Γnc 25 | ≤ n is exponentially small. Let

< ∞, example 2.6.5 of [START_REF] Petrov | Sums of independent random variables[END_REF] says that if p ≥ 2,

and example 2.6.20 of [START_REF] Petrov | Sums of independent random variables[END_REF], combined with Chebyshev's inequality, shows that if 1 ≤ p ≤ 2,

By Proposition 2.4, E[H p 1 ] < ∞, for any p < Λ. We take x = ( a c 25 E S e [|X Γ 1 |] -E S e [Γ 1 ])n to see that S e (Γ nc 25 ≥ an) ≤ c(p)n 1-p for any p < Λ. Let p tend to Λ in order to complete the proof of equation (1.11).