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

Roland Diel
email: diel@unice.fr

The heavy range of randomly biased walks on trees

Keywords: Primary 60K37, 60J80; Secondary 62G05 randomly biased random walks, branching random walks, range, non-parametric estimation

We focus on recurrent random walks in random environment (RWRE) on Galton-Watson trees. The range of these walks, that is the number of sites visited at some fixed time, has been studied in three different papers [AC18], [AdR17] and [dR16]. Here we study the heavy range: the number of edges visited at least α times for some integer α. The asymptotic behavior of this process when α is a power of the number of steps of the walk is given for all the recurrent cases. It turns out that this heavy range plays a crucial role in the rate of convergence of an estimator of the environment from a single trajectory of the RWRE.

Introduction

In this paper, random walks in random environment (RWRE) on a supercritical Galton-Watson tree are considered. We first focus on the number of edges frequently visited by the walk, this random variable is called heavy range in the paper. This can be seen in some sense as an extension of the works of [START_REF] Andreoletti | Range and critical generations of a random walk on Galton-Watson trees[END_REF], generalized to the whole class of recurrent walks on trees. A second aim is to apply our control on the heavy range to a problem of non-parametric estimation for the distribution of the environment, extending this time the work of [START_REF] Diel | Non parametric estimation for random walks in random environment[END_REF] in the one-dimensional case.

Let us first give a precise definition of the process we are interested in. Consider a supercritical Galton-Watson tree T with offspring distributed as a random variable ν. In the paper, 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 also denote by x, y the sequence of vertices realizing the unique shortest path between x and y, by |x| the generation of x that is the length of the path e, x and we write x < y (resp. x ≤ y) when y is a descendant of x that is when x is an element of e, y * (resp. of e, y ). We also write x ∧ y for the common ancestor of x and y belonging to the largest generation. 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 assume that V (e) = 0 and we denote the increments of V (x) by ω x := V (x) -V (x * ). For any generation n and conditionally to E n = { T n , (V (x), x ∈ T n ) }, the variables ( ω xi , i ≤ ν x ) where x is a vertex of T such that |x| = n are assumed to be i.i.d. distributed as a random variable ( ω i , i ≤ ν ). We denote by P the distribution of E = { T, ( V (x), x ∈ T ) }; this variable is called the random environment of the walk.

For a given realization of E, we consider the Markov chain (X n ) n∈N on T ∪ { e * } with transition probabilities defined by the following relations:

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 (xi) = 1 1 + νx i=1 e -ωx i , ∀j ≤ ν x , P E ( X n+1 = x j |X n = x ) = e -V (xj ) e -V (x) + νx i=1 e -V (xi) = e -ωx j 1 + νx i=1 e -ω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 defined as the measure P E integrated with respect to the law of E:

P( • ) = P E ( • ) P( dE ) .
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. We finally introduce P * , the annealed probability conditioned on the survival set of the tree T.

The walk (X n ) n∈N , called biased random walk on a tree, was first introduced by R. Lyons (see [START_REF] Lyons | Random walks and percolation on trees[END_REF] and [START_REF] Lyons | Random walks, capacity and percolation on trees[END_REF]). In our case where the bias is random, the first references go back to R. Lyons and R. Pemantle [START_REF] Lyons | Random walk in a random environment and first-passage percolation on trees[END_REF] and M.V. Menshikov and D. Petritis [START_REF] Menshikov | On random walks in random environment on trees and their relationship with multiplicative chaos[END_REF]. Random walks in random environment on trees form a subclass of canonical models in the more general framework of random motions in random media that are widely used in physics. They are a natural extension of the one dimensional model, originally introduced in the works of [START_REF] Chernov | Replication of a multicomponent chain, by the "lightning mechanism[END_REF]. These models have been intensively studied in the last four decades, mostly in the physics and probability theory literature.

The behaviors of randomly biased walks on trees differ deeply from the behaviors of the RWRE in the one-dimensional case. In particular there are several regimes for both recurrent and transient cases. A complete classification for the recurrent cases is given by G. Faraud [START_REF] Faraud | A central limit theorem for random walk in a random environment on marked galton-watson trees[END_REF] (for the transient cases, see E. Aidekon [START_REF] Aïdékon | Transient random walks in random environment on a galton-watson tree[END_REF]). It can be determined from the fluctuations of log-Laplace transform ψ(s) := log E |z|=1 e -sV (z) as resumed in Figure 1. Here we focus on the recurrent cases that is to say when inf s∈[0,1] ψ(s) ≤ 0. They present essentially three different asymptotic regimes which depend on the fluctuation of ψ. In the paper, we need a bunch of classical assumptions which are summarized here: Assumption A1.

• the Galton-Watson tree is supercritical:

E |x|=1 1 = E[ ν ] ∈ (1, ∞).
• the log-Laplace transform ψ is well defined on a neighborhood of [0, 1]: ∃r 1 , r 2 > 0, ∀s ∈ [-r 1 , 1 + r 2 ], ψ(s) < ∞ .

(1)

• inf s∈[0,1] ψ(s) ≤ 0 (so (X n ) n∈N is recurrent).

• let t 0 := inf { s ≥ 0, ψ(s) = 0 } then:

E |z|=1 e -t0V (z) 2 < +∞. ( 2
)
and if t 0 = 1:

if ψ (1) ≥ 0, there exists δ > 0 such that E[ν 1+δ ] < +∞,

-if ψ (1) < 0, let κ := inf{s > 1, ψ(s) = 0} ∈ (1, +∞], (3)
when κ < ∞,

E |z|=1 e -κV (z) • max(-V (z), 0) < +∞ . (4)
Let us briefly describe the different recurrent cases (assuming the above conditions). First, when inf s∈[0,1] ψ(s) < 0 (Figure 2: A), the walk is positive recurrent and the largest generation visited up to an instant n, X * n := max k≤n |X k | is of the order log n ( [START_REF] Hu | A subdiffusive behavior of recurrent random walk in random environment on a regular tree[END_REF]), this is the slowest case, even slower than one dimensional Sinai's random walk [START_REF] Ya | The limit behaviour of a one-dimensional random walk in a random medium[END_REF]).

If inf s∈[0,1] ψ(s) = 0 (Figure 2: B and C), then different behaviors appear depending on the sign of ψ (1). When ψ (1) ≥ 0 (Figure 2: B), there are again two possible cases: if ψ (1) > 0 then the walk is positive recurrent whereas when ψ (1) = 0 the walk is null recurrent. However these two cases lead to the same asymptotic behavior for X * n (up to some multiplicative constant) which is of the order (log n) 3 (see [START_REF] Hu | Slow movement of recurrent random walk in random environment on a regular tree[END_REF] and [START_REF] Faraud | Almost sure convergence for stochastically biased random walks on trees[END_REF]).

Finally, when ψ (1) < 0 (Figure 2: C), the walk is null recurrent and X * n is of the order n 1-1/ min(κ,2) where κ is defined in (3) (see [START_REF] Hu | A subdiffusive behavior of recurrent random walk in random environment on a regular tree[END_REF], [START_REF] Faraud | A central limit theorem for random walk in a random environment on marked galton-watson trees[END_REF], [START_REF] Aïdékon | Scaling limit of the recurrent biased random walk on a galton-watson tree[END_REF], [dR16]).

In this paper we study the heavy range: the number of edges of the tree which are frequently visited by the walk. Precisely, for x ∈ T, let N n x be the number of times the walk (X n ) n∈N visits the edge (x * , x) before time n:

N n x := n k=1 1 { X k-1 =x * ,X k =x } .
Then, for any α > 0 the heavy range (of level α) is the random variable

