Yueyun Hu

Zhan Shi

MINIMAL POSITION AND CRITICAL MARTINGALE CONVERGENCE IN BRANCHING RANDOM WALKS, AND DIRECTED POLYMERS ON DISORDERED TREES

Keywords: subject classification. 60J80 Branching random walk, minimal position, martingale convergence, spine, marked tree, directed polymer on a tree

We establish a second-order almost sure limit theorem for the minimal position in a one-dimensional super-critical branching random walk, and also prove a martingale convergence theorem which answers a question of Biggins and Kyprianou [Electron. J. Probab. 10 (2005) 609-631]. Our method applies, furthermore, to the study of directed polymers on a disordered tree. In particular, we give a rigorous proof of a phase transition phenomenon for the partition function (from the point of view of convergence in probability), already described by Derrida and Spohn [J. Statist. Phys. 51 (1988) 817-840]. Surprisingly, this phase transition phenomenon disappears in the sense of upper almost sure limits.

Introduction.

1.1. Branching random walk and martingale convergence. We consider a branching random walk on the real line R. Initially, a particle sits at the origin. Its children form the first generation; their displacements from the origin correspond to a point process on the line. These children have children of their own (who form the second generation), and behave-relative to their respective positions-like independent copies of the initial particle. And so on.

We write |u| = n if an individual u is in the nth generation, and denote its position by V (u). [In particular, for the initial ancestor e, we have V (e) = 0.] We assume throughout the paper that, for some δ > 0, δ + > 0 and δ -> 0,

E |u|=1 1 1+δ < ∞, (1.1)
By (1.2), ψ(t) < ∞ for t ∈ [-δ -, 1 + δ + ]. Following Biggins and Kyprianou [START_REF] Biggins | Fixed points of the smoothing transform: The boundary case[END_REF], we assume

ψ(0) > 0, ψ(1) = ψ ′ (1) = 0. (1.3)
Since the number of particles in each generation forms a Galton-Watson tree, the assumption ψ(0) > 0 in (1.3) says that this Galton-Watson tree is super-critical.

In the study of the branching random walk, there is a fundamental martingale, defined as follows: u) , n = 0, 1, 2, . . .

