Xinxin Chen

Hui He

On large deviation probabilities for empirical distribution of branching random walks: Schröder case and Böttcher case

Keywords: Mathematics Subject Classifications (2010): 60J60, 60F10 Branching random walk, large deviation, Schröder case, Böttcher case

Given a super-critical branching random walk on R started from the origin, let Z n (•) be the counting measure which counts the number of individuals at the n-th generation located in a given set. Under some mild conditions, it is known in [5] that for any interval A ⊂ R, Zn( √ nA) Zn(R) converges a.s. to ν(A), where ν is the standard Gaussian measure. In this work, we investigate the convergence rates of

for ∆ ∈ (0, 1 -ν(A)), in both Schröder case and Böttcher case.

Introduction and Main results

Branching random walk and its empirical distribution

Branching random walk, as an interesting object in probability theory, has been widely considered and well studied these years. The recent developments can be referred to Hu-Shi [START_REF] Hu | Minimal position and critical martingale convergence in branching random walks, and directed polymers on disordered trees[END_REF], Shi [START_REF] Shi | Branching random walks. École d' Été[END_REF]. On the other hand, this object is closely related to many other random models, for example, multiplicative cascades, random fractals and random walk in random environment (see e.g. Hu-Shi [START_REF] Hu | A subdiffusive behaviour of recurrent random walk in random environment on a regular tree[END_REF][START_REF] Hu | The slow regime of randomly biased walks on trees[END_REF], Liu [START_REF] Liu | Fixed points of a generalised smoothing transformation and applications to branching processes[END_REF][START_REF] Liu | On generalised multiplicative cascades[END_REF]).

Generally speaking, in a branching random walk, the point processes independently produced by the particles, formulated by the number of children and their displacements, all follow the so-called reproduction law. However, in this work, we consider a simpler model by assuming that the number of children and the motions are independent. Let us construct it in the following way.

We take a Galton-Watson tree T , rooted at ρ, with offspring distribution {p k ; k ≥ 0}. For any u, v ∈ T , we write u v if u is an ancestor of v or u = v. Moreover, to each node v ∈ T \ {ρ}, we attach a real-valued random variable X v and define its position by

S v := ρ≺u v X u .
Let S ρ := 0 for convenience. Suppose that given the tree T , {X v ; v ∈ T \ {ρ}} are i.i.d. copies of some random variable X (which is called step size). Thus, {S u ; u ∈ T } is a branching random walk. For any n ∈ N, we introduce the following counting measure

Z n (•) = |v|=n,v∈T 1 {Sv∈•} ,
where |v| denotes the generation of node v, i.e., the graph distance between v and ρ. Apparently, Z 0 = δ 0 .

In this article, we always suppose that p 0 = 0, p 1 < 1. Note immediately that {Z n (R); n ≥ 0} is a supercritical Galton-Watson process with mean m := k≥1 kp k > 1. Assume that m < ∞. It is well known that the martingale

W n := Z n (R)
m n converges almost surely to some non-degenerate limit W if and only if k log kp k < ∞ (see e.g. [START_REF] Athreya | Branching Processes[END_REF]). Naturally, a central limit theorem on Z n (•), was conjectured by Harris [START_REF] Harris | The theory of branching processes[END_REF] and was proved by Asmussen-Kaplan [START_REF] Asmussen | Branching random walk I[END_REF], then was extended by Klebaner [START_REF] Klebaner | Branching random walk in varying environments[END_REF] and Biggins [START_REF] Biggins | The central limit theorem for the supercritical branching random walk, and related results[END_REF]. It says that if the step size X has zero mean and finite variance σ 2 , for A ∈ A 0 := {(-∞, x]; x ∈ R},

lim n→∞ Z n ( √ nσ 2 A) m n = ν(A)W, a.s. (1.1)
where ν is the standard Gaussian measure on R. Let Zn (•) := Zn(•) Zn(R) be the corresponding empirical distribution. Then, lim n→∞ Zn (

√ nσ 2 A) = ν(A), a.s. (1.2)
What interests us is the convergence rates of (1.1) and (1.2).

In the literature, Asmussen and Kaplan [START_REF] Asmussen | Branching random walk I[END_REF] proved that if

x n = (σ √ n)x + o( √ n) with x ∈ R, then lim n→∞ E m -n Z n ((-∞, x n ]) -ν((-∞, x])W 2 = 0.
Recently, Chen [START_REF] Chen | Exact convergence rates for the distribution of the particles in branching random walks[END_REF], under some regular assumptions, proved that as n → ∞,

Z n ( √ nσ 2 A) m n -ν(A)W = 1 √ n ξ(A) + o( 1 √ n
), a.s. (1.3) where ξ(A) is some explicitly defined random variable. Later, Gao and Liu [START_REF] Gao | Exact convergence rates in central limit theorems for a branching random walk with a random environment in time[END_REF] generalized this convergence for a branching random walk in some random environment. They also, in [START_REF] Gao | Second and third orders asymptotic expansions for the distribution of particles in a branching random walk with a random environment in time[END_REF], obtained the second and third orders in this asymptotic expansion. In particular, if A = R, one can refer to [START_REF] Heyde | Some central limit analogues for supercritical Galton-Watson processes[END_REF] and [START_REF] Athreya | Large Deviation Rates for branching processes-I. Single type case[END_REF] for convergence rate of W n to W . Furthermore, by taking A a singleton, the local version of this convergence has been investigated by Révész [START_REF] Révész | Random walks of infinitely many particles[END_REF], Chen [START_REF] Chen | Exact convergence rates for the distribution of the particles in branching random walks[END_REF] and Gao [START_REF] Gao | Exact convergence rate of the local limit theorem for branching random walks on the integer lattice[END_REF], even in higher dimensions.

In this paper, we aim at understanding the so-called large deviation behaviour of the convergence (1.2), by considering the decaying rate of the following probability

P Zn ( √ nσ 2 A) -ν(A) ≥ ∆ , (1.4)
with ∆ > 0 a small constant.

In fact, this problem has been investigated by Louidor and Perkins [START_REF] Louidor | Large deviations for the empirical distribution in the branching random walk[END_REF] by assuming that p 0 = p 1 = 0 (Böttcher case) and that X is simple random walk's step. Recently, Louidor and Tsairi [START_REF] Louidor | Large deviations for the empirical distribution in the general branching random walk[END_REF] extend this result to the Böttcher case with bounded step size by allowing dependence between the motions of children and their numbers. However, if X is not bounded, its tail distribution will be involved in the arguments and many regimes will appear in the asymptotic behaviours of (1.4).

In what follows, we will consider (1.4) in the Böttcher case by assuming that the step size X has either Weibull tail distribution or Gumbel tail distribution. Also, we will study this problem in the Schöder case where p 1 > 0 = p 0 .

Main results

In the following of this paper, we always assume that , E(e θZ 1 (R) ) = k≥0 p k e θk < ∞, for some θ > 0, (1.5) and that X is symmetric, with E[X 2 ] = σ 2 = 1.

(1.6)

Remark 1.1. The assumption of symmetry of X is not necessary, but simplifies the proof. As long as Λ(•), defined in (1.9) below, is finite on an open interval including 0, our arguments work.

The exact value of E[X 2 ] does not play crucial role in our arguments either, but simplifies notion. We only need that X satisfies the classic central limit theorem.

Before stating our main results, we first introduce some notations. Let A be the algebra generated by {(-∞, x], x ∈ R}. For p ∈ (ν(A), 1) with A ∈ A \ ∅ such that ν(A) > 0, define

I A (p) = inf {|x| : ν(A -x) ≥ p} ;
(1.7)

J A (p) = inf y : sup x∈R ν((A -x)/ 1 -y) ≥ p, y ∈ [0, 1] . (1.8)
We say that X fulfills Cramér's condition if E[e κX ] < ∞, for some κ > 0. In this case, we can define the so-called logarithmic moment generating function and its inverse: for any t ∈ R and

s ∈ R + , Λ(t) =: log E[e tX ] ∈ [0, ∞] and Λ -1 (s) := inf{t > 0 : Λ(t) ≥ s}, (1.9)
with the convention that inf ∅ = sup{t > 0 : Λ(t) < ∞}.

Theorem 1.1 (Schröder case). Assume that p 1 > p 0 = 0 and X fulfills Cramér's condition. For p ∈ (ν(A), 1), if I A (p) < ∞ and I A (p) is continuous at p, then

lim n→∞ 1 √ n log P Zn ( √ nA) ≥ p = -Λ -1 (log 1 p 1 )I A (p).
Remark 1.2. If we replace Cramér's condition in above theorem by P(X > z) = Θ(1)e -λz α as z → ∞ with λ > 0 and 0 < α < 1, then using same idea of proving (1.10) below, we may have

lim n→∞ 1 n α/2 log P Zn ( √ nA) ≥ p = -λI A (p) α . Theorem 1.2 (Schröder case). Assume that p 1 > p 0 = 0. For p ∈ (ν(A), 1), if I A (p) = ∞ and J A (p) is continuous at p, then lim n→∞ 1 n log P Zn ( √ nA) ≥ p = (log p 1 )J A (p).
The next theorems concern the Böttcher case where p 0 = p 1 = 0. If I A (p+) = I A (p) < ∞, the decaying rate of (1.4) depends on the tail distribution of X, and also on the tree structure. In the following two theorems, we study two typical tail distributions of step size X: Weibull tail and Gumbel tail. Besides, we introduce b := min{k ≥ 1 : p k > 0} and B := sup{k ≥ 1 :

p k > 0} ∈ [b, ∞].
Theorem 1.3 (Böttcher case, Weibull tail). Assume that p 0 = p 1 = 0. Suppose P(X > z) = Θ(1)e -λz α as z → ∞ for some constant α > 0 and λ > 0. Take p ∈ (ν(A), 1) such that I A (p) < ∞ and I A (p) is continuous at p.

1. If α ≤ 1 and B > b, then lim n→∞ 1 n α/2 log P Zn ( √ nA) ≥ p = -λI A (p) α . (1.10) 2. If α > 1 and B > b, then lim n→∞ (log n) α-1 n α/2 log P Zn ( √ nA) ≥ p = - 2 log b log B α(log B -log b) α-1 λI A (p) α .
(1.11)

3. If B = b, then there exist C α > c α > 0 such that -C α ≤ lim inf n→∞ 1 n α/2 log P Zn ( √ nA) ≥ p ≤ lim sup n→∞ 1 n α/2 log P Zn ( √ nA) ≥ p ≤ -c α .
(1.12)

Theorem 1.4 (Böttcher case, Gumbel tail). Assume that p 0 = p 1 = 0. Suppose P(X > z) = Θ(1)e -e z α as z → ∞ for some constant α > 0. For p ∈ (ν(A), 1) such that I A (p) < ∞ and I A (p) is continuous at p, we have

lim n→∞ n -α 2(α+1) log -log P Zn ( √ nA) ≥ p = (y α I A (p) log b) α α+1 , (1.13)
where y α := (1+α) log B (1+α) log B-log b . Remark 1.3. To obtain the exact decaying rates, we take advantage of the randomness of the embedding tree in the arguments. However, if we consider a regular tree (B = b) and motions with Weibull tail, such idea does not work any more and the situation becomes more delicate. We believe that in this case, there is a close link between the decaying rate and the a.s. convergence (1.3).