R n α := x∈T 1 { N n x ≥α } . (5)
Note that for α = 1, the above random variable is the usual range. In this case, the asymptotic behavior is known for all null recurrent cases, see [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 [dR16]. The heavy range is then a natural generalization of the usual range which helps to understand how the random walk spreads on the tree.

Consider now the n th return to e * :

T 0 := 0 and ∀n ≥ 1, T n := inf{k > T n-1 , X k = e * } .
The following theorem gives the behavior of the heavy range taken at time T n in all recurrent cases. Note that in these cases, T n is almost surely finite for every integer n.

Theorem 1.1. Assume A1. For any θ ≥ 0,

log + R T n n θ log n
converges in P * -probability to a constant ξ θ where log + x stands for log(max(1, x)). Moreover, when θ ≥ 1, ξ θ = 0 and, when θ < 1:

• if inf s∈[0,1] ψ(s) < 0 or inf s∈[0,1] ψ(s) = 0 with ψ (1) ≥ 0, then ξ θ = t 0 (1 -θ). (6)
• if inf s∈[0,1] ψ(s) = 0 with ψ (1) < 0, then

ξ θ = κ(1 -θ) if 1 < κ ≤ 2, (7)
ξ θ = max 2 -κθ, 1 -θ if κ ∈ (2, ∞]. (8)
The proof of Theorem 1.1 for θ < 1 is given in Section 3. The cases θ ≥ 1 are then easily obtained using the results in the cases θ < 1 and the fact that, for any n ≥ 1, R T n n θ is a non-increasing function of θ.

Note that (6) corresponds to the slow cases, that is when X n behaves like a power of log n. Also t 0 < 1 if and only if the random walk is positive recurrent whereas t 0 = 1 corresponds to the so called boundary case for the branching potential (ψ(1) = ψ (1) = 0).

For the diffusive cases, that is when κ > 2, the heavy range is of the order n 2-κθ+o(1) , larger than n 1-θ for θ ≤ 1/(κ -1). Conversely, for θ ≥ 1/(κ -1), that is to say if we are interested in sites often visited by the walk, the range is of the order n 1-θ . We will see in the proof that this fact depends deeply where the edges sufficiently visited are localized on the tree.

The asymptotics of the heavy range in deterministic time will be easier to interpret in terms of the behavior of the walk. They are described in Theorem 1.3. The theorem is proved using Theorem 1.1 and a control on T n , it is done in Section 3.3.

The behavior of T n has been studied in [START_REF] Andreoletti | Spread of visited sites of a random walk along the generations of a branching process[END_REF] and more precisely in [START_REF] Hu | The slow regime of randomly biased walks on trees[END_REF] and [START_REF] Hu | Local times of subdiffusive biased walks on trees[END_REF], for completeness we recall these results in the following remark; note that in these papers the results are given for the n th -return time to the root e and not to e * but this does not change the rates of convergence.

Remark 1.2.

1. If inf s∈[0,1] ψ(s) = 0, with ψ (1) = 0 then in probability T n /(n log n) converges in probability to a positive limit (see [START_REF] Hu | The slow regime of randomly biased walks on trees[END_REF], Proposition 2.5). 2. If inf s∈[0,1] ψ(s) = 0, ψ (1) < 0 and κ = 2, T n /n min(κ,2) converges in law to a positive limit and if κ = 2, (T n log n)/n 2 converges in law to a positive limit (see [START_REF] Hu | Local times of subdiffusive biased walks on trees[END_REF], Corollary 1.2). 3. Finally if ψ (1) > 0 with inf s∈[0,1] ψ(s) = 0 or inf s∈[0,1] ψ(s) < 0 then T n /n converges in probability to a positive limit (both are positive recurrent random walks).

The behavior of the heavy range in deterministic time is given in the following theorem:

Theorem 1.3. Assume A1. For any θ ∈ [0, 1], log + R n n θ log n
converges in P * -probability to a constant ξθ .

Moreover,

• if inf s∈[0,1] ψ(s) ≤ 0 with ψ (1) ≥ 0, then ξθ = ξ θ = t 0 (1 -θ), • if inf s∈[0,1] ψ(s) = 0 with ψ (1) < 0 and -if 1 < κ ≤ 2, then ξθ = 1 -κθ for θ ≤ 1/κ and 0 otherwise, -if κ ∈ (2, ∞], then ξθ = max(1 -κθ , 1/2 -θ) for θ ≤ 1/2 and 0 otherwise.
Let us compare, for null recurrent cases, the heavy range R n n θ for θ > 0 and the regular range, that is R n 1 . It is proved in [START_REF] Andreoletti | Range and critical generations of a random walk on Galton-Watson trees[END_REF] that for the slow case, when ψ(1) = ψ (1) = 0, log n n R n 1 converges in probability to an explicit positive constant, whereas for the sub-diffusive and diffusive case, when ψ(1) = 0, ψ (1) < 0, it is proved in [START_REF] Aïdékon | Scaling limit of the recurrent biased random walk on a galton-watson tree[END_REF] and [dR16] that the correct normalization for the convergence in probability of R n 1 is simply 1/n. So for the regular range we observe that subdiffusive and diffusive cases spread more than in the slow case. For the heavy range the opposite appears, indeed when ψ(1) = ψ (1) = 0, t 0 = 1 and ξθ = 1 -θ which is larger than 1 -κθ for κ > 1. This tells us that the environment of the slow null recurrent case creates much more vertices where the walk spends larger amount of time than in the other cases.

Here we obtain the first order for the asymptotic expansion of the heavy range for any recurrent cases and of course a natural question is now to obtain the correct normalization for this range.

Non-parametric estimation of the law of the environment

The study of the heavy range has been partly motivated by the statistical problem we present here. The statistical study of random processes in random environment has been overlooked in the literature until recently, when new biophysics experiments produced data that can be modeled (at least in an ideal-case setup) by RWRE. For example in [START_REF] Marinari | Infering dna sequences from mechanical unzipping: an ideal-case study[END_REF], RWRE are used as a mathematical model of a mechanical denaturation of DNA. Consequently, a new series of works appeared on statistical procedures aiming at estimating the distribution of the environment from a RWRE trajectory.

We start with a brief resume of what has been done recently in the one dimensional discrete case. Recall that for RWRE on Z, the environment is a sequence of random variables (ρ x ) x∈Z . When the environment is i.i.d., the estimation of the distribution of ρ 0 observing only the RWRE (X n ) n∈N is a natural problem. The first theoretical result appears in [START_REF] Adelman | Random walks in random environment: What a single trajectory tells[END_REF] which treats the problem in a general settings with no quantitative purpose, then in [START_REF] Andreoletti | On the estimation of the potential of sinai's rwre[END_REF] and [START_REF] Andreoletti | DNA unzipping via stopped birth and death processes with unknown transition probabilities[END_REF] particular cases are detailed. Recently more attention has been paid to the one dimensional case: the aim was to provide a parametric estimation of the distribution of the environment with the help of a single trajectory of random walk (X n ) n∈N ([CFL + 14], [START_REF] Falconnet | Asymptotic normality and efficiency of the maximum likelihood estimator for the parameter of a ballistic random walk in a random environment[END_REF], [START_REF] Falconnet | Maximum likelihood estimation in the context of a sub-ballistic random walk in a parametric random environment[END_REF], [START_REF] Comets | Maximum likelihood estimator consistency for recurrent random walk in a parametric random environment with finite support[END_REF]). When the environment is a Markov chain a parametric approach can also be found in [START_REF] Andreoletti | Hidden markov model for parameter estimation of a random walk in a markov environment[END_REF]. The problem of non-parametric estimation has been studied in [START_REF] Diel | Non parametric estimation for random walks in random environment[END_REF], the aim of the result we present below is to extend their studies to the more delicate case of randomly biased random walks on supercritical Galton-Watson trees.

Indeed, the next step after the model of RWRE for mechanical denaturation of DNA in [START_REF] Marinari | Infering dna sequences from mechanical unzipping: an ideal-case study[END_REF], is to construct a similar model for mechanical denaturation of RNA. But while DNA molecules are quite linear, RNA molecules present a more complicated geometry with secondary structure (see [START_REF] Gerland | Force-induced denaturation of rna[END_REF]). It seems then natural to describe RNA molecules with trees and to mimic its mechanical denaturation by a random walk in random environment on a tree. However, the estimation of the distribution of the environment for a random walk on a tree is much more complicated as we have to study the law of the transitions of a branching random walk and not only a real random variable. Therefore, we only consider here a very particular and simple case; this part of the paper has to be seen as a first step to understand how the methods used for the one-dimensional case can be generalized. So, for all the statistical results in this part and in Section 4, we add to A1 the following assumptions:

Assumption A2.
• the reproduction law of the Galton-Watson is bounded: ∃K > 0, P( ν ≤ K ) = 1 .

• given the tree up to generation n and the number of children ν x of some x ∈ T such that |x| = n, the variables ( ω xi ) 1≤i≤νx are i.i.d. with the same distribution as some variable ω.

Our aim is then to estimate the distribution of ω given the observation of a single trajectory of the walk (X n ) n∈N up to time T n . In particular we need T n to be finite which is the case by recurrence of X. Precisely, we give an estimation of the c.d.f F of

ρ := (1 + e -ω ) -1 (9)
instead of the one of ω, but this is of course equivalent as conversely ω = log[ρ/(1 -ρ)].

Remark 1.4. It is possible to relax the condition on ν: if we suppose that the distribution is not bounded but only subgaussian, we still have the same rates of convergence in the following theorems. However the proof is more technical and for the sake of clarity we have chosen to present only the bounded case.

We need to assume a regularity condition on F . For that we use γ-Hölder seminorms and spaces: for any γ ∈ (0, 1], the Hölder space C γ is the set of continuous functions f : [0, 1] → R such that

f γ = sup u =v |f (v) -f (u)| |v -u| γ < ∞
and for γ ∈ (1, 2] the Hölder space C γ is the set of continuously differentiable functions f : [0, 1] → R such that

f γ = f ∞ + sup u =v |f (v) -f (u)| |v -u| γ-1 < ∞.
Our first theorem gives rates of convergence for our estimator.

Theorem 1.5. Assume A1, A2 and that the c.d.f. F of ρ is γ-Hölder for some γ ∈ (0, 2]. There exists an estimator F n of F , function of the trajectory ( X k ) 0≤k≤T n , such that for any > 0, n r-F n -F ∞ tends to 0 in P * -probability where

i) r = γt0 γ+t0 if inf s∈[0,1] ψ(s) < 0, inf s∈[0,1] ψ(s) = 0, with ψ (1) ≥ 0, ii) r = γκ γ+κ if inf s∈[0,1] ψ(s) = 0, ψ (1) < 0 and κ ≤ 2, iii) r = 2γ γ+κ if inf s∈[0,1] ψ(s) = 0, ψ (1) < 0 and 2 < κ ≤ 2 + γ, iv) r = γ γ+1 if inf s∈[0,1] ψ(s) = 0, ψ (
1) < 0 and κ > 2 + γ. In the previous theorem, the rate of convergence is given as a function of the parameter n. However, as the number of steps for the walk is the true sample size, it is more natural to give a rate depending on T n . This is done in the following corollary which is a direct consequence of Theorem 1.5 and Remark 1.2.

Corollary 1.6. Assume conditions of Theorem 1.5. The estimator F n is such that for any > 0,

( T n ) r-F n -F ∞ tends to 0 in P * -probability where i) r = γt0 γ+t0 if inf s∈[0,1] ψ(s) < 0, inf s∈[0,1] ψ(s) = 0, with ψ (1) ≥ 0, ii) r = γ γ+κ if inf s∈[0,1] ψ(s) = 0, ψ (1) < 0 and κ ≤ 2 + γ, iii) r = γ 2(γ+1) if inf s∈[0,1] ψ(s) = 0, ψ (1) < 0 and κ > 2 + γ.
The corollary shows that our best rate is obtained in the limit case t 0 = 1. It seems to be the best compromise between the number of visited sites and the number of times most of the sites are visited. Comparing our result on a tree to the recurrent one dimensional random walk of [START_REF] Diel | Non parametric estimation for random walks in random environment[END_REF], we remark that the error rates are really different. Indeed, in their paper, the time of observation used instead of T n is τ n , the first time the coordinate n is reached by the walk and Corollary 2 in [START_REF] Diel | Non parametric estimation for random walks in random environment[END_REF] gives for the recurrent case an error rate of the order log log τ n / log τ n . This is very large compared to what is obtained here in Corollary 1.6, so recurrent walks on the tree naturally yield a better rate for the error. The reason comes from the range of the different walks: for the one dimensional recurrent case very few coordinates are visited before time n, around (log n) 2 , whereas (see Theorem 1) for the walk on the tree the range is much larger (of the order of a power of n).

We now give a more explicit description of F n . For this purpose, we introduce the following family of estimators

F α n (u) := 1 R T n α E[ ν ] x∈T ψ αu α N T n x * , N T n x ( 10
)
where

ψ l α (i, j) := 1 { i≥α } i-1+j α-1 l-1 k=0 i -1 k j α -1 -k ,
using the conventions 0/0 = 0 and n k = 0 if 0 ≤ n < k. The logic behind the definition of the F α n will become clear in Section 4. The following theorem shows that the ( F α n ) n are estimators of the c.d.f. F with a risk bound depending on the heavy range R T n α . Theorem 1.7. Assume A1, A2 and that the c.d.f. F of ρ is in C γ for some γ ∈ (0, 2]. Then for any integers α, n ≥ 1, and any real z > 0, we have

P F α n -F ∞ ≥ K E[ ν ] z + log α + 2 log R T n α 2R T n α + 2 F γ α γ/2 ≤ Ce -z .
Theorem 1.7 shows that the random part of the error rate of our estimator is a function of the heavy range introduced in the previous subsection. To obtain the random optimal F α n for the estimation of F , a compromise must be done between considering sites which have been sufficiently visited, that is choosing a large α, and considering a sufficiently large number of sites, that is choosing α small enough. Remark that, in this theorem, we work with probability P and not P * . Theorem 1.5 and 1.7 will be proved in Section 4.

Overview of the proofs

The proof of Theorem 1.1 is divided into two parts : an upper bound given in Proposition 3.1 and lower bounds given in Propositions 3.3 and 3.4. Propositions 3.3 explains the contribution of the first generations of the tree, while 3.4 describes the contribution of larger generations. For all these bounds, arguments are adapted to the hypothesis done on the environment. More specifically important differences appear whether the largest generation visited by the walk before n returns to e * , X * T n , is small that is typically a power of log n or larger, that is typically a power of n. These behaviors are resumed in Lemma 3.2.

The upper bound of Proposition 3.1 is obtained by an estimation of the mean of the heavy range R T n n θ and by Markov's inequality. The most technical part is the study of the case X * T n ∼ n p (Case 2 in the proof of Proposition 3.1): indeed for this case, some sites with large potential which are far from the root are of major importance. It appears that these sites are essentially visited during a single excursion from e * to e * (contribution 2,2 in the proof) but that the walk is trapped a long time in their neighborhood. Then thanks the many-to-one Lemma (Lemma 2.1 in Section 2) the central issue is to study a random walk (S n ) n∈N on Z and especially a related random variable H S . for which the tail distribution function is estimated in Lemma 2.2 in Section 2. For the lower bound, which is more delicate to obtain, we decompose the proof into two Propositions. Proposition 3.3 is dedicated to the contribution of the first generations of the tree, that is sites x such that |x| ≤ (log n) 3 . It works for every cases (slow and fast) but is not always optimal for the fast ones. It is based on the idea that any sites x close to the root such that max u≤x V (u) ≤ (1 -θ -δ) log n for a small δ > 0 satisfy, with a high probability N T n x ≥ n θ (see ( 28)). This fact is obtained by a precise estimate of the Laplace transform of N T 1

x . Then it remains to show that the cardinal of the set

{x ∈ T, |x| ≤ (log n) 3 , V (x) ≤ (1 -θ -δ) log n} is larger than n t0(1-θ-2δ
) . This part is the object of Proposition 2.5. Proposition 3.4 completes the estimation of Proposition 3.3 for the fastest cases. Indeed in these cases, the random walk can visit generations of order a power of n before the n th return to e * and can be trapped a long time in some sites of these generations. More precisely in this proposition, we consider the vertices on the tree such that the variable H x := y≤x e V (y)-V (x) is of order n θ . The reason for that is the same as above: whenever the walk touches such an x, its local time at this vertex will be, with a large probability, larger than n θ . A first step in the proof is to introduce time independence, under quenched measure P E , as those x are visited only during a single excursion between two returns to e * (cf. Lemma 3.5). This independence allows to apply Tchebytchev inequality : see Lemma 3.7. From this lemma, it appears that two random variables which depend only on the environment have to be controlled. And thanks to concentration Lemma 2.4, a control depending only on their means and variances can be obtained. These quantities are computed in Lemma 3.8 and Lemma 3.9.