W n := |u|=n e -V (
∅ := 0 . (1.4)
Since W n ≥ 0, it converges almost surely.

When ψ ′ (1) < 0, it is proved by Biggins and Kyprianou [START_REF] Biggins | Seneta-Heyde norming in the branching random walk[END_REF] that there exists a sequence of constants (a n ) such that Wn an converges in probability to a nondegenerate limit which is (strictly) positive upon the survival of the system. This is called the Seneta-Heyde norming in [START_REF] Biggins | Seneta-Heyde norming in the branching random walk[END_REF] for branching random walk, referring to Seneta [START_REF] Seneta | On recent theorems concerning the supercritical Galton-Watson process[END_REF] and Heyde [START_REF] Heyde | Extension of a result of Seneta for the super-critical Galton-Watson process[END_REF] on the rate of convergence in the classic Kesten-Stigum theorem for Galton-Watson processes.

The case ψ ′ (1) = 0 is more delicate. In this case, it is known (Lyons [START_REF] Lyons | A simple path to Biggins' martingale convergence for branching random walk[END_REF]) that W n → 0 almost surely. The following question is raised in Biggins and Kyprianou [START_REF] Biggins | Fixed points of the smoothing transform: The boundary case[END_REF]: are there deterministic normalizers (a n ) such that Wn an converges?

We aim at answering this question.

Theorem 1.1. Assume (1.1), (1.2) and (1.3). There exists a deterministic positive sequence (λ n ) with 0 < lim inf n→∞ λn n 1/2 ≤ lim sup n→∞ λn n 1/2 < ∞, such that, conditionally on the system's survival, λ n W n converges in distribution to W , with W > 0 a.s. The distribution of W is given in (10.3).

The limit W in Theorem 1.1 turns out to satisfy a functional equation. Such functional equations are known to be closely related to (a discrete version of) the Kolmogorov-Petrovski-Piscounov (KPP) traveling wave equation; see Kyprianou [START_REF] Kyprianou | Slow variation and uniqueness of solutions to the functional equation in the branching random walk[END_REF] for more details.

The almost sure behavior of W n is described in Theorem 1.3 below. The two theorems together give a clear image of the asymptotics of W n .

1.2. The minimal position in the branching random walk. A natural question in the study of branching random walks is about inf |u|=n V (u), the position of the leftmost individual in the nth generation. In the literature the concentration (in terms of tightness or even weak convergence) of inf |u|=n V (u) around its median/quantiles has been studied by many authors. See, for example, Bachmann [START_REF] Bachmann | Limit theorems for the minimal position in a branching random walk with independent logconcave displacements[END_REF] and Bramson and Zeitouni [START_REF] Bramson | Tightness for a family of recursion equations[END_REF], as well as Section 5 of the survey paper by Aldous and Bandyopadhyay [START_REF] Aldous | A survey of max-type recursive distributional equations[END_REF]. We also mention the recent paper of Lifshits [START_REF] Lifshits | Some limit theorems on binary trees[END_REF], where an example of a branching random walk is constructed such that inf |u|=n V (u)median({inf |u|=n V (u)}) is tight but does not converge weakly.

We are interested in the asymptotic speed of inf |u|=n V (u). Under assumption (1.3), it is known that, conditionally on the system's survival,

1 n inf |u|=n V (u) → 0 a.s., (1.5) inf |u|=n V (u) → +∞ a.s. (1.6)
The "law of large numbers" in (1.5) is a classic result, and can be found in Hammersley [START_REF] Hammersley | Postulates for subadditive processes[END_REF], Kingman [START_REF] Kingman | The first birth problem for an age-dependent branching process[END_REF] and Biggins [START_REF] Biggins | The first-and last-birth problems for a multitype agedependent branching process[END_REF]. The system's transience to the right, stated in (1.6), follows from the fact that W n → 0, a.s.

A refinement of (1.5) is obtained by McDiarmid [START_REF] Mcdiarmid | Minimal positions in a branching random walk[END_REF]. Under the additional assumption E{( |u|=1 1) 2 } < ∞, it is proved in [START_REF] Mcdiarmid | Minimal positions in a branching random walk[END_REF] that, for some constant c 1 < ∞ and conditionally on the system's survival, lim sup

n→∞ 1 log n inf |u|=n V (u) ≤ c 1 a.s.
We intend to determine the exact rate at which inf |u|=n V (u) goes to infinity. Remark. (i) The most interesting part of Theorem 1.2 is (1.7)- (1.8). It reveals the presence of fluctuations of inf |u|=n V (u) on the logarithmic level, which is in contrast with known results of Bramson [START_REF] Bramson | Minimal displacement of branching random walk[END_REF] and Dekking and Host [START_REF] Dekking | Limit distributions for minimal displacement of branching random walks[END_REF] stating that, for a class of branching random walks, 1 log log n inf |u|=n V (u) converges almost surely to a finite and positive constant.

(ii) Some brief comments on (1.3) are in order. In general [i.e., without assuming ψ(1) = ψ ′ (1) = 0], the law of large numbers (1.5) reads 1 n inf |u|=n V (u) → c, a.s. (conditionally on the system's survival), where c := inf{a ∈ R : g(a) ≥ 0}, with g(a) := inf t≥0 {ta + ψ(t)}. If

t * ψ ′ (t * ) = ψ(t * ) (1.10)
for some t * ∈ (0, ∞), then the branching random walk associated with the point process V (u) := t * V (u) + ψ(t * )|u| satisfies (1.3). That is, as long as (1.10) has a solution [which is the case, e.g., if ψ(1) = 0 and ψ ′ (1) > 0], the study will boil down to the case (1.3).

It is, however, possible that (1.10) has no solution. In such a situation, Theorem 1.2 does not apply. For example, we have already mentioned a class of branching random walks exhibited in Bramson [START_REF] Bramson | Minimal displacement of branching random walk[END_REF] and Dekking and Host [START_REF] Dekking | Limit distributions for minimal displacement of branching random walks[END_REF], for which inf |u|=n V (u) has an exotic log log n behavior.

(iii) Under suitable assumptions, Addario-Berry [START_REF] Addario-Berry | Ballot theorems and the heights of trees[END_REF] obtains a very precise asymptotic estimate of E[inf |u|=n V (u)], which implies (1.9).

(iv) In the case of branching Brownian motion, the analogue of (1.9) was proved by Bramson [START_REF] Bramson | Maximal displacement of branching Brownian motion[END_REF], by means of some powerful explicit analysis. 1.3. Directed polymers on a disordered tree. The following model is borrowed from the well-known paper of Derrida and Spohn [START_REF] Derrida | Polymers on disordered trees, spin glasses, and traveling waves[END_REF]: Let T be a rooted Cayley tree; we study all self-avoiding walks (= directed polymers) of n steps on T starting from the root. To each edge of the tree is attached a random variable (= potential). We assume that these random variables are independent and identically distributed. For each walk ω, its energy E(ω) is the sum of the potentials of the edges visited by the walk. So the partition function is (ω) , where the sum is over all self-avoiding walks of n steps on T, and β > 0 is the inverse temperature.

Z n := ω e -βE
More generally, we take T to be a Galton-Watson tree, and observe that the energy E(ω) corresponds to (the partial sum of) the branching random walk described in the previous sections. The associated partition function becomes Clearly, when β = 1, W n,1 is just the W n defined in (1.4).

If 0 < β < 1, the study of W n,β boils down to the case ψ ′ (1) < 0, which was investigated by Biggins and Kyprianou [START_REF] Biggins | Seneta-Heyde norming in the branching random walk[END_REF]. In particular, conditionally on the system's survival,

W n,β
E{W n,β } converges almost surely to a (strictly) positive random variable.

We study the case β ≥ 1 in the present paper.

Theorem 1.3. Assume (1.1), (1.2) and (1.3). Conditionally on the system's survival, we have

W n = n -1/2+o(1)
a.s. (1.12) Theorem 1.4. Assume (1.1), (1.2) and (1.3), and let β > 1. Conditionally on the system's survival, we have (1) in probability. (1.15) Again, the most interesting part in Theorem 1.4 is (1.13) and (1.14), which describes a new fluctuation phenomenon. Also, there is no phase transition any more for W n,β at β = 1 from the point of view of upper almost sure limits.

lim sup n→∞ log W n,β log n = - β 2 a.s., (1.13) lim inf n→∞ log W n,β log n = - 3β 2 a.s., (1.14)
W n,β = n -3β/2+o
The remark on (1.3), stated after Theorem 1.2, applies to Theorems 1.3 and 1.4 as well.

An important step in the proof of Theorems 1.3 and 1.4 is to estimate all small moments of W n and W n,β , respectively. This is done in the next theorems.

Theorem 1.5. Assume (1.1), (1.2) and (1.3). For any γ ∈ [0, 1), we have

0 < lim inf n→∞ E{(n 1/2 W n ) γ } ≤ lim sup n→∞ E{(n 1/2 W n ) γ } < ∞. (1.16)
Theorem 1.6. Assume (1.1), (1.2) and (1.3), and let β > 1. For any 0 < r < 1 β , we have

E{W r n,β } = n -3rβ/2+o(1) , n → ∞. (1.17)
The rest of the paper is as follows. In Section 2 we introduce a change-ofmeasures formula (Proposition 2.1) in terms of spines on marked trees. This formula will be of frequent use throughout the paper. Section 3 contains a few preliminary results of the lower tail probability of the martingale W n . The proofs of the theorems are organized as follows:

• Section 4 relies on ideas borrowed from Bramson [START_REF] Bramson | Maximal displacement of branching Brownian motion[END_REF], and does not require the preliminaries in Sections 2 and 3.

Sections 5 and 6 are the technical part of the paper, where a common idea is applied in two different situations.

Throughout the paper we write q := P{the system's extinction} ∈ [0, 1).

The letter c with a subscript denotes finite and (strictly) positive constants. We also use the notation ∅ := 0, ∅ := 1, and 0 0 := 1. Moreover, we use a n ∼ b n , n → ∞, to denote lim n→∞ an bn = 1.

2. Marked trees and spines. This section is devoted to a change-ofmeasures result (Proposition 2.1) on marked trees in terms of spines. The material of this section has been presented in the literature in various forms; see, for example, Chauvin, Rouault and Wakolbinger [START_REF] Chauvin | Growing conditioned trees[END_REF], Lyons, Pemantle and Peres [START_REF] Lyons | Conceptual proofs of L log L criteria for mean behavior of branching processes[END_REF], Biggins and Kyprianou [START_REF] Biggins | Measure change in multitype branching[END_REF] and Hardy and Harris [START_REF] Hardy | A new formulation of the spine approach to branching diffusions[END_REF].

There is a one-to-one correspondence between branching random walks and marked trees. Let us first introduce some notation. We label individuals in the branching random walk by their line of descent, so if

u = i 1 • • • i n ∈ U := {∅} ∪ ∞ k=1 (N * ) k (where N * := {1, 2, . . .}
), then u is the i n th child of the i n-1 th child of. . . of the i 1 th child of the initial ancestor e. It is sometimes convenient to consider an element u ∈ U as a "word" of length |u|, with ∅ corresponding to e. We identify an individual u with its corresponding word.

If u, v ∈ U , we denote by uv the concatenated word, with u∅ = ∅u = u.

Let U := {(u, V (u)) : u ∈ U , V : U → R}.
Let Ω be Neveu's space of marked trees, which consists of all the subsets ω of U such that the first component of ω is a tree. [Recall that a tree t is a subset of U satisfying:

(i) ∅ ∈ t; (ii) if uj ∈ t for some j ∈ N * , then u ∈ t; (iii) if u ∈ t, then uj ∈ t if and only if 1 ≤ j ≤ ν u (t) for some nonnegative integer ν u (t).]
Let T : Ω → Ω be the identity application. According to Neveu [START_REF] Neveu | Arbres et processus de Galton-Watson[END_REF], there exists a probability P on Ω such that the law of T under P is the law of the branching random walk described in the Introduction.

Let us make a more intuitive presentation. For any ω ∈ Ω, let

T GW (ω) := the set of individuals ever born in ω, (2.1)

T(ω) := {(u, V (u)), u ∈ T GW (ω), V such that (u, V (u)) ∈ ω}. (2.2) [Of course, T(ω) = ω.]
In words, T GW is a Galton-Watson tree, with the population members as the vertices, whereas the marked tree T corresponds to the branching random walk. It is more convenient to write (2.2) in an informal way:

T = {(u, V (u)), u ∈ T GW }.
For any u ∈ T GW , the shifted Galton-Watson subtree generated by u is

T GW u := {x ∈ U : ux ∈ T GW }. (2.3)
[By shifted, we mean that T GW u is also rooted at e.] For any x ∈ T GW u , let

|x| u := |ux| -|u|, (2.4) V u (x) := V (ux) -V (u). (2.5)
As such, |x| u stands for the (relative) generation of x as a vertex of the Galton-Watson tree T GW u , and (V u (x), x ∈ T GW u ) the branching random walk which corresponds to the shifted marked subtree

T u := {(x, V u (x)), x ∈ T GW u }. Let F n := σ{(u, V (u)), u ∈ T GW , |u| ≤ n},
which is the sigma-field induced by the first n generations of the branching random walk. Let F ∞ be the sigma-field induced by the whole branching random walk.

Assume now ψ(0) > 0 and ψ(1) = 0. Let Q be a probability on Ω such that, for any n ≥ 1,

Q| Fn := W n • P| Fn . (2.6) Fix n ≥ 1. Let w (n) n be a random variable taking values in {u ∈ T GW , |u| = n} such that, for any |u| = n, Q{w (n) n = u|F ∞ } = e -V (u) W n . (2.7)
We write e, w

(n) n = {e =: w (n) 0 , w (n) 1 , w (n) 2 , . . . , w (n) n } for the shortest path in T GW relating the root e to w (n) n , with |w (n) k | = k for any 1 ≤ k ≤ n.
For any individual u ∈ T GW \ {e}, let ←u be the parent of u in T GW , and

∆V (u) := V (u) -V ( ← - u ).

Y. HU AND Z. SHI

For 1 ≤ k ≤ n, we write

I (n) k := {u ∈ T GW : |u| = k, ← - u = w (n) k-1 , u = w (n) k }. (2.8) In words, I (n) k is the set of children of w (n) k-1 except w (n)
k or, equivalently, the set of the brothers of w (n) k , and is possibly empty. Finally, let us introduce the following sigma-field:

G n := σ x∈I (n) k δ ∆V (x) , V (w (n) k ), w (n) k , I (n) k , 1 ≤ k ≤ n , (2.9)
where δ denotes the Dirac measure.

The promised change-of-measures result is as follows. For any marked tree T, we define its truncation T n at level n by

T n := {(x, V (x)), x ∈ T GW , |x| ≤ n}; see Figure 1.
Proposition 2.1. Assume ψ(0) > 0 and ψ(1) = 0, and fix n ≥ 1. Under probability Q, Throughout the paper, let ((S i , σ i ), i ≥ 1) be such that (S i -S i-1 , σ i ), for i ≥ 1 (with S 0 = 0), are i.i.d. random vectors under Q and distributed as (V (w (i) Under Q, ((V (w

(i) the random variables ( x∈I (n) k δ ∆V (x) , ∆V (w (n) k )), 1 ≤ k ≤ n, are i.i.d., distributed as ( x∈I (1) 1 δ ∆V (x) , ∆V (w (1)
(n) k ), #I (n) k ), 1 ≤ k ≤ n) is distributed as ((S k , σ k ), 1 ≤ k ≤ n). In particular, under Q, (V (w (n) k ), 1 ≤ k ≤ n) is distributed as (S k , 1 ≤ k ≤ n).
(ii) For any measurable function F : R → R + ,

E Q {F (S 1 )} = E |u|=1 e -V (u) F (V (u)) . (2.10)
In particular, we have E Q {S 1 } = 0 under (1.2) and (1.3). Corollary 2.2 follows immediately from Proposition 2.1, and can be found in several papers (e.g., Biggins and Kyprianou [START_REF] Biggins | Fixed points of the smoothing transform: The boundary case[END_REF]).

We present two collections of probability estimates for (S n ) and for (V (u), |u| = 1), respectively. They are simple consequences of Proposition 2.1, and will be of frequent use in the rest of the paper.

Corollary 2.3. Assume (1.2) and (1.3). Then

E Q {e aS 1 } < ∞ ∀|a| ≤ c 2 , (2.11) Q{|S n | ≥ x} ≤ 2 exp -c 3 min x, x 2 n (2.12) ∀n ≥ 1, ∀x ≥ 0, Q min 1≤k≤n S k > 0 ∼ c 4 n 1/2 , n → ∞, (2.13) sup n≥1 n 1/2 E Q {e b min 0≤i≤n S i } < ∞ ∀b ≥ 0, (2.14)
where c 2 := min{δ + , 1 + δ -}. Furthermore, for any C ≥ c > 0, we have

Q max 0≤j,k≤n,|j-k|≤c logn |S j -S k | ≥ C log n ≤ 2cn -(c 3 C-
Q sup |u|=1 |V (u)| ≥ x ≤ c 5 e -c 6 x
∀x ≥ 0, (2.17) with ρ(a) := δδ + 1+aδ+δ + , where δ and δ + are the constants in (1.1) and (1.2), respectively.

Proof of Corollary 2.3. By Corollary 2.2 (ii), E Q {e aS 1 } = E{ |u|=1 e (a-1)V (u) }, which, according to (1.2), is finite as long as |a| ≤ c 2 . This proves (2.11).

Once we have the exponential integrability in (2.11) for (S n ), standard probability estimates for sums of i.i.d. random variables yield (2.12), (2.13) and (2.14); see Petrov [START_REF] Petrov | Limit Theorems of Probability Theory: Sequences of independent random variables[END_REF]'s Theorem 2.7, Bingham [START_REF] Bingham | Limit theorems in fluctuation theory[END_REF] and Kozlov [START_REF] Kozlov | The asymptotic behavior of the probability of non-extinction of critical branching processes in a random environment[END_REF]'s Theorem A, respectively.

To check (2.15), we observe that the probability term on the left-hand side of (2.15) is bounded by 0≤j<k≤n,k-j≤c log n Q{|S k-j | ≥ C log n}. By (2.12),

Q{|S k-j | ≥ C log n} ≤ 2n -c 3 C for k -j ≤ c log n. This yields (2.

15).

Proof of Corollary 2.4. Write ρ := ρ(a). We have

E Q {( |u|=1 e -aV (u) ) ρ } = E Q {W ρ 1,a } = E{W ρ 1,a W 1,1 }. Let N := |u|=1 1. By Hölder's inequality, W 1,a ≤ W a/(1+δ + ) 1,1+δ + N (1-a+δ + )/(1+δ + ) , whereas W 1,1 ≤ W 1/(1+δ + )
1,1+δ + N δ + /(1+δ + ) . Therefore, by means of another application of Hölder's inequality, )] , where c 9 := [E{( |u|=1 e -V (u) ) 1+ρ(1) }] 1/(1+ρ(1)) < ∞. Now (2.17) follows from (2.16), with c 6 := c 8 ρ (1) 1+ρ(1) .

E{W ρ 1,a W 1,1 } ≤ [E(W 1,1+δ + )] (1+aρ)/(1+δ + ) [E(N 1+δ )] (δ + -aρ)/(1+δ
:= E( |u|=1 e c 8 |V (u)| ) < ∞ as long as 0 < c 8 ≤ min{δ -, 1 + δ + } [by (1.2)]. Thus, Q(A) = E{ |u|=1 e -V (u) 1 A } ≤ c 9 [P(A)] ρ(1)/[1+ρ(1
3. Preliminary: small values of W n . This preliminary section is devoted to the study of the small values of W n . Throughout the section, we assume (1.1), (1.2) and (1.3). We define two important events: S := {the system's ultimate survival}, (3.1)

S n := {the system's survival after n generations} = {W n > 0}. (3.2)
Clearly, S ⊂ S n . Recall (see, e.g., Harris [START_REF] Harris | The Theory of Branching Processes[END_REF], page 16) that, for some constant c 10 and all n ≥ 1,

P{S n \ S } ≤ e -c 10 n . (3.3)
Here is the main result of the section. Proposition 3.1. Assume (1.1), (1.2) and (1.3). For any ε > 0, there exists ϑ > 0 such that, for all sufficiently large n,

P{n 1/2 W n < n -ε |S } ≤ n -ϑ . (3.4)
The proof of Proposition 3.1 relies on Neveu's multiplicative martingale. Recall that under assumption (1.3), there exists a nonnegative random variable ξ * , with P{ξ * > 0} > 0, such that

ξ * law = |u|=1 ξ * u e -V (u) , (3.5)
where, given {(u, V (u)), |u| = 1}, ξ * u are independent copies of ξ * , and " law = " stands for identity in distribution. Moreover, there is uniqueness of the distribution of ξ * up to a scale change (see Liu [START_REF] Liu | On generalized multiplicative cascades[END_REF]); in the rest of the paper we take the version of ξ * as the unique one satisfying E{e -ξ * } = 1 2 . Let us introduce the Laplace transform of ξ * :

ϕ * (t) := E{e -tξ * }, t ≥ 0. (3.6) Let W * n := |u|=n ϕ * (e -V (u) ), n ≥ 1. (3.7)
The process (W * n , n ≥ 1) is also a martingale (Liu [27]). Following Neveu [START_REF] Neveu | Multiplicative martingales for spatial branching processes[END_REF], we call W * n an associated "multiplicative martingale." The martingale W * n being bounded, it converges almost surely (when n → ∞) to, say, W * ∞ . Let us recall from Liu [START_REF] Liu | On generalized multiplicative cascades[END_REF] (see also Kyprianou [25]) that, for some c * > 0,

log 1 W * ∞ law = ξ * , (3.8) log 1 ϕ * (t) ∼ c * t log 1 t , t → 0. (3.9)
We first prove the following lemma: Lemma 3.2. Assume (1.1), (1.2) and (1.3). There exist κ > 0 and a 0 ≥ 1 such that

E{(W * ∞ ) a |W * ∞ < 1} ≤ a -κ , ∀a ≥ a 0 , (3.10) E{(W * n ) a 1 Sn } ≤ a -κ + e -c 10 n , ∀n ≥ 1, ∀a ≥ a 0 . (3.11)
Proof. We are grateful to John Biggins for fixing a mistake in the original proof.

We first prove (3.10). In view of (3.8), it suffices to show that

E{e -aξ * |ξ * > 0} ≤ a -κ , a ≥ a 0 . (3.12)
Let q ∈ [0, 1) be the system's extinction probability. Let N := |u|=1 1. It is well known for Galton-Watson trees that q is the unique solution of E(q N ) = q (for q ∈ [0, 1)); see, for example, Harris [START_REF] Harris | The Theory of Branching Processes[END_REF], page 7. By (3.5), ϕ * (t) = E{ |u|=1 ϕ * (te -V (u) )}. Therefore, by (3.6),

P{ξ * = 0} = ϕ * (∞) = lim t→∞ E{ |u|=1 ϕ * (te -V (u) )}, which, by dominated convergence, is = E{(ϕ * (∞)) N } = E{(P{ξ * = 0}) N }. Since P{ξ * = 0} < 1, this yields P{ξ * = 0} = q.
Following Biggins and Grey [START_REF] Biggins | Continuity of limit random variables in the branching random walk[END_REF], we note that, for any t ≥ 0,

E{e -tξ * } = q + (1 -q)E{e -tξ * |ξ * > 0}.
Let ξ be a random variable such that E{e -t ξ } = E{e -tξ * |ξ * > 0} for any t ≥ 0. Let Y be a random variable independent of everything else, such that P{Y = 0} = q = 1 -P{Y = 1}. Then ξ * and Y ξ have the same law and, by (3.5), so do ξ * and |u|=1 e -V (u) Y u ξ u , where, given {u, |u| = 1}, (Y u , ξ u ) are independent copies of (Y, ξ), independent of

{V (u), |u| = 1}. Since { |u|=1 e -V (u) Y u ξ u > 0} = { |u|=1 Y u > 0}, this leads to E{e -t ξ } = E e -t |u|=1 e -V (u) Yu ξu |u|=1 Y u > 0 , t ≥ 0.
Let ϕ(t) := E{e -t ξ }, t ≥ 0. Then for any t ≥ 0 and c > 0,

ϕ(t) = E |u|=1 ϕ(te -V (u) Y u ) |u|=1 Y u > 0 ≤ E [ ϕ(te -c )] Nc |u|=1 Y u > 0 ,
where

N c := |u|=1 1 {Yu=1,|V (u)|≤c} . By monotone convergence, lim c→∞ E{N c | |u|=1 Y u > 0} = E{ |u|=1 Y u | |u|=1 Y u > 0} > 1 [because P{ |u|=1 Y u ≥ 2} > 0 by assumption (1.3)]. We can therefore choose and fix a constant c > 0 such that E{N c | |u|=1 Y u > 0} > 1. By writing f (s) := E{s Nc | |u|=1 Y u > 0}, we have ϕ(t) ≤ f ( ϕ(te -c )), ∀t ≥ 0.
Iterating the inequality yields that, for any t ≥ 0 and any n ≥ 1,

E{e -t ξ } ≤ f (n) (E{e -te -nc ξ }), that is, E{e -te nc ξ } ≤ f (n) (E{e -t ξ }), (3.13)
where f (n) denotes the nth iterate of f . It is well known for Galton-Watson trees (Athreya and Ney [START_REF] Athreya | Branching Processes[END_REF], Section I.11) that, for any s ∈ [0, 1), lim n→∞ γ -n × f (n) (s) converges to a finite limit, with γ := ( f

) ′ (0) ≤ P{ |u|=1 Y u = 1| |u|=1 Y u > 0} < 1.
Therefore, (3.13) yields (3.12), and thus (3.10). It remains to check (3.11)

. Let a ≥ 1. Since ((W * n ) a , n ≥ 0) is a bounded submartingale, E{(W * n ) a 1 Sn } ≤ E{(W * ∞ ) a 1 Sn }. Recall that W * ∞ ≤ 1; thus, E{(W * n ) a 1 Sn } ≤ E{(W * ∞ ) a 1 S } + P{S n \ S }. By (3.3), P{S n \ S } ≤ e -c 10 n . To estimate E{(W * ∞ ) a 1 S }, we identify S with {W * ∞ < 1}: on the one hand, S c ⊂ {W * n = 1, for all sufficiently large n} ⊂ {W * ∞ = 1}; on the other hand, by (3.8), P{W * ∞ < 1} = P{ξ * > 0} = 1 -q = P(S ). Therefore, S = {W * ∞ < 1}, P-a.s. Consequently, E{(W * ∞ ) a 1 S } = E{(W * ∞ ) a 1 {W * ∞ <1}
}, which, according to (3.10), is bounded by a -κ , for a ≥ a 0 . Lemma 3.2 is proved.

We are now ready for the proof of Proposition 3.1.

Proof of Proposition 3.1. Let c 11 > 0 be such that P{ξ * ≤ c 11 } ≥ 1 2 . Then ϕ * (t) = E{e -tξ * } ≥ e -c 11 t P{ξ * ≤ c 11 } ≥ 1 2 e -c 11 t and, thus, log( 1 ϕ * (t) ) ≤ c 11 t + log 2.
Together with (3.9), this yields, on the event S n , log 1

W * n = |u|=n log 1 ϕ * (e -V (u) ) ≤ |u|=n 1 {V (u)≥1} c 12 V (u)e -V (u) + |u|=n 1 {V (u)<1} (c 11 e -V (u) + log 2). Since W n = |u|=n e -V (u) , we obtain, on S n , for any λ ≥ 1, log 1 W * n ≤ c 13 λW n + c 12 |u|=n 1 {V (u)≥λ} V (u)e -V (u) , (3.14)
where c 13 := c 11 + c 12 + e log 2. Note that c 12 and c 13 do not depend on λ.

Let 0 < y ≤ 1. Since S ⊂ S n , it follows that, for c 14 := c 12 + c 13 ,

P{λW n < y|S n } ≤ P log 1 W * n < c 14 y|S n + P |u|=n 1 {V (u)≥λ} V (u)e -V (u) ≥ y S n (3.15) =: RHS 1 (3.15) + RHS 2 (3.15)
, with obvious notation.

Recall that P(S n ) ≥ P(S ) = 1 -q. By Chebyshev's inequality,

RHS 1 (3.15) ≤ e c 14 E{(W * n ) 1/y |S n } ≤ e c 14 1 -q E{(W * n ) 1/y 1 Sn }.
By (3.11), for n ≥ 1 and 0 < y ≤ 1 a 0 , with c 15 := e c 14 /(1 -q), RHS 1 (3.15) ≤ c 15 (y κ + e -c 10 n ). (3.16) To estimate RHS 2 (3.15) , we observe that

RHS 2 (3.15) ≤ 1 1 -q P |u|=n 1 {V (u)≥λ} V (u)e -V (u) ≥ y ≤ 1 (1 -q)y E |u|=n 1 {V (u)≥λ} V (u)e -V (u) = 1 (1 -q)y E Q |u|=n 1 {V (u)≥λ} V (u)e -V (u) W n = 1 (1 -q)y E Q {V (w (n) n )1 {V (w (n) n )≥λ} }. By Corollary 2.2(i), E Q {V (w (n) n )1 {V (w (n) n )≥λ} } = E Q {S n 1 {Sn≥λ} } ≤ (E Q {S 2 n }) 1/2 (Q{S n ≥ λ}) 1/2
, which, by (2.12), is bounded by c 16 n exp(-c 3 min{λ, λ 2 n }). Accordingly, RHS 2 (3.15) ≤ c 17 n y exp(-c 3 min{λ, λ 2 n }). Together with (3.15) and (3.16), it yields that, for 0 < y ≤ 1 a 0 ,

P{λW n < y|S n } ≤ c 15 (y κ + e -c 10 n ) + c 17 n y exp -c 3 min λ, λ 2 n .
Let λ := n 1/2 y -κ/2 . The inequality becomes, for 0 < y ≤ 1 a 0 and n ≥ 1,

P{n 1/2 W n < y (κ+2)/2 |S n } ≤ c 15 (y κ + e -c 10 n ) + c 17 n y exp -c 3 min{n 1/2 y κ/2 , 1} y κ .
This readily yields Proposition 3.1.

Remark. Under the additional assumption that {u, |u| = 1} contains at least two elements almost surely, it is possible (Liu [START_REF] Liu | Asymptotic properties and absolute continuity of laws stable by random weighted mean[END_REF]) to improve (3.10):

E{(W * ∞ ) a |W * ∞ < 1} ≤ exp{-a κ 1 }
for some κ 1 > 0 and all sufficiently large a, from which one can deduce the stronger version of Proposition 3.1: for any ε > 0, there exists

ϑ 1 > 0 such that P{n 1/2 W n < n -ε |S } ≤ exp(-n ϑ 1 )
for all sufficiently large n.

We complete this section with the following estimate which will be useful in the proof of Theorem 1.5. Lemma 3.3. Assume (1.1), (1.2) and (1.3). For any 0 < s < 1,

sup n≥1 E log 1 W * n s < ∞. (3.17) Proof. Let x > 1. By Chebyshev's inequality, P{log( 1 W * n ) ≥ x} = P{e x W * n ≤ 1} ≤ eE{e -e x W * n }. Since W * n is a martingale, it follows from Jensen's inequality that E{e -e x W * n } ≤ E{e -e x W * ∞ } ≤ P{W * ∞ ≤ e -x/2 } + exp(-e x/2
). Therefore,

P log 1 W * n ≥ x ≤ eP{W * ∞ ≤ e -x/2 } + exp(1 -e x/2 ). (3.18)
On the other hand, by integration by parts, ∞ 0 e -ty P(ξ

* ≥ y) dy = 1-E(e -tξ * ) t = 1-ϕ * (t) t , which, according to (3.9), is ≤ c 18 log( 1 t ) for 0 < t ≤ 1 2 . Therefore, for a ≥ 2, c 18 log a ≥ ∞ 0 e -y/a P(ξ * ≥ y) dy ≥ a 0 e -y/a P(ξ * ≥ a) dy = (1 - e -1 )aP(ξ * ≥ a). That is, P(ξ * ≥ a) ≤ c 18 1-e -1 log a a or, equivalently, P(W * ∞ ≤ e -a ) ≤ c 18 1-e -1
log a a , for a ≥ 2. Substituting this in (3.18) gives that, for any x ≥ 4,

P log 1 W * n ≥ x ≤ 2ec 18 1 -e -1 log(x/2) x + exp(1 -e x/2
).

Lemma 3.3 follows immediately.

4. Proof of Theorem 1.2: upper bound in (1.8). Assume (1.1), (1.2) and (1.3). This section is devoted to proving the upper bound in (1.8): conditionally on the system's survival,

lim inf n→∞ 1 log n inf |u|=n V (u) ≤ 1 2 , a.s. (4.1)
The proof borrows some ideas from Bramson [START_REF] Bramson | Maximal displacement of branching Brownian motion[END_REF]. We fix

-∞ < a < b < ∞ and ε > 0. Let ℓ 1 ≤ ℓ 2 ≤ 2ℓ 1 be integers; we are interested in the asymptotic case ℓ 1 → ∞. Consider n ∈ [ℓ 1 , ℓ 2 ] ∩ Z. Let 0 < c 19 < 1 be a constant, and let g n (k) := min{c 19 k 1/3 , c 19 (n -k) 1/3 + a log ℓ 1 , n ε }, 0 ≤ k ≤ n. Let L n be the set of individuals x ∈ T GW with |x| = n such that g n (k) ≤ V (x k ) ≤ c 20 k, ∀0 ≤ k ≤ n and a log ℓ 1 ≤ V (x) ≤ b log ℓ 1 ,
where x 0 := e, x 1 , . . . , x n := x are the vertices on the shortest path in T GW relating the root e and the vertex x, with |x k | = k for any 0 ≤ k ≤ n. We consider the measurable event

F ℓ 1 ,ℓ 2 := ℓ 2 n=ℓ 1 |x|=n {x ∈ L n }.
We start by estimating the first moment of #F ℓ 1 ,ℓ 2 :

E(#F ℓ 1 ,ℓ 2 ) = ℓ 2 n=ℓ 1 E{ |x|=n 1 {x∈Ln} }. Since E{ |x|=n 1 {x∈Ln} } = E Q { |x|=n e -V (x) Wn e V (x) × 1 {x∈Ln} } = E Q {e V (w (n) n ) 1 {w (n)
n ∈Ln} }, we can apply Corollary 2.2 to see that

E(#F ℓ 1 ,ℓ 2 ) = ℓ 2 n=ℓ 1 E Q {e Sn 1 {gn(k)≤S k ≤c 20 k,∀0≤k≤n,a log ℓ 1 ≤Sn≤b log ℓ 1 } } ≥ ℓ 2 n=ℓ 1 ℓ a 1 Q{g n (k) ≤ S k ≤ c 20 k, ∀0 ≤ k ≤ n, a log ℓ 1 ≤ S n ≤ b log ℓ 1 }.
We choose (and fix) the constants c 19 and c 20 such that Q{c 19 < S 1 < c 20 } > 0. Then, 1 the probability Q{•} on the right-hand side is ℓ

-(3/2)+o(1) 1 , for ℓ 1 → ∞. Accordingly, E(#F ℓ 1 ,ℓ 2 ) ≥ (ℓ 2 -ℓ 1 + 1)ℓ a-(3/2)+o(1) 1 . (4.2)
We now proceed to estimate the second moment of #F ℓ 1 ,ℓ 2 . By definition,

E[(#F ℓ 1 ,ℓ 2 ) 2 ] = ℓ 2 n=ℓ 1 ℓ 2 m=ℓ 1 E |x|=n |y|=m 1 {x∈Ln,y∈Lm} ≤ 2 ℓ 2 n=ℓ 1 ℓ 2 m=n E |x|=n |y|=m 1 {x∈Ln,y∈Lm} .
1 An easy way to see why - 3 2 should be the correct exponent for the probability is to split the event into three pieces: the first piece involving S k for 0 ≤ k ≤ n 3 , the second piece for n 3 ≤ k ≤ 2n 3 , and the third piece for 2n 3 ≤ k ≤ n. The probability of the first piece is n -(1/2)+o (1) (it is essentially the probability of S k being positive for 1 ≤ k ≤ n 3 , because conditionally on this, S k converges weakly, after a suitable normalization, to a Brownian meander; see Bolthausen [START_REF] Bolthausen | A central limit theorem for two-dimensional random walks in random sceneries[END_REF]). Similarly, the probability of the third piece is n -(1/2)+o (1) . The second piece essentially says that after n 3 steps, the random walk should lie in an interval of length of order log n; this probability is also n -(1/2)+o (1) . Putting these pieces together yields the claimed exponent - 3 2 . For a rigorous proof, the upper bound-not required here-is easier since we can only look at the event that the walk stays positive during n steps (with the same condition upon the random variable Sn), whereas the lower bound needs some tedious but elementary writing, based on the Markov property. Similar arguments are used for the random walk (S k ) in several other places in the paper, without further mention.

We look at the double sum |x|=n |y|=m on the right-hand side. By considering z, the youngest common ancestor of x and y, and writing k := |z|, we arrive at

E[(#F ℓ 1 ,ℓ 2 ) 2 ] ≤ 2 ℓ 2 n=ℓ 1 ℓ 2 m=n n k=0 E |z|=k (u,v) 1 {zu∈Ln,zv∈Lm} =: 2 ℓ 2 n=ℓ 1 ℓ 2 m=n n k=0 Λ k,n,m .
We estimate Λ k,n,m according to three different situations.

First situation: 0 ≤ k ≤ ⌊n ε ⌋. Let V z (u) := V (zu) -V (z) as in Section 2. We have 0 ≤ g n (k) ≤ V (z) ≤ c 20 n ε , and V (zu i ) ≥ 0 for 0 ≤ i ≤ n -k and V (zu n-k ) ≤ b log ℓ 1 ,
where u 0 := e, u 1 , . . . , u n-k are the vertices on the shortest path in T GW z relating the root e and the vertex u, with

|u i | z = i for any 0 ≤ i ≤ n -k. Therefore, V z (u i ) ≥ -c 20 n ε for 0 ≤ i ≤ n -k, and V z (u) ≤ b log ℓ 1 . Accordingly, Λ k,n,m ≤ E |z|=k v∈T GW z ,|v|z=m-k 1 {zv∈Lm} B n-k , where B n-k := E |x|=n-k 1 {V (x i )≥-c 20 n ε ,∀0≤i≤n-k,V (x)≤b log ℓ 1 } = E Q {e V (w (n-k) n-k ) 1 {V (w (n-k) i )≥-c 20 n ε ,∀0≤i≤n-k,V (w (n-k) n-k )≤b log ℓ 1 } } = E Q {e S n-k 1 {S i ≥-c 20 n ε ,∀0≤i≤n-k,S n-k ≤b log ℓ 1 } } ≤ ℓ b 1 Q{S i ≥ -c 20 n ε , ∀0 ≤ i ≤ n -k, S n-k ≤ b log ℓ 1 } ≤ ℓ b-(3/2)+ε+o(1) 1 ≤ ℓ b-(3/2)+2ε 1 . Therefore, Λ k,n,m ≤ ℓ b-(3/2)+2ε 1 E |z|=k v∈T GW z ,|v|z=m-k 1 {zv∈Lm} 18 Y. HU AND Z. SHI = ℓ b-(3/2)+2ε 1 E |x|=m 1 {x∈Lm}
and, thus,

ℓ 2 n=ℓ 1 ℓ 2 m=n ⌊n ε ⌋ k=0 Λ k,n,m ≤ ℓ b-(3/2)+2ε 1 (ℓ 2 -ℓ 1 + 1)(ℓ ε 2 + 1)E(#F ℓ 1 ,ℓ 2 ). (4.3)
Second situation:

⌊n ε ⌋ + 1 ≤ k ≤ min{m -⌊n ε ⌋, n}. In this situation, since V (z) ≥ max{g m (k), g n (k)} ≥ c 19 n ε/3 , we simply have V z (u) ≤ b log ℓ 1 -c 19 n ε/3 .
Exactly as in the first situation, we get

Λ k,n,m ≤ E |x|=m 1 {x∈Lm} E |x|=n-k 1 {V (x)≤b log ℓ 1 -c 19 n ε/3 } .
The second E{•} on the right-hand side is

= E Q {e S n-k 1 {S n-k ≤b log ℓ 1 -c 19 n ε/3 } } ≤ ℓ b 1 e -c 19 n ε/3 and, thus, ℓ 2 n=ℓ 1 ℓ 2 m=n min{m-⌊n ε ⌋,n} k=⌊n ε ⌋+1 Λ k,n,m ≤ ℓ b 1 e -c 19 ℓ ε/3 1 (ℓ 2 -ℓ 1 + 1)ℓ 2 E(#F ℓ 1 ,ℓ 2 ). (4.4)
Third and last situation: m -⌊n ε ⌋ + 1 ≤ k ≤ n (this situation may happen only if m ≤ n + ⌊n ε ⌋ -1). This time V (z) ≥ g m (k) ≥ a log ℓ 1 and, thus,

V z (u) ≤ (b -a) log ℓ 1 ; consequently, Λ k,n,m ≤ E |x|=m 1 {x∈Lm} E |x|=n-k 1 {V (x)≤(b-a) log ℓ 1 } ≤ ℓ b-a 1 E |x|=m 1 {x∈Lm} . Therefore, in case m ≤ n + ⌊n ε ⌋ -1, ℓ 2 n=ℓ 1 ℓ 2 m=n n k=m-⌊n ε ⌋+1 Λ k,n,m ≤ ℓ 2 n=ℓ 1 n+⌊n ε ⌋-1 m=n ℓ ε 2 ℓ b-a 1 E |x|=m 1 {x∈Lm} ≤ ℓ 2 m=ℓ 1 m n=m-2⌊m ε ⌋ ℓ ε 2 ℓ b-a 1 E |x|=m 1 {x∈Lm} ≤ 2ℓ 2ε 2 ℓ b-a 1 E(#F ℓ 1 ,ℓ 2 ).
Combining this with (4.3) and (4.4), and since

E[(#F ℓ 1 ,ℓ 2 ) 2 ] ≤ 2 ℓ 2 n=ℓ 1 ℓ 2 m=n n k=0 Λ k,n,m , we obtain E[(#F ℓ 1 ,ℓ 2 ) 2 ] [E(#F ℓ 1 ,ℓ 2 )] 2 ≤ (2ℓ b-(3/2)+2ε 1 (ℓ 2 -ℓ 1 + 1)(ℓ ε 2 + 1) + 2ℓ b 1 e -c 19 ℓ ε/3 1 (ℓ 2 -ℓ 1 + 1)ℓ 2 + 4ℓ 2ε 2 ℓ b-a 1 )(E(#F ℓ 1 ,ℓ 2 )) -1 . Since ℓ 2 ≤ 2ℓ 1 , we have 2ℓ b-(3/2)+2ε 1 (ℓ ε 2 + 1) + 2ℓ b 1 e -c 19 ℓ ε/3 1 ℓ 2 ≤ ℓ b-(3/2)+4ε 1
for all sufficiently large ℓ 1 . On the other hand,

E(#F ℓ 1 ,ℓ 2 ) ≥ (ℓ 2 -ℓ 1 + 1)ℓ a-(3/2)-ε 1 by (4.
2) (for large ℓ 1 ). Therefore, when ℓ 1 is large, we have

E[(#F ℓ 1 ,ℓ 2 ) 2 ] [E(#F ℓ 1 ,ℓ 2 )] 2 ≤ ℓ b-(3/2)+4ε 1 (ℓ 2 -ℓ 1 + 1) + ℓ b-a+3ε 1 (ℓ 2 -ℓ 1 + 1)ℓ a-(3/2)-ε 1
.

By the Paley-Zygmund inequality, P{F ℓ 1 ,ℓ 2 = ∅} ≥ 1 4 [E(#F ℓ 1 ,ℓ 2 )] 2 E[(#F ℓ 1 ,ℓ 2 ) 2 ] ; thus, P min ℓ 1 ≤|x|≤ℓ 2 V (x) ≤ b log ℓ 1 ≥ 1 4 (ℓ 2 -ℓ 1 + 1)ℓ a-(3/2)-ε 1 ℓ b-(3/2)+4ε 1 (ℓ 2 -ℓ 1 + 1) + ℓ b-a+3ε 1 . (4.5)
Of course, we can make a close to b, and ε close to 0, to see that, for any b ∈ R and ε > 0, all sufficiently large ℓ 1 and all

ℓ 2 ∈ [ℓ 1 , 2ℓ 1 ] ∩ Z, P min ℓ 1 ≤|x|≤ℓ 2 V (x) ≤ b log ℓ 1 ≥ ℓ 2 -ℓ 1 + 1 ℓ ε 1 (ℓ 2 -ℓ 1 + 1) + ℓ (3/2)-b+ε 1 . (4.6)
[This is our basic estimate for the minimum of V (x). In Section 5 we are going to apply (4.6) to ℓ 2 := ℓ 1 .]

We now let b > 1 2 and take the subsequence n j := 2 j , j ≥ j 0 (with a sufficiently large integer j 0 ). By (4.6) (and possibly by changing the value of ε), P min

n j ≤|x|≤n j+1 V (x) ≤ b log n j ≥ n -ε j .
Let τ j := inf{k : #{u : |u| = k} ≥ n 2ε j }. Then we have, for j ≥ j 0 , P τ j < ∞, min

τ j +n j ≤|x|≤τ j +n j+1 V (x) > max |y|=τ j V (y) + b log n j ≤ P min n j ≤|x|≤n j+1 V (x) > b log n j ⌊n 2ε j ⌋ ≤ (1 -n -ε j ) ⌊n 2ε j ⌋ ,
which is summable in j. By the Borel-Cantelli lemma, almost surely for all large j, we have either τ j = ∞, or min τ j +n j ≤|x|≤τ j +n j+1 V (x) ≤ max |y|=τ j V (y)+ b log n j . By the well-known law of large numbers for the branching random walk (Hammersley [START_REF] Hammersley | Postulates for subadditive processes[END_REF], Kingman [START_REF] Kingman | The first birth problem for an age-dependent branching process[END_REF] and Biggins [START_REF] Biggins | The first-and last-birth problems for a multitype agedependent branching process[END_REF]), of which (1.5) was a special case, there exists a constant c 21 > 0 such that 1 n max |y|=n V (y) → c 21 almost surely upon the system's survival. In particular, upon survival, max |y|=n V (y) ≤ 2c 21 n almost surely for all large n. Consequently, upon the system's survival, almost surely for all large j, we have either τ j = ∞, or min τ j +n j ≤|x|≤τ j +n j+1 V (x) < 2c 21 τ j + b log n j .

Recall that the number of particles in each generation forms a Galton-Watson tree, which is super-critical under assumption (1.3) (because m := E{ |u|=1 1} > 1). In particular, conditionally on the system's survival, #{u:|u|=k} m k converges a.s. to a (strictly) positive random variable when k → ∞, which implies τ j ∼ 2ε log n j log m a.s. (j → ∞). As a consequence, upon the system's survival, we have, almost surely for all large j, min

n j ≤|x|≤2n j+1 V (x) ≤ 5εc 21 log m log n j + b log n j .
Since b can be as close to 1 2 as possible, this readily yields (4.1).

5. Proof of Theorem 1.6. Before proving Theorem 1.6, we need three estimates.

The first estimate, stated as Proposition 5.1, was proved by McDiarmid [START_REF] Mcdiarmid | Minimal positions in a branching random walk[END_REF] under the additional assumption E{( |u|=1 1) 2 } < ∞.

Proposition 5.1. Assume (1.1), (1.2) and (1.3). There exists c 22 > 0 such that, for any ε > 0, we can find c 23 = c 23 (ε) > 0 satisfying

E exp c 22 inf |x|=n V (x) 1 Sn ≤ c 23 n (3+ε)/2c 22 , n ≥ 1. (5.1) Remark. Since W n ≥ exp[-inf |x|=n V (x)]
, it follows from (5.1) and Hölder's inequality that, for any 0 ≤ s < c 22 and ε > 0,

E 1 W s n 1 Sn ≤ c s/c 22 23 n (3+ε)/2s , n ≥ 1. (5.2)
This estimate will be useful in the proof of Theorem 1.5 in Section 6.

Proof of Proposition 5.1. In the proof we write, for any k ≥ 0,

V k := inf |u|=k V (u).
Taking ℓ 2 = ℓ 1 in (4.6) gives that, for any ε > 0 and all sufficiently large ℓ (say, ℓ ≥ ℓ 0 ), we have

P{V ℓ ≤ 3 2 log ℓ} ≥ ℓ -ε ; thus, P{V ℓ > 3 2 log ℓ} ≤ 1 - ℓ -ε ≤ exp(-ℓ -ε ), ∀ℓ ≥ ℓ 0 .
For any r ∈ R and integers k ≥ 1 and n > ℓ ≥ ℓ 0 , we have

P{V n > 3 2 log ℓ + r} ≤ P{#{u : |u| = n -ℓ, V (u) ≤ r} < k} + (P{V ℓ > 3 2 log ℓ}) k ≤ P{#{u : |u| = n -ℓ, V (u) ≤ r} < k} + exp(-ℓ -ε k).
By Lemma 1 of McDiarmid [START_REF] Mcdiarmid | Minimal positions in a branching random walk[END_REF], there exist c 24 > 0, c 25 > 0 and c 26 > 0 such that, for any j ≥ 1, P{#{u : |u| = j, V (u) ≤ c 24 j} ≤ e c 25 j } ≤ q + e -c 26 j , q being as before the probability of extinction. We choose j := ⌊ r c 24 ⌋ and ℓ := n -⌊ r c 24 ⌋ to see that, for all n ≥ ℓ 0 and all 0 ≤ r ≤ c 24 (n -ℓ 0 ),

P{V n > 3 2 log n + r} ≤ q + e -c 26 ⌊r/c 24 ⌋ + exp(-n -ε ⌊e c 25 ⌊r/c 24 ⌋ ⌋). Noting that {V n > 3 2 log n + r} ∩ S c n = S c n and that P{S c n } ≥ q -e -c 10 n [see (3.
3)], we obtain, for 0 ≤ r ≤ c 24 (n -ℓ 0 ),

P{V n > 3 2 log n + r, S n } (5.3)
≤ e -c 10 n + e -c 26 ⌊r/c 24 ⌋ + exp(-n -ε ⌊e c 25 ⌊r/c 24 ⌋ ⌋).

This implies that, for any 0 < c 27 < min{ c 26 c 24 , 2c 10 c 24 }, there exists a constant c 28 > 0 such that E{e On the other hand, letting δ -> 0 be as in (1.2), we have e δ -V n 1 Sn ≤ |u|=n e δ -V (u) . Since ψ(-δ -) := log E{ |u|=n e δ -V (u) } < ∞ by (1.2), we can choose and fix c 31 > 0 sufficiently large (in particular, c 31 > c 24 2 ) such that, for any x ≥ c 31 ,

P{V n > xn, S n } ≤ e -δ -xn+ψ(-δ -)n ≤ e -δ -xn/2 , ∀n ≥ 1.
Therefore, for any c 32 < δ - 2 , we have sup

n≥1 E{e c 32 V n 1 {V n >c 31 n}∩Sn } < ∞. (5.5)
Finally, (5.3) also implies that, for n ≥ ℓ 0 ,

P V n > c 24 2
n, S n ≤ e -c 10 n + e -c 26 ⌊n/2-3/(2c 24 ) log n⌋ + exp(-n -ε ⌊e c 25 ⌊n/2-3/(2c 24 ) log n⌋ ⌋). Lemma 5.2. Let X 1 , X 2 , . . . , X N be independent nonnegative random variables, and let T N := N i=1 X i . For any nonincreasing function F : (0, ∞) → R + , we have

E{F (T N )1 {T N >0} } ≤ max 1≤i≤N E{F (X i )|X i > 0}.
Moreover,

E{F (T N )1 {T N >0} } ≤ N i=1 b i-1 E{F (X i )1 {X i >0} }, where b := max 1≤i≤N P{X i = 0}. Proof. Let τ := min{i ≥ 1 : X i > 0} (with min ∅ := ∞). Then E{F (T N )× 1 {T N >0} } = N i=1 E{F (T N )1 {τ =i} }. Since F is nonincreasing, we have F (T N )× 1 {τ =i} ≤ F (X i )1 {τ =i} = F (X i )1 {X i >0} 1 {X j =0,∀j<i}
. By independence, this leads to

E{F (T N )1 {T N >0} } ≤ N i=1 E{F (X i )1 {X i >0} }P{X j = 0, ∀j < i}.
This yields immediately the second inequality of the lemma, since

P{X j = 0, ∀j < i} ≤ b i-1 .
To prove the first inequality of the lemma, we observe that E{F (X i )1

{X i >0} } ≤ P{X i > 0} max 1≤k≤N E{F (X k )|X k > 0}. Therefore, E{F (T N )1 {T N >0} } ≤ max 1≤k≤N E{F (X k )|X k > 0} N i=1 P{X i > 0}P{X j = 0, ∀j < i}. The N i=1 • • • expression on the right-hand side is = N i=1 P{X i > 0, X j = 0, ∀j < i} = N i=1 P{τ = i} = P{T N > 0} ≤ 1.
This yields the first inequality of the lemma.

To state our third estimate, let w (n) ∈ e, w (n) n be a vertex such that

V (w (n) ) = min u∈ e,w (n) n V (u). (5.6)
[If there are several such vertices, we choose, say, the oldest.] The following estimate gives a (stochastic) lower bound for 1

W n,β under Q outside a "small" set. We recall that W n,β > 0, Q-almost surely (but not necessarily P-almost surely).

Lemma 5.3. Assume (1.1), (1.2) and (1.3). For any K > 0, there exist θ > 0 and n 0 < ∞ such that, for any n ≥ n 0 , any β > 0, and any nondecreasing function G : (0, ∞) → (0, ∞),

E Q G e -βV (w (n) ) W n,β 1 En ≤ 1 1 -q max 0≤k<n E G n θβ W k,β 1 S k , (5.7)
where E n is a measurable event such that

Q{E n } ≥ 1 - 1 n K , n ≥ n 0 . Proof. Recall from (2.8) that I (n) k
is the set of the brothers of w Let G n be the sigma-field defined in (2.9). By Proposition 2.1,

Q{k is n-good|G n } = 1 {I (n) k =∅} (P{S n-k }) #I (n) k ,
where S n denotes the system's survival after n generations [see

(3.2)]. Since P{S n-k } ≥ P{S } = 1 -q, whereas #I (n) k
and #I

(1) 1

have the same distribution under Q (Proposition 2.1), we have

Q{k is n-good} ≥ E Q {1 {#I (1) 1 ≥1} (1 -q) #I (1) 1 } = c 34 ∈ (0, 1).
As a consequence, for all 1 ≤ ℓ < n, by Proposition 2.1 again,

Q n k=1 j:1≤j≤n,|j-k|≤ℓ {j is not n-good} ≤ n k=1 j:1≤j≤n,|j-k|≤ℓ Q{j is not n-good} ≤ n(1 -c 34 ) ℓ+1 ,
which is bounded by ne -c 34 (ℓ+1) (using the inequality 1 -x ≤ e -x , for x ≥ 0). Let K > 0. We take ℓ = ℓ(n) := ⌊c [where c 6 is as in (2.17)] and c 37 := max{ K+2 c 3 , c 35 } [c 3 being the constant in (2.12)]. Let E (1) n := n k=1 j:1≤j≤n,|j-k|≤⌊c 35 log n⌋ {j is n-good}, (5.8) E (2) n := max

1≤j≤n sup u∈I (n) j |V (u) -V (w (n) j-1 )| ≤ c 36 log n , (5.9) E (3) n := max 0≤j,k≤n,|j-k|≤c 35 log n |V (w (n) j ) -V (w (n) k )| ≤ c 37 log n . (5.10)
We have Q{E (1) n } ≥ 1 -ne -c 34 c 35 log n = 1 -

1 n K+1 .
On the other hand, by Corollary 2.2,

Q{(E (2) n ) c } ≤ nQ sup u∈I (1) 1 |V (u)| > c 36 log n ≤ nQ sup |u|=1 |V (u)| > c 36 log n .
Applying (2.17) yields that

Q{E (2) n } ≥ 1 -c 5 n -(c 36 c 6 -1) = 1 - c 5 n K+1 .

To estimate Q{E

(3) n }, we note that, by Corollary 2.2,

Q{(E (3) n ) c } = Q max 0≤j,k≤n,|j-k|≤c 35 log n |S j -S k | > c 37 log n ,
which, in view of (2.15), is bounded by 2c 35 n -(c 3 c 37 -1) log n. Consequently, if

E n := E (1) n ∩ E (2) n ∩ E (3) n , (5.11) then Q{E n } ≥ 1 -1
n K for all large n. It remains to check (5.7). By definition,

W n,β = n j=1 u∈I (n) j e -βV (u) x∈T GW u ,|x|u=n-j e -βVu(x) + e -βV (w (n) n ) (5.12) ≥ j∈L u∈I (n) j e -βV (u) x∈T GW u ,|x|u=n-j e -βVu(x)
for any L ⊂ {1, 2, . . . , n}. We choose L := {1 ≤ j ≤ n : |j -|w (n) || < c 35 log n}.

On the event E n , for u ∈ I

(n) j with some j ∈ L , we have V (u) ≤ V (w (n) )+ (c 36 + c 37 ) log n. Writing θ := c 36 + c 37 , this leads to W n,β ≥ n -θβ e -βV (w (n) ) × j∈L u∈I

(n) j ξ u , where

ξ u := x∈T GW u ,|x|u=n-j e -βVu(x) .
Since j∈L u∈I (n) j ξ u > 0 on E n , we arrive at

e -βV (w (n) ) W n,β 1 En ≤ n θβ j∈L u∈I (n) j ξ u 1 { j∈L u∈I (n) j ξu>0} .
Let G n be the sigma-field in (2.9). We observe that L and I

(n) j are G nmeasurable. Moreover, an application of Proposition 2.1 tells us that under Q, conditionally on G n , the random variables ξ u , u ∈ I (n) j , j ∈ L , are independent, and are distributed as W n-j,β under P. We are thus entitled to apply Lemma 5.2 to see that, if G is nondecreasing,

E Q G e -βV (w (n) ) W n,β 1 En |G n ≤ max j∈L E G n θβ W n-j,β |W n-j,β > 0 ≤ max 0≤k<n E G n θβ W k,β |W k,β > 0 .
Since P{W k,β > 0} = P{S k } ≥ P{S } = 1 -q, this yields Lemma 5.3.

We are now ready for the proof of Theorem 1.6. For the sake of clarity, the upper and lower bounds are proved in distinct parts. Let us start with the upper bound.

Proof of Theorem 1.6. The upper bound. We assume (1.1), (1.2) and (1.3), and fix β > 1.

For any Z ≥ 0 which is F n -measurable, we have

E{W n,β Z} = E Q { |u|=n e -βV (u) Wn Z} = E Q { |u|=n 1 {w (n)
n =u} e -(β-1)V (u) Z} and, thus,

E{W n,β Z} = E Q {e -(β-1)V (w (n) n ) Z}. (5.13) Let s ∈ ( β-1
β , 1), and λ > 0. (We will choose λ = 3 2 .) Then

E{W 1-s n,β } ≤ n -(1-s)βλ + E{W 1-s n,β 1 {W n,β >n -βλ } } = n -(1-s)βλ + E Q e -(β-1)V (w (n) n ) W s n,β 1 {W n,β >n -βλ } . Since e -βV (w (n) n ) ≤ W n,β , we have e -(β-1)V (w (n) n ) W s n,β ≤ 1 W s-(β-1)/β n,β
; thus, on the event {W n,β > n -βλ }, we have e -(β-1)V (w (n)

n ) W s n,β ≤ n [βs-(β-1)]λ .
Let K := [βs -(β -1)]λ + (1 -s)βλ, and let E n be the event in Lemma 5.3. Since Q(E c n ) ≤ n -K for all sufficiently large n (see Lemma 5.3), we obtain, for large n,

E{W 1-s n,β } ≤ n -(1-s)βλ + n [βs-(β-1)]λ-K + E Q e -(β-1)V (w (n) n ) W s n,β 1 {W n,β >n -βλ }∩En (5.14) = 2n -(1-s)βλ + E Q e -(β-1)V (w (n) n ) W s n,β
1 {W n,β >n -βλ }∩En .

We now estimate the expectation expression E Q {•} on the right-hand side. Let a > 0 and ̺ > b > 0 be constants such that (β -1)a > sβλ + 3 2 and [βs -(β -1)]b > 3 2 . (The choice of ̺ will be made precise later on.) We recall that w

(n) n ∈ e, w (n) n satisfies V (w (n) ) = min u∈ e,w (n) n V (
u), and consider the following events:

E 1,n := {V (w (n) n ) > a log n} ∪ {V (w (n) n ) ≤ -b log n}, E 2,n := {V (w (n) ) < -̺ log n, V (w (n) n ) > -b log n}, E 3,n := {V (w (n) ) ≥ -̺ log n, -b log n < V (w (n) n ) ≤ a log n}. Clearly, Q( 3 i=1 E i,n ) = 1. On the event E 1,n ∩ {W n,β > n -βλ }, we have either V (w (n) n ) > a log n, in which case e -(β-1)V (w (n) n ) W s n,β ≤ n sβλ-(β-1)a , or V (w (n) n ) ≤ -b log n, in which case we use the trivial inequality W n,β ≥ e -βV (w (n) n ) to see that e -(β-1)V (w (n) n ) W s n,β ≤ e [βs-(β-1)]V (w (n) n ) ≤ n -[βs-(β-1)]b (recalling that βs > β -1). Since sβλ - (β -1)a < -3 2 and [βs -(β -1)]b > 3 2 , we obtain E Q e -(β-1)V (w (n) n ) W s n,β 1 E 1,n ∩{W n,β >n -βλ } ≤ n -3/2 . (5.15)
We now study the integral on E 2,n ∩ {W n,β > n -βλ } ∩ E n . Since s > 0, we can choose s 1 > 0 and 0 < s 2 ≤ c 22 β [where c 22 is the constant in (5.1)] such that s = s 1 + s 2 . We have, on

E 2,n ∩ {W n,β > n -βλ }, e -(β-1)V (w (n) n ) W s n,β = e βs 2 V (w (n) )-(β-1)V (w (n) n ) W s 1 n,β e -βs 2 V (w (n) ) W s 2 n,β ≤ n -βs 2 ̺+(β-1)b+βλs 1 e -βs 2 V (w (n) ) W s 2 n,β
.

Therefore, by an application of Lemma 5.3 to G(x) := x s 2 , x > 0, we obtain, for all sufficiently large n,

E Q e -(β-1)V (w (n) n ) W s n,β 1 E 2,n ∩{W n,β >n -βλ }∩En ≤ n -βs 2 ̺+(β-1)b+βλs 1 1 -q max 0≤k<n E n s 2 θβ W s 2 k,β 1 S k . By definition, 1 W s 2 k,β ≤ exp(βs 2 inf |x|=k V (x)); thus, by (5.1), E{ n s 2 θβ W s 2 k,β 1 S k } ≤ c βs 2 /c 22 23
n s 2 θβ+(3+ε)/2βs 2 for all 0 ≤ k < n. We choose (and fix) the constant ̺ so large that -βs 2 ̺ + (β -1)b + βλs 1 + s 2 θβ + 3+ε 2 βs 2 < -3 2 . Therefore, for all large n,

E Q e -(β-1)V (w (n) n ) W s n,β 1 E 2,n ∩{W n,β >n -βλ }∩En ≤ n -3/2 . (5.16)
We make a partition of E 3,n : let M ≥ 2 be an integer, and let

a i := -b + i(a+b) M , 0 ≤ i ≤ M . By definition, E 3,n = M -1 i=0 {V (w (n) ) ≥ -̺ log n, a i log n < V (w (n) n ) ≤ a i+1 log n} =: M -1 i=0 E 3,n,i .
Let 0 ≤ i ≤ M -1. There are two possible situations. First situation: a i ≤ λ.

In this case, we argue that, on the event E 3,n,i , we have

W n,β ≥ e -βV (w (n) n ) ≥ n -βa i+1 and e -(β-1)V (w (n) n ) ≤ n -(β-1)a i , thus, e -(β-1)V (w (n) n ) W s n,β
≤ n βsa i+1 -(β-1)a i = n βsa i -(β-1)a i +βs(a+b)/M ≤ n [βs-(β-1)]λ+βs(a+b)/M . Accordingly, in this situation,

E Q e -(β-1)V (w (n) n ) W s n,β 1 E 3,n,i ≤ n [βs-(β-1)]λ+βs(a+b)/M Q(E 3,n,i ).
Second (and last) situation: a i > λ. We have, on

E 3,n,i ∩ {W n,β > n -βλ }, e -(β-1)V (w (n) n ) W s n,β
≤ n βλs-(β-1)a i ≤ n [βs-(β-1)]λ ; thus, in this situation,

E Q e -(β-1)V (w (n) n ) W s n,β 1 E 3,n,i ∩{W n,β >n -βλ } ≤ n [βs-(β-1)]λ Q(E 3,n,i ).

Y. HU AND Z. SHI

We have therefore proved that (1) . Combining this with (5.14), (5.15) and (5.16) yields

E Q e -(β-1)V (w (n) n ) W s n,β 1 E 3,n ∩{W n,β >n -βλ } = M -1 i=0 E Q e -(β-1)V (w (n) n ) W s n,β 1 E 3,n,i ∩{W n,β >n -βλ } ≤ n [βs-(β-1)]λ+βs(a+b)/M Q(E 3,n ). By Corollary 2.2, Q(E 3,n ) = P{min 0≤k≤n S k ≥ -̺ log n, -b log n ≤ S n ≤ a × log n} = n -(3/2)+o
E{W 1-s n,β } ≤ 2n -(1-s)βλ + 2n -3/2 + n [βs-(β-1)
]λ+βs(a+b)/M -(3/2)+o (1) .

We choose λ := 3 2 . Since M can be as large as possible, this yields the upper bound in Theorem 1.6 by posing r := 1 -s.

Proof of Theorem 1.6. The lower bound. Assume (1.1), (1.2) and (1.3). Let β > 1 and s ∈ (1 -1 β , 1). By means of (5.12) and the elementary inequality (a + b) 1-s ≤ a 1-s + b 1-s (for a ≥ 0 and b ≥ 0), we have

W 1-s n,β ≤ n j=1 u∈I (n) j e -(1-s)βV (u) x∈T GW u ,|x|u=n-j e -βVu(x) 1-s + e -(1-s)βV (w (n) n ) = n j=1 e -(1-s)βV (w (n) j-1 ) u∈I (n) j e -(1-s)β[V (u)-V (w (n) j-1 )] × x∈T GW u ,|x|u=n-j e -βVu(x) 1-s + e -(1-s)βV (w (n) n ) .
Let G n be the sigma-field defined in (2.9), and let

Ξ j = Ξ j (n, s, β) := u∈I (n) j e -(1-s)β[V (u)-V (w (n) j-1 )] , 1 ≤ j ≤ n. Since V (w (n) j ) and I (n) j , for 1 ≤ j ≤ n, are G n -measurable, it follows from Proposition 2.1 that E Q {W 1-s n,β |G n } ≤ n j=1 e -(1-s)βV (w (n) j-1 ) Ξ j E{W 1-s n-j,β } + e -(1-s)βV (w (n) n ) .
Let ε > 0 be small, and let r := 3 2 (1 -s)β -ε. By means of the already proved upper bound for E(W 1-s n,β ), this leads to, with c 38 ≥ 1,

E Q {W 1-s n,β |G n } (5.17) ≤ c 38 n j=1 e -(1-s)βV (w (n) j-1 ) (n -j + 1) -r Ξ j + e -(1-s)βV (w (n) n ) . Since E(W 1-s n,β ) = E Q { e -(β-1)V (w (n) n ) W s n,β
} [see (5.13)], we have, by Jensen's inequality [noticing that V (w

(n) n ) is G n -measurable], E(W 1-s n,β ) ≥ E Q e -(β-1)V (w (n) n ) {E Q (W 1-s n,β |G n )} s/(1-s)
, which, in view of (5.17), yields

E(W 1-s n,β ) ≥ 1 c s/(1-s) 38 × E Q (e -(β-1)V (w (n) n ) ) × n j=1 e -(1-s)βV (w (n) j-1 ) (n -j + 1) -r Ξ j + e -(1-s)βV (w (n) n ) s/(1-s) -1
.

By Proposition 2.1, if (S j -S j-1 , ξ j ), for j ≥ 1 (with S 0 := 0), are i.i.d. random variables under Q and distributed as (V (w

(1) 1 ), u∈I (1) 1 e -(1-s)βV (u) ), then the E Q {•} expression on the right-hand side is = E Q e -(β-1)Sn { n j=1 (n -j + 1) -r e -(1-s)βS j-1 ξ j + e -(1-s)βSn } s/(1-s) = E Q e [βs-(β-1)] Sn { n k=1 k -r e (1-s)β S k ξ k + 1} s/(1-s)
, where

S ℓ := S n -S n-ℓ , ξ ℓ := ξ n+1-ℓ , 1 ≤ ℓ ≤ n.
Consequently,

E(W 1-s n,β ) ≥ 1 c s/(1-s) 38 E Q e [βs-(β-1)] Sn { n k=1 k -r e (1-s)β S k ξ k + 1} s/(1-s)
.

Y. HU AND Z. SHI

Let c 39 > 0 be a constant, and define

E S n,1 := ⌊n ε ⌋-1 k=1 { S k ≤ -c 39 k 1/3 } ∩ {-2n ε/2 ≤ S ⌊n ε ⌋ ≤ -n ε/2 }, E S n,2 := n-⌊n ε ⌋-1 k=⌊n ε ⌋+1 { S k ≤ -[k 1/3 ∧ (n -k) 1/3 ]} ∩ {-2n ε/2 ≤ S n-⌊n ε ⌋ ≤ -n ε/2 }, E S n,3 := n-1 k=n-⌊n ε ⌋+1 S k ≤ 3 2 log n ∩ 3 -ε 2 log n ≤ S n ≤ 3 2 log n .
Let ρ := ρ((1 -s)β) be the constant in Corollary 2.4, and let

E ξ n,1 := ⌊n ε ⌋ k=1 { ξ k ≤ n 2ε/ρ }, E ξ n,2 := n-⌊n ε ⌋ k=⌊n ε ⌋+1 { ξ k ≤ e n ε/4 }, E ξ n,3 := n k=n-⌊n ε ⌋+1 { ξ k ≤ n 2ε/ρ }. On 3 i=1 (E S n,i ∩ E ξ n,i ), we have n k=1 k -r e (1-s)β S k ξ k + 1 ≤ c 40 n 2ε+(2ε/ρ)
, while e [βs-(β-1)] Sn ≥ n (3-ε)[βs-(β-1)]/2 (recalling that βs > β -1). Therefore, with

c 41 := (2 + 2 ρ ) s 1-s , E(W 1-s n,β ) ≥ (c 38 c 40 ) -s/(1-s) n -c 41 ε n (3-ε)[βs-(β-1)]/2 (5.18) × Q 3 i=1 (E S n,i ∩ E ξ n,i ) .
We need to bound

Q( 3 i=1 (E S n,i ∩ E ξ n,i )) from below. Let S 0 := 0. Note that, under Q, ( S ℓ -S ℓ-1 , ξ ℓ ), 1 ≤ ℓ ≤ n, are i.i.d., distributed as (S 1 , ξ 1 ). For j ≤ n, let G j be the sigma-field generated by ( S k , ξ k ), 1 ≤ k ≤ j. Then E S n,1 , E S n,2 , E ξ n,1 and E ξ n,2 are G n-⌊n ε ⌋ -measurable, whereas E ξ n,3 is independent of G n-⌊n ε ⌋ . Therefore, Q 3 i=1 (E S n,i ∩ E ξ n,i )| G n-⌊n ε ⌋ ≥ [Q(E S n,3 | G n-⌊n ε ⌋ ) + Q(E ξ n,3 ) -1]1 E S n,1 ∩E S n,2 ∩E ξ n,1 ∩E ξ n,2
.

We have

c 42 := E Q (ξ ρ 1 ) < ∞ [by (2.16)]; thus, Q{ξ 1 > n 2ε/ρ } ≤ c 42 n -2ε , which entails Q(E ξ n,3 ) = (Q{ξ 1 ≤ n 2ε/ρ }) ⌊n ε ⌋ ≥ (1-c 42 n -2ε ) ⌊n ε ⌋ ≥ 1-c 43 n -ε . To estimate Q(E S n,3 | G n-⌊n ε ⌋ ), we use the Markov property to see that, if S n-⌊n ε ⌋ ∈ I n := [-2n ε/2 , -n ε/2 ], the conditional probability is (writing N := ⌊n ε ⌋) ≥ inf z∈In Q S i ≤ 3 2 log n -z, ∀1 ≤ i ≤ N -1, 3 -ε 2 log n -z ≤ S N ≤ 3 2 log n -z ,
which is greater than N -(1/2)+o( 1) Therefore, (1) . As a consequence,

Q(E S n,3 | G n-⌊n ε ⌋ ) + Q(E ξ n,3 ) -1 ≥ n -(ε/2)+o(1) -c 43 n -ε = n -(ε/2)+o
Q 3 i=1 (E S n,i ∩ E ξ n,i ) ≥ n -(ε/2)+o(1) Q(E S n,1 ∩ E S n,2 ∩ E ξ n,1 ∩ E ξ n,2 ). (5.19) To estimate Q(E S n,1 ∩ E S n,2 ∩ E ξ n,1 ∩ E ξ n,2
), we condition on G ⌊n ε ⌋ , and note that E S n,1 and

E ξ n,1 are G ⌊n ε ⌋ -measurable, whereas E ξ n,2 is independent of G ⌊n ε ⌋ . Since Q(E S n,2 | G ⌊n ε ⌋ ) ≥ n -(3-ε)/2+o(1) , whereas Q(E ξ n,2 ) = [Q{ξ 1 ≤ e n ε/4 }] n-2⌊n ε ⌋ ≥ [1 -c 42 e -ρn ε/4 ] n-2⌊n ε ⌋ ≥ 1 -e -n ε/5 (for large n), we have Q(E S n,1 ∩ E S n,2 ∩ E ξ n,1 ∩ E ξ n,2 | G ⌊n ε ⌋ ) ≥ [Q(E S n,2 | G ⌊n ε ⌋ ) + Q(E ξ n,2 ) -1]1 E S n,1 ∩E ξ n,1 ≥ n -(3-ε)/2+o(1) 1 E S n,1 ∩E ξ n,1
.

Thus, Q(E S n,1 ∩ E S n,2 ∩ E ξ n,1 ∩ E ξ n,2 ) ≥ n -(3-ε)/2+o(1) Q(E S n,1 ∩ E ξ n,1
). Going back to (5.19), we have

Q 3 i=1 (E S n,i ∩ E ξ n,i ) ≥ n -(3/2)+o(1) Q(E S n,1 ∩ E ξ n,1 ) ≥ n -(3/2)+o(1) [Q(E S n,1 ) + Q(E ξ n,1 ) -1].
We choose the constant c 39 > 0 sufficiently small so that 1) , n → ∞.

Q(E S n,1 ) ≥ n -(ε/2)+o(1) , whereas Q(E ξ n,1 ) = Q(E ξ n,3 ) ≥ 1 -c 43 n -ε . Accordingly, Q 3 i=1 (E S n,i ∩ E ξ n,i ) ≥ n -(3+ε)/2+o(

Y. HU AND Z. SHI

Substituting this into (5.18) yields (1) . Since ε can be as small as possible, this implies the lower bound in Theorem 1.6.

E(W 1-s n,β ) ≥ n -c 41 ε n (3-ε)[βs-(β-1)]/2 n -(3+ε)/2+o
6. Proof of Theorem 1.5. The basic idea in the proof of Theorem 1.5 is the same as in the proof of Theorem 1.6. Again, we prove the upper and lower bounds in distinct parts, for the sake of clarity. Throughout the section, we assume (1.1), (1.2) and (1.3).

Proof of Theorem 1.5: The upper bound. Clearly, n 1/2 W n ≤ Y n , where We now fix 0 < s < min{ 1 2 , c 32 , c 10 c 31 , κ}. Let K ≥ 1 and let E n be the event in (5.11), satisfying Q{E n } ≥ 1 -n -K for n ≥ n 0 . We write

Y n := |u|=n (n 1/2 ∨ V (u) + )e -V (u) . Recall W * n from (3.7). Applying (3.14) to λ = 1, we see that Y n ≥ 1 c 44 log( 1 W * n ), with c 44 := c 12 + c 13 . Thus, P{Y n < x, S n } ≤ P{log( 1 W * n ) < c 44 x, S n } ≤ e c 44 E{(W * n ) 1/x 1 Sn },
E{(n 1/2 W n ) 1-s } = E{(n 1/2 W n ) 1-s 1 En } + E{(n 1/2 W n ) 1-s 1 E c n }. For n ≥ n 0 , E{W 1-s n 1 E c n } ≤ [E{W 1-2s n }] 1/2 [E{W n 1 E c n }] 1/2 = [E{W 1-2s n }] 1/2 × [Q{E c n }] 1/2 ≤ [E{W n }] (1/2)-s n -K/2 , which equals n -K/2 (since E{W n } = 1). Therefore, for n → ∞, E{(n 1/2 W n ) 1-s } ≤ E{Y 1-s n 1 En } + o(1).
Exactly as in (5.13), we have E{Y

1-s n 1 En } = E Q {(n 1/2 ∨V (w (n) n ) + )Y -s n 1 En }. Thus, for n → ∞, E{(n 1/2 W n ) 1-s } ≤ E Q {(n 1/2 + V (w (n) n ) + )Y -s n 1 En } + o(1). (6.2)
For any subset L ⊂ {1, 2, . . . , n}, we have

Y n ≥ j∈L u∈I (n) j x∈T GW u ,|x|u=n-j max{n 1/2 , V (x) + }e -V (x) = j∈L u∈I (n) j e -V (u) x∈T GW u ,|x|u=n-j max{n 1/2 , [V (u) + V u (x)] + }e -Vu(x) .
Recall that w (n) is the oldest vertex in e, w

(n) n such that V (w (n) ) = min u∈ e,w (n) n V (u)
. Let c 35 be the constant in (5.8). We choose

L :=          {j ≤ n : I (n) j = ∅, |w (n) | < j < |w (n) | + c 35 log n}, if n -|w (n) | ≥ 2c 35 log n, {j ≤ n : I (n) j = ∅, |w (n) | -c 35 log n < j < |w (n) |}, otherwise.
On the event E n , it is clear that L = ∅ and that, for any u ∈ I

(n) j (with j ∈ L ), |V (u) -V (w (n) )| ≤ c 45 log n, (6.3)
where c 45 := c 36 + c 37 , with c 36 and c 37 as in (5.9) and (5.10), respectively.

We distinguish two possible situations, depending on whether V (w (n) ) ≥ -c 46 log n, where c 46 := 1 s + c 45 . In both situations, we consider a sufficiently large n and an arbitrary u ∈ I

(n) j (with j ∈ L ). On {V (w (n) ) ≥ -c 46 log n} ∩ E n , we have max{n 1/2 , [V (u) + V u (x)] + } ≥ 1 2 (n 1/2 ∨ V u (x) + ) [this holds trivially in case V u (x) ≤ n 1/2 ; otherwise [V (u) + V u (x)] + ≥ V u (x) -(c 46 + c 45 ) log n ≥ 1 2 V u (x) +
] and, thus,

Y n ≥ 1 2 j∈L u∈I (n) j e -V (u) x∈T GW u ,|x|u=n-j max{(n -j) 1/2 , V u (x) + }e -Vu(x) =: 1 2 j∈L u∈I (n) j e -V (u) ξ u . If, however, V (w (n) ) < -c 46 log n, then on E n , V (u) ≤ V (w (n) ) + c 45 log n < -1 s log n and, since max{n 1/2 , [V (u) + V u (x)] + } ≥ n 1/2 , we have, in this case, Y n ≥ n (1/s)+(1/2) j∈L u∈I (n) j x∈T GW u ,|x|u=n-j e -Vu(x) =: n (1/s)+(1/2) j∈L u∈I (n) j η u .
Therefore, in both situations we have

Y -s n 1 En ≤ 2 s j∈L u∈I (n) j e -V (u) ξ u -s 1 En (6.4) + n -(s/2)-1 j∈L u∈I (n) j η u -s 1 En . [Since j∈L u∈I (n) j x∈T GW u
,|x|u=n-j 1 > 0 on E n , the (•) -s expressions on the right-hand side are well defined.]

We claim that there exists 0 < s 0 < 1 such that, for any ε > 0 and s ∈ (0, s 0 ),

E Q (n 1/2 + V (w (n) n ) + ) j∈L u∈I (n) j e -V (u) ξ u -s 1 En (6.5) ≤ c 48 , E Q (n 1/2 + V (w (n) n ) + ) j∈L u∈I (n) j η u -s
1 En (6.6) ≤ c 47 n 1/2+(3+ε)/2s .

We admit (6.5) and (6.6) for the time being. In view of (6.4), we obtain, for 0 < s < s * := min{ 1 2 , s 0 , c 32 , c 10 c 31 , κ},

E Q {(n 1/2 + V (w (n) n ) + )Y -s n 1 En } ≤ 2 s c 48 + o (1)
. Substituting this in (6.2), we see that sup n≥1 E{(n 1/2 W n ) 1-s } < ∞ for any s ∈ (0, s * ). This yields the last inequality in (1.16) when γ is close to 1. By Jensen's inequality, it holds for all γ ∈ [0, 1). This will complete the proof of the upper bound in Theorem 1.5.

It remains to check (6.5) and (6.6). We only present the proof of (6.5), because the proof of (6.6) is similar and slightly easier, using (5.2) in place of (6.1).

Recall G n from (2.9). By Proposition 2.1, under Q and conditionally on G n , the random variables ξ u , for u ∈ I (n) j and j ∈ L , are independent. We write L := {j(1), . . . , j(N )}, with j(1) < • • • < j(N ). It follows from the second part of Lemma 5.2 that

E Q j∈L u∈I (n) j e -V (u) ξ u -s 1 En G n ≤ N i=1 b i-1 E Q u∈I (n) j(i) e -V (u) ξ u -s 1 { u∈I (n) j(i) e -V (u) ξu>0} G n ,
where b := max j∈L Q{ u∈I (n) j e -V (u) ξ u = 0|G n }. We note that b ≤ max 1≤j≤n P{S c n-j } ≤ q, and that, for any i ≤ N , the E Q {•} expression on the right-hand side is, according to the first part of Lemma 5.2, bounded by

1 1 -q max u∈I (n) j(i) E Q e sV (u) ξ s u 1 {ξu>0} |G n . By Proposition 2.1, E Q { 1 ξ s u 1 {ξu>0} |G n } = E{ 1 Y s n-j 1 S n-j }, which is bounded
in n and j [by (6.1)]. Summarizing, we have proved that

E Q j∈L u∈I (n) j e -V (u) ξ u -s 1 En G n ≤ c 49 N i=1 q i-1 max u∈I (n) j(i)
e sV (u) .

As a consequence, the expression on the left-hand side of (6.5) is bounded by c 49 E Q {Λ n }, where

Λ n := (n 1/2 + V (w (n) n ) + ) N i=1 q i-1 max u∈I (n) j(i) e sV (u) 1 {|V (u)-V (w (n) )|≤c 45 log n} ≤ Λ n := (n 1/2 + V (w (n) n ) + ) N i=1 q i-1 max u∈I (n) j(i)
e sV (u) .

The proof of (6.5) now boils down to verifying the following estimates: there exists 0 < s 0 < 1 such that, for any s ∈ (0, s 0 ),

sup n E Q { Λ n 1 {n-|w (n) |≥2c 35 log n} } < ∞, (6.7) lim n→∞ E Q {Λ n 1 {n-|w (n) |<2c 35 log n} } = 0. (6.8)
Let us first check (6.7). Let S 0 := 0 and let (S j -S j-1 , σ j , ∆ j ), j ≥ 1, be i.i.d. random variables under Q and distributed as (V (w (1) ), #I

(1) 1 , max u∈I (1) 1 e sV (u) ). Let S n := min 0≤i≤n S i , ϑ n := inf{k ≥ 0 : S k = S n }.
[The random variable ϑ n has nothing to do with the constant ϑ in Proposition 3.1.] Writing LHS (6.7) for

E Q { Λ n 1 {n-|w (n) |≥2c 35 log n} }, it follows from Proposition 2.1 that LHS (6.7) = E Q [n 1/2 + S + n ] M i=1 q i-1 e sS ℓ(i)-1 ∆ ℓ(i) 1 {n-ϑn≥2c 35 log n} = E Q [n 1/2 + S + n ]e sS n M i=1 q i-1 e s[S ℓ(i)-1 -S ℓ(0) ] ∆ ℓ(i) 1 {n-ϑn≥2c 35 log n} ,
where ℓ(i) := inf{k > ℓ(i-1) : σ k ≥ 1} with ℓ(0) := ϑ n , and M := sup{i :

ℓ(i) < ϑ n + c 35 log n}.
At this stage, we use a standard trick for random walks: let ν 0 := 0 and let

ν i := inf k > ν i-1 : S k < min 0≤j≤ν i-1 S j , i ≥ 1.
In words, 0 = ν 0 < ν 1 < • • • are strict descending ladder times. On the event

{ν k ≤ n < ν k+1 } (for k ≥ 0), we have ϑ n = ν k and S n = S ν k . Thus, LHS (6.7) equals ∞ k=0 E Q 1 {n-ν k ≥2c 35 log n} 1 {ν k ≤n<ν k+1 } [n 1/2 + S + n ]e sSν k × M i=1 q i-1 e s[S ℓ(i)-1 -S ℓ(0) ] ∆ ℓ(i) .
For any k, we look at the expectation E Q {•} on the right-hand side. By conditioning upon (S j , σ j , ∆ j , 1 ≤ j ≤ ν k ), and since

S + n = [S ν k + (S n -S ν k )] + ≤ (S n -S ν k ) + = S n -S ν k on {ν k ≤ n < ν k+1 }, we obtain LHS (6.7) ≤ ∞ k=0 E Q {1 {n-ν k ≥2c 35 log n} e sSν k f n (n -ν k )}, (6.9)
where, for any 1

≤ j ≤ n, f n (j) := E Q 1 {ν 1 >j} [n 1/2 + S j ] M ′ i=1 q i-1 e sS m(i)-1 ∆ m(i) ,
and m(i) := inf{k > m(i-1) : σ k ≥ 1} with m(0) := 0, and M ′ := sup{i : m(i) < c 35 log n}. For brevity, we write [START_REF] Seneta | On recent theorems concerning the supercritical Galton-Watson process[END_REF] log n} for the moment. By the Cauchy-Schwarz inequality,

L n := M ′ i=1 q i-1 e sS m(i)-1 ∆ m(i) = ∞ i=1 q i-1 × e sS m(i)-1 ∆ m(i) 1 {m(i)<c
f n (j) ≤ [Q{ν 1 > j}] 1/2 [E Q {(n 1/2 + S j ) 2 |ν 1 > j}] 1/2 [E Q {L 2 n 1 {ν 1 >j} }] 1/2 .
By (2.13), Q{ν 1 > j} ≤ c 50 j -1/2 for some c 50 > 0 and all j ≥ 1. On the other hand, (n 1/2 + S j ) 2 ≤ 2(n + S 2 j ), and it is known (Bolthausen [START_REF] Bolthausen | A central limit theorem for two-dimensional random walks in random sceneries[END_REF]) that

E Q { S 2 j j |ν 1 > j} → c 51 ∈ (0, ∞) for j → ∞.
Therefore, E Q {(n 1/2 + S j ) 2 |ν 1 > j} ≤ c 52 n for some c 52 > 0 and all n ≥ j ≥ 1. Accordingly, with c 53 := c

1/2 50 c 1/2 52 , we have f n (j) ≤ c 53 j -1/4 n 1/2 [E Q {L 2 n 1 {ν 1 >j} }] 1/2 , 1 ≤ j ≤ n.
By the Cauchy-Schwarz inequality,

L 2 n ≤ ( ∞ i=1 q i-1 ) ∞ i=1 q i-1 e 2sS m(i)-1 ∆ 2 m(i) × 1 {m(i)<c 35 log n} . Therefore, for j ≥ 2c 35 log n, E Q {L 2 n 1 {ν 1 >j} } ≤ 1 1 -q ∞ i=1 q i-1 E Q {e 2sS m(i)-1 ∆ 2 m(i) 1 {m(i)<c 35 log n} 1 {ν 1 >j} } ≤ 1 1 -q ∞ i=1 q i-1 E Q {e 2sS m(i)-1 ∆ 2 m(i) 1 {m(i)≤j/2} 1 {ν 1 >j}
For any i ≥ 1, to estimate the expectation E Q {•} on the right-hand side, we apply the strong Markov property at time m(i) to see that

E Q {•} = E Q {e 2sS m(i)-1 ∆ 2 m(i) 1 {m(i)≤j/2} 1 {ν 1 >m(i)} g(S m(i) , j -m(i))
}, where g(z, k) := Q{z + S i ≥ 0, ∀1 ≤ i ≤ k} for any z ≥ 0 and k ≥ 1. By [START_REF] Bramson | Minimal displacement of branching random walk[END_REF] of Kozlov [START_REF] Kozlov | The asymptotic behavior of the probability of non-extinction of critical branching processes in a random environment[END_REF], g(z, k) ≤ c 54 (z + 1)/k 1/2 for some c 54 > 0 and all z ≥ 0 and k ≥ 1. Since z + 1 ≤ c 55 e sz for all z ≥ 0, this yields, with c 56 := c 55 1-q ,

E Q {L 2 n 1 {ν 1 >j} } ≤ c 56 ∞ i=1 q i-1 E Q e 2sS m(i)-1 ∆ 2 m(i) 1 {m(i)≤j/2} e sS m(i) (j -m(i)) 1/2 ≤ c 56 (j/2) 1/2 ∞ i=1 q i-1 E Q {e 2sS m(i)-1 +sS m(i) ∆ 2 m(i) } = 2 1/2 c 56 j 1/2 E Q ∞ i=1 q i-1 e 2sS m(i)-1 +sS m(i) ∆ 2 m(i) .
We observe that ∞ i=1 q i-1 e 2sS m(i)-1 +sS m(i) ∆ 2 m(i) ≤ ∞ k=1 q R(k)-1 e 2sS k-1 +sS k ∆ 2 k , where R(k) := #{1 ≤ j ≤ k : σ j ≥ 1}. Therefore, with c 57 := 2 1/2 c 56 ,

E Q {L 2 n 1 {ν 1 >j} } ≤ c 57 j 1/2 ∞ k=1 E Q {q R(k)-1 e 2sS k-1 +sS k ∆ 2 k } ≤ c 57 j 1/2 ∞ k=1 [E Q {q 2[R(k)-1] }] 1/2 [E Q {e 4sS k-1 +2sS k ∆ 4 k }] 1/2 . By definition, E Q {q 2[R(k)-1] } = q -2 r k , with r := Q(σ 1 = 0) + q 2 Q(σ 1 ≥ 1) < 1 [because q < 1 and Q(σ 1 = 0) < 1].
On the other hand,

E Q {e 4sS k-1 +2sS k ∆ 4 k } = E Q {e 6sS k-1 }E Q {e 2s(S k -S k-1 ) ∆ 4 k } = [E Q {e 6sS 1 }] k-1 E Q {e 2sS 1 ∆ 4 1 }.
By (2.11), there exists s # > 0 sufficiently small such that E Q {e 6sS 1 } < 1 r for all 0 < s < s # . On the other hand, E Q {∆ 8 1 } < ∞ for 0 < s < c 6 8 [by (2.17)], and

E Q {e 4sS 1 } < ∞ for 0 < s ≤ c 2 4 [by (2.11)]; thus, E Q {e 2sS 1 ∆ 4 1 } < ∞ for 0 < s < min{ c 6
8 , c 2 4 }. As a consequence, for any 0 < s < min{s # , c 6 8 , c 2 4 }, we have E Q {L 2 n 1 {ν 1 >j} } ≤ c 58 j 1/2 , for some c 58 > 0 and all n ≥ j ≥ 1 with j ≥ 2c 35 log n, which yields

f n (j) ≤ c 53 c 1/2 58 j -1/2 n 1/2 .
Going back to (6.9), we obtain, for any 0 < s < min{s # , c 6 8 , c 2 4 } and c 59 := c 53 c

1/2 58 , LHS (6.7) ≤ c 59 n 1/2 ∞ k=0 E Q 1 {n-ν k ≥2c 35 log n} e sSν k (n -ν k ) 1/2 .
By (2.13) again, 1 j 1/2 ≤ c 60 Q{ν 1 > j} for all j ≥ 1. Thus, with c 61 := c 59 c 60 ,

LHS (6.7) ≤ c 61 n 1/2 ∞ k=0 E Q {1 {n-ν k ≥2c 35 log n} e sSν k 1 {ν k+1 >n} } ≤ c 61 n 1/2 ∞ k=0 E Q {1 {ν k ≤n<ν k+1 } e sSν k },
which equals c 61 n 1/2 E Q {e s min 0≤i≤n S i }, and, according to (2.14), is bounded in n. This completes the proof of (6.7). It remains to check (6.8). By definition,

Λ n ≤ [n 1/2 + V (w (n) n ) + ]n sc 45 e sV (w (n) ) N i=1 q i-1 .
Since N i=1 q i-1 ≤ 1 1-q , this leads to, by an application of Proposition 2.1,

E Q {Λ n 1 {n-|w (n) |<2c 35 log n} } ≤ n sc 45 1 -q E Q {[n 1/2 + S + n ]e sS n 1 {n-ϑn<2c 35 log n} },
where (S i ) is as in Proposition 2.1 and, as before, S n := min 0≤i≤n S i , ϑ n := inf{k ≥ 0 :

S k = S n }. Let 0 < ε < 1 2 ; let A n := {S n > n 1/2+ε } and B n := {S n ≤ n 1/2+ε } = A c n . Since E Q {e aS 1 } < ∞ for |a| < c 2 [see (2.11)] and Q(A n ) ≤ 2 exp(-c 3 n 2ε ) [see (2.12)], the Cauchy-Schwarz inequality yields n sc 45 E Q {[n 1/2 + S + n ] × e sS n 1 An } → 0, n → ∞.
On B n , we have n 1/2 + S + n ≤ 2n

(log n) 1/2 n 1/2
(see Feller [START_REF] Feller | An Introduction to Probability Theory and Its Applications[END_REF], page 398). Therefore,

E Q {[n 1/2 + S + n ]e sS n × 1 Bn∩{n-ϑn<2c 35 log n} } ≤ c 64 n -1/2+ε (log n) 1/2 .
Summarizing, we have proved that, for any s > 0 and 0 < ε < 1 2 , when n → ∞,

E Q {Λ n 1 {n-|w (n) |<2c 35 log n} } ≤ o(1) + c 64 1 -q n sc 45 -1/2+ε (log n) 1/2 ,
which yields (6.8), as long as 0 < s < 1 2c 45 .

Proof of Theorem 1.5. The lower bound. We start with

n 1/2 W n ≥ Y n := |u|=n (n 1/2 ∧ V (u) + )e -V (u) .
Let s ∈ (0, 1). Exactly as in (5.13), we have

E{Y 1-s n } = E Q {(n 1/2 ∧ V (w (n) n ) + )Y -s n }. (6.10)
By definition,

Y n = n j=1 u∈I (n) j e -V (u) x∈T GW u ,|x|u=n-j min{n 1/2 , [V (u) + V u (x)] + }e -Vu(x) + min{n 1/2 , V (w (n) n ) + }e -V (w (n) n ) ≤ n j=1 e -V (w (n) j-1 ) u∈I (n) j e -∆u x∈T GW u ,|x|u=n-j [V (w (n) j-1 ) + + ∆ + u + V u (x) + ] × e -Vu(x) + Θ n ,
where ∆ u := V (u) -V (w

(n) j-1 ) [for u ∈ I (n) j ]
, and Θ n := V (w

(n) n ) + e -V (w (n) n )
. By means of the elementary inequality ( i a i ) -s ≥ ( i a s i ) -1 and ( i b i ) s ≤ i b s i for nonnegative a i and b i , we obtain Y -s n ≥ 1 Zn on S n , with Z n being defined as j e -sV (w (n)

j-1 ) u e -s∆u [(V (w (n) j-1 ) + ) s + (∆ + u ) s ] x e -Vu(x) s + x V u (x) + e -Vu(x) s + Θ s n ,
where j := n j=1 , u := u∈I (n) j , and x := x∈T GW u ,|x|u=n-j . We now condition upon G n , and note that V (w

(n) j ) and I (n) j are G n -measurable. By Proposition 2.1, E Q {Z n |G n } = j e -sV (w (n) j-1 ) u e -s∆u {((V (w (n) j-1 ) + ) s + (∆ + u ) s ) × E(W s n-j ) + E(U s n-j )} + Θ s n ,
where, for any k ≥ 0, U k := |y|=k V (y) + e -V (y) . By Jensen's inequality,

E(W s n-j ) ≤ [E(W n-j )] s = 1.
≤ u e -s∆u {(V (w (n) j-1 ) + ) s + (∆ + u ) s + c 67 } = [V (w (n) j-1 ) + ] s u e -s∆u + u e -s∆u {(∆ + u ) s + c 67 }.
There exists c 68 = c 68 (s) < ∞ such that e -sa {(a + ) s + c 67 } ≤ c 68 (e -sa + e -sa/2 ) for all a ∈ R. As a consequence,

E Q {Z n |G n } ≤ c 69 n j=1 e -sV (w (n) j-1 ) {[V (w (n) j-1 ) + ] s + 1} × u∈I (n) j
[e -s∆u + e -s/2∆u ] + Θ s n .

By Jensen's inequality again,

E Q { 1 Zn |G n } ≥ 1 E Q {Zn|Gn} . Since Y -s n ≥ 1
Zn on S n , this leads to

E Q {Y -s n |G n } ≥ c 70 n j=1 e -sV (w (n) j-1 ) {[V (w (n) j-1 ) + ] s + 1} u∈I (n) j [e -s∆u + e -s 2 ∆u ] + Θ s n .
We apply Proposition 2.1: if (S j -S j-1 , η j ), for j ≥ 1 (with S 0 := 0), are i.i.d. random variables (under Q) and distributed as (V (w (1) ), u∈I

1

[e -sV (u) + e -s/2V (u) ]), then

E Q {(n 1/2 ∧ V (w (n) n ) + )Y -s n } ≥ c 70 E Q n 1/2 ∧ S + n n j=1 e -sS j-1 [(S + j-1 ) s + 1]η j + e -sSn (S + n ) s ≥ c 70 E Q (n 1/2 ∧ S n )1 {min 1≤j≤n S j >0}
n j=1 e -sS j-1 (S s j-1 + 1)η j + e -sSn S s n .

Note that if S j > 0, then e -sS j [S s j + 1] ≤ c 71 e -tS j with t := s 2 . Therefore, by writing

Q (n) {•} := Q •| min 1≤j≤n S j > 0 , and
E (n)
Q the expectation with respect to Q (n) , and η j := η j + 1 for brevity, we get that

E Q {(n 1/2 ∧ V (w (n) n ) + )Y -s n } ≥ c 72 Q min 1≤j≤n S j > 0 E (n) Q n 1/2 ∧ S n n+1 j=1 e -tS j-1 η j ≥ c 72 Q min 1≤j≤n S j > 0 E (n) Q εn 1/2 1 {Sn>εn 1/2 } n+1 j=1 e -tS j-1 η j . Since Q{min 1≤j≤n S j > 0} ≥ c 73 n -1/2 [see (2.13)], this leads to E Q {(n 1/2 ∧ V (w (n) n ) + )Y -s n } ≥ c 74 εE (n) Q 1 {Sn>εn 1/2 } n+1 j=1 e -tS j-1 η j ≥ c 74 ε E (n) Q 1 n+1 j=1 e -tS j-1 η j -Q (n) {S n ≤ εn 1/2 } .
Let ρ(s) > 0 be as in Corollary 2.4. We have

E Q {( u∈I (1) 1 e -sV (u) ) ρ(s) } < ∞ by (2.16). Since ρ(s) ≤ ρ( s 2 ), we also have E Q {( u∈I (1) 1 e -s/2V (u) ) ρ(s) } < ∞. Therefore, E Q { η ρ(s)
1 } < ∞. We are thus entitled to apply Lemma 6.1 (stated and proved below) to see that E

(n) Q { 1 1+
n+1 j=1 e -tS j-1 η j } ≥ c 75 for some c 75 ∈ (0, ∞) and all n ≥ n 0 . Since

1 n+1 j=1 e -tS j-1 η j ≥ 1 1+ n+1 j=1 e -tS j-1 η j , this yields E Q {(n 1/2 ∧ V (w (n) n ) + )Y -s n } ≥ c 74 ε[c 75 -Q (n) {S n ≤ εn 1/2 }], n ≥ n 0 .
On the other hand, S n /n 1/2 under Q (n) converges weakly to the terminal value of a Brownian meander (see Bolthausen [START_REF] Bolthausen | A central limit theorem for two-dimensional random walks in random sceneries[END_REF]); in particular, lim ε→0 lim n→∞ Q (n) {S n ≤ εn 1/2 } = 0. We can thus choose (and fix) a small ε > 0 such that Q

(n) {S n ≤ εn 1/2 } ≤ c 75 2 for all n ≥ n 1 . Therefore, for n ≥ n 0 + n 1 , E Q {(n 1/2 ∧ V (w (n) n ) + )Y -s n } ≥ c 74 ε c 75 - c 75 2 .
As a consequence, we have proved that, for 0 < s < 1,

lim inf n→∞ E Q {(n 1/2 ∧ V (w (n) n ) + )Y -s n } > 0,
which, in view of (6.10), yields the first inequality in (1.16), and thus completes the proof of the lower bound in Theorem 1.5.

We complete the proof of Theorem 1.5 by proving the following lemma, which is a very simple variant of a result of Kozlov [START_REF] Kozlov | The asymptotic behavior of the probability of non-extinction of critical branching processes in a random environment[END_REF]. Lemma 6.1. Let {(X k , η k ), k ≥ 1} be a sequence of i.i.d. random vectors defined on (Ω, F , P) with P{η 1 ≥ 0} = 1, such that E{η θ 1 } < ∞ for some θ > 0. We assume E(X 1 ) = 0 and 0 < E(X 2 1 ) < ∞. Let S 0 := 0 and S n :=

X 1 + • • • + X n , for n ≥ 1. Then lim n→∞ E 1 1 + n+1 k=1 η k e -S k-1 min 1≤k≤n S k > 0 = c 76 ∈ (0, ∞). (6.11)
Proof. The lemma is an analogue of the identity (26) of Kozlov [START_REF] Kozlov | The asymptotic behavior of the probability of non-extinction of critical branching processes in a random environment[END_REF], except that the distribution of our η 1 is slightly different from that of Kozlov's, which explains the moment condition E{η θ 1 } < ∞: this condition will be seen to guarantee

lim j→∞ lim sup n→∞ E 1 1 + j k=1 η k e -S k-1 (6.12) - 1 1 + n+1 k=1 η k e -S k-1 min 1≤k≤n S k > 0 = 0.
The identity (6.12), which plays the role of Kozlov's Lemma 1 in [START_REF] Kozlov | The asymptotic behavior of the probability of non-extinction of critical branching processes in a random environment[END_REF], is the key ingredient in the proof of (6.11). Since the rest of the proof goes along the lines of [START_REF] Kozlov | The asymptotic behavior of the probability of non-extinction of critical branching processes in a random environment[END_REF] with obvious modifications, we only prove (6.12) here. Without loss of generality, we assume θ ≤ 2 (otherwise, we can replace θ by 2). We observe that, for n > j, the integrand in (6.12) is nonnegative, and is Let LHS (6.13) denote the n 1/2 n+1 k=j+1 E{•} expression on the left-hand side. Let S i = S i (k) := S i+k -S k , i ≥ 0. It is clear that ( S i , i ≥ 0) is independent of (η k , X 1 , . . . , X k ), and is distributed as (S i , i ≥ 0). Write S k-1 := min 1≤j≤k-1 S j and S n-k := min 1≤i≤n-k S i . Then

≤ n+1 k=j+1 η k e -S k-1 1 + n+1 k=1 η k e -S k-1 ≤ n+1 k=j+1 η k e -S k-1 1 + n+1 k=1 η k e -S k-1 θ/2 ≤ n+1 k=j+1 η k e -S k-1 θ/2 , which is bounded by n+1 k=j+1 η θ/2 k e -θ/2S k-1 . Since P{min 1≤k≤n S k > 0} ∼ c 4 /n 1/2 [see (2.
LHS (6.13) ≤ n 1/2 n+1 k=j+1 E{η θ/2 k e -θ/2S k-1 1 {S k-1 >0, S n-k >-S k-1 -X k } }.
To estimate E{•} on the right-hand side, we first condition upon (η k , S k-1 , S k-1 , X k ), which leaves us to estimate the tail probability of S n-k . At this stage, it is convenient to recall (see [START_REF] Bramson | Minimal displacement of branching random walk[END_REF] of Kozlov [START_REF] Kozlov | The asymptotic behavior of the probability of non-extinction of critical branching processes in a random environment[END_REF]) that P{ S n-k > -y} ≤ c 54 1+y + (n-k+1) 1/2 for some c 54 > 0 and all y ∈ R. Accordingly,

LHS (6.13) ≤ c 54 n 1/2 n+1 k=j+1 E η θ/2 k e -θ/2S k-1 1 {S k-1 >0} 1 + (S k-1 + X k ) + (n -k + 1) 1/2 ≤ c 54 n 1/2 n+1 k=j+1 E η θ/2 k e -θ/2S k-1 1 {S k-1 >0} 1 + S k-1 + X + k (n -k + 1) 1/2 .
On the right-hand side, (η k , X k ) is independent of (S k-1 , S k-1 ). We condition upon (S k-1 , S k-1 ): for any z ≥ 1, an application of the Cauchy-Schwarz inequality gives

E{η θ/2 k (z + X + k )} ≤ [E(η θ k )] 1/2 [E{(z + X + k ) 2 }] 1/2 . Of course, E(η θ k ) = E(η θ 1
) < ∞ by assumption, and E{(z

+ X + k ) 2 } ≤ 2E(z 2 + X 2 k ) = 2[z 2 + E(X 2 1 )]. Thus, E{η θ/2 k (z + X + k )} ≤ c 77 z for z ≥ 1. Consequently, with c 78 := c 54 c 77 , LHS (6.13) ≤ c 78 n 1/2 n+1 k=j+1 E e -θ/2S k-1 1 {S k-1 >0} 1 + S k-1 (n -k + 1) 1/2 ≤ c 79 n 1/2 n+1 k=j+1 E e -θ/3S k-1 1 {S k-1 >0} 1 (n -k + 1) 1/2 ,
the last inequality following from the fact that sup x>0 (1 + x)e -θ/6x < ∞.

We use once again the estimate (2.13), which implies

1 (n-k+1) 1/2 ≤ c 80 P{S i > S k-1 , ∀k ≤ i ≤ n}. Since (S i -S k-1 , k ≤ i ≤ n) is independent of (S k-1 , S k-1 ), this implies, with c 81 := c 79 c 80 , LHS (6.13) ≤ c 81 n 1/2 n+1 k=j+1 E{e -θ/3S k-1 1 {S k-1 >0,S i >S k-1 ,∀k≤i≤n} } Y. HU AND Z. SHI ≤ c 81 n 1/2 n+1 k=j+1 E{e -θ/3S k-1 1 {S n >0} },
where S n := min 1≤i≤n S i . It remains to check that lim j→∞ lim sup

n→∞ n 1/2 n+1 k=j+1 E{e -θ/3S k-1 1 {S n >0} } = 0. (6.14)
This would immediately follow from Lemma 1 of Kozlov [START_REF] Kozlov | The asymptotic behavior of the probability of non-extinction of critical branching processes in a random environment[END_REF], but we have been kindly informed by Gerold Alsmeyer (to whom we are grateful) of a flaw in its proof, on page 800, line 3 of [START_REF] Kozlov | The asymptotic behavior of the probability of non-extinction of critical branching processes in a random environment[END_REF], so we need to proceed differently. Since

E{e -θ/3S k-1 1 {S n >0} } ≤ n -(3/2)+o(1) (n -k + 2) -1/2 (for n → ∞) uniformly in k ∈ [ n 2 , n + 1], we have n 1/2 n+1 k=⌊n/2⌋ E{e -θ/3S k-1 1 {S n >0} } → 0, n → ∞.
On the other hand, (36) of Kozlov [START_REF] Kozlov | The asymptotic behavior of the probability of non-extinction of critical branching processes in a random environment[END_REF] (applied to δ = 1 2 and η i = 1 there) implies that lim j lim sup n n 1/2 ⌊n/2⌋ k=j+1 E{e -θ/3S k-1 1 {S n >0} } = 0. Therefore, (6.14) holds: Lemma 6.1 is proved. Upper bounds. Let ε > 0. By Theorem 1.6 and Chebyshev's inequality, P{W n,β > n -(3β/2)+ε } → 0. Therefore, W n,β ≤ n -(3β/2)+o (1) in probability, yielding the upper bound in (1.15).

The upper bound in (1.14) follows trivially from the upper bound in (1.15).

It remains to prove the upper bound in Theorem 1.3. Fix γ ∈ (0, 1). Since W γ n is a nonnegative supermartingale, the maximal inequality tells that, for any n ≤ m and any λ > 0, (P{W k,β ≤ n -(3β/2)-ε }) ⌊n 2ε ⌋ , which, according to (7.1), is bounded by n exp(-n -ε ⌊n 2ε ⌋) (for all sufficiently large n), thus summable in n. By the Borel-Cantelli lemma, almost surely for all sufficiently large n, we have either τ n = ∞, or min k∈[n/2,n] W k+τn,β > n -(3β/2)-ε exp[-β max |x|=τn V (x)]. Conditionally on the system's ultimate survival, we have 1 n max |x|=n V (x) → c 21 a.s., τ n ∼ 2ε log n log m a.s., n → ∞, and W n,β ≥ min k∈[n/2,n] W k+τn,β for all sufficiently large n. This readily yields lower bounds in (1.14) and (1.15): conditionally on the system's survival, W n,β ≥ n -(3β/2)+o (1) almost surely (and a fortiori, in probability).

P max n≤j≤m W γ j ≥ λ ≤ E(W γ n ) λ ≤ c
The lower bound in Theorem 1.3 is along exactly the same lines, but using Theorem 1.5 instead of Theorem 1.6. Wn converges to 1 in probability (conditionally on the system's survival).

Proposition 10.1. Assume (1.1), (1.2) and (1.3). For any γ > 0, there exists γ 1 > 0 such that, for all sufficiently large n,

P W n+1 W n -1 ≥ n -γ |S ≤ n -γ 1 . (10.1)
Proof. Let 1 < β ≤ min{2, 1 + ρ(1)}, where ρ(1) is the constant in Corollary 2.4.

We use a probability estimate of Petrov [START_REF] Petrov | Limit Theorems of Probability Theory: Sequences of independent random variables[END_REF], page 82: for centered random variables ξ 1 , . . . , ξ ℓ with E(|ξ i | β ) < ∞ (for 1 ≤ i ≤ ℓ), we have

E{| ℓ i=1 ξ i | β } ≤ 2 ℓ i=1 E{|ξ i | β }.
By definition, on the set S n , we have Let ε > 0 and b > 0. Let s ∈ ( β-1 β , 1). Define D n := {W n ≥ n -(1/2)-ε } ∩ {W n,β ≤ n -(3β/2)+b }. By Proposition 3.1, P{W n < n -(1/2)-ε , S } ≤ n -ϑ for some ϑ > 0 and all large n, whereas, by Theorem 1.6, P{W n,β > n -(3β/2)+b } ≤ n 3β(1-s)/2-(1-s)b E{W 1-s n,β } = n -(1-s)b+o (1) . Therefore, P{S \ D n } ≤ n -ϑ + n -(1-s)b+o (1) , n → ∞.

W n+1 W n -1 =
On the other hand, since S ⊂ S n , it follows from (10.2) and Chebyshev's inequality that, for n → ∞, We choose ε and b sufficiently small such that γβ -β + b + εβ < 0. Proposition 10.1 is proved.

P W n+1 W n -1 ≥ n -γ , D n , S ≤ n γβ E c 83 W n,β
We now have all of the ingredients needed for the proof of Theorem 1.1.

Proof of Theorem 1.1. Once Proposition 10.1 is established, the proof of Theorem 1.1 follows the lines of Biggins and Kyprianou [START_REF] Biggins | Seneta-Heyde norming in the branching random walk[END_REF].

Assume (1.1), (1.2) and (1.3). Let λ n > 0 satisfy E{(λ n W n ) 1/2 } = 1. That is,

λ n := {E(W 1/2 n )} -2
. By Theorem 1.5, we have 0 < lim inf n→∞ λn n 1/2 ≤ lim sup n→∞ λn n 1/2 < ∞, and (λ n W n ) is tight. Let W be any possible (weak) limit of (λ n W n ) along a subsequence. By Theorem 1.5 and dominated convergence, E( W 1/2 ) = 1. We now prove the uniqueness of W .

By definition,

W n+1 = |v|=1 e -V (v) x∈T GW v ,|x|v=n
e -Vv (x) .

By assumption, λ n W n → W in distribution when n goes to infinity along a certain subsequence. Thus, λ n W n+1 converges weakly (when n goes along the same subsequence) to |v|=1 e -V (v) W v , where, conditionally on (v, V (v), |v| = 1), W v are independent copies of W .

On the other hand, by Proposition 10.1, λ n W n+1 also converges weakly (along the same subsequence) to W Therefore,

W law = |v|=1 e -V (v) W v .
This is the same equation for ξ * in (3.5). Recall that (3.5) has a unique solution up to a scale change (Liu [27]), and since E( W 1/2 ) = 1, we have W It follows that, conditionally on the system's survival, λ n W n converges in distribution to W .

Theorem 1 . 2 .

 12 Assume (1.1), (1.2) and (1.3). Conditionally on the system's survival, we have

  Section 4: upper bound in part (1.8) of Theorem 1.2. • Section 5: Theorem 1.6. • Section 6: Theorem 1.5. • Section 7: Theorem 1.3, as well as parts (1.14) and (1.15) of Theorem 1.4. • Section 8: (the rest of) Theorem 1.2. • Section 9: part (1.13) of Theorem 1.4. • Section 10: Theorem 1.1.

1k

  )); (ii) conditionally on G n , the truncated shifted marked subtrees T ) under Q, given G n , is identical to the distribution of T n-|x| under P.

Corollary 2 . 2 .

 22 Assume ψ(0) > 0 and ψ(1) = 0, and fix n ≥ 1.

Fig. 1 .

 1 Fig. 1. Spine; The truncated shifted subtrees T n-|x| x ,T n-|y| y , T n-|z| z , . . . are actually rooted at e.

|x|=n |y|=m 1

 1 {x∈Ln,y∈Lm} = n k=0 |z|=k (u,v) 1 {zu∈Ln,zv∈Lm} , where the double sum (u,v) is over u, v ∈ T GW z such that |u| z = n -k and |v| z = m -k and that the unique common ancestor of u and v in T GW z is the root. Therefore,

  c 27 V n 1 {3/2 log n<V n ≤c 24 /2n}∩Sn } ≤ c 28 n c 29 , with c 29 := ( 3 2 + c 24 c 25 ε)c 27 . Therefore, E{e c 27 V n 1 {V n ≤c 24 /2n}∩Sn } ≤ c 30 n c 29 , n ≥ 1, (5.4) where c 30 := c 28 + 1.

Y

  . HU AND Z. SHI Therefore, for any c 33 < min{ c 10 c 31 , c 26 2c 31 }, sup n≥1 E{e c 33 V n 1 {c 24 /2n<V n ≤c 31 n}∩Sn } < ∞, which, combined with (5.4) and (5.5), completes the proof of Proposition 5.1, with c 22 := min{c 27 , c 32 , c 33 }.

  any pair 0 ≤ k < n, we say that the level k is n-good ifI (n) k = ∅ and T GW u survives at least n -k generations, ∀u ∈ I (n) k ,where T GW u is the shifted Galton-Watson subtree generated by u [see (2.3)]. By T GW u surviving at least n -k generations, we mean that there exists v ∈ T GW u such that |v| u = n -k [see (2.4) for notation]. In words, k is n-good means any subtree generated by any of the brothers of w (n) k has offspring for at least n -k generations.

6 24Y

 6 35 log n⌋ with c 35 := K+2 c 34 . Let c 36 := K+2 c . HU AND Z. SHI

1 Y s n 1 1 Y c 32 n 1

 1111 which, according to(3.11), is bounded by e c 44 (x κ + e -c 10 n ) for 0 < x ≤ 1 a 0 . Thus, for any fixed c > 0 and 0 < s < min{ c 10 c , κ}, we have sup n≥1 E{ {Y n≥e -cn }∩Sn } < ∞. On the other hand, let c 31 and c 32 be as in(5.5); since Y n ≥ exp{-inf |u|=n V (u)}, it follows from (5.5) that sup n≥1 E{ {Y n<e -c 31 n }∩Sn } < ∞. As a consequence,

k

  [START_REF] Bramson | Minimal displacement of branching random walk[END_REF])], we only need to check that lim e -θ/2S k-1 1 {min 1≤i≤n S i >0} } = 0. (6.[START_REF] Bramson | Minimal displacement of branching random walk[END_REF]

7 .

 7 Proof of Theorem 1.3 and (1.14)-(1.15) of Theorem 1.4. In this section we prove Theorem 1.3, as well as parts (1.14)-(1.15) of Theorem 1.4. We assume (1.1), (1.2) and (1.3) throughout the section. Proof of Theorem 1.3 and (1.14) and (1.15) of Theorem 1.4.

82 λn γ/ 2 ,

 2 the last inequality being a consequence of Theorem 1.5. Let ε > 0 and let n k := ⌊k 2/ε ⌋.Then k P{max n k ≤j≤n k+1 W γ j ≥ n -(γ/2)+ε k } < ∞. By the Borel-Cantelli lemma, almost surely for all large k, max n k ≤j≤n k+1 W j < n -(1/2)+(ε/γ) k. Since ε γ can be arbitrarily small, this yields the desired upper bound:W n ≤ n -(1/2)+o(1) a.s.Proof of Theorem 1.3 and (1.14) and (1.15) of Theorem 1.4. Lower bounds. To prove the lower bound in (1.14) and (1.15), we use the Paley-Zygmund inequality and Theorem 1.6 to see thatP{W n,β > n -(3β/2)+o(1) } ≥ n o(1) , n → ∞. (7.1)This is the analogue of (4.5) for W n . From here, the argument follows the lines in the proof of the upper bound in (1.8) of Theorem 1.2 (Section 4), and goes as follows: let ε > 0 and let τ n := inf{k ≥ 1 : #{u : |u| = k} ≥ n 2ε }.Then P τ n < ∞, min k∈[n/2,n] W k+τn,β ≤ n -(3β/2)-ε exp -β max |x|=τn V (x) ≤ k∈[n/2,n] P τ n < ∞, W k+τn,β ≤ n -(3β/2)-ε exp -β max |x|=τn V (x) ≤ k∈[n/2,n]

8 .

 8 Proof of Theorem 1.2. Assume (1.1), (1.2) and(1.3). Let β > 1. We trivially have W n,β ≤ W n exp{-(β -1) inf |u|=n V (u)} and W n,β ≥ exp{-β × inf |u|=n V (u)}. Therefore, 1 β log 1 W n,β ≤ inf |u|=n V (u) ≤ 1 β-1 log Wn W n,β on S n . Since β can be as large as possible, by means of Theorem 1.3 and of parts (1.14) and (1.15) of Theorem 1.4, we immediately get (1.7) and (1.9).Since W n ≥ exp{-inf |u|=n V (u)}, the lower bound in (1.8) follows immediately from Theorem 1.3, whereas the upper bound in (1.8) was already proved in Section 4.

9 .

 9 Proof of part (1.13) of Theorem 1.4. The upper bound follows from Theorem 1.3 and the elementary inequality W n,β ≤ W β n , the lower bound from (1.8) and the relation W n,β ≥ exp{-β inf |u|=n V (u)}.

10 .

 10 Proof of Theorem 1.1. The proof of Theorem 1.1 relies on Theorem 1.5 and a preliminary result, stated below as Proposition 10.1. Theorem 1.5 ensures the tightness of (n 1/2 W n , n ≥ 1), whereas Proposition 10.1 implies that W n+1

e,

  -Vu(x) -1 ,where T GW and |x| u are as in (2.1) and (2.4), respectively. Conditioning on F n , and applying Proposition 2.1 and Petrov's probability inequality recalled above, we see that, on S n , where c 83 := 2E{| |v|=1 e -V (v) -1| β } < ∞ [see (2.16)], and W n,β is as in(1.11).

W β n 1

 1 Dn∩Sn≤ c 83 n γβ-(3β/2)+b+[(1/2)+ε]β .MINIMAL POSITION, BRANCHING RANDOM WALKS47As a consequence, when n → ∞,P W n+1 W n -1 ≥ n -γ , S ≤ n -ϑ + n -(1-s)b+o(1) + c 83 n γβ-β+b+εβ .

law=

  c 84 ξ * , with c 84 := [E{(ξ * ) 1/2 }] -2 . The uniqueness (in law) of W shows that λ n W n converges weakly to W when n → ∞. By (3.3), P{W n > 0} = P{S n } → P{S } = P{ξ * > 0}. Let W > 0 be a random variable such that E(e -aW ) = E(e -a W | W > 0), ∀a ≥ 0. (10.3)

c 7 e -c 8 x , where c 7

	+ ) ,
	which is finite [by (1.2) and (1.1)]. This implies (2.16).
	To prove (2.17), we write A := {sup |u|=1 |V (u)| ≥ x}. By Chebyshev's
	inequality, P(A) ≤

  1/2+ε ; thus, E Q {[n 1/2 + S + n ]e sS n × 1 Bn∩{n-ϑn<2c 35 log n} } ≤ 2n 1/2+ε E Q {e sS n 1 {n-ϑn<2c 35 log n} }. It is clear that S n ≤ S ⌊n/2⌋ := min 0≤i≤n/2 S i , and that {n -ϑ n < 2c 35 log n} ⊂ { n 2 -ϑ n/2 < 2c 35 log n}, where ϑ n/2 := min{k ≥ 0 : S k = min 0≤i≤n-⌊n/2⌋ S i }, with S i := S i+⌊n/2⌋ -S ⌊n/2⌋ , i ≥ 0. Since S ⌊n/2⌋ and ϑ n/2 are independent, we have E Q {e sS n 1 {n-ϑn<2c 35 log n} } ≤ E Q {e sS ⌊n/2⌋ }Q{ n 2 -ϑ n/2 < 2c 35 log n}. By (2.14), E Q {e sS ⌊n/2⌋ } ≤ c 62 n -1/2 ; on the other hand, Q{ n 2 -ϑ n/2 < 2c 35 log n} ≤ c 63

  On the other hand, by (3.9), U k ≤ c 65 log 1

	W * k ] s } ≤ c 66 . Therefore, the n , of course) is 65 E{[log 1 k ) ≤ c s and, thus, by Lemma 3.3, E(U s W * k u sum on the right-hand side (without Θ s

Acknowledgments. We are grateful to Bruno Jaffuel, Gerold Alsmeyer, John Biggins and Alain Rouault for pointing out errors in the first versions of the manuscript, and to John Biggins for fixing Lemma 3.2. We also wish to thank two referees for their careful reading and for very helpful suggestions, without which we would not have had enough courage to remove the uniform ellipticity condition in the original manuscript.