To accomplish this work, we also state the result when X is bounded, which is obtained by Louidor and Tsairi in [START_REF] Louidor | Large deviations for the empirical distribution in the general branching random walk[END_REF]. Theorem 1.5 (Böttcher case, Theorem 1.2 of [START_REF] Louidor | Large deviations for the empirical distribution in the general branching random walk[END_REF]). Assume that p 0 = p 1 = 0. If ess sup X = L for some 0 < L < ∞, for p ∈ (ν(A), 1) such that I A (p) < ∞ and I A (p) is continuous at p, we have

lim n→∞ 1 n 1/2 log -log P Zn ( √ nA) ≥ p = I A (p) log b L . (1.14)
The following result is universal, regardless of the tail distribution of X, when

I A (p) = ∞.
Theorem 1.6 (Böttcher case, Theorem 1.2 of [START_REF] Louidor | Large deviations for the empirical distribution in the general branching random walk[END_REF]). Assume that p 0 = p 1 = 0. For p ∈ (ν(A), 1) such that I A (p) = ∞ and J A (p) is continuous at p, we have

lim n→∞ 1 n log -log P Zn ( √ nA) ≥ p = J A (p) log b.
At the end of this section, let us say a couple of words on strategy of proofs, which is partially inspired by that of Loudior and Perkins. To have { Zn ( √ nA) ≥ p}, we take an intermediate generation t n and suppose that most individuals at this generation are positioned around x √ n, so that finally Zn (

√ nA) ≈ ν n-tn ( √ n(A -x)) ≈ ν( n n-tn (A -x)) p.
This brings out the definitions of I A (p) and J A (p). If I A (p) < ∞, we take t n = o(n); otherwise, we take t n = Θ(n). Moreover, the effort made up to generation t n depends not only on branching but also on motions, which brings out the different treatments in different regimes.

The rest of this paper is organised as follows. In Sect. 2, we present some basic facts on random walks and branching random walks which will be used frequently in our proofs of main results. We study the Schröder case in Sect. 3, where Theorems 1.1 and 1.2 are proved. In Sect. 4, Böttcher case is treated. Theorems 1.3 and 1.4 will be proved. Let C 1 , C 2 , • • • and c 1 , c 2 , • • • denote positive constants which might change from line to line. As usual, f n = O(g n ) or f n = O(1)g n mean that f n ≤ Cg n for some C > 0 and all n ≥ 1. f n = Θ(1)g n means that f n is bounded both above and below by g n asymptotically. f n = o(g n ) or f n = o n (1)g n mean that lim n→∞ fn gn = 0.

Preliminary results

In this section, we present some well-known facts and useful lemmas, which will be applied frequently in the next sections. Denote by ν

n := P X * • • • * P X n times
, the distribution of a X-random walk at the n-th step. Recall that ν represents the standard normal distribution on the real line. The following lemma states some basic facts about ν and ν n .

Lemma 2.1. Let A ∈ A \ ∅ and p ∈ (0, 1).

1. The mapping (a, b) → ν(aA + b) ∈ C ∞ (R 2 )
. Moreover, it is Lipschitz on b and is uniformly continuous on K × R for any compact set K.

If 0 < I

A (p) < ∞, then there exists x ∈ R with |x| = I A (p) such that ν(A -x) ≥ p.
3. 0 ≤ J A (p) < 1 and there exists x ∈ R and r ∈ (0, 1) with r = J A (p) such that ν((A -

x)/ √ 1 -r) ≥ p.
4. If p > ν(A), then either 0 < I A (p) < ∞ or I A (p) = ∞, J A (p) ∈ (0, 1).

(i)

Let A - ε := {x ∈ A : B(x, ε) ⊂ A} be the ε-interior of A, and

A + ε := ∪ x∈A B(x, ε) be the ε-neighbourhood of A. Then A - ε ⊂ ∩ y∈[-ε/2,ε/2] (A -y) and A \ A - ε ⊂ (∂A) + ε and ∪ y∈[-ε/2,ε/2] (A -y) ⊂ A + ε and A + ε \ A ⊂ (∂A) + ε , where (∂A) + ε is the ε-neighbourhood of ∂A and lim ε↓0 ν((∂A) + ε ) = ν(∂A) = 0. (ii) Moreover, sup x∈R |ν(A + ε -x) -ν(A -x)| = sup x∈R |ν(A + ε \ A -x)| ≤ sup x ν((∂A -x) + ε ).
If Leb(•) is the Lebesgue measure on R, we have Leb(∂A) = ν(∂A) = 0, and

sup x ν((∂A -x) + ε ) ≤ Leb((∂A) + ε ) → 0, as ε ↓ 0.
6. As ν(∂A) = 0, for any l > 1, we have the following uniform convergence,

lim n→∞ sup a∈[l -1 ,l] sup b∈R ν n ( √ n(aA + b)) -ν(aA + b) = 0.
In fact, (1)-( 4) and ( 6) can be found in Lemmas 2.1, 2.2 and 2.4 of [START_REF] Louidor | Large deviations for the empirical distribution in the branching random walk[END_REF], ( 5) is a basic property. So we feel free to omit its proof.

Let M be the collection of locally finite counting measures on R. For any ζ ∈ M which is finite, we can write it as

ζ = |ζ| i=1 δ x i with x i ∈ R
P   Zζ n (A) > 1 |ζ| x∈ζ ν n (A -x) + ∆   ≤ C 1 e -C 2 ∆ 2 |ζ| , (2.1)
The same holds if >, +∆ are replaced by <, -∆, respectively.

The next two lemmas are slightly stronger versions of (1.2).

Lemma 2.3. Let A ∈ A \ ∅. Let {a n : n ≥ 1} and {b n : n ≥ 1} be two deterministic sequences such that a n → 1 and b n → 0. Then as n → ∞,

Zn ( √ n(a n A + b n )) a.s. -→ ν(A). (2.2)
We feel free to omit its proof as it is a direct consequence of (1.2).

Lemma 2.4. Take the same assumptions as in Lemma 2.3. Then for any finite ζ ∈ M, as n → ∞,

Z√ nζ n ( √ n(a n A + b n )) a.s. -→ x∈ζ ν(A -x)W x x∈ζ W x , (2.3)
where √ nζ = x∈ζ δ x √ n and {W x : x ∈ ζ} are i.i.d. random variables distributed as W .

Proof. For any A ∈ A and x ∈ R, as n → ∞,

Z δ x √ n n ( √ nA) m n -W ν(A -x) a.s.
-→ 0.

This convergence, together with the branching property of Galton-Watson process, gives

Z√ nζ n ( √ nA) a.s. -→ x∈ζ ν(A -x)W x x∈ζ W x . (2.4)
We thus conclude by Lemma 2.3.

When p 1 > 0, denote by χ the so-called Schröder constant with

m -χ = p 1 . (2.5)
We also recall here a result from Lemma 13 in [START_REF] Fleischmann | Large deviations for sums indexed by the generations of a Galton-Watson process[END_REF]. Note that Z n (R) = |Z n | for the counting measure Z n .

Lemma 2.5. If p 1 > 0, then there exists a constant C 3 > 0 such that

P (|Z n | = k) ≤ C 3 1 k ∧ k χ-1 p n 1 , ∀k, n ≥ 1. (2.6)
The next lemma is the well-known Cramér theorem; see Theorem 3.7.4 in [START_REF] Dembo | Large Deviation Techniques and Applications[END_REF]. Recall that ν n the distribution of a X-random walk at n-th step.

Lemma 2.6. If E[e κX ] < ∞ for some κ > 0, for any a > 0 and ε > 0, as n → ∞,

lim n→∞ 1 n log ν n ((-(a + )n, -an]) = -γ(a) := -sup t>0 {at -Λ(t)}. (2.7)
For a < 0, we have a similar result with γ(a) = γ(-a). This result follows immediately from Cramér's theorem, which says that for any a > 0,

lim n→∞ 1 n log ν n ((-∞, -an]) = -γ(a),
where the rate function γ(a) ≥ 0 and convex.

3 Schröder case For the lower bound, we will make a single branch up to some generation O( √ n), and the random walk along this branch moves to the level x √ n so that the descendants at the n-th generation behave like Zn ( √ nA) ≈ ν(A -x) ≥ p with high probability. For the upper bound, we will begin with a rough bound. Then an iteration method will be applied to improve the bound and to obtain the exact limit.

Lower bound

Recall Λ(t) = log E[e tX ], (1.9) and (2.7). Define Λ(p 1 ) := inf

a>0 log 1 p 1 + γ(a) a .
One could check that We only consider the case where x < 0. The case where x > 0 can be treated similarly. For any a > 0, let C a := I A (p)+ε a and t n := C a √ n . Note that -aC a = x. Observe that for any η > 0,