The statistical results are obtained by the estimation of the moments of ρ = (1 + e -ω ) -1 . In Proposition 4.1, we give a risk bound for an estimator of the moments m α,β := E ρ α (1 -ρ) β . Remark that the randomness of this bound depends only on the heavy range. Then, thanks to the Hölder regularity of F , this function can be approximated by the family of functions u →

F α (u) = αu -1 k=0 α-1 k m k,α-1-k (see Lemma 4.3).
We can therefore use (a slight variation of) the estimators introduced in Proposition 4.1 to construct estimators of F α and give a risk bound, this is done in Lemma 4.4. Theorem 1.7 follows directly while the last section explains how to obtain Theorem 1.5.

The rest of the paper is organized as follows. In Section 2 we present tools related to the environment together with estimates for potential V that will be used in Section 3. More specifically we study the number of vertices with low potential which have a great importance for the slow cases. Section 3 is the heart of the paper, we study the heavy range and prove Theorem 1.1. This section is decomposed into two subsections the first one deals with an upper bound for the heavy range and the second one with a lower bound. Note that the proof of the lower bound is more technical and need in particular to estimate the fluctuations of the environment, these estimates are more complex for the sub-diffusive and diffusive cases than for the slow cases. Then, in Section 4, we prove Theorem 1.5 on the non-parametric estimation problem of the environment.

Finally, throughout the paper, the letter C stands for a universal constant which value can change from line to line.

Preliminaries on the environment

In this section we present results related to the environment which are used in Section 3. Like in the whole paper, we assume in this section that conditions A1 are valid. In a first subsection we give useful technical lemmata and in a second one, we state and prove a result concerning the number of vertices with low potential V .

Let us begin with some notations specific to the environment. For u ∈ T, we denote by V u the environment centered at u: for any x ≥ u, V u (x) := V (x) -V (u). We also denote the maximum of V u between u and x by V u and the minimum of V between e and x by V u :

V u (x) := max u≤y≤x V (y) and V u (x) := min u≤y≤x V (y). (11)
We write V for V e and V for V e . Remark that if u and v are different vertices of the same generation , then, given T , ( V u (x) ) x≥u and ( V v (x) ) x≥v are i.i.d. and distributed as V under P.

Technical estimates

We first 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). It will be used several times in the paper to compute different expectations related to the environment.

Lemma 2.1 (Many-to-one Formula). For any integer m and any t > 0,

E |x|=m f (V (y), e ≤ y ≤ x) = E e tSm+ψ(t)m f (S i , 0 ≤ i ≤ m) .
where (S n ) n∈N is the random walk starting at 0 and 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))   .
The following lemma deals with a key random variable which appears in the study of the heavy range (via the edge local time of random walk (X n ) n∈N , see below (26)) after that many-to-one Formula is applied. Lemma 2.2. Assume ψ(1) = 0 and ψ (1) < 0 and that the parameter κ defined in (3) is finite. Let us consider the random walk (S n ) n∈N of the many-to-one Lemma with t = 1 and define for any ≥ 0, the random variable:

H S := k=0 e S k -S . (12)
Then, we can find three constants C ≥ c and A > 0 such that

∀m ≥ 1, ∀ ∈ N, P H S ≥ m ≤ C m κ-1 , and ∀m ≥ 1, ∀ ≥ A log m, P H S ≥ m ≥ c m κ-1 .
Proof. By definition of S 1 , E[ -S 1 ] = ψ (1) < 0 and E e -(κ-1)S1 = e ψ(κ) = 1. According to Lemma 1 in [START_REF] Kesten | A limit law for random walk in a random environment[END_REF] for the lattice case and to Theorem 2 in [START_REF] Grincevicius | On a limit distribution for a random walk on lines[END_REF] for the non-lattice case, +∞ j=0 e -Sj is P-a.s. finite and there are some constants c, C, such that for m ≥ 1,

c m κ-1 ≤ P +∞ j=0 e -Sj ≥ m ≤ C m κ-1 .
As for any ∈ N, H S L = k=0 e -S k where L = stands for the equality in law, this leads directly to the upper bound of the lemma. For the lower bound, we remark that

P H S ≥ m ≥ P ∞ k=0 e -S k ≥ 3 2 m -P ∞ k= +1 e -S k > m 2 .
And we only have to prove that for large enough,

P ∞ k= +1 e -S k > m/2 is negligible compared to 1/m κ-1 . Indeed, consider the event A := {∀k ≥ + 1, e -S k ≤ m 2k 2 }. On A , ∞ k= +1 e -S k ≤ m 2 ∞ k= +1 1 k 2 ≤ m 2 .
Therefore, Markov inequality yields

P ∞ k= +1 e -S k > m/2 ≤ P A = P k≥ +1 e -S k > m 2k 2 ≤ k≥ +1 P e -(κ-1)S k /2 > m 2k 2 (κ-1)/2 ≤ 2 m (κ-1)/2 k≥ +1 k κ-1 e kψ( κ+1 2 ) ≤ Cm -(κ-1)/2 κ-1 e ψ( κ+1 2 ) ,
As ψ( κ+1 2 ) < 0, we can find a constant A such that for ≥ A log m, the above expression is o(m -(κ-1) ). This concludes the proof of the lemma.

We give now a control of the maximum of V at the very first generations of the tree. Recall that P * is the probability P conditioned on the survival of the tree.

Lemma 2.3. For any δ > 0, we can find two positive constants , b 1 such that for n large enough,

P * max |u|≤ log n |V (u)| ≥ δ log n ≤ n -b1 .
Note that the optimal bound, that is to say the one that leads to the almost-sure behavior of max |u|≤ log n V (u), is well known (see for example [START_REF] Andreoletti | The number of generations entirely visited for recurrent random walks on random environment[END_REF]) but its exact value has no importance here.

Proof. Recall the definition of r 1 in (1), for any > 0 and a > 0,

P max |u|≤ log n V (u) ≥ a log n ≤ j≤ log n E |v|=j 1 { V (v)≥a log n } ≤ j≤ log n E |v|=j e r1V (v)-r1a log n ≤ j≤ log n e -r1a log n+jψ(-r1) ≤ Ce -log n(r1a-ψ(-r1))
for some constant C > 0. Then choosing a large enough so that r 1 a > ψ(-r 1 ) and taking = δ/a, we obtain the bound for max V . For min V , the proof is the same except we work with t 0 instead of r 1 :

P min |u|≤ log n V (u) ≤ -a log n ≤ j≤ log n E |v|=j 1 { V (v)≤-a log n } ≤ j≤ log n E |v|=j e -t0V (v)-t0a log n ≤ j≤ log n e -t0a log n ≤ Cn -a t0 log n.
As the non-extinction probability is positive, there is a constant C > 0 such that for any n ≥ 1,

P * max |u|≤ log n |V (u)| ≥ δ log n ≤ CP max |u|≤ log n |V (u)| ≥ δ log n .
which concludes the proof.

The above lemma is used in the following section to obtain independence between the different branches of the tree. It will be used together with the following concentration lemma.

Lemma 2.4. Consider two integers and L and L + 1 sets A 1 ∈ B(R), . . . , A L+1 ∈ B(R L+1 ). Define, for any u ∈ T such that |u| = , the variable

Z u := u≤x,|x|≤L+ e -t0Vu(x) 1 { ( Vu(y), u≤y≤x )∈A |x|-+1 } .
There exists a constant a > 1 depending only on the reproduction distribution ν such that, for large enough,

P * |u|= Z u < E[ Z ] ≤ E Z 2 E[ Z ] 2 a - where Z = |x|≤L e -t0V (x) 1 { ( V (y), y≤x )∈A |x| } .
Proof. We first work with the conditional probability P(•|T ) so that random variables (Z n u , |u| = ) are independent and identically distributed as Z under P. Denote by D the number of vertices at generation . Tchebychev's inequality gives:

P |u|= Z u -D E[ Z ] > D 2 E[ Z ] T ≤ 4 D E Z 2 E[ Z ] 2 .
Now, we have to control D . In the Böttcher case, i.e. ν({ 0, 1 }) = 0, D ≥ 2 P * -a.s.(= P-a.s.) and the result of the lemma follows.

In the Schröder case, i.e. ν({ 0, 1 }) > 0, Corollary 5 in [START_REF] Fleischmann | On the left tail asymptotics for the limit law of a supercritical galton-watson processes in the bötcher case[END_REF] and Theorem 1 in [START_REF] Dubuc | La densité de la loi-limite d'un processus en cascade expansif[END_REF] (see also Theorem 4 in [START_REF] Biggins | Large deviations in the supercritical branching process[END_REF]) tell us that we can find two constants c 1 , c 2 > 1 such that for large enough, P * (D ≤ c 1 ) ≤ c - 2 . Therefore, in this case denoting by P ne > 0 the non-extinction probability

P * |u|= Z u < E[ Z ] ≤ P |u|= Z u < E[ Z ] , D > c 1 P ne + c - 2 ≤ E P |u|= Z u < D E[ Z ] /2 T 1 D >c 1 P ne + c - 2 ≤ 4 P ne E Z 2 E[ Z ] 2 c - 1 + c - 2 ≤ 4 P ne E Z 2 E[ Z ] 2 (c - 1 + c - 2 ),
and we only have to take a < c 1 ∧ c 2 to conclude the proof.

Number of vertices with low potential

Fix some constant c > 0. In this subsection we are interested in a lower bound for the random variable

|x|≤(log n) 3 1 { V (x)≤c log n } .
where V is defined in (11). It counts the number of sites x with generation smaller than (log n) 3 such that the potential in the path from the root to x remains below c log n. We will see in the next section that this random variable is naturally related to the heavy range. The proof we propose here is based on Lemma 2.3 which implies that the very first generations of the tree have no important impact on the value of V . This point can be used to obtain independence and then apply Lemma 2.4. Proposition 2.5. Assume A1. Let c > 0, For any δ ∈ (0, 1 ∧ c), there exists a > 0 such that for large n,

P * |x|≤(log n) 3 1 { V (x)≤c log n } ≤ n t0(c-δ) ≤ n -a .
Proof. We first use Lemma 2.3 to control V (u) on the very first generations of the tree: we can choose > 0 and b 1 > 0 such that for n large enough

P * A n ≤ n -b1 with A n := {max |u|= n V (u) < δ 4 log n} and n = log n .
The strategy is then similar for the different cases (depending on ψ), the only difference is the generation we have to work with. Let us take some constant B ≥ 0 and a sequence of integers ( n ) n∈N such that, for n large enough, n + n is smaller than (log n) 3 ; the exact choice of the sequence depends on ψ and will be explicitly given later. Consider now the collection of random variables:

∀n ≥ 1, ∀u ∈ T, Z n u := x≥u |x|= n+ n e -t0Vu(x) 1 { (c-δ/2) log n≤Vu(x),V u(x)≤(c-δ/4) log n, V u (x)≥-B } .
For n large enough, on the event A n ,

|x|≤(log n) 3 1 { V (x)≤c log n } ≥ |u|= n x≥u |x|= n + n 1 { V u (x)≤(c-δ/4) log n } ≥ n t0(c-δ/2) |u|= n Z n u .
Hence, concentration Lemma 2.4 implies that there exists a constant b 2 > 0 such that for n large enough,

P * |x|≤(log n) 3 1 { V (x)≤c log n } ≤ n t0(c-δ/2) E[ Z n ] ≤ E ( Z n ) 2 E[ Z n ] 2 n -b2 + P * A n (13)
where

∀n ≥ 1, Z n := |x|= n e -t0V (x) 1 { (c-δ/2) log n≤V (x),V (x)≤(c-δ/4) log n, V (x)≥-B } .
So we only have to control E[ Z n ] and E ( Z n ) 2 to prove the proposition.

• First for the mean E[ Z n ] the proof is different depending on the value of ψ (t 0 ): Case 1: ψ (t 0 ) < 0. Recall that in this case either t 0 = 1 and ψ(1) = inf s∈[0,1] ψ(s) = 0, or t 0 < 1 and inf s∈[0,1] ψ(s) < 0. We choose n = log n with = (c -3δ/8)/|ψ (t 0 )|. Many-to-one formula of Lemma 2.1 with t = t 0 gives

E[ Z n ] = P (c -δ/2) log n ≤ S n , S n ≤ (c -δ/4) log n, S n ≥ -B ≥ 1 -P( (c -δ/2) log n > S n ) -P S n > (c -δ/4) log n -P S n < -B .
For any B ≥ 0 and λ > 0 such that ψ(t 0 + λ) < 0, Markov inequality yields

P S n < -B ≤ k≤ n P( S k < -B ) ≤
k≤ n e -λB e ψ(t0+λ)k ≤ e -λB 1 -e ψ(t0+λ) , so taking B large enough, for any n, P(S n < -B) ≤ C < 1. And, as the process S is the sum of i.i.d. random variables with mean |ψ (t 0 )| and c -δ/2 < |ψ (t 0 )| < c -δ/4, using exponential Markov inequality we can also prove that for some constant b 3 > 0,

P( (c -δ/2) log n > S n ) ≤ n -b3 and P S n > (c -δ/4) log n ≤ n -b3 .
Combining these bounds, we obtain that for any n ≥ 1,

E[ Z n ] ≥ 1 C > 0 . ( 14
)
Case 2: ψ (t 0 ) = 0. In this case either t 0 < 1 or ψ(1) = ψ (1) = 0. We can basically use the same method as in the case ψ (t 0 ) < 0 except that important generations (see [START_REF] Andreoletti | Spread of visited sites of a random walk along the generations of a branching process[END_REF], [START_REF] Andreoletti | Range and critical generations of a random walk on Galton-Watson trees[END_REF]) are now the ones of the order (log n) 2 . So we take this time n = ( log n) 2 for some > 0 and we can choose B = 0. Many-to-one Lemma yields like above

E[ Z n ] = P (c -δ/2) log n ≤ S n , S n ≤ (c -δ/4) log n|S n ≥ 0 P S n ≥ 0 .
We know (see [START_REF] Aidékon | The seneta-heyde scaling for the branching random walk[END_REF], equation (2.8)) that the limit lim n→+∞ n 1/2 P(S n ≥ 0) = d > 0 exists, also by invariance principle (see [START_REF] Bolthausen | On a functional central limit theorem for random walks conditioned to stay positive[END_REF]),

lim n→∞ P (c -δ/2) log n ≤ S n , S n ≤ (c -δ/4) log n S n ≥ 0 = lim n→∞ P (c -δ/2)(σ ) -1 ≤ S n /σ n , S n /σ n ≤ (c -δ/4)(σ ) -1 S n ≥ 0 = P (c -δ/2)(σ ) -1 ≤ M, M ≤ (c -δ/4)(σ ) -1 ≥ 1 C > 0.
where M is the Brownian meander and σ 2 := Var(S 1 ) = E( |x|=1 V 2 (x)e -V (x) ) < +∞ by (1). So finally we obtain in this case: for n large enough,

E[ Z n ] ≥ 1 C log n . ( 15
)
• For E (Z n ) 2 , we first introduce the sequence of variables

∀k ∈ N, M k := |x|=|y|=k e -t0V (x)-t0V (y) 1 { V (x)∧V (y)≥-B } .
For any k ∈ N,

M k+1 ≤ |u|=|v|=k e -t0V (u)-t0V (v) 1 { V (u)∧V (v)≥-B } x s.t. x * =u y s.t.y * =v e -t0Vu(x)-t0Vv(y) = u =v |u|=|v|=k e -t0V (u)-t0V (v) 1 { V (u)∧V (v)≥-B } x s.t. x * =u y s.t.y * =v e -t0Vu(x)-t0Vv(y) + |u|=k e -2t0V (u) 1 { V (u)≥-B } x,y s.t. x * =y * =u e -t0Vu(x)-t0Vu(y) .
Then taking conditional expectation with respect to

E k := σ ( T k , (V (x), |x| ≤ k) ) , the above expression gives E[ M k+1 |E k ] ≤ M k E   |x|=1 e -t0V (x)   2 + |u|=k e -2t0V (u) 1 { V (u)≥-B } E   |x|=|y|=1 e -t0V (x)-t0V (y)   ≤ M k + C |u|=k e -t0V (u) .
Note that E |x|=|y|=1 e -t0V (x)-t0V (y) = E ( |x|=1 e -t0V (x) ) 2 is finite thanks to (2). And we get recursively, as

M 0 = 1, E[ M k+1 ] ≤ 1 + CE   |u|≤k e -t0V (u)   = 1 + C(k + 1).
This gives the bound for the second moment:

E (Z n ) 2 ≤ E[ M n ] ≤ C n .
Collecting this bound together with the one for E[ Z n ] in (13), this concludes the proof.

Lower and Upper bound for the heavy range of recurrent walks

In this section, we prove Theorems 1.1 and 1.3. We consider separately lower and upper bounds. The upper bounds are easier to obtain than the lower ones so they are treated for all cases at the beginning of this section in Proposition 3.1. For the lower bounds we treat separately the contribution coming from vertices with low potential in Proposition 3.3 and the contribution coming from vertices with high potential in Proposition 3.4. It turns out that for slow random walks, that is to say random walks with logarithmic behavior, the contribution coming from vertices with low potential is sufficient to obtain the asymptotics for the log-heavy range. Conversely, for fast but sub-diffusive cases, that is to say when 1 < κ < 2, then only vertices with high potential contribute. Finally for diffusive cases, that is to say for κ ≥ 2 then either vertices with low or high potential contribute depending on the value of θ.

Remind that P E x stands for the probability where the environment is fixed and the index x stands for the starting point of the random walk. To obtain the bounds, the following environment-related variable is essential:

∀x ∈ T, H x := y≤x e V (y)-V (x) . ( 16
)
Indeed the important quenched probabilities below are related to H x . For any x ∈ T, let T x := inf{k ≥ 0, X k = x} be the hitting time of vertex x. As the walk (X n ) n∈N is recurrent, the expressions of the probability of hitting x before e * starting from the root and the probability of hitting x before e * starting from x * are the same as for a one-dimensional walk: the restriction of (X n ) n∈N to the path e * , x . So a standard result for one-dimensional random walks in random environment (see [START_REF] Golosov | Localization of random walks in one-dimensional random environments[END_REF]) yields, for any x ∈ T,

a x := P E e (T x < T e * ) = 1/ z∈ e,x e V (z) = e -V (x) H x (17)
and

b x := P E x * (T x < T e * ) = z∈ e,x * e V (z) / z∈ e,x e V (z) = 1 - 1 H x . (18)

Upper bounds

The main results of this section is the following proposition, it gives the upper bounds for R T n n θ depending on the value of θ. The proof is quite short compared to the lower bounds and gives a good idea of what can be expected for the lower bounds.

Proposition 3.1. Assume A1 and fix θ ∈ [0, 1). For any δ > 0, there is a constant > 0 such that, for n large enough,

• in all cases but ψ(1) = 0 and ψ (1) < 0,

P R T n n θ > n t0(1-θ)+δ ≤ n -,
• if instead ψ(1) = 0 and ψ (1) < 0,

-if 1 < κ ≤ 2, P R T n n θ > n κ(1-θ)+δ ≤ n -, -if κ ∈ (2, ∞], P R T n n θ > n (2-κθ)∨(1-θ)+δ ≤ n -.
To prove the proposition, we have to control the largest generations visited by the walk before n returns to e * :

X * T n = max 0≤k≤T n |X k |.
The different behaviors of this random variable, which depend on ψ, have been studied in [START_REF] Hu | Slow movement of recurrent random walk in random environment on a regular tree[END_REF], [START_REF] Hu | A subdiffusive behavior of recurrent random walk in random environment on a regular tree[END_REF] and [START_REF] Faraud | Almost sure convergence for stochastically biased random walks on trees[END_REF]. In the following lemma we present a simpler version of their results adapted to our purpose: Lemma 3.2. If inf s∈[0,1] ψ(s) = 0 and ψ (1) ≥ 0 there exist B, b > 0 such that for n large enough,

P( X * T n ≥ L n ) ≤ n -b with L n = B(log n) 3 .
Otherwise if ψ (1) < 0 for any > 0, there exists b > 0 such that, for n large enough,

P( X * T n ≥ L n ) ≤ n -b with L n = n min(κ-1,1)+ .
Finally if inf s∈[0,1] ψ(s) < 0 there exist B > 0 and b > 0 such that for n large enough,

P( X * T n ≥ L n ) ≤ n -b with L n = B log n.
Proof. By the strong Markov property,

P E ( X * T n ≥ L n ) = 1 -1 -P E T |Ln| < T e * n where T |Ln|
is the hitting time of generation L n :

T |Ln| = inf { t ≥ 0 / ∃x ∈ T, |x| = L n and X t = x }
where inf ∅ = ∞. As for any x ∈ [0, 1], 1 -(1 -x) n ≤ nx, integrating the previous equality with respect to the distribution of E gives

P( X * T n > L n ) ≤ nP T |Ln| < T e * .
This probability has been intensively studied in [START_REF] Hu | Slow movement of recurrent random walk in random environment on a regular tree[END_REF], [START_REF] Hu | A subdiffusive behavior of recurrent random walk in random environment on a regular tree[END_REF], [START_REF] Faraud | Almost sure convergence for stochastically biased random walks on trees[END_REF] and [START_REF] Hu | Local times of subdiffusive biased walks on trees[END_REF]. More precisely, when inf s∈[0,1] ψ(s) = 0: if ψ (1) ≥ 0 then Equation (5.4) in [START_REF] Faraud | Almost sure convergence for stochastically biased random walks on trees[END_REF] gives, for B large enough, the existence of a constant c 1 > 1 such that lim sup

n→+∞ 1 log n log P T |Ln| < T e * ≤ -c 1 , (19)
If instead ψ (1) < 0 then Proposition 4.2 (ii and iii) in [START_REF] Hu | A subdiffusive behavior of recurrent random walk in random environment on a regular tree[END_REF] implies

lim sup n→+∞ 1 log n log P T |Ln| < T e * ≤ -1 -/2, (20)
(note that Proposition 4.2 is written for regular trees and the return time in e * is replaced by the return time in e but this does not change the normalization rate). Finally, if inf s∈[0,1] ψ(s) < 0, according to the proof of Theorem 1.1 in [START_REF] Hu | A subdiffusive behavior of recurrent random walk in random environment on a regular tree[END_REF], for B large enough there exists c 2 > 1 such that, lim sup

n→+∞ 1 log n log P T |Ln| < T e * ≤ -c 2 . ( 21
)
The different results of the lemma are now direct consequences of ( 19), ( 20) and (21).

We are now ready to prove the proposition.

Proof of Proposition 3.1. We first restrict the sum over the whole tree to the first L n generations where L n is the sequence introduced in Lemma 3.2 corresponding to the assumptions about ψ:

P R T n n θ > n t0(1-θ)+δ ≤ P( X * T n ≥ L n ) + n -t0(1-θ)-δ E |x|≤Ln P E N T n x ≥ n θ ( 22
)
where the second term in the above upper bound comes from Markov inequality. Thanks to Lemma 3.2, we only have to bound the last expectation

E |x|≤Ln P E (N T n x ≥ n θ ) .
The proof is different whether L n is a power of n or a power of log n. Case 1: L n is of the order (log n) p , p > 0. We split the sum into two terms depending on the value of V (x): define

Σ 1 := E |x|≤Ln P E (N T n x ≥ n θ )1 { V (x)≤(1-θ) log n } and Σ 2 := E |x|≤Ln P E (N T n x ≥ n θ )1 { V (x)>(1-θ) log n } .
For Σ 1 , we bound P E (N T n x ≥ n θ ) by 1 and use the many-to-one Formula, Lemma 2.1, with t = t 0 :