Λ(p 1 ) = Λ -1 (log 1 p 1 ) ∈ (0, ∞). ( 3
P( Zn ( √ nA) ≥ p) ≥ P Zn ( √ nA) ≥ p, Z tn (R) = Z tn ((-a(1 + η)t n , -at n ]) = 1
which by Markov property at time t n implies that,

P( Zn ( √ nA) ≥ p) ≥ P (Z tn (R) = Z tn ((-a(1 + η)t n , -at n ]) = 1) inf y∈(-a(1+η)tn,-atn] P Zδy n-tn ( √ nA) ≥ p = p tn 1 ν tn (-(a(1 + η)t n , -at n ]) inf y∈((1+η)x √ n,x √ n] P Zn-tn ( √ nA -y) ≥ p . (3.3)
It remains to treat the probability on the right hand side. Let A(x, η)

:= ∩ y 0 ∈((1+η)x,x] (A -y 0 ). Observe that for any y ∈ (-a(1 + η)C a √ n, -aC a √ n], Zn-tn ( √ nA -y) ≥ Zn-tn ( √ nA(x, η)) = Zn-tn √ n -t n √ n √ n -t n A(x, η) .
On the other hand, by ( 5) of Lemma 2.1, for η > 0 small enough,

ν(A(x, η)) ≥ ν(A -x) -δ/2 ≥ p + δ/2. It follows that inf y∈((1+η)x √ n,x √ n] P Zn-tn ( √ nA -y) ≥ p ≥ P Zn-tn √ n -t n √ n √ n -t n A(x, η) ≥ p ≥ P Zn-tn √ n -t n √ n √ n -t n A(x, η) ≥ ν(A(x, η)) -δ/2 ,
which, as n → ∞, converges to 1 in view of Lemma 2.3. Going back to (3.3), this means that for η > 0 small enough and n large enough,

P( Zn ( √ nA) ≥ p) ≥ 1 2 p tn 1 ν tn (-a(1 + η)t n , -at n ] .
This yields that lim inf

n→∞ 1 √ n log P Zn ( √ nA) ≥ p ≥ C a log p 1 + lim inf n→∞ C a t n log ν tn (-a(1 + η)t n , -at n ] ,
which, by (2.7), implies

lim inf n→∞ 1 √ n log P Zn ( √ nA) ≥ p ≥ -C a log 1 p 1 + γ(a) .
As the limit on the right hand side does not depend on a, we obtain that lim inf

n→∞ 1 √ n log P Zn ( √ nA) ≥ p ≥ -(I A (p) + ε) inf a>0 log 1 p 1 + γ(a) a = -(I A (p) + ε) Λ(p 1 ),
which implies the lower bound.

Remark 3.1. If X is a simple random walk, then we have

Λ(p 1 ) = log 1 + 1 -p 2 1 -log p 1 ∈ (0, ∞).

Upper bound

In this subsection, we are going to show that lim sup

n→∞ 1 √ n log P Zn ( √ nA) ≥ p ≤ -I A (p) Λ(p 1 ). (3.4)
We believe that the strategy of lower bound is somehow optimal. For the upper bound, we consider also some intermediate generation of order O( √ n), where, to get { Zn ( √ nA) ≥ p}, the population size should be atypically small and the extreme positions should be close to ±I A (p) √ n.

For ε ∈ (0, 1/2) small, a ∈ R + , define

N (a) = [a(1 -ε) √ n] and B n := [-I A (p)(1 -ε) √ n, I A (p)(1 -ε) √ n].
Moreover, there exists δ ∈ (0, p -ν(A)) small enough such that

sup z∈Bn/ √ n ν(A -z) ≤ p -δ. (3.5)
The following lemma states the idea presented at the beginning of this section. It gives also a rough upper bound. Let M B be the collection of all locally finite counting measures on R which vanish outside

B; i.e., M B = {ζ ∈ M : ζ(B c ) = 0}. Recall that |ζ| is the total mass of ζ ∈ M. Lemma 3.2.
Suppose that all assumptions in Theorem 1.1 hold. Then there exists α > 0, such that for a = I A (p)α and n large enough,

P(Z N (a) (B c n ) ≥ 1) = o n (1)P( Zn ( √ nA) ≥ p) (3.6)
Moreover, we have

P( Zn ( √ nA) ≥ p) = (1 + o n (1))P(Z N (a) ∈ M Bn , |Z N (a) | ≤ n, Zn ( √ nA) ≥ p). (3.7)
Consequently, there exists some constant C 4 > 0 such that for all n ≥ 1,

P( Zn ( √ nA) ≥ p) ≤ C 4 p αI A (p)(1-ε) √ n 1 (3.8)
Proof. The proof will be divided into two subparts. Subpart 1: We shall prove (3.6). Observe that by symmetry of ν N and Markov inequality,

P(Z N (a) (B c n ) ≥ 1) ≤ 2P Z N (a) [I A (p)(1 -ε) √ n, +∞) ≥ 1 ≤ 2E Z N (a) [I A (p)(1 -ε) √ n, +∞) = 2m N (a) ν N (a) [I A (p)(1 -ε) √ n, +∞) .
By Chernoff bound of Cramér's theorem, one sees that

ν N (a) [I A (p)(1 -ε) √ n, +∞) = ν N (a) I A (p) a N (a), +∞ ≤ exp -N (a)γ I A (p) a ,
which implies that

P(Z N (a) (B c n ) ≥ 1) ≤2e -N (a)(γ( I A (p) a )-log m) =2e - √ n(1-ε)(aγ( I A (p) a )-a log m) . (3.9) Meanwhile, lim a↓0 a(γ(I A (p)/a) -log m) = I A (p) lim a→+∞ γ(a) -log m a = I A (p) lim a→+∞ γ(a) + log 1 p 1 a > I A (p) Λ(p 1 ).
where the inequality follows from the definition of Λ(p 1 ). Therefore, for any α ∈ (0, 1) small enough and any ε > 0 small enough, with a = I A (p)α, we have lim sup

n 1 √ n log P(Z N (a) (B c n ) ≥ 1) ≤ -(1 + ε)I A (p) Λ(p 1 ).
Therefore, in view of the lower bounded obtained in Lemma 3.1, one could choose α > 0 and ε 0 > 0 sufficiently small such that for ε ∈ (0, ε 0 ),

P(Z N (a) (B c n ) ≥ 1) = o n (1)P( Zn ( √ nA) ≥ p),
which is just (3.6).

P(Z N (a) ∈ M Bn , Zn ( √ nA) ≥ p) = ζ∈M Bn P(Z N (a) = ζ, Zn ( √ nA) ≥ p) = ζ∈M Bn P(Z N (a) = ζ)P Zζ n-N (a) ( √ nA) ≥ p . (3.10)
By ( 1) and ( 6) of Lemma 2.1, we have

sup z∈Bn |ν n-N (a) ( √ nA -z) -ν(A - z √ n )| = o n (1).
So, by (3.5), for n large enough and any ζ ∈ M Bn , one has

p ≥ sup z∈Bn ν(A - z √ n ) + δ ≥ 1 |ζ| z∈ζ ν n-N (a) ( √ nA -z) + δ/2.
Therefore, (3.10) becomes

P(Z N (a) ∈ M Bn , Zn ( √ nA) ≥ p) ≤ ζ∈M Bn P(Z N (a) = ζ)P   Zζ n-N (a) ( √ nA) ≥ 1 |ζ| z∈ζ ν n-N (a) ( √ nA -z) + δ/2   , which, by Lemma 2.2, is bounded by C 1 ζ∈M Bn P(Z N (a) = ζ)e -C 2 |ζ|δ 2 /4
. This gives that

P(Z N (a) ∈ M Bn , Zn ( √ nA) ≥ p) ≤ C 1 ∞ k=1 P(|Z N (a) | = k)e -c 1 k . (3.11)
As a consequence of (2.6),

P(Z N (a) ∈ M Bn , Zn ( √ nA) ≥ p) ≤ c 2 p N (a) 1
.

(3.12)

Furthermore, following the same arguments to get (3.11), we have

P(Z N (a) ∈ M Bn , |Z N (a) | ≥ n, Zn ( √ nA) ≥ p) ≤ C 1 ∞ k=n P(|Z N (a) | = k)e -c 1 k ≤ C 1 e -c 1 n = o n (1)P( Zn ( √ nA) ≥ p), (3.13)
where the last equality follows from Lemma 3.1. Then (3.6) and (3.13) yield that

P( Zn ( √ nA) ≥ p) ≤ P Z N (a) / ∈ M Bn + P Z N (a) ∈ M Bn , Zn ( √ nA) ≥ p = o n (1)P Zn ( √ nA) ≥ p + P(Z N (a) ∈ M Bn , |Z N (a) | < n, Zn ( √ nA) ≥ p), (3.14)
which, together with (3.12), gives (3.7) and (3.8).

More generally, for ρ n = 1 + o n (1), we also have

P( Zn ( √ n(ρ n A)) ≥ p) ≤ C 5 e -log 1 p 1 I A (p)α(1-ε) √ n .
The arguments above still work by remarking (1) of Lemma 2.1 which says that

sup A∈A |ν(ρ n A) -ν(A)| = O(|ρ n -1|) = o n (1)
and that sup

A∈A |ν(A -z) -ν(A -y)| = O(|y -z|).
In what follows, we fix α > 0, the real number taken in the previous lemma and take ε ∈ (0, ε 0 ).

Here is the key lemma for the iteration of the upper bound.

Lemma 3.3. Suppose that all assumptions in Theorem 1.1 hold. Take ρ n = 1 + o n (1). If we have lim sup

n log P( Zn ( √ nρ n A) ≥ p) √ n ≤ -LI A (p), (3.15)
for some L > 0, then lim sup

n log P( Zn ( √ nρ n A) ≥ p) √ n ≤ -F (L)I A (p), (3.16)
where

F (L) := α inf u∈R log 1 p 1 + γ(u) -uL + L with α > 0 chosen in Lemma 3.2.
Remark 3.2. By Lemma 3.2, we could take L = α log 1 p 1 . One can see that

F (L) ≤ Λ(p 1 ) for L ≤ Λ(p 1 ) in Lemma A.1.
Proof. Recall that a = αI A (p) is fixed here. By (3.7), it suffices to consider

P(Z N (a) ∈ M Bn , |Z N (a) | < n, Zn ( √ nρ n A) ≥ p) with N (a) = [a(1 -ε) √ n].
In the rest of this proof, we write N and B for N (a) and B n , respectively. Let

ρ n := ρ n √ n √ n-N . We observe that given {Z N = ζ}, Zn ( √ nρ n A) = Zζ n-N ( √ nρ n A) ≤ max z∈ζ Zz n-N ( √ n -N (ρ n A)), (3.17)
where the last inequality follows from the elementary inequality

k i=1 a i k i=1 b i ≤ max i≤k a i b i , ∀a i ≥ 0, b i > 0.
Then (3.17) gives

P(Z N ∈ M B , |Z N | < n, Zn ( √ nρ n A) ≥ p) ≤ P Z N ∈ M B , |Z N | < n, max z∈Z N Zz n-N ( √ n -N (ρ n A)) ≥ p . (3.18)
For any M > 0, let us consider a partition on B:

(1 -ε) √ nu 0 < (1 -ε) √ nu 1 < • • • < (1 -ε) √ nu M , where u i+1 -u i = η := 2I A (p)
M with u 0 = -I A (p) and u M = I A (p). Then the r.h.s of (3.18) is less than

P M -1 i=0 Z N ∈ M B , |Z N | < n, max z∈Z N ∩J i Zz n-N ( √ n -N (ρ n A)) ≥ p ,
where

J 0 = [(1 -ε) √ nu 0 , (1 -ε) √ nu 1 ]
and

J i = (1 -ε) √ nu i , (1 -ε) √ nu i+1 , 1 ≤ i ≤ M -1.
It follows from Markov property that

P(Z N ∈ M B , |Z N | < n, Zn ( √ nρ n A) ≥ p) ≤ M -1 i=0 ζ∈M B ,|ζ|≤n P (Z N = ζ) P max z∈ζ∩J i Zz n-N ( √ n -N (ρ n A)) ≥ p ≤ M -1 i=0 ζ∈M B ,|ζ|≤n P (Z N = ζ) z∈ζ∩J i P Zn-N ( √ n -N (ρ n A) -z) ≥ p ≤ M -1 i=0   ζ∈M B ,|ζ|≤n P (Z N = ζ) ζ(J i )   P Zn-N √ n -N ρ n (A + 2η -(1 -ε)u i ) ≥ p . (3.19)
The last inequality holds for η > 0 and n large enough, because that for n sufficiently large, for any z ∈ J i , we have

√ n -N (ρ n A) -z ⊂ √ n -N ρ n (A + 2η -(1 -ε)u i ),
where

A + 2η = ∪ x∈A B(x, 2η) is the 2η-neighbourhood of A. Observe that for any 0 ≤ i ≤ M -1, ζ∈M B ,|ζ|≤n P (Z N = ζ) ζ(J i ) ≤ nP (|Z N | ≤ n, Z N (J i ) ≥ 1) ≤ nE [|Z N |; |Z N | ≤ n] ν N (J i ) . (3.20) Again, by (2.6), E[|Z N |; |Z N | ≤ n] ≤ nP(|Z N | ≤ n) ≤ c 3 n χ+1 p N 1 . (3.21)
On the other hand, by (2.7) and Chernoff bound,

ν N (J i ) ≤ e -N inf u i ≤u≤u i+1 γ(u/a) . ( 3
P(Z N ∈ M B , |Z N | < n, Zn ( √ nρ n A) ≥ p) ≤ c 3 n χ+2 p N 1 M -1 i=0 e -N inf u i ≤u≤u i+1 γ(u/a) P Zn-N √ n -N ρ n (A + 2η -(1 -ε)u i ) ≥ p . (3.23) It remains to bound P Zn-N ( √ n -N ρ n (A + 2η -(1 -ε)u i )) ≥ p .
Here we are going to use the assumption (3.15). We first consider A + 2η -(1-ε)u i and the corresponding

I A + 2η -(1-ε)u i (p). According to (5) of Lemma 2.1, we have for any x ∈ R, λ((∂A) + 2η ) + ν(A -x) ≥ ν(A + 2η -x) ≥ ν(A -x).
We take η > 0 sufficiently small (i.e., M large enough) so that λ((∂A) 2η ) ≤ δ/2, which ensures that for any u ∈ R,

I A-u (p -δ/2) ≤ I A + 2η -u (p) ≤ I A-u (p). (3.24)
Moreover, by (3.5), sup

u 0 ≤u≤u M ν(A + 2η -(1 -ε)u) ≤ p -δ/2
. So, we can apply (3.15) and obtain that lim sup

n→∞ 1 √ n log P Zn-N ( √ n -N ρ n (A + 2η -(1 -ε)u i )) ≥ p ≤ -LI A + 2η -(1-ε)u i (p) ≤ -LI A-(1-ε)u i (p -δ/2). Let us now introduce x + (p) := inf{x ≥ 0 : ν(A -x) ≥ p} and x -(p) := inf{x ≥ 0 : ν(A + x) ≥ p}. Clearly I A (p) = x + (p) ∧ x -(p). For u ∈ (u 0 , u M ), I A-u (p) = (x + (p) -u) ∧ (x -(p) + u).
By (1) of Lemma 2.1, we can choose δ > 0 sufficiently small such that x ± (p -δ/2) ∈ [x ± (p)(1ε), x ± (p)). This brings that

I A-(1-ε)u i (p -δ/2) ≥ (1 -ε)((x + (p) -u i ) ∧ (x -(p) + u i )). It implies that lim sup n→∞ 1 √ n log P Zn-N ( √ n -N ρ n (A + 2η -u i )) ≥ p ≤ -L(1 -ε)((x + (p) -u i ) ∧ (x -(p) + u i )).
As a result, (3.23) entails that lim sup

n→∞ 1 √ n log P(Z N ∈ M B , |Z N | < n, Zn ( √ nρ n A) ≥ p) ≤ -(1 -ε) min 0≤i≤M -1 a log 1 p 1 + a inf u i ≤u≤u i+1 γ(u/a) + L((x + (p) -u i ) ∧ (x -(p) + u i )) ≤ -(1 -ε) inf u 0 ≤u≤u M a log 1 p 1 + aγ(u/a) + L((x + (p) -u) ∧ (x -(p) + u)) + ηL, (3.25)
as u i+1 -u i = η. Observe that for any

u 0 ≤ u ≤ u M , a log 1 p 1 + aγ(u/a) + L(x + (p) -u) ≥ inf u∈R a log 1 p 1 + aγ(u/a) + L(x + (p) -u) , and
a log 1 p 1 + aγ(u/a) + L(x -(p) + u) ≥ inf u∈R a log 1 p 1 + aγ(u/a) + L(x -(p) + u) .
Recall that a = αI A (p) and that the symmetry of the distribution of step size implies that γ(u) = γ(-u). Therefore, inf

u 0 ≤u≤u M a log 1 p 1 + aγ(u/a) + L((x + (p) -u) ∧ (x -(p) + u)) ≥ inf u∈R a log 1 p 1 + aγ(u/a) + L(x + (p) -u) ∧ inf u∈R a log 1 p 1 + aγ(u/a) + L(x -(p) + u) = inf u∈R a log 1 p 1 + aγ(u/a) + Lu + L(x + (p) ∧ x -(p)) = F (L)I A (p),
which, together with (3.7)and (3.25), implies (3.16), by letting η ↓ 0 and ε ↓ 0 in (3.25). We complete the proof. Now we are prepared to prove (3.4).

Proof of (3.4). We begin with the rough bound in (3.8). Let L 0 = -α log p 1 and

L k := F (L k-1 ), ∀k ≥ 1.
In view of Lemma (3.3), by iteration, we get that for any k ≥ 0, lim sup

n→∞ 1 √ n log P Zn ( √ nA) ≥ p ≤ -I A (p)L k .
By Lemma A.1, lim k→∞ L k = Λ(p 1 ). We thus conclude (3.4).

Proof of Theorem 1.2:

I A (p) = ∞
The idea of the proof is mainly borrowed from Louidor and Perkins [21, Section 2.3.2]. Recall that

J A (p) = inf y : sup x∈R ν((A -x)/ √ 1 -y) ≥ p, y ∈ [0, 1] .
Lemma 3.4. Suppose that all assumptions in Theorem 1.2 hold. Then

lim inf n→∞ 1 n log P Zn ( √ nA) ≥ p ≥ J A (p) log p 1 . (3.26)
Proof. Since J A (p) is continuous at p, then by (3) in Lemma 2.1, for any ε > 0 small enough, we may find r ∈ (0, 1), x ∈ R and δ > 0, η > 0, such that

J A (p) -ε < r < J A (p) + ε and ν(∩ y∈[x-η,x+η] (A -y)/ √ 1 -r) ≥ p + δ. Set t n = rn + x √ n; m = n -t n ; B n := [(x -η) √ n, (x + η) √ n].
Observe that P( Zn (

√ nA) ≥ p) ≥ P( Zn ( √ nA) ≥ p, Z tn ∈ M Bn , |Z tn | = 1).
Applying Markov property at time t n implies that

P( Zn ( √ nA) ≥ p) ≥P(Z tn ∈ M Bn , |Z tn | = 1) inf y∈Bn P( Zδy n-tn ( √ nA) ≥ p) =p tn 1 ν tn (B n ) inf y∈[(x-η) √ n,(x+η) √ n] P( Zm ( √ nA -y) ≥ p) ≥p tn 1 ν tn (B n )P Zm ( √ mρ n ∩ y∈[x-η,x+η] (A -y) √ 1 -r ) ≥ p where ρ n = √ n(1-r) √ m → 1. By Lemma 2.1, ν m √ mρ n ∩ y∈[x-η,x+η] (A -y) √ 1 -r -ν ∩ y∈[x-η,x+η] (A -y) √ 1 -r = o n (1).
So for n large enough,

ν m √ mρ n ∩ y∈[x-η,x+η] (A -y) √ 1 -r ≥ ν ∩ y∈[x-η,x+η] (A -y) √ 1 -r -δ/2 ≥ p + δ/2.
This, together with Lemma 2.1 entails that

P( Zn ( √ nA) ≥ p) ≥p tn 1 ν tn (B n )P Zm √ mρ n ∩ y∈[x-η,x+η] (A -y) √ 1 -r ≥ ν m √ mρ n ∩ y∈[x-η,x+η] (A -y) √ 1 -r -δ/2 ≥p tn 1 ν tn ( √ n[x -η, x + η])(1 + o n (1)).
Note that ν tn ( √ n[x -η, x + η]) = Θ(1) by classical central limit theorem. As a consequence, lim inf

n→∞ 1 n log P Zn ( √ nA) ≥ p ≥ r log p 1 ≥ (J A (p) + ε) log p 1 .
We obtain (3.26) by letting ε ↓ 0.

Lemma 3.5. Suppose that all assumptions in Theorem 1.2 hold. Then for any ε > 0 small enough,

lim sup n→∞ 1 n log P Zn ( √ nA) ≥ p ≤ (J A (p) -ε) log p 1 . (3.27) Proof. For ε ∈ (0, J A (p)) small enough, set t n = (J A (p) -ε)n . Then P( Zn ( √ nA) ≥ p) = ζ∈M P( Zζ n-tn ( √ nA) ≥ p)P(Z tn = ζ). (3.28)
By the definition of J A (p), there exists δ > 0 such that for ε ∈ [ε, 2ε],

sup y∈R ν A -y 1 -J A (p) + ε ≤ p -δ. (3.29)
(1) and ( 5) of Lemma 2.1 show that for n large enough,

1 |ζ| y∈ζ ν n-tn ( √ nA -y) ≤ 1 |ζ| y∈ζ ν( √ n √ n -t n A - y √ n -t n ) + δ/2 ≤ p -δ/2.
This implies that

P Zζ n-tn ( √ nA) ≥ p ≤P   Zζ n-tn ( √ nA) ≥ 1 |ζ| y∈ζ ν n-tn ( √ nA -y) + δ/2   ,
which by Lemma 2.2 is less than C 1 e -C 2 δ 2 |ζ|/4 . Going back to (3.28) and using (2.6), we have

P( Zn ( √ nA) ≥ p) ≤ ζ∈M C 1 e -C 2 δ 2 |ζ|/4 P(Z tn = ζ) = ∞ k=1 C 1 P(|Z tn | = k)e -c 4 k ≤c 5 ∞ k=1 p tn 1 k χ-1 e -c 4 k ≤ c 6 p tn 1 . (3.30)
This yields (3.27) immediately.

Theorem 1.2 follows directly from the lemmas 3.4 and 3.5.

Böttcher case

In this section, we suppose that p 0 = p 1 = 0. As we claimed in the introduction, different tail distributions of step size bring out different regimes. To obtain Theorems 1.3 and 1.4, we need to treat the sub-exponential and the super-exponential decaying tails differently. In this section, we assume that 2 ≤ b < B ≤ ∞, P(X > z) = Θ(1)e -λz α as z → ∞ with α ∈ (0, 1], λ > 0 and also that I A (p) < ∞ and I A (•) is continuous at p = ν(A) + ∆. We are devoted to proving

lim n→∞ 1 n α/2 log P( Zn ( √ nA) -ν(A) ≥ ∆) = -λI A (p) α . (4.1)
Lower bound of (4.1): Suppose that at the first generation, the root gives birth to exactly b children, denoted by

ρ 1 , • • • , ρ b . Moreover, suppose that their positions are S ρ 1 ∈ [(x -η) √ n, (x + η) √ n], S ρ i ∈ [-M, M ] for 2 ≤ i ≤ b.
Here we take M > 0 such that

P(|X| ≤ M ) ≥ 1/2.
As I A (•) is continuous and finite at p, for any ε > 0 small enough, there exist x ∈ R and η > 0, δ > 0 such that inf

y∈[x-η,x+η] ν(A -y) ≥ p + δ, |x| = I A (p) + ε.
By Lemma (2.4), given

E := {|Z 1 | = b, S ρ 1 ∈ [(x -η) √ n, (x + η) √ n], S ρ i ∈ [-M, M ], ∀i = 2, • • • , b}, lim inf n→∞ Zn ( √ nA) ≥ (p + δ)W 1 + b i=2 ν(A)W i b i=1 W i , where W i , i = 1, 2, • • • , b are i.i.d. copies of W . This shows that lim inf n→∞ P( Zn ( √ nA) ≥ p|E) ≥P lim inf n→∞ Zn ( √ nA) ≥ p + δ/2 E ≥P (p + δ)W 1 + b i=2 ν(A)W i b i=1 W i ≥ p + δ/2 =:C A,p,δ,b .
Since B > b, W has a continuous positive density on (0, ∞); see Athreya and Ney [4, Chapter II, Lemma 2]. So C A,p,δ,b is a positive real number. Consequently,

P( Zn ( √ nA) -ν(A) ≥ ∆) ≥P Zn ( √ nA) ≥ p|E P(E) ≥Θ(1)p b e -λ(|x|-η) α n α/2 (1 + o n (1)) 1 2 b-1
.

Taking limits yields that lim inf n→∞ 1 n α/2 log P( Zn (

√ nA) -ν(A) ≥ ∆) ≥ -λ(I A (p) + ε -η) α .
Letting ε ↓ 0 and η ↓ 0 gives that lim inf

n→∞ 1 n α/2 log P( Zn ( √ nA) -ν(A) ≥ ∆) ≥ -λI A (p) α .
Upper bound of (4. Observe that

P Zn ( √ nA) ≥ p ≤ P(Z tn (B c n ) ≥ 1) + P(Z tn ∈ M Bn , Zn ( √ nA) ≥ p) ≤ 2P(Z tn ((I A (p) -ε) √ n, ∞) ≥ 1) + ζ∈M Bn P(Z tn = ζ)P( Zζ n-tn ( √ nA) ≥ p). (4.3)
On the one hand, by Markov inequality,

P(Z tn ((I A (p) -ε) √ n, ∞) ≥ 1) ≤ E[Z tn ((I A (p) -ε) √ n, ∞)] = m tn ν tn ((I A (p) -ε) √ n, ∞). (4.4)
It is known (see [START_REF] Nagaev | Large deviations of sums of independent random variables[END_REF]) that

ν tn ((I A (p) -ε) √ n, ∞) = e -λ(I A (p)-ε) α n α/2 +o(n α/2 ) , α < 1; ≤ e -(λ-ε)(I A (p)-ε) √ n E[e (λ-ε)X ] tn , α = 1, (4.5)
where for α = 1, we use Markov inequality again by noting that E[e -(λ-ε)X ] < ∞ for ε ∈ (0, λ).

On the other hand, for any ζ ∈ M Bn , because of (4.2), one has

1 |ζ| x∈ζ ν(A - x √ n ) ≤ p -δ.
Again by (6) of Lemma 2.1, for n large enough,

1 |ζ| x∈ζ ν n-tn ( √ nA -x) ≤ p -δ/2.
This, combined with Lemma 2.2, implies that

P( Zζ n-tn ( √ nA) ≥ p) ≤P   Zζ n-tn ( √ nA) ≥ 1 |ζ| x∈ζ ν n-tn ( √ nA -x) + δ/2   ≤C 1 e -C 2 |ζ|δ 2 /4 . (4.6)
In view of (4.4), (4.5) and (4.6), (4.3) becomes

P Zn ( √ nA) ≥ p ≤ 2m tn e -(λ-ε)(I A (p)-ε) α n α/2 +o(n α/2 ) + C 1 ζ∈M Bn P(Z tn = ζ)e -C 2 |ζ|δ 2 /4 ≤ 2m tn e -(λ-ε)(I A (p)-ε) α n α/2 +o(n α/2 ) + C 1 e -c 7 b tn ,
as |Z tn | ≥ b tn . We take t > α 2 log b so that b tn n α/2 and hence

P( Zζ n-tn ( √ nA) ≥ p) ≤ e -(λ-ε)(I A (p)-ε) α n α/2 +o(n α/2 ) .
We thus obtain that lim sup

n→∞ 1 n α/2 log P( Zζ n-tn ( √ nA) ≥ p) ≤ -(λ -ε)(I A (p) -ε) α ,
which, together with the lower bound above, concludes (4.1).

Proof when step size has super-exponential decay

In this section, we assume that the tail distribution of step size is P(X > x) = Θ(1)e -λx α with α > 1. The embedding tree is assumed to be random with 2 ≤ b < B ≤ +∞. We are going to prove the following convergence: for p ∈ (ν(A), 1) such that I A (p) is continuous and finite, we have

lim n→∞ (log n) α-1 n α/2 log P Zn ( √ nA) ≥ p = - 2 log b log B α(log B -log b) α-1 λI A (p) α , (4.7)
with the convention that

2 log b log B α(log B-log b) = 2 log b α if B = ∞.
Lower bound of (4.7): According to the definition of I A (p), for any δ > 0 small enough, there exist x 0 ∈ R, ε > 0 and η > 0 such that

I A (p) < |x 0 | ≤ I A (p) + ε, inf y∈[x 0 -η,x 0 +η] ν(A -y) ≥ p + δ.
Take an integer d > b such that p d > 0. (If B < ∞, then we choose d = B. If B = ∞, we will let d → ∞ later.) Let t n = t 1 log n -t 2 log log n with some t 1 , t 2 > 0. Then for sufficiently large n, let

s n = log log n + t n log b log d , Υ = 2 log b log d α(log d -log b) .
Let us construct a tree t of height t n in the following way. First, t tn-sn := {v ∈ t : |v| ≤ t s -s n } is a b-regular tree. Using Neveu's notation [START_REF] Neveu | Arbres et processus de Galton-Watson[END_REF], let U := ∪ n≥1 N n + ∪ {ρ} be the infinite Ulam-Harris tree, to code the vertices. Here denote u * = (1, • • • , 1) to be the first individual of the (t n -s n )-th generation in the lexicographic order. Next, t(u * ) is a d-regular tree and {t(u) : u = u * , |u| = t n -s n } are all b-regular trees, where for any u ∈ t, t(u) := {v ∈ t : u v} is the subtree of t rooted at u. Recall from the very beginning of this paper that T is the embedded Galton-Watson tree. Let T tn = {u ∈ T : |u| ≤ t n }. Define the following event

E tn,b,d = {T tn = t, S u ∈ [(x 0 -η) √ n, (x 0 + η) √ n], for all |u| = t n s.t. u ∈ t(u * )}, (4.8)
which means that all the descendants of u * at the t n -th generation are positioned in the interval

[(x 0 -η) √ n, (x 0 + η) √ n]. It follows immediately that P Zn ( √ nA) ≥ p ≥ P Zn ( √ nA) ≥ p|E tn,b,d P(E tn,b,d ) (4.9)
and that

P(E tn,b,d ) ≥ p b tn b p d sn d P t (S u ∈ [(x 0 -η) √ n, (x 0 + η) √ n], ∀u ∈ t(u * ), |u| = t n ), (4.10)
where P t = P(•|T tn = t). To bound the probability on the R. H. S. of (4.10), let us take the following labels (step sizes):

X v ∈ (x 0 - η 2 ) √ n t n -s n , (x 0 + η 2 ) √ n t n -s n , ∀ ρ ≺ v u * ; and X v ∈ [-M, M ], ∀ v ∈ t(u * ) and |v| ≤ t n ,
where M is a fixed real number such that P(X ∈ [-M, M ]) ≥ 1/2. Observe that for n large enough, for any u ∈ t(u * ) s.t. |u| = t n ,

S u ∈ (x 0 - η 2 ) √ n -M s n , (x 0 + η 2 ) √ n + M s n ⊂ [(x 0 -η) √ n, (x 0 + η) √ n].
As a consequence,

P t (S u ∈ (x 0 -η) √ n, (x 0 + η) √ n], ∀u ∈ t(u * ), |u| = t n ) ≥P X ∈ (x 0 - η 2 ) √ n t n -s n , (x 0 + η 2 ) √ n t n -s n tn-sn × 1<k≤sn P(X ∈ [-M, M ]) d k ≥ 1 2 2d sn c tn-sn 8 exp -λ(t n -s n ) 1-α |x 0 | - η 2 α n α/2 .
Here we take t 1 = α 2 log b and t 2 = 2α log b so that

n α/2 (t n -s n ) α-1 = (1 + o n (1))Υ α-1 n α/2 (log n) α-1 d sn b tn .
Therefore, by (4.10),

P(E tn,b,d ) ≥ exp -λ |x 0 | - η 2 α Υ α-1 n α/2 (log n) α-1 + o n α/2 (log n) α-1 . ( 4
M 0 = ζ ∈ M : |ζ| = d sn + b tn -b sn , ζ([(x 0 -η) √ n, (x 0 + η) √ n]) ≥ d sn .
For any ζ ∈ M 0 , by considering only the particles in

[(x 0 -η) √ n, (x 0 + η) √ n], 1 |ζ| x∈ζ ν( √ nA -x) ≥ d sn d sn + b tn -b sn inf y∈[x 0 -η,x 0 +η] ν(A -y) ≥ log n log n + 1 (p + δ),
which, combining with (5) of Lemma 2.1, implies that for n large enough,

1 |ζ| x∈ζ ν n-tn ( √ nA -x) ≥ p + δ/2.
This means that for any

ζ ∈ M 0 ,    Zζ n-tn ( √ nA) ≥ 1 |ζ| x∈ζ ν n-tn ( √ nA -x) -δ/2    ⊂ { Zζ n-tn ( √ nA) ≥ p}, as p = ν(A) + ∆. Note that Z tn ∈ M 0 given E tn,b,d .
Then by Lemma 2.2, we have

P( Zn ( √ nA) ≥ p|E tn,b,d ) ≥ P   Zζ n-tn ( √ nA) ≥ 1 |ζ| x∈ζ ν n-tn ( √ nA -x) -δ/2   ζ=Zt n ∈M 0 ≥ 1 -C 1 e -C 2 d sn δ 2 /4 ≥ 1 2 ,
for all n large enough. This implies that

P( Zn ( √ nA) ≥ p) ≥ 1 2 P(E tn,b,d ),
which, together with (4.11), gives

lim inf n→∞ (log n) α-1 n α/2 log P( Zn ( √ nA) ≥ p) ≥ -λ |x 0 | - η 2 α Υ α-1 . (4.12)
Then we get the lower bound by letting δ ↓ 0 and d ↑ B.

Upper bound of (4.7): Again, by the definition of I A (p), for any δ > 0 small enough, there exist η > 0 such that sup

|y|≤I A (p)-η ν(A -y) ≤ p -δ. Let B n := [(-I A (p) + η) √ n, (I A (p) -η) √ n], t n = α log b 2 log n . Observe that for any ζ ∈ M, 1 |ζ| x∈ζ ν(A - x √ n ) = 1 |ζ| x∈ζ∩Bn ν(A - x √ n ) + 1 |ζ| x∈ζ∩B c n ν(A - x √ n ) ≤p -δ + ζ(B c n ) |ζ| ,
which is less than p -δ/2 as soon as

ζ(B c n )
|ζ| ≤ δ/2. Further, by ( 5) of Lemma 2.1, for all n large enough,

M 1 := ζ ∈ M : ζ(B c n ) |ζ| ≤ δ/2 ⊂    ζ ∈ M : 1 |ζ| x∈ζ ν n-tn ( √ nA -x) ≤ p -δ/4    . (4.13)
By conditioning on {Z tn = ζ} for any ζ ∈ M 1 , we observe that

P( Zn ( √ nA) ≥ p) ≤P( Ztn (B c n ) > δ/2) + P( Zn ( √ nA) ≥ p, Ztn (B c n ) ≤ δ/2) =P( Ztn (B c n ) > δ/2) + ζ∈M 1 P(Z tn = ζ)P Zζ n-tn ( √ nA) ≥ p ,
which, by (4.13), is bounded by

P( Ztn (B c n ) > δ/2) + ζ∈M P(Z tn = ζ)P   Zζ n-tn ( √ nA) ≥ 1 |ζ| x∈ζ ν n-tn ( √ nA -x) + δ/4   . Note that |Z tn | ≥ b tn . In view of Lemma 2.2, ζ∈M P(Z tn = ζ)P   Zζ n-tn ( √ nA) ≥ 1 |ζ| x∈ζ ν n-tn ( √ nA -x) + δ/4   ≤ C 1 e -c 9 b tn . Since P( Ztn (B c n ) > δ/2) ≤ P(Z tn (B c n ) ≥ δb tn /2), then P( Zn ( √ nA) ≥ p) ≤ P(Z tn (B c n ) ≥ δb tn /2) + C 1 e -c 9 b tn . (4.14)
It remains to bound P(Z tn (B c n ) ≥ δb tn /2), which will be investigated separately in two cases: B = ∞ and B < ∞.

First case: B = ∞. Note that by Markov inequality and symmetry of X,

P(Z tn (B c n ) ≥ δb tn /2) ≤P(Z tn (B c n ) ≥ 1) ≤m tn ν tn (B c n ) ≤ 2m tn ν tn (I A (p) -η) √ n, ∞ .
Then (1) of Lemma A.2 implies that lim sup

n→∞ (log n) α-1 n α/2 log P(Z tn (B c n ) ≥ δb tn /2) ≤ -λ 2 log b α α-1 (I A (p) -η) α . As b tn ≥ n α/2 b n α/2 t α-1 n
, in view of (4.14), we get

lim sup n→∞ (log n) α-1 n α/2 log P( Zn ( √ nA) ≥ p) ≤ -λ 2 log b α α-1 (I A (p) -η) α ,
which, with the help of (4.12), proves (4.7) in the case of B = ∞ by letting η ↓ 0.

Second case: b < B < ∞. The proof will be divided into three subparts. . For n large enough, we have δb tn /4 ≥ B sn . Observe that

P(Z tn (B c n ) ≥ δb tn /2) ≤ 2P Z tn ((I A (p) -η) √ n, ∞) ≥ B sn .
Recall that up to the t n -th generation, the genealogical tree T tn is Galton-Watson. Set

I(n) = (I A (p) -η) √ n. Then P(Z tn ((I A (p) -η) √ n, ∞) ≥ B sn ) = t P(T tn = t)P t   |u|=tn, u∈t 1 {Su>I(n)} ≥ B sn   .
Observe that

   |u|=tn, u∈t 1 {Su>I(n)} ≥ B sn    ⊂    J ⊂tt n , |J |=B sn u∈J {S u > I(n)}    , (4.15)
where t tn = {u ∈ t : |u| = t n }. This yields that

P(Z tn ((I A (p) -η) √ n, ∞) ≥ B sn ) ≤ t P(T = t) J ⊂tt n , |J |=B sn P t u∈J {S u > I(n)} (4.16)
We claim that for any t and J ⊂ t tn with |J | = B sn ,

P t u∈J {S u > I(n)} ≤ c 10 t n B sn e -λn α + (c 10 n) tnB sn exp      - λ ((I A (p) -η) √ n -t n ) α t n -s n + 1 B 1/(α-1) -1 α-1      . ( 4
.17) (4.17) will be proved in Subpart 2. Notice that

# {J ⊂ t tn , |J | = B sn } = |t tn | B sn ≤ B tn B sn ,
which, together with (4.17) and (4.16), gives

P(Z tn (B c n ) ≥ δb tn /2) ≤ B tn B sn ×   c10tnB sn e -λn α + (c 10 n) tnB sn exp      - λ ((I A (p) -η) √ n -t n ) α t n -s n + 1 B 1/(α-1) -1 α-1         . Note that B sn ≤ n α/2
(log n) 2α and

B tn B sn = (B tn )! (B sn )!(B tn -B sn )! ≤ B tnB sn (B sn )! ≤ B tnB sn .
Then

t n B sn log n =O(1) n α/2 (log n) 2α-2 n α/2 (log n) α-1 , ((I A (p) -η) √ n -t n ) α t n -s n + 1 B 1/(α-1) -1 α-1 = n α/2 (log n) α-1 Υ α-1 (I A (p) -η) α + o n (1) , where Υ = 2 log b log B α(log B-log b) . So, P(Z tn (B c n ) ≥ δb tn /2) ≤ exp - λn α/2 (log n) α-1 Υ α-1 (I A (p) -η) α + o n (1) .
In view of (4.14), we conclude that lim sup

n→∞ (log n) α-1 n α/2 log P( Zn ( √ nA) ≥ p) ≤ -λΥ α-1 (I A (p) -η) a ,
which, by letting η → 0, gives what we need. .

Subpart 2:

This subpart is devoted to demonstrating (4.17). For any J , define t J = {v ∈ t : ρ ≺ v u, u ∈ J }. One sees that L.H.S. of (4.17

) ≤ P t   ρ≺v u |X v | ≥ I(n), ∀u ∈ J   ≤P t sup v∈t J |X v | ≥ n + P t   sup v∈t J |X v | ≤ n; ρ≺v u |X v | ≥ I(n), ∀u ∈ J   . (4.18)
It follows from the tail distribution of X that there exists c 11 ≥ 1 such that

P(|X| ≥ x) ≤ c 11 e -λx α , ∀x ≥ 0.
As a consequence, we have

P t sup v∈t J |X v | ≥ n ≤ |t J |P(|X| ≥ n) ≤ c 11 t n B sn e -λn α . (4.19)
Meanwhile,

P t   sup v∈t J |X v | ≤ n; ρ≺v u |X v | ≥ I(n), ∀u ∈ J   ≤ xv∈N∩[0,n),v∈t J P t   v∈t J {|X v | ∈ [x v , x v + 1]}   1 min u∈J ρ≺v u (xv+1)≥I(n) ≤ xv∈N∩[0,n),v∈t J c 11 tnB sn e -λ v∈t J x α v 1 min u∈J ρ≺v u xv≥I 1 (n) , (4.20)
where I 1 (n) = I(n) -t n . We need to bound R.H.S. of (4.20). To end this, we CLAIM that from {x v , v ∈ t J }, one can construct a rooted deterministic tree t * J with labels x ρ = 0 and

{x * v , v ∈ t * J \ {ρ}} ⊂ {x v , v ∈ t J } such that v∈t J x α v ≥ v∈t * J (x * v ) α , min |u|=tn,u∈t * J ρ≺v u x * v ≥ min u∈J ρ≺v u x v ≥ I 1 (n), (4.21)
and that t * J contains a single branch up to the generation t n -s n , then it has the B-regular structure up to the generation t n . The detailed construction will be postponed to Subpart 3.

With the help of (4.21), we get that R.H.S. of (4.20)

≤c tnB sn 11 n |t J | sup x * v ∈N,x * v <n,v∈t * J e -λ v∈t * J (x * v ) α 1 min |u|=tn ρ≺v u x * v ≥I 1 (n) . (4.22)
Note that min

|u|=tn ρ≺v u x * v ≥ I 1 (n) leads to |u|=tn ρ≺v u x * v ≥ I 1 (n)B sn , which means k 0 i=1 |u|=i x * u + tn i=1+k 0 |u|=i x * u B i-k 0 ≥ I 1 (n), with k 0 = t n -s n . Note that #{u ∈ t * J : |u| = i} = 1, i ≤ k 0 ; B i-k 0 , k 0 < i ≤ t n . Write x * i = |u|=i x * u for i ≤ k 0 and x * i = |u|=i x * u B i-k 0 for k 0 < i ≤ t n . So we have 1 {min |u|=tn ρ≺v u x * v ≥I 1 (n)} ≤ 1 { tn i=1 x * i ≥I 1 (n)} . Consequently, sup x * v ∈N∩[0,n),v∈t * J e -λ v∈t * J (x * v ) α 1 min |u|=tn ρ≺v u x * v ≥I 1 (n) ≤ sup x * v ∈N∩[0,n),v∈t * J e -λ v∈t * J (x * v ) α 1 tn i=1 x * i ≥I 1 (n)
.

(4.23) Moreover, as α > 1, by convexity of x → x α on R + , we obtain that for

k 0 < i ≤ t n , |u|=i x * u α ≥ B i-k 0 |u|=i x * u B i-k 0 α = B i-k 0 (x * i ) α ,
and |u|=i (x * u ) α = (x * i ) α for 1 ≤ i ≤ k 0 .
Again using convexity implies that, for any

µ i > 0, v∈t * (x * v ) α ≥ k 0 i=1 (x * i ) α + tn i=k 0 +1 B i-k 0 (x * i ) α = k 0 i=1 (x * i ) α + tn i=1+k 0 B i-k 0 µ -α i (µ i x * i ) α ≥   k 0 + tn i=1+k 0 B i-k 0 µ -α i   k 0 i=1 x * i + tn i=1+k 0 B i-k 0 µ 1-α i x * i k 0 + tn i=1+k 0 B i-k 0 µ -α i α
.

By taking

µ i > 0 such that B i-k 0 µ 1-α i = 1, one sees that given tn i=1 x * i ≥ I 1 (n), we have v∈t * (x * v ) α ≥ k 0 + tn i=1+k 0 B -i-k 0 α-1 1-α tn i=1 x * i α ≥ ((I A (p) -η) √ n -t n ) α t n -s n + 1 B 1/(α-1) -1 α-1 . ( 4
≤ c 11 t n B sn e -λn α + (c 11 n) tnB sn exp      - λ ((I A (p) -η) √ n -t n ) α t n -s n + 1 B 1/(α-1) -1 α-1      . ( 4.25)
We have completed the proof of (4.17).

Subpart 3:

We now explain how to construct {x * v , v ∈ t * }. Recall that k 0 = t n -s n and |Z t k | is the number of particles at the k-th generation in t. Then Observe that only a part of the particles in t has been selected and that the positions at the final generation of t * are all getting higher. (4.21) is satisfied.

|Z t i+k 0 | ≥ B i , ∀1 ≤ i ≤ t n -k 0 = s n . 0 1 2 3 4 -2 -

LDP when the tree is regular

Unfortunately, the arguments above do not all work when the embedding tree T is regular. We could only get the upper and lower bound for the large deviation behaviours:

-C α ≤ lim inf n→∞ 1 n α/2 log P Zn ( √ nA) -ν(A) ≥ ∆ ≤ lim sup n→∞ 1 n α/2 log P Zn ( √ nA) -ν(A) ≥ ∆ ≤ -c α . (4.26)
Lower bound No matter whether α < 1 or α ≥ 1, we only consider the first generation and suppose that

S u ∈ [(x -η) √ n, (x + η) √ n], ∀|u| = 1,
where

|x| = I A (p) + ε with inf y∈[x-η,x+η] ν(A -y) ≥ p + δ for some δ, η, ε > 0. Given E := {S u ∈ [(x -η) √ n, (x + η) √ n], ∀|u| = 1}, lim inf n→∞ Zn ( √ nA) ≥ p + δ. Then P Zn ( √ nA) -ν(A) ≥ ∆ ≥P(S u ∈ [(x -η) √ n, (x + η) √ n], ∀|u| = 1; Zn ( √ nA) ≥ p) ≥P( Zn ( √ nA) ≥ p|E)P(E),
where lim inf n→∞ P( Zn (

√ nA ≥ p|E) ≥ P(lim inf n→∞ Zn ( √ nA) ≥ p|E) = 1.
On the other hand,

P(E) = P(X ∈ [(x -η) √ n, (x + η) √ n]) b = (1 + o n (1))e -λb(x-η) α n α/2 .
We thus deduce that lim inf n→∞ 1 n α/2 log P Zn (

√ nA) -ν(A) ≥ ∆ ≥ -λb(x -η) α .
We obtain the lower bound in Observe that

Z tn (B c n ) b tn = |u|=tn 1 |Su|≥(I A (p)-η) √ n b tn ≤ 1 (I A (p) -η) √ n |u|=tn |S u | b tn . Moreover, |S u | ≤ ρ≺v u |X u | implies that Z tn (B c n ) b tn ≤ 1 (I A (p) -η) √ n |u|=tn |S u | b tn ≤ 1 (I A (p) -η) √ n tn k=1 |u|=k |X u | b k .
It follows that

P( Zn ( √ nA) -ν(A) ≥ ∆) ≤P   tn k=1 |u|=k |X u | b k ≥ δ(I A (p) -η) √ n   + C 1 e -c 9 n α/2 =P     tn k=1 |u|=k |X u | b k   α ≥ [δ(I A (p) -η) √ n] α   + C 1 e -c 9 n α/2 .
By convexity of x → x α , for any µ k > 0, one sees that

  tn k=1 |u|=k |X u | b k   α =   tn k=1 |u|=k µ k b k (µ -1 k |X u |)   α ≤( tn k=1 µ k ) α tn k=1 |u|=k µ k b -k (µ -1 k |X u |) α tn k=1 µ k ≤µ α-1 tn k=1 |u|=k b -k µ 1-α k |X u | α ,
where µ = ∞ k=1 µ k . We are going to take a decreasing sequence µ k = k -2 so that µ < ∞. Therefore, for any θ > 0,

P( Zn ( √ nA) -ν(A) ≥ ∆) ≤P   µ α-1 tn k=1 |u|=k b -k µ 1-α k |X u | α ≥ [δ(I A (p) -η) √ n] α   + C 1 e -c 9 n α/2 ≤e -θ µ α-1 δ α (I A (p)-η) α n α/2 E   exp{θ tn k=1 |u|=k b -k µ 1-α k |X u | α }   + C 1 e -c 9 n α/2 . (4.27)
We then show that for θ > 0 sufficiently small such that sup k≥1 θb -k k 2(α-1) ≤ λ/2, there exists

c λ > 0 such that E   exp{θ tn k=1 |u|=k b -k µ 1-α k |X u | α }   ≤ e c λ θt 2α-1 n .
In fact, by independence,

E   exp{θ tn k=1 |u|=k b -k µ 1-α k |X u | α }   = tn k=1 |u|=k E exp{θb -k k 2(α-1) |X u | α } = tn k=1 |u|=k 1 + ∞ 0 θb -k k 2(α-1) e θb -k k 2(α-1) x P(|X u | α ≥ x)dx .
The tail distribution of X shows that P(|X| ≥ x) ≤ c 11 e -λx α for any x ≥ 0. It follows that

E   exp{θ tn k=1 |u|=k b -k k 2(α-1) |X u | α }   ≤ tn k=1 |u|=k 1 + c 11 ∞ 0 θb -k k 2(α-1) e θb -k k 2(α-1) x-λx dx = tn k=1 |u|=k 1 + c 11 θb -k k 2(α-1) λ -θb -k k 2(α-1) ≤ exp    tn k=1 |u|=k c 11 θb -k k 2(α-1) λ -θb -k k 2(α-1)    < e c λ θt 2α-1 n .
Plugging it into (4.27) yields that

P( Zn ( √ nA) -ν(A) ≥ ∆) ≤ e -θ µ α-1 δ α (I A (p)-η) α n α/2 +c λ θt 2α-1 n + C 1 e -c 9 n α/2 .
Recall that t n = O(log n). We have lim sup

n→∞ 1 n α/2 log P( Zn ( √ nA) -ν(A) ≥ ∆) ≤ -c α .

Proof of Theorem 1.4: step size has Gumbel tail distribution

In this section, we assume that the tail distribution of step size is of Gumbel's type, in other words, where y α = (1+α) log B (1+α) log B-log b . The ideas of proof are similar to that used in Section 4.1.2. However, we do not need to assume B > b.

P(X ≥ x) = Θ (

Lower bound of (4.28)

As stated in Section 4.1.2, for any sufficiently small δ > 0, there exist

x 0 ∈ R, ε, η > 0 such that inf |y-x 0 |≤η ν(A -x) ≥ p + δ, I A (p) < x 0 -η < x 0 ≤ I A (p) + ε. Take d ≥ b an integer such that p d > 0. (Again, if B < ∞, then we choose d = B. If B = ∞, we will let d → ∞ later.) Let t n = tn α 2(α+1) - 2 log n log b , s n = log n + t n log b log d ∧ t n , y α (d) = (1 + α) log d (1 + α) log d -log b
where t > 0 will be determined later on. With these d, t n , s n , recall event E tn,d,b from (4.8). It follows that

P( Zn ( √ nA) -ν(A) ≥ ∆) ≥ P( Zn ( √ nA) -ν(A) ≥ ∆; E tn,d,b ). (4.29) Define M 2 = ζ ∈ M : |ζ| = d sn + b tn -b sn , ζ([(x 0 -η) √ n, (x 0 + η) √ n]) ≥ d sn .
We have for any

ζ ∈ M 2 , 1 |ζ| x∈ζ ν(A - x √ n ) ≥ d sn b tn -b sn + d sn inf y∈[x 0 -η,x 0 +η] ν(A -y) ≥ n n + 1 (p + δ),
which, together with (5) of Lemmma 2.1, implies that for all n sufficiently large,

1 |ζ| x∈ζ ν n-tn ( √ nA -x) ≥ p + δ/2.
Note that, Z tn ∈ M 2 , given E tn,d,b . Consequently,

P( Zn ( √ nA) ≥ p; E tn,d,b ) ≥ ζ∈M 2 P(Z tn = ζ; E tn,d,b )P Zζ n-tn ( √ nA) ≥ p ≥ ζ∈M 2 P(Z tn = ζ; E tn,d,b )P   Zζ n-tn ( √ nA) ≥ 1 |ζ| x∈ζ ν n-tn ( √ nA -x) -δ/2   ≥ P(E tn,d,b )(1 -C 1 e -C 2 |ζ|δ 2 /4 ),
where the last inequality follows from Lemma 2.2. As |ζ| ≥ b tn , for n large enough, and t = X α log b . We suppose that for any ancestor of u * : u u * ,

P( Zn ( √ nA) -ν(A) ≥ ∆) ≥ 1 2 P(E tn,d,b ). ( 4
X u ∈ X n 1 2(α+1) , X n 1 2(α+1) + η 2t n 1 2(α+1) ,
and that for any descendant of u * : u

* ≺ u s.t. |u| ≤ t n , X u ∈ X α n α 2(α+1) -(|u| + s n -t n ) log d 1 α , X α n α 2(α+1) -(|u| + s n -t n ) log d 1 α + η 2t n 1 2(α+1)
. This ensures that for any descendant u of u * at the t n -th generation, its position S u satisfies

S u -(t n -s n )X n 1 2(α+1) + sn k=1 X α -kn -α 2(α+1) log d 1 α n 1 2(α+1) ≤ η √ n/2, where as n → ∞, t n ≈ tn α 2(α+1) , s n ≈ log b log d t n and (t n -s n )X n 1 2(α+1) + sn k=1 X α -kn -α 2(α+1) log d 1 α n 1 2(α+1) = √ n 1 - log b log d tX + log b log d t 0 (X α -x log d) 1 α dx + o n (1) = √ n(x 0 + o n (1)).
So for all n large enough, we have

S u ∈ [(x 0 -η) √ n, (x 0 + η) √ n], ∀u * ≺ u, |u| = t n .
As a result,

P t (S u ∈ [(x 0 -η) √ n, (x 0 + η) √ n], ∀u * ≺ u, |u| = t n ) ≥P X ∈ [X n 1 2(α+1) , X n 1 2(α+1) + η 2t n 1 2(α+1) ] tn-sn × sn k=1 P X ∈ X α n α 2(α+1) -k log d 1 α , X α n α 2(α+1) -k log d 1 α + η 2t n 1 2(α+1) d k ≥ 1 2 d sn+1 c tn-sn 12 exp -(t n -s n )e X α n α 2(α+1) - sn k=1 d k e X α n α 2(α+1) -k log d .
Plugging it into (4.31) implies that

P(E tn,d,b ) ≥ p b tn b p nb tn d 1 2 db tn c tn 12 exp -t n e X α n α 2(α+1) = exp -(1 + o n (1))t n e X α n α 2(α+1)
.

Going back to (4.30), we hence conclude the lower bound by letting d ↑ B.

Upper bound

Let B n := [(-I A (p) + η) √ n, (I A (p) -η) √ n], t n = tn α 2(α+1)
with some t > 0. Recall (4.13). One sees that for any ζ ∈ M and n large enough,

ζ(B c n ) |ζ| ≤ δ/2 ⊂    1 |ζ| x∈ζ ν n-tn ( √ nA -x) ≤ p -δ/4    .
Again, similar to (4.14), we thus have

P( Zn ( √ nA) -ν(A) ≥ ∆) ≤ P(Z tn (B c n ) ≥ δb tn /2) + C 1 e -c 9 b tn . (4.32)
Here we need to treat P(Z tn (B c n ) ≥ δb tn /2) separately in the two following cases.

Upper bound: B = ∞ In this case, y α = 1. By Markov inequality, we have

P(Z tn (B c n ) ≥ δb tn /2) ≤ 2 δ b -tn E[Z tn (B c n )] = 4 δ b -tn m tn ν tn ((I A (p) -η) √ n, ∞).
In view of (2) of Lemma A.2, one has immediately, lim inf

n→∞ 1 n α 2(α+1) log -log P(Z tn (B c n ) ≥ δb tn /2) ≥ I A (p) -η t α .
In (4.32), b tn = exp{t log bn α 2(α+1) }. We choose t = (I A (p)-η) α α+1

(log b)

1 α+1 so that t log b = I A (p)-η t α . We thus conclude that lim inf n→∞ 1 n α 2(α+1) log -log P( Zn ( √ nA) -ν(A) ≥ ∆) ≥ ((I A (p) -η)y α log b) α 2(α+1)) .
Upper bound: b ≤ B < ∞ Following the same idea applied in (4.16), we take

s n = t n log b -log n log B , k 0 = t n -s n ,
and reconstruct the special subtree t * J . It follows from the Gumbel tail distribution of X that there exists c 13 ≥ 1 such that

P(|X| ≥ x) ≤ c 13 e -e x α
, and ∀x ≥ 0.

Similarly to (4.16), (4.18), (4.20) and (4.19), one sees that

P(Z tn (B c n ) ≥ δb tn /2) ≤ 2B tnB sn   c13tnB sn e -e n α + c tnB sn 13 n tnB sn max x * u ≥0,u∈t * J tn k=1 x * k ≥I 1 (n) exp    - u∈t * J e (x * u ) α       . (4.33) Note that u∈t * J e (x * u ) α ≥ tn-sn k=1 |u|=k e (x * u ) α + sn k=1 |u|=k+tn-sn e (x * u ∨M ) α - sn k=1 B k e M α .
where

M ≥ 0 is chosen so that x → e x α is convex on [M, ∞). Immediately, |u|=k+tn-sn e (x * u ∨M ) α ≥ B k e ( x * u ∨M B k ) α
. So, In fact, either 1/α ≥ sup t∈R + Λ (t) ≥ Λ (θ), or there exists t 1/α > 0 such that 1/α = Λ (t 1/α ) and then γ(1/α) = t t/α α -Λ(t 1/α ). This follows that αγ(1/α) -α log m = t 1/α -α(Λ(t 1/α ) + log m) ≥ θ.

As Λ(t) ≥ 0, we have t 1/α > θ. Consequently, Λ (θ) ≤ Λ (t 1/α ) = 1/α.

On the other hand, as

L 0 ≤ L k ≤ θ, L k+1 -L k = α(Λ(θ) -Λ(L k )) ≥ αΛ (L k )(θ -L k ) ≥ αΛ (L 0 )(θ -L k ) ≥ 0.
This shows that θ -L k → 0.

The following lemma concerns large deviation probabilities of sums of independent random variables. The results are possibly well-known to some experts or implicitly contained in some articles.

Lemma A.2. Suppose that {X i } i≥1 is a sequence of i.i.d. random variables, having the same distribution as X. X is symmetric.

(1) If P(X ≥ x) = Θ(1)e -λx α as x → ∞ with some λ > 0 and α > 1, then for a > 0, and for a sequence of integers (t n ) such that t n = o(n (2) If P(X ≥ x) = Θ(1)e -e x α as x → ∞ with some α > 0, then for any a > 0 and any sequence t n ↑ ∞ such that t n = o √ n (log n)

|X i | ≥ a √ n ≥ a α .
We have completed the proof.

3. 1

 1 Proof of Theorem 1.1: I A (p) < ∞ and I A is continuous at p In this section, we are going to demonstrate Theorem 1.1.

Subpart 2 :

 2 We turn to prove (3.7) and(3.8). According to(3.6), to bound P( Zn ( √ nA) ≥ p), we only need to consider P(Z N (a) ∈ M Bn , Zn ( √ nA) ≥ p). Note that by Markov property at time N (a),

4. 1

 1 Proof of Theorem 1.3: step size has Weibull tail distribution 4.1.1 Proof when step size has (sub)-exponential decay

  1): Take an intermediate generation t n = t log n with some t > 0. Let B n = [(-I A (p) + ε) √ n, (I A (p) -ε) √ n] with ε > 0 small enough. Note that there exists δ > 0 such that sup x∈[-I A (p)+ε,I A (p)-ε] ν(A -x) ≤ p -δ. (4.2)

. 11 )

 11 It remains to bound P Zn ( √ nA) ≥ p|E tn,b,d . Define

Subpart 1 :

 1 Recall that t n = α 2 log b log n . Let s n = tn log b-2α log log n log B

FigD:

  FigA: Original tree

  (4.26) with C α = λb(I A (p)) α . Upper bound When α ≤ 1, the arguments in Section 4.1.1 still work for regular tree. So the upper bound is obtained with c α = λ(I A (p)) α in the case of α ≤ 1. When α > 1, (4.14) still holds. So, for B n = [-(I A (p) -η) √ n, (I A (p) -η) √ n] and t n = α log b 2 log n , P( Zn ( √ nA) -ν(A) ≥ ∆) ≤ P(Z tn (B c n ) ≥ δb tn /2) + C 1 e -c 9 b tn .

  1)e -e x α with α > 0, for x → ∞. In what follows, we are devoted to demonstrating that if I A is finite and continuous at p = ν(A) + ∆, then lim n→∞ n -α 2(α+1) log -log P Zn ( √ nA) -ν(A) > ∆ = (y α I A (p) log b)

  .30) Recall that u * = (1, • • • , 1) with |u * | = t n -s n . It remains to consider P(E tn,d,b ), which by (4.10) is P(E tn,d,b ) ≥ p b tn b p d sn d P t (S u ∈ [(x 0 -η) √ n, (x 0 + η) √ n], ∀u > u * , |u| = t n ). (4.31) Let X = (x 0 y α (d) log b) 1 α+1

B,( 1 +X n α 2 (

 12 (k-tn+sn) + . Let Ξ n := max{(x * k ) α + (k -t n + s n ) + log B; 1 ≤ k ≤ t n }. Then, u∈t * J e (x * u ) α ≥ e Ξn -B sn+1 e M α .Plugging it into (4.33) implies thatP(Z tn (B c n ) ≥ δb tn /2) ≤ e -(1+on(1))n α + 2(c 13 Bn) tnB sn max Ξn + B sn+1 e M α }. and Ξ n ≥ s n log B = (t log b + o n (1))n α 2(α+1) . Let K n := Ξ n n -α2(α+1) . Then,(I A (p) -η) + o n (1) ≤ 1 -log b log B + o n (1) tK 1/α n + t log b/ log B 0 K n -x log B α) log B .In view of the right hand side of (4.34) where t n B sn ≤ tn n b tn , we take t such that t n log b ≤ Ξ n . In other words, t ≤ K n / log b. This choice entails thatK 1+1/α n log B -log b log B log b + o n (1) + α (1 + α) log B ≥ I A (p) -η + o n (1).Thus, setting X = [(I A (p) -η)y α log b] α α+1 and t = X log b , we haveK n ≥ X (1 + o n (1)), b tn ≤ e X n α 2(α+1) and t n B sn log n e α+1) .As Ξ n = K n n α 2(α+1) , applying this to (4.34) yields that for sufficiently large n,P(Z tn (B c n ) ≥ δb tn /2) ≤e -(1+on(1))n α + 2(c 13 Bn) tnB sn exp -e X (1+on(1))n α 2(α+1) + c 14 t n B sn ≤e -(1+on(1))e n α + exp -(1 + o n (1))e [(I A (p)-η)yα log b] log[-log P(Z tn (B c n ) ≥ δb tn /2)] ≥ [(I A (p) -η)y α log b] α α+1 .Going back to (4.32), as b tn = e X n log P( Zn (√ nA) -ν(A) ≥ ∆)] ≥ [(I A (p) -η)y α log b] α α+1 ,which ends the proof of the upper bound of Theorem 1.4 by letting η ↓ 0.Hence, lim k→∞ L k = L ∞ ≤ θ. Here αΛ (θ) ≤ 1 because we need to take α > 0 small so that αγ(1/α) -α log m ≥ inf a>0 γ(a) -log p 1 a = θ.

1 3 )

 3 and t n → ∞, we have

  and |ζ| < ∞ the total mass. For convenience, we write x ∈ ζ if ζ{x} ≥ 1. There exists C 1 , C 2 > 0 such that for all ∆ > 0 sufficiently small and n ≥ 1, for any finite ζ ∈ M,

	Let {Z ζ n }
	be the branching random walk started from Z ζ 0 = ζ. Similarly, let Zζ n (•) be the corresponding
	empirical distribution. Because of (1.5), we have the following lemma, borrowed from [21].
	Lemma 2.2.

  2/α+1 , Proof of (1): Note that there exists c 15 > 0 such that for any x ≥ 0,P(|X| ≥ x) ≤ c 15 e -λx α . | < n, |X i | ∈ [x i , x i + 1) (|X i | ∈ [x i , x i + 1], ∀1 ≤ i ≤ t n )where in the last inequality we use the fact that the convexity of mapping x → x α for α > 1 implies Similarly, for any ε > 0 there exists some constant c 16 ≥ 1 such that ≤ c 15 t n e -e n α + (c 16 n) tn exp -(1 -ε)e

		P	tn	|X i | ≥ a √	n, sup	|X i | < n
			i=1					1≤i≤tn
			=						P	tn	|X i | ≥ a √	n, sup
				x i ∈[0,n)∩N,i=1,••• ,tn	i=1
			≤
					tn i=1	x i ≥a √ n-tn;
				x i ∈[0,n)∩N,i=1,••• ,tn
									tn
			≤						c tn 15 exp -λ	x α i
					tn i=1	x i ≥a √ n-tn;	i=1
			≤	x i ∈[0,n)∩N,i=1,••• ,tn tn i=1 x i ≥a √ n-tn;	c tn 15 exp -λ	(a √ t α-1 n -t n ) α n
			x i ∈[0,n)∩N,i=1,••• ,tn ≤ (nc 15 ) tn exp -λ	(a √ t α-1 n -t n ) α n	,	(A.3)
								tn i=1	x α i ≥ t n	tn i=1 x i t n	α	≥	(a	√ t α-1 n -t n ) α n	.
	Plugging (A.2) and (A.3) into (A.1), we obtain that
								lim sup n→∞	t α-1 n n α/2 log P	i=1 tn	|X i | ≥ a	√ n ≤ -λa α ,
	which suffices to conclude (1) of Lemma A.2.
	Proof of (2): P	tn i=1	lim inf n→∞ |X i | ≥ a √ n ≤ c 15 t n e -e n α t α n n α/2 log -log P + P	tn tn i=1 i=1	X i ≥ a |X i | ≥ a √ √ n n, sup ≥ a α . a √ tn n	α	,	(A.4)
	Proof. It suffices to consider P where we use the fact	tn i=1 |X i | ≥ a √	n . Observe that
	P	tn i=1	|X i | ≥ a	√	n ≤ P sup 1≤i≤tn tn i=1 e x α i ≥ exp max |X i | ≥ n + P 1≤i≤tn x α i ≥ exp tn i=1	|X i | ≥ a √ tn i=1 x i n, sup 1≤i≤tn α t n .	|X i | < n .	(A.1)
	Consequently,
								n→∞ lim inf	t α
	Apparently,
							P sup