Σ 1 ≤ E |x|≤Ln 1 { V (x)≤(1-θ) log n } ≤ E |x|≤Ln e t0((1-θ) log n-V (x)) = n t0(1-θ) Ln i=0 E e t0(Si-Si) = n t0(1-θ) (L n + 1).
For Σ 2 , we first compute the expectation of N T n

x at fixed environment:

E E N T n x = n i=1 E E N T i x -N T i-1 x = nE E N T 1 x = n a x 1 -b x = ne -V (x) (23)
where a x and b x have been defined in ( 17) and ( 18). Now we can apply Markov inequality to P E (N T n x ≥ n θ ) and use many-to-one formula with t = t 0 ≤ 1:

Σ 2 ≤ n (1-θ) E |x|≤Ln e -V (x) 1 { V (x)>(1-θ) log n } ≤ n (1-θ) e (t0-1)(1-θ) log n E |x|≤Ln e -t0V (x) 1 { V (x)>(1-θ) log n } ≤ n t0(1-θ) (L n + 1).
Inserting the upper bounds of Σ 1 and Σ 2 in (22) concludes the proof in this first case.

Case 2: L n is of the order n min(κ-1,1)+ . Note that in this case, ψ satisfies inf s∈[0,1] ψ(s) = 0 with ψ (1) < 0, so t 0 = 1. We assume in the definition of L n that = δ/2 and take some real d > 0 which value will be fixed later. First we split the expectation E |x|≤Ln 1 { N T n x ≥n θ } into two parts Σ 1 and Σ 2 , depending on the values of V (x):

Σ 1 := E |x|≤Ln P E N T n x ≥ n θ 1 { V (x)≤d log n } and Σ 2 := E |x|≤Ln P E N T n x ≥ n θ 1 { V (x)>d log n } .
We first deal with Σ 1 . Equality (23), Markov inequality and many-to-one Formula, Lemma 2.1, with t = 1 yield

Σ 1 ≤ E |x|≤Ln ne -V (x) n -θ 1 { V (x)≤d log n } = n 1-θ Ln j=1 P S j ≤ d log n .
As ψ (1) < 0 we can choose a r > 0 in such way that ψ(1 + r) < 0. Let A > 0. When L n is larger than A log n, where we have used the equality E e -rS1 = e ψ(1+r) obtained from Lemma 2.1. So the last sum is smaller than e rd log n e Aψ(1+r) log n , and choosing A large enough, this converges to 0. Therefore when ψ (1) < 0, the following bound holds for some constant C > 0:

Σ 1 ≤ Cn 1-θ log n . (25)
We now have to deal with Σ 2 . For x ∈ T, consider E n x := n i=1 1 { ∃k∈[T i-1 ,T i ), X k =x } the number of excursions where x has been hit. We split once again Σ 2 into two other sums depending on the value of

E n x : Σ 2,1 = E |x|≤Ln 1 { N T n x ≥n θ } 1 { V (x)>d log n } 1 { E n x ≥2 } and Σ 2,2 = E |x|≤Ln 1 { N T n x ≥n θ } 1 { V (x)>d log n } 1 { E n x =1 } .
We first prove that, for d large enough, the walk will be able to reach a vertex x satisfying V (x) > d log n during a unique excursion [T i-1 , T i ). Under P E , E n x follows the binomial distribution B(n, a x ), thus

P E ( E n x ≥ 2 ) ≤ E E [ E n x ] -P E ( E n x = 1 ) = na x (1 -(1 -a x ) n-1 ) ≤ n 2 a 2
x ≤ n 2 e -2V (x) and many-to-one Formula yields

Σ 2,1 ≤ n 2 Ln j=1 E e Sj -2Sj 1 { Sj >d log n } ≤ L n n 2-d ≤ 1 (26)
for d large enough. For Σ 2,2 , we first notice that

P E N T n x ≥ n θ , E n x = 1 = n i=1 P E (N T i x -N T i-1 x ≥ n θ , ∀j = i, N (j)
x -N (j-1) x = 0).

In particular, P E (N T n x ≥ n θ , E n x = 1) ≤ na x (b x ) n θ and thanks to many-to-one Formula, we get

Σ 2,2 ≤ nE |x|≤Ln a x (b x ) n θ 1 { V (x)>d log n } ≤ n Ln j=1 E 1 H S j 1 - 1 H S j n θ
where H S j = j m=1 e Sm-Sj is the random variable defined in Lemma 2.2. Now remark that if

H S j ≤ n θ /(3 log n), then 1 -1/H S j n θ ≤ 1/n 3 and so Ln j=1 E 1 H S j 1 - 1 H S j n θ 1 { H S j ≤n θ /(3 log n) } ≤ L n /n 3
and according to Lemma 2.2,

E 1 H S j 1 - 1 H S j n θ 1 { H S j >n θ /3 log n) } ≤ 3 log n n θ P H S j > n θ 3 log n ≤ C (log n) κ n κθ . Finally, Σ 2,2 ≤ C(log n) κ L n n 1-κθ . ( 27
)
The bounds obtained for Σ 1 , Σ 2,1 and Σ 2,2 in (25), ( 26) and ( 27) give the result in this second case.

Lower bounds

In this section, we prove two propositions: the first one gives a lower bound for the heavy range R T n n θ for any cases but is only optimal for the slowest cases, that is to say for random walks with logarithmic behavior. This first proposition is obtained by considering vertices with low potential (see definition of set A n below). The second one, Proposition 3.4, which is more technical to obtain, deals only with the fast cases, that is to say when ψ(1) = 0 and ψ (1) < 0 and focuses on vertices with high potential.

Proposition 3.3. Assume A1 and fix θ ∈ [0, 1). For any 0 < δ < t 0 (1 -θ), there exists a constant > 0 such that for n large enough,

P * |x|≤(log n) 3 1 { N T n x ≥n θ } < n t0(1-θ)-δ ≤ n -.
Remark that the upper bound for R T n n θ given in Proposition 3.1 for the case inf s∈[0,1] ψ(s) = 0 and ψ (1) < 0 can be larger than the lower bound obtained in the above proposition. This means that we ignore vertices with high potential that are of great importance in this case. They are treated in Proposition 3.4.

Proof. Consider the subset

∀n ≥ 1, A n := x ∈ T, V (x) ≤ (1 -θ -δ) log n, and |x| ≤ (log n) 3 .
Let us assume for the moment that for n large enough,

P x∈An 1 { N T n x <n θ } ≥ 1 ≤ e -n θ , ( 28
) then P |x|≤(log n) 3 1 { N T n x ≥n θ } < n t0(1-θ)-δ ≤ P |A n | < n t0(1-θ)-δ + e -n θ
and the control on the cardinal of A n given in Proposition 2.5, taking c = 1 -θ -δ, concludes the proof the proposition. So let us now prove (28). Fix an environment E = (T, ω) and consider a vertex x ∈ T. By the strong Markov property, the sequence (N T i

x -N T i-1

x , i ≥ 1) is, under P E = P E e , an i.i.d. sequence with law given by N T 1

x (remark that N (0)

x = 0). Applying exponential Markov inequality, we have for any η > 0 and α > 0,

P E N T n x ≤ α = P n i=1 [N T i x -N T i-1 x ] < α = P E e -η n i=1 [N T i x -N T i-1 x ] > e -ηα ≤ exp ηα + n log E E e -ηN T 1 x ) . ( 29
)
It is easy to see, by the strong Markov property, that the distribution of

N T 1 x under P E x is geometrical with parameter 1 -b x , so that log E E exp(-ηN T 1 x ) = log (1 -a x ) + a x E E x exp(-ηN T 1 x ) = log ( 1 -a x + a x (1 -b x )/(e η -b x ) ) ≤ -a x + a x (1 -b x )/(1 + η -b x ) .
Then coming back to (29) with η = (1 -b x ), we obtain

P E N T n x ≤ α ≤ exp - na x 2 + (1 -b x )α . ( 30
)
The equations of a x and b x given in ( 17) and ( 18) imply that a x /(1 -b x ) = e -V (x) . Together with (30), this gives

P E N T n x ≤ α ≤ e -ax 2 ( n-e V (x) α ) .
As for any x ∈ A n , e -V (x) ≥ n -(1-θ-δ) and a x ≥ 1/(n 1-θ-δ (log n) 3 ), the above inequality implies that

P E x∈An 1 { N T n x <n θ } ≥ 1 ≤ x∈An P E N T n x ≤ n 1-δ e -V (x) ≤ |A n |e -n θ+δ (1-n -δ )/(log n) 3 .
Integrating with respect to the distribution of E, we obtain for n large enough:

P x∈An 1 { N T n x <n θ } ≥ 1 ≤ CE[ |A n | ] e -n θ+δ/2 .
Then we only need an appropriate upper bound for E[ |A n | ] to complete the proof. This is a direct consequence of many-to-one Formula. Indeed, taking t = t 0 in Lemma 2.1, we get

E[ |A n | ] =E |x|≤(log n) 3 1 { V (x)≤(1-θ-δ) log n } = (log n) 3 k=1 E e t0S k +kψ(t0) 1 { S k ≤(1-θ-δ) log n } ≤ (log n) 3 n t0(1-θ-δ) .
The following proposition deals with the rapid cases (ψ(1) = 0, ψ (1) < 0): we treat the vertices with large potential left aside in the previous proposition. Quite technical, the proof is decomposed in essentially four Lemmata. Proposition 3.4. Assume A1 and suppose we are in the case

inf s∈[0,1] ψ(s) = ψ(1) = 0 , ψ (1) < 0 and κ = inf { s > 1, ψ(s) = 0 } < ∞ . Define ζ := (κ -1) -1 ∧ 1 and consider a real θ ∈ [0, ζ). For any constant 0 < δ < (κ -1)(ζ -θ),
there exists a positive number such that for n large enough,

P * R T n n θ ≤ n 2∧κ-κθ-δ ≤ n -.
In the sequel it is enough to consider generations slightly smaller than typical visited generations for this cases (that is n (κ-1)∧1 , as recalled in Lemma 3.2), so we define

L δ n := n (κ-1)∧1-δ/2 = n (κ-1)ζ-δ/2 .

First let us introduce the set Γ

n = Γ 1 n ∩ Γ 2 n where Γ 1 n = x ∈ T / n θ ≤ H x ≤ n θ+δ/16 , V (x) ≥ 4 log n and Γ 2 n = x ∈ T / z≤x H z ≤ n 1-7δ/16 and ∀z ≤ x, H z ≤ n ζ ,
with H x given in (16). The set Γ n contains the vertices which are the main contributors to the heavy range. Remark that, when κ ≤ 2, the condition ∀z ≤ x, H z ≤ n ζ is implied by the condition on the sum z≤x H z and is therefore useless in this case.

The set Γ n is such that the walk visits most of these vertices more than n θ times with a large probability. Then, as

R T n n θ ≥ |x|≤L δ n 1 { N T n x ≥n θ } 1 { x∈Γn } ,
we only have to obtain a lower bound for the above sum. We first prove in the following lemma that, with a large probability, the walk reaches a given vertex of Γ n during a single excursion [T i-1 , T i ).

Lemma 3.5. For any x ∈ T, recall

E n x := n i=1 1 { ∃k∈[T i-1 ,T i ), X k =x }
the number of excursions where the walk hits vertex x. Then, for n large enough,

P |x|≤L δ n 1 { E n x ≥2 } 1 { x∈Γn } ≥ 1 ≤ n -1 .
Proof. Under P E , E n x follows the binomial distribution B(n, a x ) = B(n, e -V (x) /H x ) so

P E ( E n x ≥ 2 ) ≤ E E [ E n x ] -P E ( E n x = 1 ) = na x (1 -(1 -a x ) n-1 ) ≤ n 2 a 2 x . Moreover, for x ∈ Γ n , n 2 a 2 x = n 2 e -2V (x) H -2 x ≤ n -2 e -V (x) and E |x|≤L δ n P E ( E n x ≥ 2 ) 1 { x∈Γn } ≤ n -2 E |x|≤L δ n e -V (x) ≤ n -2 L δ n ≤ n -1 .
And Markov inequality gives the result of the lemma.

Previous lemma shows that there is independence between the contributions of the different excursions. This is an important fact to obtain the lower bound in Lemma 3.7. We also need a control on the mean E E N T 1

x N T 1 y given in Lemma 3.6 below; this result is similar to Lemma 5.2 in [START_REF] Hu | The slow regime of randomly biased walks on trees[END_REF], but we give here a short proof for completeness. Lemma 3.6. For any x, y ∈ T,

if x ≤ y, E E N T 1 x N T 1 y = e -V (y) ( 2H x -1 ) (31) else E E N T 1 x N T 1 y = 2e -V (x)-V (y)+V (x∧y) H x∧y . ( 32
)
Proof. A direct calculation leads to (31) when x = y. We proceed by induction on the generations for the general case. The result is obvious for x = y = e. Suppose now that Equations ( 31

σ-algebra G m = σ E, (N T 1 x , |x| ≤ m) . Given G m , N T 1 y follows the negative binomial distribution BN (N T 1 y * , 1/(1 + e -(V (y)-V (y * ))
)). Then,

E E N T 1 x N T 1 y F m = N T 1 x N T 1 y * e -(V (y)-V (y * )) .
Taking the expectation leads to (31). Finally, if |x| = |y| = m + 1, same kinds of arguments show that

E E N T 1 x N T 1 y F m = N T 1 x * N T 1 y * e -(V (x)-V (x * ))-(V (y)-V (y * )) ,
if x * = y * and otherwise

E E N T 1 x N T 1 y F m = N T 1 x * (N T 1 x * + 1)e -(V (x)-V (x * ))-(V (y)-V (y * ))
and the result follows.

Lemma 3.7. There is a constant C such that for n large enough,

P E   n i=1 |x|≤L δ n 1 { N T i x -N T i-1 x ≥n θ } 1 { x∈Γn } ≤ n 1-θ-δ/8 |x|≤L δ n e -V (x) 1 { x∈Γn }   ≤ C n 1-δ/8 |x|,|y|≤L δ n H x∧y e -V (x)-V (y)+V (x∧y) 1 { x,y∈Γn } |x|≤L δ n e -V (x) 1 { x∈Γn } 2 , P-a.s.
Proof. As the excursions are i.i.d. under P E , we first use Tchebytchev inequality with probability measure P E to obtain:

P E   n i=1 |x|≤L δ n 1 { N T i x -N T i-1 x ≥n θ } 1 { x∈Γn } ≤ n 2 |x|≤L δ n P E N T 1 x ≥ n θ 1 { x∈Γn }   ≤ 4 n |x|,|y|≤L δ n P E N T 1 x ∧ N T 1 y ≥ n θ 1 { x,y∈Γn } |x|≤L δ n P E N T 1 x ≥ n θ 1 { x∈Γn } 2 , (33)
where the numerator comes from the computation of the variance at fixed environment:

Var E n i=1 |x|≤L δ n 1 { N T i x -N T i-1 x ≥n θ } 1 { x∈Γn } = nVar E |x|≤L δ n 1 { N T 1 x ≥n θ } 1 { x∈Γn } ≤ n |x|,|y|≤L δ n P E N T 1 x ∧ N T 1 y ≥ n θ 1 { x,y∈Γn } .
Remark now that for any x ∈ T, P E (N T 1 x ≥ n θ ) = a x (b x ) n θ , with a x and b x given in respectively (17) and (18) (and n θ stands for the smallest integer larger than n θ ). As for x ∈ Γ n , H x ∈ [n θ , n θ+δ/16 ], there is a constant C such that for any n ≥ 1,

|x|≤L δ n P E (N T 1 x ≥ n θ )1 { x∈Γn } ≥ C n θ+δ/16 |x|≤L δ n e -V (x) 1 { x∈Γn } . (34)
To bound the numerator in (33), we use Markov-type inequality:

|x|,|y|≤L δ n P E N T 1 x ∧ N T 1 y ≥ n θ 1 { x,y∈Γn } ≤ 1 n 2θ x,y≤L δ n E E N T 1 x N T 1 y 1 { x,y∈Γn } ≤ 2 n 2θ |x|,|y|≤L δ n e -V (x)-V (y)+V (x∧y) H x∧y 1 { x,y∈Γn } .
The last bound of the previous equation is obtained by the control of

E E N T 1 x N T 1 y
given in Lemma 3.6. The next step is to control the numerator and the denominator of the bound obtained in the previous Lemma. We start with the easiest part, the upper bound for the mean of the numerator. Lemma 3.8. For n large enough,

G n := E |x|,|y|≤L δ n H x∧y e -V (x)-V (y)+V (x∧y) 1 { x,y∈Γn } ≤ Cn 1+2(κ-1)(ζ-θ)-23δ/16 .
Proof. Remark first that G n can be written in the following way

G n = L δ n i=1 E |u|=i e -V (u) H u 1 { u∈Γn } + v =ṽ v * =ṽ * =u e -Vu(v)-Vu(ṽ) x≥v |x|≤L δ n y≥ṽ |y|≤L δ n e -Vv(x) e -Vṽ(y) 1 { x,y∈Γn }
where we recall that for any z ≥ w, V w (z) = V (z) -V (w) is the potential centered at w. Furthermore, for any x ∈ Γ n and any ancestor v ≤ x, the variable H x can be decomposed as follows

H x = e -Vv(x) H v + v<z≤x e Vv(z)-Vv(x) ≤ e -Vv(x) n ζ + H (v)
x where H (v)

x = v≤z≤x e Vv(z)-Vv(x) . Now remark that, for u < v ≤ x and u < ṽ ≤ y,

{ u ∈ Γ n } ⊂B u and { x, y ∈ Γ n } ⊂ A x ∩ A y ∩ B u where A x := {n θ ≤ e -Vv(x) n ζ + H (v) x }, A y := {n θ ≤ e -Vṽ(y) n ζ + H (ṽ) y } and B u := z≤u H z ≤ n 1-7δ/16 . So |u|=i e -V (u) H u 1 { u∈Γn } + v =ṽ v * =ṽ * =u e -Vu(v)-Vu(ṽ) x≥v |x|≤L δ n y≥ṽ |y|≤L δ n e -Vv(x) e -Vṽ(y) 1 { x,y∈Γn } ≤ |u|=i e -V (u) H u 1 Bu 1 + v =ṽ v * =ṽ * =u e -Vu(v)-Vu(ṽ) x≥v |x|≤L δ n e -Vv(x) 1 Ax y≥ṽ |y|≤L δ n e -Vṽ(y) 1 Ay .
The variables H (v) x and V v (x) depend only on the potential centered at v and are independent of the other branches and of the potential of the vertices before v. The same is true for H (ṽ) y and V ṽ (y). Therefore, conditioning to variables up to generation i and using many-to-one Formula of Lemma 2.1 with t = 1, we obtain

G n ≤ L δ n i=1 E H S i 1 { j≤i H S j ≤n 1-7δ/16 } 1 + E v =ṽ v * =ṽ * =e e -V (v)-V (ṽ) L δ n -i-1 k=0 φ k,ζ 2 (35)
where for any integer k > 0 and any b > θ, φ k,b := P e -S k n b + H S k > n θ . The upper bound of φ k,b will be used several times in the sequel so we start by giving a general estimation. First, φ k,b ≤ P e -S k n b > n θ /2 + P H S k > n θ /2 . According to Lemma 2.2, there is a constant C > 0 such that for any n large enough, P H S k > n θ /2 ≤ Cn -(κ-1)θ . And, by Markov inequality, for any 0 < δ < (κ -1)(b -θ),

P e -S k > 1 2n b-θ ≤ Cn (κ-1)(b-θ)-δ/2 E e -(κ-1-δ 2(b-θ) )S k = Ce kψ(κ-δ 2(b-θ) ) n (κ-1)(b-θ)-δ/2 .
Therefore, as ψ κ -δ 2(b-θ) < 0, there exists d > 0 such that

φ k,b ≤ C(n -(κ-1)θ + e -dk n (κ-1)(b-θ)-δ/2 ). ( 36
)
Then applying this inequality in our case that is to say when b = ζ, this gives, as

L δ n = n (κ-1)ζ-δ/2 , for n large enough, ∀i < L δ n , L δ n -i-1 k=0 φ k,ζ ≤ Cn (κ-1)(ζ-θ)-δ/2 .
Moreover, by Assumption (2), E v =ṽ,|v * |=|ṽ * |=1 e -V (v)-V (ṽ) is finite. Hence, to conclude the proof of the lemma, we only have to remark that

L δ n i=1 H S i 1 { j≤i H S j ≤n 1-7δ/16 } ≤ n 1-7δ/16
. Indeed we add terms to the sum only while the sum stays smaller than n 1-7δ/16 so the final result has to be smaller too.

In the following lemma, we focus on the lower bound for the denominator in Lemma 3.7. Note that we also need a technical estimates which are gathered in Lemma 3.10. Its proof is postponed at the end of this section. Lemma 3.9. There is a constant > 0, such that for n large enough,

P * |x|≤L δ n e -V (x) 1 { x∈Γn } < n (κ-1)(ζ-θ)-5δ/8 ≤ n -.
Proof. We use the same strategy as in the proof of Proposition 2.5: we cut the tree at an early generation to obtain independence and then use concentration Lemma 2.4. We first use Lemma 2.3 to control V (u) on the very first generations of the tree: there exist b, > 0 such that P * A n ≤ n -b where A n = ∀u ∈ T n , |V (u)| ≤ δ 8 log n and n = log n . So for n large enough, on the event

A n , ∀u ∈ T n , H u ≤ n 2δ/8 n ≤ n 3δ/8 and ∀u ≤ x, H (u) x ≤ H x ≤ H (u)
x + e -Vu(x) n 3δ/8 .

Recall that for any u ≤ x, V u (x) = V (x) -V (u) and H

= u≤y≤x e Vu(y)-Vu(x) . Fix now some constant B > 0 and consider the collection of random variables :

∀n ≥ 1, ∀u ∈ T, Z n u = x>u |x|≤L δ n e -Vu(x) 1 { x∈Γn,u } , with Γ n,u = Γ 1 n,u ∩ Γ 2 n,u
where the Γ i n,u are the following new sets of constraints on the environment

Γ 1 n,u = x ∈ T / n θ ≤ H u x ≤ n θ+δ/16 /2, V u (x) ≥ 2 log n and Γ 2 n,u = x ∈ T / z≤x H u z ≤ n 1-3δ/8 /2 and ∀u ≤ z ≤ x, V u (z) ≥ -B and H u z ≤ n ζ /2 .
The definitions of Γ n , Γ n,u and inequalities in (37) imply that on A n ,

|x|≤L δ n e -V (x) 1 { x∈Γn } ≥ n -δ/8 |u|= n Z n u ,
so concentration Lemma 2.4 shows that, for some > 0 and n large enough

P * |x|≤L δ n e -V (x) 1 { x∈Γn } ≤ n -δ/8 E[ Z n ] ≤ 8 E ( Z n ) 2 E[ Z n ] 2 n -+ P * (A n ), (38)
where

Z n = |x|≤L δ n -n e -V (x) 1 { x∈Γn,e } . The next step is to control E[ Z n ] and E ( Z n ) 2 .
• A lower bound for the mean E[ Z n ]. Lemma 2.1 with t = 1, gives :

E[ Z n ] = L δ n -n i=0 P n θ ≤ H S i ≤ n θ+δ/8 /2, S i ≥ 2 log n, j≤i H S j ≤ n 1-3δ/8 /2, H S i ≤ n ζ /2, S i ≥ -B ≥ L δ n -n i= d log n P n θ ≤ H S i - 5 m=1 p m,i ,
where r n := max j≤n r j and r n := min j≤n r j for any sequence (r n ) n∈N and d is a constant which can be chosen as large as needed. The probabilities

p 1,i := P( S i < 2 log n ) , p 2,i := P n θ+δ/16 /2 ≤ H S i , p 3,i := P n θ ≤ H S i , S i < -B p 4,i := P n θ ≤ H S i ≤ n θ+δ , H S i > n ζ /2 and p 5,i := P n θ ≤ H S i , j≤i H S j ≥ n 1-3δ/8 /2
are estimated in the following technical lemma which proof can be found at the end of the section.

Lemma 3.10. If we choose d large enough, there is a constant C > 0 such that for n large enough and any i ∈ { d log n, . . . , n }, p 1,i ≤ n -2(κ-1)θ , p 2,i ≤ Cn -(κ-1)(θ+δ/16) , p 3,i ≤ Ce -((κ-1)ζ-δ)B n -(κ-1)θ , p 4,i ≤ Cn -(κ-1)θ-δ/16) and p 5,i ≤ Cn -(κ-1)θ-δ/16) .