1≤i≤tn |X i | ≥ n ≤ t n P(|X| ≥ n) ≤ c 14 t n e -λn α . (A.2) 1≤i≤tn |X i P 1≤i≤tn |X i | < n n n α/2 log -log P tn i=1

Acknowledgement. We are grateful to Prof. Zhan Shi for enlightenment on Lemma 3.3. Hui He is supported by NSFC (No. 11671041, 11531001, 11371061).

This shows that there are sufficiently many particles in t. As always, we say that s u := ρ<v≤u x v is the position of u ∈ t and x u its displacement. For each u ∈ t and that κ(u) is the number of its children, if it is selected to be in t * , x * u = x u (but its ancestor line might be changed, so might be its position).

At the (t n -1)-th generation, there are at least B sn-1 particles in t. Let us rearrange them according to their positions:

(together with their descedants) to be in t * . Those particles are said to be selected. For u (j) , if κ(u (j) ) = B, we jump to consider u (j+1) . Otherwise, we prune B -κ(u (j) ) unselected particles at the t n -th generation and graft them to u (j) . The fact that |Z t tn | = B sn ensures that u (j) finally has B children for any ∀1 ≤ j ≤ B sn-1 .

Suppose that we have already got the B i+1 particles with their descendants for the generation k 0 + i + 1 of t * . We are interested in their parents at the (k 0 + i)-th generation in t, the number of which is at least B i . We rearrange them according to their positions:

their descendants in t * , For w (j) , if κ(w (j) ) = B, we jump to consider u (j+1) . Otherwise, we prune B -κ(w (j) ) unselected particles at the (k 0 + i + 1)-th generation together with their descendants and graft these subtrees to w (j) .

We continue this backward construction until the k 0 -th generation where there is only one particle in t * . We then take directly all its ancestors in t to establish the single branch of t * .

In the following figure, we give an example of this construction. The horizontal axis represents generations and the vertical axis represents positions of particles. In FigA, from the tree t, we choose B sn particles in J and colour them in red. In FigB, we subtract all the ancestors of the red particles and remove the others. In FigC, we do the pruning and grafting for the last two generations as explained above. In FigD, we get the final labelled tree t * in blue while the red particles are those chosen in J . The blue dashed lines link the particles and their added descendants at each step.

A Appendix

Proof. This sequence (L k ) k≥1 is non-decreasing, so its limit exists. In fact, if L ∈ (0, Λ -1 (log 1 Note that the rate function γ is convex, so we only need that γ (u) = L and the infimum is log 1 p 1 -Λ(L) ≥ 0. Note that if L k ≤ θ := Λ(p 1 ), log 1 p 1 = Λ(θ), and