Collecting the different upper bounds given in the previous lemma, we obtain for large n,

5 m=1 p m,i ≤ Cn -(κ-1)θ n -δ/16 + e -λB .
Therefore for B and n large enough,

E[ Z n ] ≥ L δ n -n i= d log n P n θ ≤ H S i - 5 m=1 p m,i ≥ CL δ n n -(κ-1)θ = Cn (κ-1)(ζ-θ)-δ/2 .
• An upper bound for E (Z n ) 2 . We barely use the same arguments as in the proof of Lemma 3.8: first E (Z n ) 2 can be written as

L δ n i=1 E |u|=i e -2V (u) 1 { u∈Γn } + v =ṽ v * =ṽ * =u e -Vu(v)-Vu(ṽ)
x≥v y≥ṽ e -Vv(x) e -Vṽ(y) 1 { x,y∈Γn } .

Then in the same way as we have obtained (35) we get

E (Z n ) 2 ≤ L δ n i=1 E e -Si 1 { Si≥-B } 1 + E v =ṽ v * =ṽ * =e e -V (v)-V (ṽ) L δ n -i-1 k=0 φ k,ζ 2
and same arguments as in the proof of Proposition 3.8 (see Equation (36) and below) show that

E (Z n ) 2 ≤ Cn 2(κ-1)(ζ-θ)-δ L δ n i=1 E e -Si 1 { Si≥-B } .
All that is left to do is to control the first part of the sum, again by a Markov inequality: as

ψ(2 ∧ κ -δ) < 0, L δ n i=1 E e -Si 1 { Si≥-B } ≤ e B L δ n i=1 E e -(1∧(κ-1)-δ)Si ≤ e B ∞ i=1 e iψ(2∧κ-δ)) < ∞ and finally E (Z n ) 2 ≤ Cn 2(κ-1)(ζ-θ)-δ . The bounds obtained for E[ Z n ], E (Z n ) 2
and Inequality (38) conclude the proof.

We are now ready to prove the main result of this section, Proposition 3.4.

Proof of Proposition 3.4. We only have to collect all the previous results. Thanks to Lemma 3.5 we can separate the excursions and, as κ ∧ 2 -κθ = 1 -θ + (κ -1)(ζ -θ), thanks to Lemma 3.9 we can introduce the variable Σ n := |x|≤L δ n e -V (x) 1 { x∈Γn } . So these two Lemmata imply

P * R T n n θ ≤ n κ∧2-κθ-δ ≤ n -1 + n - + P * n i=1 |x|≤L δ n 1 { N T i x -N T i-1 x ≥n θ } 1 { x∈Γn } ≤ n 1-θ-3δ/8 Σ n , Σ n ≥ n (κ-1)(ζ-θ)-5δ/8
for some constant > 0. Using now the quenched concentration Lemma 3.7, as the non-extinction probability is positive, the probability of the right-hand side of the previous equation can be bounded by

C n 1-δ/8 E   Σ n -2 |x|,|y|≤L δ n H x∧y e -V (x)-V (y)+V (x∧y)1 { x,y∈Γn } 1 { Σn≥n (κ-1)(ζ-θ)-5δ/8 }   ≤Cn -1-2(κ-1)(ζ-θ)-11δ/8 G n .
Finally, the bound of G n given in Lemma 3.8 shows that

P * R T n n θ ≤ n κ∧2-κθ-δ ≤ 1 n + 1 n + 1 n δ/16 .
This concludes the proof of the proposition.

We finish the section by the proof of Lemma 3.10 which is essentially based on simple estimates for sums of i.i.d. random variables.

Proof of Lemma 3.10. The probability p 1,i has already been bounded in this paper, see (24): as i ≥ d log n , p 1,i ≤ n -D with D as large as needed if d is large enough. The bound for p 2,i is given in Lemma 2.2.

For the other p .,i we need some more work. At the end, the calculus for p 3,i , p 4,i and p 5,i are very similar so we give the details for p 5,i and then sketch the proofs for p 3,i and p 4,i .

Fix some A > 0 and let i n = max(0, i -A log n ). Then H S i = H S in e -Si n,i + H S in,i where for k ≤ , S k, = S -S k and H S k, := j=k+1 e S k,j -S k, .

Note that H S in is independent of (S in,i , H S in,i ). First, we have that p 5,i is smaller than

P H n,i ≥ n θ , j≤in H S j ≥ n 1-3δ/8 /4, H S in ≤ n 2 + P H S in ≥ n 2 + P in<j≤i H S j ≥ n 1-3δ/8 /4
with H n,i := n 2 e -Si n ,i + H S in,i . By independence, the first term above is smaller than

P H n,i ≥ n θ P j≤in H S j ≥ n 1-3δ/8 /4 .
As H n,i has the same distribution as the random variable n 2 e -Si-i n +H S i-in , then P H n,i ≥ n θ = φ i-in,2 where φ k,b was previously defined and estimated in (36). So for A large enough

P H n,i ≥ n θ ≤ Cn -θ(κ-1) .
Moreover, as ζ ≤ 1, E H S j (κ-1)ζ-δ/16 is bounded and as (κ -1)ζ ≤ 1,

E j≤in H S j (κ-1)ζ-δ/16 ≤ j≤in E H S j (κ-1)ζ-δ/16 ≤ CL δ n .
Markov inequality yields, for any i ≤ L δ n , P j≤in H S j ≥ n 1-3δ/8 /4 ≤ CL δ n n -((κ-1)ζ-δ/16)(1-3δ/8) ≤ Cn -δ/16 .

Similarly P in<j≤i H S j ≥ n 1-3δ/8 /4 ≤ Cn -((κ-1)ζ-δ/16)(1-3δ/8) log n and finally by Lemma 2.2, P H S in ≥ n 2 ≤ Cn -2(κ-1) . As ζ > θ, for δ small enough, this yields

p 5,i ≤ Cn -(κ-1)θ-δ/16 .
Same kind of arguments give the same bound for p 4,i . Finally, for p 3,i , with the same decomposition as above we can write

p 3,i ≤ P H n,i ≥ n θ , S in < -B + P H S in ≥ n 2 + P min in≤k≤i S k ≤ -B
and by independence, P H n,i ≥ n θ , S in < -B = P H n,i ≥ n θ P S in < -B . Let λ = (κ -1)ζ -δ. As ψ(1 + λ) < 0, for any 0 ≤ l < i, P min l≤k≤i S k ≤ -B ≤ e -λB e ψ(1+λ)l 1 -e ψ(1+λ) then p 3,i ≤ C e -λB n -(κ-1)θ + n -2λ + e ψ(1+λ)A log n ≤ Ce -λB n -(κ-1)θ .

Proof of Theorem 1.3

This Theorem is a direct consequence of Theorem 1.1 and of Remark 1.2, we only give a proof for the case inf s∈[0,1] ψ(s) = 0 with ψ (1) < 0 and κ ∈ (2, ∞] for θ > 0 such that 1 -κθ > 1/2 -θ.

According to Remark 1.2, for any > 0,

lim n→∞ P * T n (1+ )/2 ≥ n = 1. ( 39
)
Then fix some > 0 and denote θ = 2θ/(1 + ). Suppose that is small enough to have 2 -κθ ≥ 1 -θ . For n ≥ 2,

P * log + R n n θ log n ≥ 1 -κθ + 2 ≤ P *   log + R T n (1+ )/2 n θ log n ≥ 1 -κθ + 2   + P * T n (1+ )/2 < n .
Then, as θ = 1+ 2 θ ,

P *   log + R T n (1+ )/2 n θ log n ≥ 1 -κθ + 2   = P *    log + R T n (1+ )/2 ( n (1+ )/2 ) θ log n (1+ )/2 ≥ 2(1 -κ((1 + )/2)θ + 2 ) 1 +    ≤ P *   log + R T n (1+ )/2 n (1+ )/2 θ log n (1+ )/2 ≥ 2 -κθ + 2 1 +   .
Then (39) and Theorem 1.1 show that for any small enough,

lim n→∞ P * log + R n n θ log n ≥ (1 -κθ + 2 ) = 0 .
The lower bound and the other cases can be obtained with similar arguments.

4. Estimation of the c.d.f.

In this section we prove Theorem 1.7 and Theorem 1.5. For that purpose, we use the same global strategy as in [START_REF] Diel | Non parametric estimation for random walks in random environment[END_REF], that is to say we begin by estimating the moments of ρ (defined in (9)) and we use these estimators to build a family of estimators F α n of the c.d.f. We finally choose an estimator of the family which minimizes the risk bound. The important difference comparing to [START_REF] Diel | Non parametric estimation for random walks in random environment[END_REF] is that in our case the state space is now a Galton-Watson tree instead of Z. Recall that in this part, we assume not only A1 but also A2:

• the reproduction law of the Galton-Watson is bounded: ∃K > 0, P( ν ≤ K ) = 1 .

• given the tree up to generation n and the number of children ν x of some x ∈ T such that |x| = n, the variables ( ω xi ) 1≤i≤νx are i.i.d. with the same distribution as some variable ω.

Estimation of the moments of ρ

First remark that the marked tree (x ∈ T, N T n x ) is a sufficient statistic for the trajectory ( X t ) t∈[0,T n ] . Indeed for any admissible sequence ( a k ) k∈{ 0,...,t n) } , the likelihood is

P X 0 = a 0 , . . . , X T n = a t (n) T = x∈T E 1 1 + νx i=1 e -ωx i n (n) x νx i=1 e -ωx i 1 + νx i=1 e -ωx i n (n) x i T where n (n) x := t (n) k=1 1 { a k-1 =x * , a k =x } .
It is then natural to construct our estimator using these random variables. A second important point is that, for a fixed environment and tree, that is to say under

P E , ∀x ∈ T, P E N T n x = j N T n y |y|<|x| = N T n x * + j -1 j ρ i x (1 -ρ x ) j
where ρ x = ( 1 + e -ωx ) -1 . So the moments of ρ are convenient quantities to estimate and we first focus on them. The estimator of m α,β = E ρ α (1 -ρ) β is constructed following the same strategy as in [START_REF] Diel | Non parametric estimation for random walks in random environment[END_REF]. is based on the simple combinatoric equality:

∀i ≥ α, j≥β i -α + j -β i -α a i+1 (1 -a) j = a α (1 -a) β . (40)
Indeed, denoting for any integers α, β, i, j ≥ 0,

Φ α,β (i, j) = 1 { i≥α+1,j≥β } i+j-(α+1+β) i-(α+1) i+j-1 j , (41)
we have for any x ∈ T,

E E Φ α,β (N T n x * , N T n x ) N T n y , |y| < |x| = j≥β Φ α,β (N T n x * , j)P E N T n x = j N T n y , |y| < |x| =1 { N T n x * ≥α+1 } ρ α x (1 -ρ x ) β .
It is then natural to estimate the moments m α,β of ρ with the following random variable:

m α,β n = 1 E[ ν ] R T n α+1 x∈T y,s.t. y * =x Φ α,β (N T n x , N T n y )
where we use the convention: 0/0 = 0. Remark that the series here are in fact simple sums as only a finite number of N T n x are non zero. These estimators satisfy a concentration property:

Proposition 4.1. Assume A1 and A2 and fix α, β ∈ Z + . There is a positive constant C, such that for any integer n ≥ 0 and any real number z > 0,

P m α,β n -m α,β ≥ α!β! (α + β)! K E[ ν ] z + 2 log R T n α+1 2R T n α+1 ≤ Ce -z .
Proof. We consider the following construction of the Galton-Watson tree T. Define a sequence of i.i.d.r.v. (ν k ) k∈N distributed as ν.

We introduce the sequence (y k ) k∈N * to designate the vertices of the tree T ∪ { e * } in level order, generation by generation. We start with y 0 = e * , y 1 = e which has ν 1 children. These children are ordered arbitrarily, the first vertex is called y 2 and has ν 2 children, the second one y 3 with ν 3 children and so on. Once no more vertices are present at this generation, we move to the next one and so on (see Figure 3). The sequence can be finite with last element y Nmax . In this case, we start

m α,β n = 1 E[ ν ] R T n α+1 ∞ k=1 y,s.t. y * =y k Φ α,β (N T n y k , N T n y ) .
Denote by (F k ) k∈N the following filtration: F 0 = σ N T n e and for k ≥ 0,

F k+1 = σ F k , σ ν k+1 , (N T n y , y * = y k+1 ) . (42)
In the following lemma we introduce a martingale which is the main tool to obtain Proposition 4.1. Lemma 4.2. Let α, β ∈ Z + . For probability measure P, the sequence Z α,β k k≥0

defined, for all integer k ≥ 0, by

Z α,β 0 = 0 and ∀k ≥ 1, Z α,β k = 1 { N T n y k ≥α+1 } y,y * =y k Φ α,β N T n y k , N T n y -E[ ν ] m α,β
is a martingale difference sequence with respect to ( F k ) k∈N .

Proof. First recall the following result which is a slight variation of Lemma 3.1 in [START_REF] Aïdékon | Scaling limit of the recurrent biased random walk on a galton-watson tree[END_REF]. It can be proved using the same arguments: for any n ≥ 1, under P the marked tree x ∈ T, N T n x is a multi-type Galton-Watson tree. Its initial type is n and its mean matrix is given by: ∀i

, j ≥ 0, m i,j = E |x|=1 1 { N T i x =j } = i -1 + j j E |x|=1 e -jωx ( 1 + e -ωx ) i+j (43)
= i -1 + j j E[ ν ] E (1 -ρ) j ρ i . Now, Z α,β k
is obviously an integrable and F k -measurable random variable. Moreover, according to (43), for any i ≥ α + 1 and any k ≥ 1,

E 1 { N T n y k =i } y,y * =y k Φ α,β N T n y k , N T n y F k-1 = 1 { N T n y k =i } E |x|=1 Φ α,β i, N T i x = 1 { N T n y k =i } ∞ j=0 Φ α,β (i, j) E |x|=1 1 { N T i [x]=j } = 1 { N T n y k =i } ∞ j=β i -(α + 1) + j -β i -(α + 1) E[ ν ] E (1 -ρ) j ρ i = 1 { N T n y k =i } E[ ν ] m α,β .
From this last equality we easily obtain E Z α,β k F k-1 = 0 which completes the proof of the lemma.

We can now prove Proposition 4.1. We only have to show that:

∀z > 0, P ∞ k=1 Z α,β k ≥ α!β! ( α + β)! ) K R T n α+1 z + 2 log R T n α+1 /2 ≤ Ce -z . (44)
We know, according to Lemma 4.2, that the process (M k ) k∈N defined by

M 0 = 0 and ∀k ≤ 1, M k = k i=1 Z α,β
i is a martingale with respect to (F k ) k∈N . We could directly apply a concentration inequality but to obtain a better bound we first remark that some of the increments Z α,β k are zero so we consider the sequence of stopping times (with respect to the filtration (F k ) k∈N ):

τ 0 = 0 and ∀m ≥ 1, τ m+1 = inf k > τ m , N T n y k ≥ α + 1 ( 45
)
where inf ∅ = ∞. As the other variables Z α,β k are null, we have that

M τm = m i=1 Z α,β τi and R T n α+1 = ∞ m=1 1 { τm<∞ } where if τ m = ∞, M ∞ = ∞ i=1 Z α,β i
which is a sum with only a finite number of non-zero terms. Now an elementary combinatoric argument shows that, for i ≥ α + 1 and j ≥ β,

i -1 + j -α -β i -1 -α α + β α ≤ i -1 + j i -1 .
Thus, for any i, j ≥ 0, 0 ≤ Φ α,β (i, j) ≤ α + β α Therefore the stopped martingale ( M τm∧l ) l≥0 is uniformly integrable and Doob's optional sampling theorem implies that (M τm ) m∈N is a martingale. As for any m ≥ 0,

M τm-1 -E[ ν ] m α,β ≤ M τm ≤ M τm-1 -E[ ν ] m α,β + K,
McDiarmid's inequality (see Theorem 6.7 in [START_REF] Mcdiarmid | On the method of bounded differences[END_REF]) leads now to the following concentration result: for any integer m ≥ 0 and any real z > 0,

P |M τm | ≥ α + β α -1 K mz/2 ≤ 2e -z .
Then a union bound concludes the proof:

P ∞ k=1 Z α,β k ≥ α!β! ( α + β)! ) K R T n α+1 z + 2 log R T n α+1 /2 =P ∞ m=1 R T n α+1 = m ; |M τm | ≥ α + β α -1 K m 2 ( z + 2 log m ) ≤ ∞ m=1 P |M τm | ≥ α + β α -1 K m 2 ( z + 2 log m ) ≤ 2e -z m≥1 e -2 log m = π 2 3 e -z .

Estimation of the cumulative distribution function

In this section we prove Theorem 1.7 using the estimation of the moments m α,β to approximate the cumulative distribution function F of ρ.

Define for any u ∈ [0, 1] and any α ∈ N * ,

F α (u) = αu -1 k=0 α -1 k m k,α-1-k ,
where x → x is the floor function and -1 k=0 = 0. When the function F is regular enough, it is a classical result that it is well approximated by F α . A precise statement is given in Lemma 6 of [START_REF] Diel | Non parametric estimation for random walks in random environment[END_REF] which we recall here. It is then natural to use the estimator defined in (10):

F α n (u) = 1 R T n α E[ ν ] x∈T ψ αu α N T n x * , N T n x with ψ l α (i, j) = 1 { i≥α } i-1+j α-1 l-1 k=0 i -1 k j α -1 -k .
Indeed, for any i ≥ α, ψ l α (i, j) = l-1 k=0 α-1 k Φ k,α-1-k (i, j), where Φ k,α-1-k is defined in (41). Thus, this estimator is essentially the one obtained from the moment estimators of the previous subsection, but using only the sites x satisfying N T n x ≥ α. Notice that for any 1 ≤ l ≤ α and i ≥ α, j ≥ 0,

l-1 k=0 i k j α -1 -k ≤ α-1 k=0 i -1 k j α -1 -k = i -1 + j α -1 ,
thus ψ l α ∈ [0, 1]. Moreover, Vandermonde's identity:

∀i, j ≥ 0,

α-1 k=0 i -1 k j α -1 -k = i -1 + j α -1
shows that any F α n is a (random) c.d.f. We now have to prove that F α n estimates correctly F α . This is done in the following lemma.

Lemma 4.4. For any integers α, n ≥ 1 and any real z > 0,

P F α n -F α ∞ ≥ K E[ ν ] z + log α + 2 log R T n 2R T n α ≤ Ce -z .
Proof. The proof follows the same lines as the one of Proposition 4.1. We introduce the sequence:

∀0 ≤ ≤ α, ∀k ∈ N, Y α, k = 1 { N T n y k ≥α } y,y * =y k ψ α N T n y k , N T n y -E[ ν ] F α ( /α ) .
Using same kind of arguments as in the proof of Lemma 4.2, we can show that Y α, k k∈N is a martingale difference sequence with respect to the filtration (F k ) k∈N defined in (42). As The inequality of Theorem 1.7 follows now immediately from Lemma 4.3, Lemma 4.4 and the fact that F is γ ∧ 1-Hölder.

F α n -F α ∞ = max

Proof of Theorem 1.5

The main step of the proof is to show that we can find a constant C such that for any integer n ≥ 1, and any real z > 0, there exists a r.v. α z,n depending only on ( X k ) 0≤k≤T n such that

P F αz,n n -F ∞ ≥ inf α≥1 4K E[ ν ] z + log α + 2 log R T n α 2R T n α + 10 F γ α γ/2 ≤ Ce -z . (46)
Theorem 1.5 can then be easily deduced from (46) using the estimations of R T n α given in Theorem 1.1. Equation (46) and the estimator F αz,n n is obtained from the collection F α n α≥1 via Goldenshluger-Lepski's method (see [START_REF] Goldenshluger | Universal pointwise selection rule in multivariate function estimation[END_REF]). We explain the construction below. We fix first some real number z > 0 and define for any integer α ≥ 1,

G(α) = K E[ ν ] z + log α + 2 log R T n α 2R T n α and ∆(α) = sup α ≥1 F α n -F α∧α n -G(α ) .
Lemma 4.4 and a union bound show that, for some C > 0,

P ∀α ≥ 1, F α n -F α ∞ ≤ G(α) ≥ 1 -Ce -z . (47)
Moreover, by Lemma 4.3 and the fact that F is γ ∧ 1-Hölder, we have the following control on the bias of the estimator:

F -F α ∞ ≤ 2 F γ α γ/2 . ( 48
)
The random variable α z,n is defined by α z,n = arg min α≥1 { ∆(α) + G(α) } .

We now have to check that α z,n satisfies (46). Let

Ω = ∀α ≥ 1, F α n -F α ∞ ≤ G(α) .

Figure 1 :

 1 Figure 1: Recurrence criteria for (X n ) n∈N on Galton-Watson trees

Figure 2 :

 2 Figure 2: Log-Laplace ψ and corresponding behaviors of (X n ) n∈N .

  j ≤ d log n ) ≤ A log n + Ln j=A log n P e -rSj ≥ e -rd log n (24) ≤ A log n + Ln j=A log n e rd log n e ψ(1+r)j ,

  ) and (32) are true for any |x| ∨ |y| ≤ m for some integer m and consider two vertices x and y such that |x| ∨ |y| ≤ m + 1. If |x| ∨ |y| ≤ m, the result is direct. If |x| ≤ m and |y| = m + 1, we consider the

Figure 3 :

 3 Figure 3: Vertices numbering

- 1 =

 1 Φ α,β (α + 1, β) ≤ 1 and for any m ≥ 0, |Z α,β m | ≤ K where K is the upper bound of the support of ν. Moreover, for any m ∈ N, the stopped process ( M τm∧l ) l≥0 is still a martingale. For any m ∈ N, |M τm∧l | ≤ mK.

Lemma 4. 3 .

 3 Suppose that the functionF ∈ C γ for some γ ∈ (0, 2]. For any integer α ≥ 1, max 0≤ ≤α |F ( /α) -F α ( /α)| ≤ F γ 2 γ (α + 1) γ/2 .

  log α + 2 log R T n α ) ≤ Ce -z .So we now consider martingale M α,l k k∈N defined by M α,l k := j≤k Y α,l j and the same sequence of stopping times (τ m ) m∈N as the one defined in (45) except that α + 1 is replaced by α:τ 0 = 0 and ∀m ≥ 1, τ m+1 = inf l > τ m , N T n y l ≥ α .The process M α,l τm m∈N is still a martingale and for any m ≥ 1,M α,l τm-1 -E[ ν ] F α ( /α ) ≤ M α,l τm ≤ M α,l τm-1 -E[ ν ] F α ( /α ) + K .Then Mc Diarmid's inequality (Theorem 6.7 in[START_REF] Mcdiarmid | On the method of bounded differences[END_REF]) yields, for any 1 ≤ ≤ α,∀k ∈ N, ∀z > 0, P M α, k ≥ K kz 2 ≤ 2e -zand a union bound gives the result: log α + 2 log k) ≤ 2e -z

Acknowledgment: we are grateful to an anonymous referee for comments that were useful to improve the presentation of the paper.

By (47), P ( Ω ) ≥ 1 -Ce -z . On Ω, using first the definition of ∆(α) and then the one of α z,n , we get for any α ≥ 1,

The first term is non positive on Ω, the second one is bounded by