# Branching random walk with infinite progeny mean: A tale of two tails

Souvik Rayª, Rajat Subhra Hazraᵇ,ᶜ,*, Parthanil Royᵈ, Philippe Soulierᵉ

Received 3 November 2021; received in revised form 14 November 2022; accepted 2 March 2023

Available online 4 March 2023

## Abstract

We study the extremes of branching random walks under the assumption that the underlying Galton-Watson tree has infinite progeny mean. It is assumed that the displacements are either regularly varying or they have lighter tails. In the regularly varying case, it is shown that the point process sequence of normalized extremes converges to a Poisson random measure. We study the asymptotics of the scaled position of the rightmost particle in the nth generation when the tail of the displacement behaves like $exp(-K(x))$, where either K is a regularly varying function of index $r > 0$, or K has an exponential growth. We identify the exact scaling of the maxima in all cases and show the existence of a non-trivial limit when $r > 1$.

©2023 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).

MSC: primary 60J80; 05C81; secondary 60G70

Keywords: Branching random walk; Galton-Watson tree with infinite progeny mean; Cloud speed; Point processes; Extremes

## 1. Introduction

Branching random walk is a very important model in the context of statistical physics and probability. The basic model is very simple and intuitive. It starts with a particle at the

<footnote>ªDepartment of Statistics, Stanford University, United States of America</footnote>

<footnote>ᵇLeiden University, The Netherlands</footnote>

<footnote>ᶜIndian Statistical Institute, Kolkata, India</footnote>

<footnote>ᵈIndian Statistical Institute, Bangalore, India</footnote>

<footnote>ᵉUniversité Paris-Nanterre, France</footnote>

<footnote>* Corresponding author at: Leiden University, The Netherlands.</footnote>

<footnote>E-mail addresses: souvikr@stanford.edu (S. Ray), r.s.hazra@math.leidenuniv.nl (R.S. Hazra), parthanil.roy@gmail.com (P. Roy), philippe.soulier@parisnanterre.fr (P. Soulier).</footnote>
origin. The particle splits into a random number of particles following a specified progeny distribution and each new particle makes a random displacement on $\mathbb{R}$. The new particles form the first generation. Each particle in the first generation splits into a random number of particles according to the same law and independently of the past as well as of the other particles in the same generation. Each new particle makes a random displacement from the position of its parent following the same displacement distribution, independently from other particles. The new particles form the second generation. This mechanism goes on. This resulting system is called a branching random walk (BRW).

It is clear that the particles in the system described above naturally form a rooted Galton–Watson tree if we forget about their positions. The progeny distribution of this branching process will be denoted by $\{p_k\}_{k\ge0}$, with $p_k := \mathbb{P}(Z_1 = k)$, where $Z_n$ denotes the number of individuals at generation $n \ge 0$ with $Z_0 = 1$. This Galton–Watson tree will be denoted by $\mathbb{T} = (V, E)$, where $V$ is the set of vertices of the tree and $E$ is the collection of edges. The collection of particles or vertices at the $n$th generation will be denoted by $D_n$.

We identify each edge $e_v$ of the Galton–Watson tree with its vertex $v$ away from the root; we then assign a real-valued random variable $X_{e_v}$, the displacement of the corresponding particle. Our model implies that conditioned on the Galton–Watson tree $\mathbb{T}$, $\{X_e : e \in E\}$ is a collection of i.i.d. random variables. Because of the underlying tree structure, for each vertex $v$, there is a unique geodesic path connecting it to the root. We shall denote the collection of all edges on this path by $I_v$. It is easy to see that the position of the particle corresponding to the vertex $v$ is given for $v \in V$ by

$$S_v := \sum_{e \in I_v} X_e.$$

The collection $\{S_v : v \in V\}$ is called the Branching Random Walk (BRW) induced by the tree $\mathbb{T} = (V, E)$ and the displacements $\{X_e : e \in E\}$. The main focus of the study of BRW is the study of the asymptotic behaviour of $\{S_v : v \in D_n\}$ when $n$ tends to $\infty$, or the behaviour of functions such as the maximum displacement, $M_n := \max_{v \in D_n} S_v$; the range of the displacements $R_n := (\max_{v \in D_n} S_v - \min_{v \in D_n} S_v)$; order statistics or different gap statistics, etc.

## Literature review:

The earliest works on branching random walks include [11,27,30]. This model and its extreme value theory have now become very important because of their connections to various probabilistic models (e.g., Gaussian free fields, conformal loop ensembles, multiplicative cascades, tree polymers, etc.); see [1,2,14,21,28]. Extremes of the branching random walk with heavy-tailed displacement has been studied by [6,7,9,10,22,23,25,35]. The point process of displacements of a branching random walk with finite progeny mean is described through a Cox-cluster process, rather implicitly in case of light-tailed displacements [33] and more explicitly in the heavy tailed set-up [9]. The limiting point process seems to have an universal stability structure, as was predicted by [15]. For a detailed discussion of such stability properties, we refer the readers to [8,34,42] and also refer to the exposition by [41] for a detailed background on the topic. Infinite mean branching processes and branching random walks (with infinite progeny mean) are intimately tied up with many scale free networks and hence important in study of random graphs. See for example the recent work of [20,31,43–45] which explore the relationship of infinite mean branching process with various graph properties. The branching random walks considered in these random graph models live on $\mathbb{Z}^d$.
The main focus of this paper will be on the analysis of the behaviour of the BRW when the progeny distribution has infinite mean, i.e., $E(Z_1) = \infty$. We would like to point out here the conditions in [2] under which the weak limit for the left-most position was computed. Although the conditions allowed for the progeny distribution to have infinite mean, they will fail to hold whenever the progeny variables have infinite mean and are independent from the tree structure, the foundational assumption of our analysis in this paper. In the branching process literature, the asymptotic behaviour of the number of particles in the $n$th generation under infinite mean was first studied in [17,40]. The conditions in [40] were later improved by [18,26,39]. In this article we shall follow throughout the sufficient conditions mentioned in [18]. It was shown in [18] that if the progeny distribution has a moment index (cf. Remark 2.2) $\alpha \in (0, 1)$, then

$$ \alpha^n \log Z_n \xrightarrow{a.s} W, \qquad (1.1) $$

where $W$ is a non-negative random variable, and almost surely positive on the event of survival of the tree. In other words, in the infinite mean set-up, the generation size explodes in a double-exponential manner if the tree survives. As a consequence we establish that in this case the Galton–Watson tree, up to the $n$th generation, has most of its particles in the last generation, i.e., the total progeny up to the $(n-1)$th generation is negligible when compared to the number of particles at the $n$th generation (see Lemma 2.4). This presence of a huge number of particles in the last generation, shows that most pairs of particles in the last generation have very few common ancestors and therefore the dependence between their displacements is very low. Consequently, it is expected that the behaviour of $\{S_v : v \in D_n\}$ will be close to the behaviour of $Z_n$ many independent realizations of the displacement random variable. These heuristics will provide the correct results when displacements are heavy tailed but not when the displacements are light tailed. We shall see that in the case of distributions with tails decaying at infinity at a rate faster than the exponential distribution, contributions from other generations, and hence the appropriately scaled maxima converge to a non-trivial constant.

### Main contributions:

In Section 3 we shall restrict our attention to the situation where the displacement distribution has a regularly varying right tail with index $-\beta$, i.e., if $F$ is the displacement distribution function, then

$$ \lim_{x \to \infty} \frac{1 - F(tx)}{1 - F(x)} = t^{-\beta}, \quad \forall t > 0, \qquad (1.2) $$

for some $\beta > 0$. We denote the class of regularly varying functions with index $-\beta$ by $RV_{-\beta}$. To analyse the asymptotic behaviour of the $n$th generation, as $n$ becomes large, we shall take the approach of point process theory. We shall scale the positions of the particles with non-negative displacement in the $n$th generation by $C_n := F^{-}(1 - \frac{1}{Z_n})$. Throughout this paper, $F^{-}$ will denote the (left-continuous) inverse of $F$, defined as $F^{-}(y) := \inf\{s : F(s) \ge y\}$, for all $y \in [0, 1]$. Choice of this random scaling is inspired by the deterministic scaling used in [10]. In Theorem 3.2, we show that the point process converges to a Poisson random measure with intensity measure $\tau_{\beta}^{+}$, where $\tau_{\beta}^{+}([x, \infty)) = x^{-\beta}$, for all $x > 0$. This shows there is no clustering in the limit under the above scaling and the dependency structure gets camouflaged by the size of the last generation. An important consequence comes from Corollary 3.4. We show that the maximum displacement $M_n$ grows doubly exponentially conditioned on the survival of the tree, that is

$$ \alpha^n \log M_n \xrightarrow{P} \frac{W}{\beta}. \qquad (1.3) $$
Here $P \to$ corresponds to convergence in probability. One can, in fact show almost sure convergence of the first $k$ order statistics in the log scale to the same limit, see Theorem 3.5. As announced, both tail indices come into play in these asymptotics. The point process result stated in Theorem 3.2 can be used also to get various other order statistics of the displacement random variables. The proof of the point process convergence relies on the one large jump principle which we use to show that the point process based on the scaled positions in the $n$th generation is close (in an appropriate metric) to the point process based on the displacements in the last generation (see Lemma 2.4).

In Section 4 we consider the case when the right tail is no-longer regularly varying. We assume that tail of the displacement distribution is asymptotically like $\exp(-K(x))$ where $K(x)$ is regularly varying with index $r \in (0, \infty)$. Important examples of such distribution include Gaussian, exponential and Weibull random variables. Under some additional conditions on the left tail we show in Theorem 4.2 that almost surely the following asymptotics is true:

$$ \lim_{n \to \infty} \frac{M_n}{L(\log Z_n)} = \begin{cases} (1 - \alpha^{\frac{1}{r-1}})^{\frac{1}{r-1}}, & \text{if } r > 1, \\ 1, & \text{if } 0 < r \le 1. \end{cases} \quad (1.4) $$

where $L = K^{-}$ is the left-continuous inverse of $K$. We would like to point out the change in behaviour of the maximum when $r > 1$. When $r \le 1$, it still happens that the resulting contribution comes from the last generation of the branching process but when $r > 1$, there are non-negligible contributions from all the generations. Although this does not change the rate of growth for the maximum displacement, the effect is apparent in the limiting constant.

In Section 5 we consider the case when the right tail decays much faster than those considered in Section 4. In particular, we assume that $1-F(x) = \exp(-K(x))$ where $L := K^{-}$ is slowly varying at $\infty$. Under some additional technical conditions on the growth rate of $L$, we show in Theorem 5.2 that almost surely the following asymptotics hold true:

$$ \lim_{n \to \infty} \frac{M_n}{\sum_{k=1}^{n} L(\alpha^{-k})} = 1. \quad (1.5) $$

Unlike the previous cases, here each generation contributes equally to the right-most displacement in the last generation and the resulting maximum position $M_n$ has magnitude of strictly higher order than $L(\log Z_n)$, the magnitude of the largest displacement in the last generation. See Section 5 for a detailed explanation of the phenomenon.

It is noteworthy that the results for the displacement in the Gumbel domain of attraction are not uniform, contrary to the i.i.d. case. Here, we observe different normalizations according to the tail, whereas for $n$ i.i.d. observations, it always hold that $M_n/L(\log n)$ converges to 1 in probability, and almost surely under a very mild restriction, see [19, Theorem 5.4.5].

The speed of a branching random walk can be defined in many ways. The cloud speed, burst speed and sustainable speed are some of the possibilities. We refer to [36] for definition and detailed discussions on these topics. The equivalence of these three notions of speed was established by [11,27,30] under assumptions of finite progeny mean and finiteness of the moment generating function. The later condition was removed by [25] where the tail of displacement random variables were assumed to follow a semi-exponential distribution, which changed the rate of growth of the maxima. The definitions of the speeds was modified accordingly. In Section 6, we define properly scaled versions of cloud, burst and sustainable speeds under Assumptions 3.1, 4.1 and 5.1. We then establish the equivalence of these three notions of speeds in each of those cases.
We would now like to point out an aspect which differentiates the nature of the main results in Section 3, Section 4 and Section 5. In Section 3, Corollary 3.4 provides us with an weak limit of properly scaled $M_n$ (as stated in (3.7)). This can be watered down to a version concerned with in-probability limit for $\log M_n$ after proper scaling, see (3.8). Since the limit in (3.8) is non-degenerate, it can be viewed also as a weak limit. A similar phenomenon occurs in Theorem 4.2 where we state an almost sure limit for properly scaled version of $M_n$ in (4.3), which again can be interpreted as an weak limit due to non-degeneracy of the limit. In both of these cases we take another logarithm and compute a degenerate almost sure limit which we refer to as the cloud speed. In contrast to these, Theorem 5.2 immediately gives us a degenerate almost sure limit. In certain spirit, therefore, Theorem 5.2 provides us with the cloud speed when F satisfies Assumption 5.1. We do not get any weak limit here, although the proof technique is very similar to the one employed to prove Theorem 4.2.

## Notation

We use the notation $X_n \stackrel{\text{a.s.}}{\sim} a_n$ to indicate that $X_n/a_n \to 1$ almost surely. We also use the notion that $a_n$ grows at least exponentially to mean $\liminf_{n\to\infty} n^{-1} \log a_n > 0$. Similarly a sequence $a_n$ grows at least double-exponentially when $\liminf_{n\to\infty} n^{-1} \log \log a_n > 0$. For any real number $x$, we shall denote its non-negative part by $x^+$. Most of our results will be “conditioned on the survival of the Galton–Watson tree”. In places where it is obvious we skip this phrase. Given the tree, we will denote $D_n$ to be the particles in the $n$th generation. $e_v$ will denote the edge that connects particle or node $v$ to $p(v)$ where $p(v)$ will refer to the parent/immediate ancestor of the particle $v$. Also $C(v)$ will denote the set of all children of the particle $v$. Throughout the paper, the notations $\stackrel{\text{a.s.}}{\longrightarrow} \stackrel{\text{P}}{\longrightarrow}$ and $\stackrel{\text{D}}{\longrightarrow}$ will stand for almost sure convergence, convergence in probability and weak convergence respectively. The notation $\mathbb{1}(A)$ will denote the indicator function for the event $A$. Binomial($n$, $p$) and Poisson($\lambda$) will denote Binomial and Poisson distributions respectively with corresponding parameters. We also introduce the notation $G_{(\delta)}$ to denote the distribution function of $\lfloor Z^\delta \rfloor$ where $Z \sim G$, for any distribution function $G$ supported on non-negative integers.

## 2. Infinite progeny mean branching process

We shall first recall the main result of [18] on the asymptotic properties of the Galton–Watson tree under the assumption that the progeny mean is infinite. Throughout this paper, $G$ will denote the distribution function of $Z_1$, the non-negative integer valued branching progeny and $\tilde{G} = 1 - G$ will denote its survival function.

**Assumption 2.1 (Assumption on the Branching Random Variable).** There exists a function $\gamma : \mathbb{R}^+ \to \mathbb{R}^+$ and a constant $\alpha \in (0, 1)$ such that,

(D1) $\gamma$ is non-increasing.

(D2) $x \mapsto x^{\gamma(x)}$ is non-decreasing.

(D3) $\int_0^\infty \gamma(e^{e^x}) dx < \infty$.

(D4) $\exists x_0 > 0$, such that

$$x^{-\gamma(x)} \le x^{\alpha} \tilde{G}(x) \le x^{\gamma(x)}, \quad \forall x \ge x_0.$$
**Remark 2.2.** It is easily seen that $\alpha$ is the moment index of $G$, i.e. $E[Z_1^p] < \infty$ for all $p < \alpha$ and $E[Z_1^p] = \infty$ for all $p > \alpha$. Distribution functions with Pareto tails of the form $cx^{-\alpha}$ satisfy Assumption 2.1. More generally, if $\tilde{G}(x) = x^{-\alpha}L(x)$ with $L$ slowly varying and either $(\log L(x))/\log(x)$ or $-(\log L(x))/\log(x)$ satisfying (D1)–(D4), then $G$ satisfies Assumption 2.1. However, regular variation of $\tilde{G}$ is not implied by Assumption 2.1. It is also easily seen that if two distributions $G_1, G_2$ are tail equivalent (in the sense that there exist finite, positive constants $C_1$ and $C_2$ such that $C_1\tilde{G}_1(x) \le \tilde{G}_2(x) \le C_2\tilde{G}_1(x)$ for large $x$) and one satisfies the conditions in Assumption 2.1, then so does the other one.

We now quote the main result of [18].

**Theorem 2.3 (Theorem 1, [18]).** Under Assumption 2.1, there exists a non-degenerate, non-negative random variable $W$ such that

$$ \alpha^n \log(Z_n + 1) \xrightarrow{a.s.} W. \qquad (2.1) $$

Moreover, $P(W = 0) = q$ where $q$ is the probability of extinction of the Galton–Watson tree.

The convergence Eq. (2.1) shows that conditioning on the survival of the tree is equivalent to conditioning on the event $W > 0$, that is, the events $\mathbb{T}$ survives} and $\{W > 0\}$ differ by an event of probability zero.

A consequence of Theorem 2.3 which will be used to prove our results is the following lemma which tells that almost all the mass of the tree is concentrated in the last generation. To be more precise, total mass of the tree before the last generation is comparable to the mass of the last generation only in the log-scale.

**Lemma 2.4.** Assume the progeny distribution satisfies Assumption 2.1. Then for any $s > 0$, conditionally on survival at $\mathbb{T}$,

$$ \frac{1}{\log Z_n} \log \left( \sum_{i=0}^{n-1} Z_i^s \right) \xrightarrow{a.s.} s\alpha. $$

**Proof.** Take $\omega \in (W > 0) \cap (\alpha^n \log(Z_n + 1) \to W)$. Then we have $\alpha^n \log(Z_n(\omega)) \to W(\omega)$. Choose $\varepsilon > 0$ and get $n_0 \in \mathbb{N}$ such that

$$ \exp(\alpha^{-n}(1 - \varepsilon)W(\omega)) \le Z_n(\omega) \le \exp(\alpha^{-n}(1 + \varepsilon)W(\omega)), \quad \forall n \ge n_0. \qquad (2.2) $$

Now, for all $n > n_0$, using (2.2) we have

$$ \begin{aligned} \frac{1}{\log Z_n(\omega)} \log \sum_{i=n_0}^{n-1} Z_i^s(\omega) &\le \frac{1}{\log Z_n(\omega)} \log \sum_{i=n_0}^{n-1} \exp(\alpha^{-i}(1+\varepsilon)sW(\omega)) \\ &\le \frac{1}{\log Z_n(\omega)} \log \left[ n \exp(\alpha^{-(n-1)}(1+\varepsilon)sW(\omega)) \right] \\ &\le \frac{\log n + \alpha^{-(n-1)}(1+\varepsilon)sW(\omega)}{\alpha^{-n}(1-\varepsilon)W(\omega)} \to s\alpha \frac{1+\varepsilon}{1-\varepsilon}, \end{aligned} \qquad (2.3) $$

where the last line is true since $W(w) > 0$. Noting that $Z_n(\omega) \to \infty$ and then taking $\varepsilon \downarrow 0$, we conclude that

$$ \limsup_{n \to \infty} \frac{1}{\log Z_n(\omega)} \log \sum_{i=0}^{n-1} Z_i^s(\omega) \le s\alpha. $$
An exactly similar argument shows the lower bound. This completes the proof. □

Both Theorem 2.3 and Lemma 2.4 consider the homogeneous branching process, i.e. a branching process with identical progeny distribution over the generations. Indeed, in this article we shall restrict our attention to homogeneous branching processes only. But the techniques we shall apply to prove the main results in Section 5 will require some results analogous to Theorem 2.3, but in the context of a special kind of inhomogeneous branching trees. We shall explain the premise and state the result below while deferring the proof to the Appendix.

Consider the inhomogeneous branching process starting with one particle at the 0th generation and where the particles of the nth generation, for any $n \ge 0$, produce i.i.d. number of off-springs, having distribution function $G_n$, independent of previous generations as well as the particles in the same generation. We assume the following assumption on the progeny sequence $\{G_n : n \ge 0\}$.

**Assumption 2.5.** There exists $x_0 \in (0, \infty)$ and a sequence of positive real numbers $\{\alpha_n : n \ge 0\}$ in $(0, 1)$, bounded away from 0 and 1, such that for some $\gamma : \mathbb{R}^+ \mapsto \mathbb{R}^+$ satisfying (D1), (D2) and (D3), we have the following.

$$x^{-\gamma(x)} \le x^{\alpha_n} \bar{G}_n(x) \le x^{\gamma(x)}, \quad \forall x \ge x_0, \forall n \ge 0.$$

**Theorem 2.6.** Let $Z_n$ denote the size of the nth generation for the inhomogeneous branching process with progeny sequence $\{G_n : n \ge 0\}$ satisfying Assumption 2.5. Then there exists an event $E$ with $\mathbb{P}(E) > 0$ and a positive random variable $W^*$ such that

$$\left( \prod_{j=0}^{n-1} \alpha_j \right) \log(Z_n + 1) \xrightarrow{a.s.} W^*, \text{ on } E.$$

**Remark 2.7.** Theorem 2.3 is clearly a special case of Theorem 2.6 for the choice of the sequence $G_n = G$ and $\alpha_n = \alpha$ for all $n \ge 0$. We want to emphasize the fact that the proof of Theorem 2.6 uses Theorem 2.3 and hence does not provide an independent proof of Theorem 2.3.

**Remark 2.8.** The proof of Theorem 2.6 uses Lemma 4.5, which will be proved in the Appendix. We would like to point out here that Lemma 4.5 will also be instrumental in proving the main result in Section 4, namely Theorem 4.2.

### 3. BRW with regularly varying displacements

In this section we shall describe the extremes of the branching random walk when the displacement variables associated with the edges are i.i.d. with regularly varying tail. In this case, one can derive the exact asymptotics of the point process of rescaled positions and show that the behaviour is similar to an i.i.d. set-up. When the progeny distribution has finite mean and satisfies the Kesten–Stigum condition the point process behaviour was described in [9]. The extremes in such a set-up (with finite mean) with more general conditions were derived in [23]. We now extend the above results to infinite mean progeny distribution.

**Assumption 3.1.** Given the tree $\mathbb{T} = (V, E)$ we assume
(R1) the displacement random variables {$X_e$}$_{e \in E}$ are i.i.d. with distribution F.

(R2) $1 - F \in RV_{-\beta}$, for some $\beta > 0$.

(R3) there exists $\upsilon \in (\alpha\beta, \infty)$ such that $x^{\upsilon}F(-x) = O(1)$ as $x \to \infty$.

Recall that $F^{-}$ is the left-continuous inverse of F. Let us now define the random scaling

$$
C_n := F^{-} \left( 1 - \frac{1}{Z_n} \right) = \left( \frac{1}{1-F} \right)^{-} (Z_n). \qquad (3.1)
$$

Let us consider the set $\mathcal{E} := (0, \infty]$, with the usual topology (obtained by the one-point uncompactification of $[0, \infty]$). Keeping in mind the notation for the BRW defined in Section 1, we define,

$$
N_n^+ := \sum_{v \in D_n} \delta_{C_n^{-1} S_v^+} = \sum_{v \in D_n} \delta_{C_n^{-1} (\sum_{e \in I_v} x_e)^+}, \quad \forall n \ge 1.
$$

We consider point processes as random elements in the space $M_p(\mathcal{E})$ of all Radon point
measures on a locally compact and separable metric space $\mathcal{E}$ (for this section $\mathcal{E} = (0, \infty]$).
Here $M_p(\mathcal{E})$ is endowed with the vague convergence; for further details on point processes,
see [29,37,38]. The following result describes the asymptotic behaviour of the point process
$N_n^+$. In this paper, $PRM(\mu)$, for a measure $\mu$ on $\mathbb{R}$, will refer to the *Poisson random measure*
on $\mathbb{R}$ with mean measure $\mu$; see [37, Section 3.3] for a detailed exposition on Poisson random
measures.

**Theorem 3.2.** *Under Assumptions 2.1 and 3.1 we have*

$$
N_n^+ \xrightarrow{D} PRM(\tau_\beta^+), \quad \text{conditioned on survival,}
$$

where $\tau_{\beta}^{+}$ is the unique measure on $(0, \infty]$ such that $\tau_{\beta}^{+}((x, \infty]) = x^{-\beta}$.

Theorem 3.2 describes the asymptotics for the point process generated by the non-negative parts of the scaled positions of particles in the nth generation. Indeed, this result will be enough regarding our analysis of asymptotic behaviour for the displacement of the right-most particle. Nevertheless, an asymptotics for the point process generated by scaled positions of the particles can be derived under a stronger condition than (R3), known in literature as tail-balance condition, which in effect dictates that the left tail for the distribution F should decay at least as fast as the right tail. In contrast, note that (R3) allows the left tail of F to be slightly heavier than its right tail.

**Theorem 3.3.** Let *Assumptions 2.1 and 3.1* holds true. Moreover, *assume that*

$$
\lim_{x \to \infty} \frac{\mathbb{P}(X > x)}{\mathbb{P}(|X| > x)} = 1 - \lim_{x \to \infty} \frac{\mathbb{P}(X < -x)}{\mathbb{P}(|X| > x)} = p \in (0, 1],
$$

where $X \sim F$. Under these assumptions, we have

$$
N_n := \sum_{v \in D_n} \delta_{C_n^{-1} S_v} \xrightarrow{D} PRM(\tau_\beta), \quad \text{conditioned on survival,}
$$

where $\tau_\beta$ is the unique measure on $[-\infty, \infty]$ such that $\tau_\beta((x, \infty]) = x^{-\beta}$ and $\tau_\beta([-\infty, -x)) = (1-p)x^{-\beta}/p$, for any $x > 0$.

We shall omit the proof of **Theorem 3.3** since it follows exactly the same arguments used
in the proof of **Theorem 3.2**. The above result verifies Brunet and Derrida [15] conjectures
in this setup with the limiting extremal point process being a Poisson random measure with no clustering. The reason behind this cluster-breaking phenomenon is that the extremes are governed by the last generation displacements thanks to regular variation and Lemma 2.4, which will be the key ingredient in the proof.

**Proof of Theorem 3.2.** The proof will consist of two steps. Let us first define

$$ \tilde{N}_n^+ := \sum_{v \in D_n} \delta_{C_n^{-1} X_{e_v}^+}, \quad \forall n \ge 1, $$

where $e_v$ denotes the edge that connects particle or node $v$ to its parent, for $v \in D_n$, $n \ge 1$. In the first step, we will prove that

$$ \tilde{N}_n^+ \xrightarrow{D} PRM(\tau_\beta^+), \quad (3.2) $$

conditionally on survival. Let $d_v$ be a metric which induces the topology of vague convergence. Next we shall demonstrate that the point processes $N_n^+$ and $\tilde{N}_n^+$ are asymptotically close, i.e.,

$$ d_v(\tilde{N}_n^+, N_n^+) \xrightarrow{P} 0, \quad (3.3) $$

conditionally on survival. Theorem 3.2 then follows by applying [12, Theorem 4.1]. □

**Proof of (3.2).** Consider $\{X_i\}_{i \ge 1} \stackrel{\text{i.i.d.}}{\sim} F$, independent of $\mathbb{T}$. We define $b_n = F^{-}(1 - 1/n)$. Thus $C_n = b_{Z_n}$ and

$$ \tilde{N}_n^+ = \sum_{v \in D_n} \delta_{C_n^{-1} X_{e_v}^+} \stackrel{d}{=} \sum_{j=1}^{Z_n} \delta_{C_n^{-1} X_j^+} = \sum_{j=1}^{Z_n} \delta_{b_{Z_n}^{-1} X_j^+} $$

By [37, Proposition 3.21] we have

$$ \sum_{i=1}^{n} \delta_{b_n^{-1} X_i^+} \xrightarrow{D} PRM(\tau_\beta^+), \quad \text{as } n \to \infty. $$

We also have $Z_n \xrightarrow{a.s.} \infty$, conditioned on survival with $\{Z_i\}_{i \ge 1}$ being independent to $\{X_i\}_{i \ge 1}$. Therefore,

$$ \tilde{N}_n^+ \stackrel{d}{=} \sum_{j=1}^{Z_n} \delta_{b_{Z_n}^{-1} X_j^+} \xrightarrow{D} PRM(\tau_\beta), \quad \text{as } n \to \infty, \text{ conditioned on survival.} \quad \square $$

**Proof of (3.3).** Here $\mathbb{1}(\cdot)$ denotes the indicator variable for the event inside the parenthesis and $A$ denotes the event that $\mathbb{T}$ survives. Fix Lipschitz continuous function $g \in C_K^+(\mathcal{E})$ with $\text{supp}(g) \subseteq (\delta, \infty]$. It is enough to show that for any $\varepsilon > 0$,

$$ \mathbb{P}[|N_n^+(g) - \tilde{N}_n^+(g)| \ge \varepsilon | A] \to 0. $$

Define $U_n = \sum_{k=1}^{n-1} \sum_{v \in D_k} \mathbb{1}\{C_n^{-1}|X_{e_v}| > n^{-2}\}$. On the event $\{U_n = 0\}$, all the displacements occurred until the $(n-1)$th generation are of absolute size at most $C_n/n^2$. Therefore, for any $v \in D_n$, we have

$$ |C_n^{-1} S_v^+ - C_n^{-1} X_{e_v}^+| \le \sum_{e \in I_v: e \ne e_v} C_n^{-1} |X_e| \le \sum_{e \in I_v: e \ne e_v} n^{-2} = (n-1)n^{-2} < 1/n. $$
Two situations can arise on {$U_n = 0$}: if $C_n^{-1}X_{e_v}^+ \le \delta/2$, and $n$ is large enough such that $\delta/2 > 1/n$, then $C_n^{-1}S_v^+ < \delta$, and therefore $g(C_n^{-1}S_v^+) = g(C_n^{-1}X_{e_v}^+) = 0$. Otherwise, using the Lipschitz continuity of $g$, we can say that $|g(C_n^{-1}S_v^+) - g(C_n^{-1}X_{e_v}^+)| \le M/n$, for Lipschitz constant $M \in (0, \infty)$. Combining these two bounds we conclude that, on {$U_n = 0$}, for large enough $n$,

$$ 
\begin{aligned}
|N_n^+(g) - \tilde{N}_n^+(g)| &\le \sum_{v \in D_n} |g(C_n^{-1}S_v^+) - g(C_n^{-1}X_{e_v}^+)| \\
&\le \frac{M}{n} \sum_{v \in D_n} \mathbb{1}\{C_n^{-1}X_{e_v}^+ > \delta/2\} \\
&= \frac{M}{n} \tilde{N}_n^+((\delta/2, \infty]).
\end{aligned}
$$

Hence, for any $\varepsilon > 0$, and large enough $n$,

$$ \mathbb{P}[|N_n^+(g) - \tilde{N}_n^+(g)| \ge \varepsilon | A] \le \mathbb{P}[\frac{M}{n}\tilde{N}_n^+((\delta/2, \infty]) \ge \varepsilon | A] + \mathbb{P}(U_n \ge 1 | A). \quad (3.4) $$

By (3.2), {$\tilde{N}_n^+((\delta/2, \infty])$}$_{n \ge 1}$ is a tight family since the set $(\delta/2, \infty]$ is relatively compact in $\mathcal{E}$. This implies that the first term on the right hand side converges to 0. We now prove that the second term in the right of (3.4) tends to 0. For any $e \in E$, conditioned on $\mathbb{T}$, $\mathbb{1}\{C_n^{-1}|X_e| > n^{-2}\}$ is a Bernoulli random variable with parameter $p_n \le \bar{F}(n^{-2}C_n) + F(-n^{-2}C_n)$. Hence,

$$ \mathbb{P}[U_n \ge 1 | \mathbb{T}] \le \mathbb{E}[U_n | \mathbb{T}] = p_n \sum_{k=1}^{n-1} Z_k. $$

By Assumption (R2) and applying [37, Proposition 0.8(i),(v)] on the non-decreasing function $1/\bar{F} \in RV_\beta$, we have $\log F^{-}(1 - 1/x) = (1/\beta + o(1))\log x$, as $x \to \infty$. Therefore, on $(W > 0)$, $\log C_n = \log F^{-}(1 - 1/Z_n) = (1/\beta + o_p(1))\log Z_n$, which implies $C_n/n^2 \to \infty$. Applying again [37, Proposition 0.8(i)] on the function $\bar{F} \in RV_{-\beta}$, we obtain $\log \bar{F}(n^{-2}C_n) = (-\beta + o_p(1))\log(n^{-2}C_n)$, on $(W > 0)$. Combining the above mentioned asymptotics we get, on $W > 0$,

$$ 
\begin{aligned}
\log \left( \bar{F}(n^{-2}C_n) \sum_{k=1}^{n-1} Z_k \right) &= -(\beta + o_p(1)) \log C_n + 2(\beta + o_p(1)) \log n + \log \sum_{k=1}^{n-1} Z_k \\
&= -(1 + o_p(1)) \log Z_n + 2(\beta + o_p(1)) \log n + \log \sum_{k=1}^{n-1} Z_k \\
&= -(1 + o_p(1)) \log Z_n + 2(\beta + o_p(1)) \log n \\
&\quad + (\alpha + o_p(1)) \log Z_n \to -\infty
\end{aligned}
\quad (3.5) $$

as $\log Z_n$ grows exponentially on $(W > 0)$ and $\alpha < 1$. In the last line, we have used Lemma 2.4 with $s = 1$. Similarly, applying (R3), we get the following almost surely on $W > 0$.

$$ 
\begin{aligned}
\log \left( F(-n^{-2}C_n) \sum_{k=1}^{n-1} Z_k \right) &\le -(\nu \log C_n + 2\nu \log n + O(1)) + \log \sum_{k=1}^{n-1} Z_k \\
&= -(\nu/\beta + o_p(1)) \log Z_n + 2\nu \log n + (\alpha + o_p(1)) \log Z_n \to -\infty.
\end{aligned}
\quad (3.6) $$

Combining (3.5) and (3.6), we conclude the proof. $\square$

Some corollaries can easily be derived from Theorem 3.2 about the asymptotic behaviour of the ordered statistic of the displacement of the particles in the $n$th generation as $n \to \infty$.
**Corollary 3.4.** Fix $k \ge 1$. Let, $M_n^{(k)}$ be the $k$th maximum value in the set $\{S_v : v \in D_n\}$. Then under assumptions of **Theorem 3.2**, we have

$$ \mathbb{P}(C_n^{-1} M_n^{(k)} \le x) \to \exp(-x^{-\beta}) \left[ \sum_{j=0}^{k-1} \frac{1}{j!} x^{-\beta j} \right] \quad (3.7) $$

as $n \to \infty$ conditioned on the survival of the tree. Moreover,

$$ \alpha^n \log M_n^{(k)} \xrightarrow{p} \frac{W}{\beta}, \quad \text{conditioned on survival.} \quad (3.8) $$

**Proof.** For any $x > 0$ and $k \ge 1$ we have from **Theorem 3.2**

$$ \mathbb{P}(N_n^+((x, \infty]) \le k-1 | \mathbb{T} \text{ survives}) \to \mathbb{P}(\text{Poisson}(x^{-\beta}) \le k-1). $$

Also, observe that $(N_n^+((x, \infty]) \le k-1) = (C_n^{-1} M_n^{(k)} \le x)$ and

$$ \mathbb{P}(\text{Poi}(x^{-\beta}) \le k-1) = \exp(-x^{-\beta}) \left[ \sum_{j=0}^{k-1} \frac{1}{j!} x^{-\beta j} \right] = H(x) $$

for some distribution function $H$ which gives mass on $(0, \infty)$. Therefore,

$$ C_n^{-1} M_n^{(k)} \xrightarrow{D} H, \quad \text{conditioned on survival.} \quad (3.9) $$

This proves the first part of the result. On taking logarithms on both sides of (3.9) and multiplying by $\alpha^n$ we have

$$ \alpha^n \log M_n^{(k)} - \alpha^n \log C_n \xrightarrow{p} 0. \quad (3.10) $$

Under Assumption (R2), $(1/(1-F))^{\leftarrow} \in RV_{1/\beta}$. Using [37, Proposition 0.8], we have,

$$ \frac{\alpha^n \log C_n}{\alpha^n \log Z_n} = \frac{\log C_n}{\log Z_n} = \frac{\log [(1/(1-F))^{\leftarrow}(Z_n)]}{\log Z_n} \xrightarrow{a.s.} \frac{1}{\beta}, \quad \text{conditioned on survival.} $$

Finally using **Theorem 2.3** we have

$$ \alpha^n \log C_n \xrightarrow{a.s.} \beta^{-1} W, $$

conditioned on survival. Using (3.10) we have the desired result. $\square$

**Corollary 3.4** says that the rightmost particles of the BRW go away from the origin in a double-exponential speed in this set-up. Such double-exponential growth was also observed only for the rightmost particle in a related setup by [45]. Indeed we can improve the convergence in (3.7) to almost sure convergence as demonstrated by **Theorem 3.5**. We want to emphasize the fact that this result is independent of **Theorem 3.2**, in the sense that its proof does not use the assertion made in the statement of **Theorem 3.2**. Indeed, **Theorem 3.2** can only yield convergence in probability for the random variable sequence $\alpha^n \log M_n^{(k)}$ as demonstrated in **Corollary 3.4**.

**Theorem 3.5.** For any $k \in \mathbb{N}$, under the assumptions of **Theorem 3.2**, conditionally on the survival of the Galton–Watson tree $\mathbb{T}$,

$$ \lim_{n \to \infty} \alpha^n \log M_n^{(k)} = \beta^{-1} W, \quad \text{almost surely.} $$
**Proof of Theorem 3.5.** We shall first prove the lower bound. Let $u_{n,k}^* \in D_n$ denotes the vertex such that $X_{e_{u_{n,k}^*}}$ is the $k$th largest of the collection $\{X_{e_v} : v \in D_n\}$. Independence of the tree structure $\mathbb{T}$ and the displacement variables guarantee that conditioned on $\mathbb{T}$, the random vertex $p(u_{n,k}^*)$ is a uniformly chosen random element from $D_{n-1}$ and hence $S_{p(u_{n,k}^*)} | \mathbb{T} \sim F^{*(n-1)}$ where $F^{*l}$ denotes the $l$-fold convolution of $F$. Fix any $\varepsilon > 0$ and $\beta_1 > \beta$. On the event $(W > 4\varepsilon)$, We have the following for large enough $n$.

$$
\begin{aligned}
& \log \mathbb{P} \left( \alpha^n \log X_{e_{u_{n,k}^*}} \le \beta_1^{-1} (W - 2\varepsilon) \middle| \mathbb{T} \right) \\
& \le \log \left\{ \binom{Z_n}{Z_n - k + 1} \left[ F \left( \exp \left( \beta_1^{-1} (W - 2\varepsilon) \alpha^{-n} \right) \right) \right]^{Z_{n-k+1}} \right\} \\
& \le k \log Z_n + (Z_n - k + 1) \log \left[ 1 - \bar{F} \left( \exp \left( \beta_1^{-1} (W - 2\varepsilon) \alpha^{-n} \right) \right) \right] \\
& \le k \log Z_n - (Z_n - k + 1) \bar{F} \left( \exp \left( \beta_1^{-1} (W - 2\varepsilon) \alpha^{-n} \right) \right) \\
& \le k \log Z_n - C_1 (Z_n - k + 1) \exp \left( -(W - 2\varepsilon) \alpha^{-n} \right),
\end{aligned}
\quad (3.11)
$$

for some (non-random) constant $C_1 > 0$. We have used Potter's bound [37, Proposition 0.8(ii)] in (3.11). By Theorem 2.3, we have, conditionally on survival of the tree,

$$ \alpha^n \log [C_1(Z_n - k + 1) \exp(-(W - 2\varepsilon)\alpha^{-n}) - k \log Z_n] \xrightarrow{a.s.} 2\varepsilon, $$

and hence

$$ \mathbb{P} \left( \alpha^n \log X_{e_{u_{n,k}^*}} \le \beta_1^{-1} (W - 2\varepsilon) \middle| \mathbb{T} \right) \le \exp \left( - \exp \left( \varepsilon \alpha^{-n} \right) \right), $$

for all $n \ge N_1(\varepsilon)$, where $N_1(\varepsilon)$ is finite almost surely. On the other hand, for large enough $n$,

$$
\begin{aligned}
\mathbb{P} \left( \alpha^n \log(S_{p(u_{n,k}^*)}^{-} + 1) > \beta_1^{-1} \varepsilon \middle| \mathbb{T} \right) &\le F^{*(n-1)} \left( -\exp(\beta_1^{-1} \varepsilon \alpha^{-n}) + 1 \right) \\
&\le nF \left( -\exp(\beta_1^{-1} \varepsilon \alpha^{-n})/(n-1) + 1/(n-1) \right) \\
&\le C_2 n \left( \exp(\beta_1^{-1} \varepsilon \alpha^{-n})/(n-1) - 1/(n-1) \right)^{-\gamma} \\
&\le C_3 n^{1+\gamma} \exp(-\gamma \beta_1^{-1} \varepsilon \alpha^{-n}),
\end{aligned}
$$

where $C_2, C_3$ are non-random finite constants. Applying First Borel-Cantelli Lemma and taking $\beta_1 \downarrow \beta$, we can conclude $\liminf_{n \to \infty} \alpha^n \log S_{u_{n,k}^*} = \liminf_{n \to \infty} \alpha^n \log(S_{p(u_{n,k}^*)} + X_{e_{u_{n,k}^*}}) \ge \beta^{-1}(W - \varepsilon)$ almost surely on the event $(W > 4\varepsilon)$. Recalling that the event $(W > 0)$ and the event of survival of the tree are same almost surely, we take $\varepsilon \downarrow 0$ and conclude that $\liminf_{n \to \infty} \alpha^n \log S_{u_{n,k}^*} \ge \beta^{-1}W$, almost surely on $(W > 0)$. The lower bound now follows from the observation that

$$ M_n^{(k)} \ge \min_{j=1}^k S_{u_{n,j}^*}, \quad \forall n \ge 1. $$

It is enough to prove the upper bound for $k=1$. Observe that for fixed $\beta_2 \in (0, \beta)$ and $\varepsilon > 0$, by Potter's bound [37, Proposition 0.8(ii)], we have for some finite constant $C_4$ and $n$ large enough,

$$
\begin{aligned}
\mathbb{P} \left( \alpha^n \log M_n^{(1)} \ge \beta_2^{-1} (W + 2\varepsilon) \middle| \mathbb{T} \right) &\le \sum_{v \in D_n} \mathbb{P} \left( S_v \ge \exp \left( \beta_2^{-1} (W + 2\varepsilon) \alpha^{-n} \right) \middle| \mathbb{T} \right) \\
&\le Z_n n \bar{F} \left( \frac{1}{n} \exp \left( \beta_2^{-1} (W + 2\varepsilon) \alpha^{-n} \right) \right)
\end{aligned}
$$
$$ \leq C_4 Z_n n^{\beta_2+1} \exp(-\alpha^{-n}(W + 2\varepsilon)). $$

By Theorem 2.3, we have, conditionally on survival of the tree,

$$ \alpha^n \log [C_2 Z_n n^{\beta_2+1} \exp(-\alpha^{-n}(W + 2\varepsilon))] \xrightarrow{a.s.} -2\varepsilon, $$

and hence

$$ \mathbb{P} \left( \alpha^n \log M_n^{(1)} \geq \beta_2^{-1} (W + 2\varepsilon) \mid \mathbb{T} \right) \leq \exp(-\varepsilon \alpha^{-n}), $$

for all $n \geq N_2(\varepsilon)$, where $N_2(\varepsilon)$ is finite almost surely. Applying First Borel–Cantelli Lemma and taking $\beta_2 \uparrow \beta$, we conclude the proof. $\square$

## 4. BRW with rapidly varying tails

**Assumption 4.1.** $F$ is a distribution function on $\mathbb{R}$ with the following properties.

(F1) $F(x) < 1$, $\forall x \in \mathbb{R}$, and $K := -\log(1 - F)$ is regularly varying at $\infty$ with index $r \in (0, \infty)$.

(F2) For some $M \in (0, \infty)$ and $\eta > 0$, $F(-t) \leq M(\log|t|)^{-2-\eta}$, for $t$ large enough.

Examples of distributions satisfying (F1) include the Weibull distributions with $K(x) = cx^r$ and the Gaussian distribution with $K(x) \sim x^2/2$. Assumption (F1) is very close to implying that $F$ is in the domain of attraction for the maximum of the Gumbel distribution, but some additional condition on $K$ is needed to ensure that property; see e.g. [16] for examples and counterexamples.

Let $L$ be the left-continuous inverse of $K$, that is

$$ L(u) = \inf\{x : K(x) > u\}, \quad u \in (0, 1). \tag{4.1} $$

Then $F^{-}(x) = L(-\log(1-x))$, for all $0 < x < 1$ and $L$ is regularly varying at $\infty$ with index $1/r$; cf. [37, Proposition 0.8(v)]. By the regular variation of $L$ and Theorem 2.3, it is not hard to see the following formula (cf. [37, Proposition 0.8]), that for all $a > 0$,

$$ \lim_{n \to \infty} \frac{L(a \log Z_n)}{L(\alpha^{-n})} = a^{1/r} W^{1/r}, \quad \text{almost surely conditioned on survival.} \tag{4.2} $$

We now state our main result.

**Theorem 4.2.** Let Assumptions 2.1 and 4.1 hold. Then, almost surely conditioned on survival,

$$ \lim_{n \to \infty} \frac{M_n}{L(\log Z_n)} = \begin{cases} (1 - \alpha^{\frac{1}{r-1}})^{\frac{1}{r-1}}, & \text{if } r > 1, \\ 1, & \text{if } 0 < r \le 1. \end{cases} $$

As an immediate corollary of Theorem 4.2 and (4.2), we obtain that almost surely conditioned on survival,

$$ \lim_{n \to \infty} \frac{M_n}{L(\alpha^{-n})} = [(1 - \alpha^{\frac{1}{r-1}})^{\frac{1}{r-1}} \lor 1] W^{\frac{1}{r-1}}, \tag{4.3} $$

where $x_+$ denotes the non-negative part of $x$.

**Comments and examples.** The case $r < 1$ contains subexponential distributions in the domain of attraction (for the maximum) of the Gumbel law. The heuristic properties of such distributions is the “single large jump principle”, which means that the sum of a finite number
of i.i.d. random variables having a subexponential distribution is large when exactly one of the summands is large. Given this principle and the double exponential growths of the population, it is expected that the maximum $M_n$ will be large only if one displacement of the last generation is large. Thus Theorem 4.2 confirms the intuition in the case $r < 1$. This is similar to the case of regularly varying displacements considered in Theorem 3.2. However, we could not obtain the convergence of the point process of exceedance in the present case, and we do not know if the same result (as in the case of regularly varying displacements) can be expected. The case $r = 1$ contains distributions which are subexponential (take for instance $K(x) = x(\log x)^{-\beta}$ with $\beta > 0$, [24, cf. Example 1.4.3 (b)]), and distributions which are not subexponential such as the exponential distribution. However, we obtain the same result as in the subexponential case.

The case $r > 1$ is more intriguing. It contains distributions which are also in the domain of attraction of the Gumbel law, but are not subexponential. Heuristically, this implies that a sum of i.i.d. random variables with such a distribution is large when many or all terms contribute significantly to the sum. However, the double exponential growth of the population implies that the displacements of the older generation contribute less. The form of the limit hints at exponential smoothing. More precisely, if $K(x) \sim cx^r$, it can be shown, using results on the tail of the sum of i.i.d. random variables with such distribution, see e.g. [4, Theorem 1.1] or [3, Theorem 4.1], that the approximate asymptotic behaviour of $M_n$ is the same as the behaviour of

$$ \max_{1 \le j \le Z_n} \sum_{i=1}^{n} \alpha^{\frac{n-i}{r}} X_i^{(j)} $$

where $X_i^{(j)}$ are i.i.d. and independent of $Z_n$. For Gaussian displacements which corresponds to $K(x) \sim x^2/2$, we have $L(x) \sim \sqrt{2x}$ and Theorem 4.2 reads

$$ \lim_{n \to \infty} \frac{M_n}{\sqrt{\log Z_n}} = \sqrt{\frac{2}{1-\alpha}}, \quad \text{almost surely conditionally on survival,} $$

and (4.3) becomes

$$ \lim_{n \to \infty} \alpha^{n/2} M_n = \sqrt{\frac{2W}{1-\alpha}}, \quad \text{almost surely conditionally on survival.} $$

We now turn to the proof of Theorem 4.2, for which we will need the following lemma whose proof is in the Appendix.

**Lemma 4.3.** Suppose that we have a filtration $\{\mathcal{F}_n : n \ge 0\}$ on the probability space $(\Omega, \mathcal{F}, \mathbb{P})$ and an $\mathcal{F}_n$-adapted non-negative integer-valued process $\{\zeta_n : n \ge 0\}$ such that $\liminf_{n \to \infty} n^{-1} \log \zeta_n > 0$, almost surely. Further assume that for all $n \ge 1$, there exists a collection of random variables, $\{G_{n,i} : i \le \zeta_n\}$ satisfying the following two conditions.

(1) The collection $\{G_{n,i} : i \le \zeta_n\}$ is $\mathcal{F}_{n+1}$-measurable.

(2) Conditioned on $\mathcal{F}_n$, $\{G_{n,i} : i \le \zeta_n\}$ is a collection of i.i.d. variables with distribution function $F$ satisfying $F(x) < 1$ for all $x$ and $K(L(x)) \sim x$ as $x \to \infty$, where $K = -\log(1-F)$ and $L$ is the left-continuous inverse of $K$. Also assume that

$$ \lim_{t \to 1} \lim_{x \to \infty} \frac{L(tx)}{L(x)} = 1. $$
Fix a sequence {$\psi_n$}$_{n \ge 1}$ in (0, 1), bounded away from 1 and let $l_n$ be another $F$-adapted non-negative integer valued process such that $\log l_n \stackrel{\text{a.s.}}{\sim} (1 - \psi_n) \log \zeta_n$ and $\psi_n \log \zeta_n \stackrel{\text{a.s.}}{\to} \infty$, as $n \to \infty$. Let $G_{i:\zeta_n}$ be the ith largest element in {$G_{n,1}, \dots, G_{n,\zeta_n}$}. Then,

$$ \frac{G_{l_n;\zeta_n}}{L(\psi_n \log \zeta_n)} \xrightarrow{\text{a.s.}} 1, \text{ as } n \to \infty. $$

The assertion is also true if we take $l_n = \psi_n = 1$ for all $n \ge 1$.

**Remark 4.4.** If $F$ satisfies (F1) then the assumptions on $F$, stated in Lemma 4.3, holds true. By [13, Theorem 1.5.12], we have $K(L(x)) \sim x$ as $x \to \infty$, whereas $L(tx)/L(x) \to t^{1/r}$ as $x \to \infty$, since $L$ is regularly varying with index $1/r$.

For i.i.d. regularly varying random variables (i.e. when $G_n = G$ for all $n$), the next result is a stronger version of the law of iterated logarithm; see e.g. [46]. Since Assumption 2.5 does not imply regular variation and we deal with triangular arrays with random row sizes, we provide a proof based on estimates of the Laplace transform of the distributions $G_n$ due to [18] in the Appendix.

**Lemma 4.5.** Fix a sequence of distribution functions {$G_n : n \ge 0$} satisfying Assumption 2.5 with moment index sequence {$\alpha_n : n \ge 0$}. Suppose that we have a filtration {$F_n : n \ge 0$} on the probability space $(\Omega, \mathcal{F}, \mathcal{P})$ and an $F_n$-adapted positive integer-valued process {$\zeta_n : n \ge 0$} such that $\liminf_{n \to \infty} n^{-1} \log \log \zeta_n > 0$, almost surely. Assume that for all $n \ge 0$, there exists a collection of random variables, {$L_{n,i} : i \le \zeta_n$} satisfying the following two conditions.

(1) The collection {$L_{n,i} : i \le \zeta_n$} is $F_{n+1}$-measurable.

(2) Conditioned on $F_n$, {$L_{n,i} : i \le \zeta_n$} is a collection of i.i.d. variables having distribution function $G_n$.

Then we can find a positive integer valued finite random variable $N$ such that

$$ 0 < \prod_{n \ge N+1} \frac{\alpha_n \log \sum_{i=1}^{\zeta_n} L_{n,i}}{\log \zeta_n} < \infty, \text{ almost surely .} $$

Consequently,

$$ \frac{\alpha_n \log \sum_{i=1}^{\zeta_n} L_{n,i}}{\log \zeta_n} \xrightarrow{\text{a.s.}} 1, \text{ as } n \to \infty. $$

We now have all the necessary ingredients for the proof of Theorem 4.2. We shall split the proof into a lower and an upper bound.

**Proof of Theorem 4.2, lower bound.** The idea to obtain a lower bound is to truncate the tree at the kth generation from the last one. We obtain a bound for the displacements up to the generation $n-k$ of the form $\vartheta_k L(\log Z_n)$ with $\vartheta_k \to 0$ as $k \to \infty$. The most delicate part of the proof is then to choose subsets of vertices from each of the remaining generations such that all the vertices in those subsets are among the ones having largest displacements from their parents in their respective generations but still having a path from the $(n-k)$th generation through these subsets to the last generation. The first criterion forces us to choose the subsets as small as possible while the second one requires the subsets to be large. As a trade-off between them we get our required lower bound.
To be more precise, fix an integer $k \ge 1$ and $\delta_0, \dots, \delta_k \in (0, 1)$. We define recursively a finite sequence of subsets of vertices from the tree. Set $B_{n,n-k} = D_{n-k}$. Let $A_{n,n-k}$ be the set of vertices in $D_{n-k}$ whose displacements from their parents are among the largest $\lfloor Z_{n-k}^{1-\delta_k} \rfloor$ many of those in $B_{n,n-k}$. For $i = 1, \dots, k$; let $B_{n,n-k+i}$ be the set of children of the vertices in $A_{n,n-k+i-1}$ and let $A_{n,n-k+i}$ be the set of vertices in $B_{n,n-k+i}$ whose displacements from their parents are among the largest $\lfloor |B_{n,n-k+i}|^{1-\delta_{k-i}} \rfloor$ many of those in $B_{n,n-k+i}$. We always break the ties uniformly at random whenever some of the displacements are equal.

Our construction has been done in such a way that on the event ($|A_{n,n}| > 0$), there exists at least one ray of vertices starting from $A_{n,n-k}$ and going through $A_{n,n-k+i}$ for all $0 \le i \le k$. Let $v_{n-k}^*$ be one such vertex in $A_{n,n-k}$ generating such a ray. Then the following crucial observation will be pivotal in proving our lower bound.

$$M_n \mathbb{1}(|A_{n,n}| > 0) \ge \mathbb{1}(|A_{n,n}| > 0) \max_{v \in A_{n,n}} S_v \ge \mathbb{1}(|A_{n,n}| > 0) \left[ S_{p(v_{n-k}^*)} + \sum_{i=0}^k \min_{v \in A_{n,n-k+i}} X_{e_v} \right]. \quad (4.4)$$

The lower bound will then follow after establishing appropriate lower bounds for the two terms within bracket in the right hand side of (4.4). All the almost sure statements, which appear in the following proof, are assumed to be conditioned on the survival of the tree.

We start by obtaining a lower bound to the first term in the right hand side of (4.4). We employ an argument similar to the one used in the proof of lower bound in Theorem 3.5. Notice that if we condition on $\{Z_i : i \ge 1\}$, independence of progeny and displacement variables guarantee that $p(v_{n-k}^*)$, the parent of the vertex $v_{n-k}^*$, is a uniform random element from $D_{n-k-1}$ after conditioning and hence $S_{p(v_{n-k}^*)}$ has distribution $F^{*(n-k-1)}$, where $F^*$ denotes the $l$-fold convolution of $F$. Fix an arbitrary $\varepsilon > 0$ and observe that for large enough $n$,

$$\begin{aligned} \mathbb{P} (L(\alpha^{-n})^{-1} S_{p(v_{n-k}^*)} \le -\varepsilon | \{Z_i\}_{i \ge 1} ) &= F^{*(n-k-1)}(-\varepsilon L(\alpha^{-n})) \\ &\le (n-k-1)F(-\varepsilon L(\alpha^{-n})/(n-k-1)) \quad (4.5) \\ &\le nF(-\varepsilon L(\alpha^{-n})/n) \\ &\le Mn(\log \varepsilon + \log L(\alpha^{-n}) - \log n)^{-2-\eta} \le M_1 n^{-1-\eta}, \quad (4.6) \end{aligned}$$

for some finite positive constant $M_1$, depending on $\varepsilon$, $\alpha$, $r$ and $M$. The inequality (4.5) follows from a simple application of union bound, whereas the inequalities in (4.6) follow from Assumption (F2) and the fact that $\log L(\alpha^{-n}) \sim -\frac{n}{r} \log \alpha$; see [37, Proposition 0.8(i)]. Since the final expression is summable and $\varepsilon$ is arbitrary, an application of the first Borel–Cantelli Lemma implies that $\liminf_{n \to \infty} L(\alpha^{-n})^{-1} S_{p(v_{n-k}^*)} \ge 0$, almost surely.

As a first step to get a lower bound on the second term in the right hand side of (4.4), we make the following two claims.

(1) $\liminf_{n \to \infty} \alpha^n \log |A_{n,n-k+i}|$, $\liminf_{n \to \infty} \alpha^n \log |B_{n,n-k+i}| > 0$, almost surely, for all $0 \le i \le k$.

(2) $\log |A_{n,n-k+i}| \stackrel{\text{a.s.}}{\sim} \alpha^{-1}(1 - \delta_{k-i}) \log |A_{n,n-k+i-1}|$, for all $1 \le i \le k$.

The first claim, in particular, implies that $|A_{n,n}| \stackrel{\text{a.s.}}{\longrightarrow} \infty$, leading to the following simplification of (4.4).

$$\liminf_{n \to \infty} L(\alpha^{-n})^{-1} M_n \ge \liminf_{n \to \infty} L(\alpha^{-n})^{-1} \left[ S_{p(v_{n-k}^*)} + \sum_{i=0}^k \min_{v \in A_{n,n-k+i}} X_{e_v} \right]. \quad (4.7)$$
The proof of the claims will be carried out by an induction on $i$. Note that,

$$ \alpha^n \log |A_{n,n-k}| \stackrel{\text{a.s.}}{\sim} \alpha^n (1-\delta_k) \log |B_{n,n-k}| = \alpha^n (1-\delta_k) \log Z_{n-k} \stackrel{\text{a.s.}}{\sim} \alpha^k (1-\delta_k) W > 0. \quad (4.8) $$

This establishes the first claim for $i = 0$. The vertices in $A_{n,n-k}$ produce i.i.d. numbers off-springs (independent of their current positions) having distribution $G$ and their sum (i.e., the total number of children) is $|B_{n,n-k+1}|$; thus Lemma 4.5 gives $\log |B_{n,n-k+1}| \stackrel{\text{a.s.}}{\sim} (1/\alpha) \log |A_{n,n-k}|$. Here we have applied Lemma 4.5 with $\mathcal{F}_n$ being the $\sigma$-algebra which contains all the information (tree structure and displacement) of the tree upto generation $(n-k)$, $\zeta_n = |A_{n,n-k}|$ and $G_n \equiv G$. The validity of the two conditions needed to apply Lemma 4.5 is guaranteed by (4.8) and the independence of displacements in one generation of the tree from the information of previous generations. Finally, the identity $|A_{n,n-k+1}| = \lfloor |B_{n,n-k+1}|^{1-\delta_{k-1}} \rfloor$ yields that $\log |A_{n,n-k+1}| \stackrel{\text{a.s.}}{\sim} \alpha^{-1}(1-\delta_{k-1}) \log |A_{n,n-k}|$. This proves the induction hypothesis for the base case $i = 1$. The proof of the veracity of the induction hypothesis for $i = l+1$ assuming it is true for $i = l$ goes exactly along the same lines.

Using the claim established just above, we can conclude that

$$ \alpha^n \log |A_{n,n-k+i}| \to \alpha^{k-i} W \prod_{j=0}^{i} (1 - \delta_{k-j}), \quad (4.9) $$

almost surely, for all $0 \le i \le k$. In particular, $|A_{n,n-k+i}|$ and hence $|B_{n,n-k+i}|$ grows doubly-exponentially almost surely.

Now observe that by construction $\min_{v \in A_{n,n-k+i}} X_{ev}$ is the $\lfloor |B_{n,n-k+i}|^{1-\delta_{k-i}} \rfloor$th largest element in the collection $\{X_{ev} : v \in B_{n,n-k+i}\}$. Also notice that conditioned on the information of the tree upto generation $(n-k+i)$, the collection $\{X_{ev} : v \in B_{n,n-k+i}\}$ is just an i.i.d. sample from distribution function $F$. Hence, using Lemma 4.3 and the fact that $|B_{n,n-k+i}|$ grows doubly-exponentially almost surely, we obtain the following for $0 \le i \le k$.

$$ \liminf_{n \to \infty} \frac{\min_{v \in A_{n,n-k+i}} X_{ev}}{L(\delta_{k-i} \log |B_{n,n-k+i}|)} \ge 1, \quad \text{almost surely.} $$

Here we have applied Lemma 4.3 with $\mathcal{F}_n$ being the $\sigma$-algebra which contains all the information (tree structure and displacement) of the tree upto generation $(n-k+i)$, $\zeta_n = |B_{n,n-k+i}|$ and $\psi_n \equiv \delta_{k-i}$. Again using the fact $|A_{n,n-k+i}| = \lfloor |B_{n,n-k+i}|^{1-\delta_{k-i}} \rfloor$ and regularly variation of $L$, we obtain for $0 \le i \le k$ the following.

$$ \liminf_{n \to \infty} \frac{\min_{v \in A_{n,n-k+i}} X_{ev}}{L(\log |A_{n,n-k+i}|)} \ge \left( \frac{\delta_{k-i}}{1 - \delta_{k-i}} \right)^{1/r}, \quad \text{almost surely.} \quad (4.10) $$

By (4.9), (2.1) and the regular variation of $L$ and the Uniform Convergence Theorem for regularly varying functions, we have

$$ \lim_{n \to \infty} \frac{L(\log |A_{n,n-k+i}|)}{L(\alpha^{-n})} = \left( \alpha^{k-i} \prod_{j=0}^{i} (1 - \delta_{k-j}) W \right)^{1/r}. \quad (4.11) $$

The limits (4.10) and (4.11) yield, for $i = 0, \dots, k$,

$$ \liminf_{n \to \infty} \frac{\min_{v \in A_{n,n-k+i}} X_{ev}}{L(\alpha^{-n})} \ge \left( \alpha^{k-i} \frac{\delta_{k-i}}{1 - \delta_{k-i}} \prod_{j=0}^{i} (1 - \delta_{k-j}) W \right)^{1/r}. $$
Combining all the previous limit estimates for the terms in right hand side of (4.7) and using (4.2), we obtain

$$ \liminf_{n \to \infty} \frac{M_n}{L(\log Z_n)} \ge \sum_{i=0}^{k} \left( \alpha^{k-i} \frac{\delta_{k-i}}{1 - \delta_{k-i}} \prod_{j=0}^{i} (1 - \delta_{k-j}) \right)^{1/r} . $$

Maximizing over the right hand side we conclude that

$$ \liminf_{n \to \infty} \frac{M_n}{L(\log Z_n)} \ge f_k := \sup \left\{ \sum_{i=0}^{k} \left( \alpha^{k-i} \frac{\delta_{k-i}}{1 - \delta_{k-i}} \prod_{j=0}^{i} (1 - \delta_{k-j}) \right)^{1/r} \mid \delta_0, \dots, \delta_k \in (0, 1) \right\} . $$

In order to compute $f_k$, we define, for $k \ge 1$ and $\delta_0, \dots, \delta_k \in (0, 1)$,

$$ h_k(\delta_0, \dots, \delta_{k-1}) := \sum_{i=0}^{k} \left( \alpha^{k-i} \frac{\delta_{k-i}}{1 - \delta_{k-i}} \prod_{j=0}^{i} (1 - \delta_{k-j}) \right)^{1/r} = \sum_{i=0}^{k} \left( \alpha^i \delta_i \prod_{q=i+1}^{k} (1 - \delta_q) \right)^{1/r}, \\ f_k = \sup \{ h_k(\delta_0, \dots, \delta_k) : \delta_0, \dots, \delta_k \in (0, 1) \} $$

Taking $\delta_0 \uparrow 1$ and $\delta_i \downarrow 0$ for $i \ge 1$ yields $f_k \ge 1$. Furthermore,

$$ h_k(\delta_0, \dots, \delta_k) = (\alpha^k \delta_k)^{1/r} + (1 - \delta_k)^{1/r} h_{k-1}(\delta_0, \dots, \delta_{k-1}), $$

and hence we have for all $k \ge 1$,

$$ \begin{aligned} f_k &= \sup \left\{ \alpha^{k/r} \delta_k^{1/r} + (1 - \delta_k)^{1/r} h_{k-1}(\delta_0, \dots, \delta_{k-1}) : \delta_0, \dots, \delta_k \in (0, 1) \right\} \\ &= \sup \left\{ \alpha^{k/r} \delta_k^{1/r} + (1 - \delta_k)^{1/r} f_{k-1} : \delta_k \in (0, 1) \right\} \\ &= \begin{cases} (\alpha^{k/(r-1)} + f_{k-1}^{r/(r-1)})^{1-1/r}, & \text{if } r > 1, \\ \max \{\alpha^{k/r}, f_{k-1}\}, & \text{if } 0 < r \le 1. \end{cases} \end{aligned} $$

For $r > 1$, opening the recursion we get $f_k^{r/(r-1)} = f_0^{r/(r-1)} + \sum_{i=1}^k \alpha^{i/(r-1)}$. Having observed that $f_0 = \sup \{\delta_0^{1/r} : \delta_0 \in (0, 1)\} = 1$, we conclude

$$ f_k^{r/(r-1)} = \begin{cases} \sum_{i=0}^{k} \alpha^{i/(r-1)}, & \text{if } r > 1, \\ 1, & \text{if } 0 < r \le 1. \end{cases} $$

Letting $k$ tend to $\infty$, we therefore conclude that almost surely,

$$ \begin{aligned} \liminf_{n \to \infty} \frac{M_n}{L(\log Z_n)} &\ge \begin{cases} (1 - \alpha^{1/(r-1)})^{\frac{1}{r}-1}, & \text{if } r > 1, \\ 1, & \text{if } 0 < r \le 1. \end{cases} \\ &= (1 - \alpha^{1/(r-1)})^{\frac{1}{r}-1} \lor 1. \end{aligned} $$

This proves the lower bound. $\square$

We now proceed to prove the upper bound. We first establish a preliminary non sharp upper bound which will be used to obtain the sharp one. This preliminary bound is basically obtained by summing over maximum displacement from the parent in each generation.
**Lemma 4.6.** Under the assumptions of Theorem 4.2, there exists an almost surely finite random variable A such that

$$ \limsup_{n \to \infty} \frac{M_n}{L(\log Z_n)} \le \frac{AW^{1/r}}{1 - \alpha^{1/r}}, \quad \text{almost surely.} \qquad (4.12) $$

**Proof.** Introduce the notation

$$ \tilde{M}_{Z_i} := \max_{v \in D_i} X_{ev}. $$

Note that $M_n \le \sum_{i=1}^n \tilde{M}_{Z_i}$. Since $K(L(x)) \ge x$, for all $x$, we get

$$ \begin{aligned} \mathbb{P}[\tilde{M}_{Z_i} > L((1 + \varepsilon) \log Z_i) | \mathbb{T}] &= 1 - (F \circ L((1 + \varepsilon) \log Z_i))^{Z_i} \\ &= 1 - (1 - \exp(-K \circ L((1 + \varepsilon) \log Z_i)))^{Z_i} \\ &\le 1 - (1 - \exp(-(1 + \varepsilon) \log Z_i))^{Z_i} \\ &= 1 - (1 - Z_i^{-1-\varepsilon})^{Z_i} \le Z_i^{-\varepsilon}. \end{aligned} $$

Since the last expression is summable, we have by Borel–Cantelli Lemma, almost surely conditioned on survival,

$$ M_n \le \sum_{i=1}^{n} \tilde{M}_{Z_i} \le \sum_{i=1}^{n} L((1 + \varepsilon) \log Z_i) + \sum_{i=1}^{\infty} (\tilde{M}_{Z_i} \vee 0) \mathbf{1}(\tilde{M}_{Z_i} > L((1 + \varepsilon) \log Z_i)), \qquad (4.13) $$

where the second expression in the right hand side of (4.13) is finite almost surely. By (4.2), there exists a random finite number A such that $L((1 + \varepsilon) \log Z_i) \le AL(\alpha^{-i})$ for all $i \ge 1$, almost surely. Therefore, almost surely conditionally on survival,

$$ \begin{aligned} \limsup_{n \to \infty} \frac{M_n}{L(\alpha^{-n})} &\le \limsup_{n \to \infty} \frac{1}{L(\alpha^{-n})} \sum_{i=1}^{n} L((1 + \varepsilon) \log Z_i) \\ &\le A \limsup_{n \to \infty} \frac{1}{L(\alpha^{-n})} \sum_{i=1}^{n} L(\alpha^{-i}) = \frac{A}{1 - \alpha^{1/r}}, \end{aligned} $$

where the last assertion follows from Lemma A.4. By Theorem 2.3 and (4.2), this proves (4.12). □

Before diving into the main part of the proof for the upper bound, let us try to explain in a few words how does the proof work. We first fix some $k \ge 1$ and cut the tree at generation $(n-k)$. We use the preliminary bound obtained from (4.12) for the displacements until generation $(n-k)$. The upper bound on the displacements occurred in the last $k$ generations is then obtained from Lemma 4.7, which gives an upper bound to the maximum position in the last generation of a BRW, started with (possibly random) exponentially growing number of vertices but grown only upto a finite number of generations. Combining them together and taking $k$ tend to infinity will finish our proof.

**Lemma 4.7.** Fix $k \ge 1$. Consider a probability space $(\Omega, \mathcal{F}, \mathbb{P})$ and a filtration $\{\mathcal{H}_k : k \in \mathbb{Z}\}$. Start with an $\mathcal{H}_n$-adapted sequence of random positive integers $\{\sigma_n\}_{n \ge 1}$ satisfying $\liminf_{n \to \infty} n^{-1} \log \log \sigma_n > 0$, almost surely. Consider the following dynamics. Start with $\sigma_n$
particles in 0th generation (possibly scattered randomly over the real line) Then grow a BRW, $\mathbb{B}_n$, up to k generations with progeny distribution G satisfying Assumption 2.1 and displacement distribution F satisfying Assumption (F1). Let $V_{n,q}$ denotes the set of vertices in qth generation of $\mathbb{B}_n$. Assume the following conditions.

(1) $\mathcal{H}_{n+q}$ contains all the information (cardinality and position of its constituents particles on the real line) of the random set $V_{n,q}$, for all $0 \le q \le k$, and $n \ge 1$.

(2) Fix $m \ge 2$. Conditionally on $\mathcal{H}_{m-1}$, $V_{n,m-n}$ is a BRW generation step for progeny G and displacement F from $V_{n,m-n-1}$, $\forall \max(m-k, 1) \le n \le m-1$. Further, these BRW generation steps are conditionally independent of each other conditional on $\mathcal{H}_{m-1}$.

Let $S_{n,v,q}$ denotes the displacement of the particle $v \in V_{n,t}$ from its ancestor in generation $q$, $0 \le q \le t \le k$, for the BRW $\mathbb{B}_n$. Then we have the following asymptotic behaviour almost surely.

$$ \limsup_{n \to \infty} \frac{\max_{v \in V_{n,k}} S_{n,v,0}}{L(\log \sigma_n)} \le \tilde{\alpha}_k := \begin{cases} \left(\sum_{i=1}^k \alpha^{-i/(r-1)}\right)^{1-1/r}, & \text{if } r > 1, \\ \alpha^{-k/r}, & \text{if } r \in (0, 1]. \end{cases} \quad (4.14) $$

**Remark 4.8.** In the statement of Lemma 4.7 and its proof, the statement “Conditional on $G$, $S_1$ is a BRW generation step for progeny G and displacement F from $S$” means that the $\sigma$-algebra $G$ contains all the information (the size and the position of its constituent particles) for the (random) set $S$ and $S_1$ is the first generation of a BRW with progeny G and displacement F having $S$ as the 0th generation, conditional on $G$. Conditional independence of two or more BRW generation steps will refer to conditional independence of progeny sizes and displacements induced in those steps.

To explain briefly how the proof of Lemma 4.7 works, we partition the first generation $V_{n,1}$ according to their displacements from their parents and recursively use similar partitioning technique on the sets of children of each partition block of the first generation. We continue with this recursive partitioning until the last generation. We then provide an upper bound to the total displacement incurred on a path travelling from the initial to last generation by the sum of maximum displacements of each partition block in which its constituent edges lie. Maximizing over such paths followed by optimizing over suitable partitions yield our required upper bound.

**Proof of Lemma 4.7.** We shall prove (4.14) by induction on $k$. As usual, $X_e$ will denote the displacement associated with the edge $e$ and $e_v$ denotes the edge connecting the particle $v$ to its parent $p(v)$. Note that the sequence $\{\tilde{\alpha}_k\}$ satisfies the recursion

$$ \tilde{\alpha}_{k+1} = \begin{cases} \alpha^{-1/r}(\tilde{\alpha}_k^{r/(r-1)} + 1)^{(r-1)/r}, & r > 1, \\ \alpha^{-1/r}\tilde{\alpha}_k, & 0 < r \le 1. \end{cases} \quad (4.15) $$

We start by proving the case $k = 1$. Since $|V_{n,1}|$ is the sum of $\sigma_n$ many i.i.d. variables having distribution G, Lemma 4.5 yields $\log|V_{n,1}| \stackrel{a.s.}{\sim} (1/\alpha) \log \sigma_n$, in particular $\liminf_{n \to \infty} n^{-1} \log \log |V_{n,1}| > 0$, almost surely. Here we have applied Lemma 4.5 with $\mathcal{F}_n = \mathcal{H}_n$, $\zeta_n = \sigma_n$, $G_n \equiv G$. Using independence of progeny and displacements, we have by Lemma 4.3 (applied with $\zeta_n = |V_{n,1}|$, $l_n = \psi_n = 1$) that $\max_{v \in V_{n,1}} X_{ev} \stackrel{a.s.}{\sim} L(\log|V_{n,1}|)$. Combining these two equivalences and using regular variation of L, we get

$$ \max_{v \in V_{n,1}} S_{n,v,0} = \max_{v \in V_{n,1}} X_{ev} \stackrel{a.s.}{\sim} \alpha^{-1/r} L(\log \sigma_n) = \tilde{\alpha}_1 L(\log \sigma_n), $$
proving the claim for $k = 1$.

Suppose the claim holds true for $k = 1, \dots, m$, for some $m \ge 1$. We proceed to prove the hypothesis for $m+1$. We will classify the particles according to the size of the first step. Fix a partition $\Pi = \{1 = \delta_0 > \delta_1 > \dots > \delta_l = 0\}$ of $[0, 1]$ and write $\|\Pi\|_r := \max_{i=1}^l |\delta_i^{1/r} - \delta_{i-1}^{1/r}|$. Consider a partition of $V_{n,1}$ as follows. Let $v_{(i)}$ be the particle in $V_{n,1}$ with $i$th largest displacement from its parent among the particles in $V_{n,1}$. The subset $A_{n,i}$ is then defined to be consisting of all those particles $v_{(j)}$ with $\lfloor|V_{n,1}|^{1-\delta_{i-1}}\rfloor \le j < \lfloor|V_{n,1}|^{1-\delta_i}\rfloor$, for all $i = 1, \dots, l$. Keep $v_{(|V_{n,1}|)}$ in the subset $A_{n,l}$. Clearly, $\{A_{n,i}\}_{1 \le i \le l}$ forms a partition of $V_{n,1}$. Notice that $|A_{n,i}| \stackrel{\text{a.s.}}{\sim} \lfloor|V_{n,1}|^{1-\delta_i}\rfloor - \lfloor|V_{n,1}|^{1-\delta_{i-1}}\rfloor$ grows double-exponentially almost surely, since $\log|V_{n,1}| \stackrel{\text{a.s.}}{\sim} (1/\alpha) \log \sigma_n$. Let $V_{n,m+1,i}$ be the set of particles in the $(m+1)$th generation with first generation ancestor in the subset $A_{n,i}$. Fixing our attention only to the subtree generated by elements in $A_{n,i}$, we notice this particular subtree to be of height $m$ and satisfies the conditions of **Lemma 4.7** (with $\sigma_n = |A_{n,i}|$). Therefore, by the induction hypothesis, we have the following for all $1 \le i \le l$.

$$ \limsup_{n \to \infty} \frac{\max_{v \in V_{n,m+1,i}} S_{n,v,1}}{L(\log |A_{n,i}|)} \le \tilde{\alpha}_m. $$

Observe that $\log|A_{n,i}| \stackrel{\text{a.s.}}{\sim} \log|V_{n,1}|^{1-\delta_i}$ $\stackrel{\text{a.s.}}{\sim} ((1-\delta_i)/\alpha) \log \sigma_n$. Combining this with the previous bound, we conclude that

$$ \limsup_{n \to \infty} \frac{\max_{v \in V_{n,m+1,i}} S_{n,v,1}}{L(\log \sigma_n)} \le \left( \frac{1-\delta_i}{\alpha} \right)^{1/r} \tilde{\alpha}_m. $$

By our construction, $\max_{u \in A_{n,i}} S_{n,u,0} = \max_{u \in A_{n,i}} X_{e_u}$ is the $\lfloor|V_{n,1}|^{1-\delta_{i-1}}\rfloor$th largest among the collection $\{X_{e_v} : v \in V_{n,1}\}$. Having almost sure exponential growth of $|V_{n,1}|$, we obtain by **Lemma 4.3**, $\max_{u \in A_{n,i}} S_{n,u,0} \stackrel{\text{a.s.}}{\sim} L(\delta_{i-1} \log|V_{n,1}|) \stackrel{\text{a.s.}}{\sim} (\delta_{i-1}/\alpha)^{1/r} L(\log \sigma_n)$. Combining the previous two estimates, observing that

$$ \max_{v \in V_{n,m+1,i}} S_{n,v,0} \le \max_{v \in V_{n,m+1,i}} S_{n,v,1} + \max_{u \in A_{n,i}} S_{n,u,0}, $$

and taking minimum over the partitions $\Pi$, we obtain that almost surely,

$$ \begin{aligned} \limsup_{n \to \infty} \frac{\max_{v \in V_{n,m+1}} S_{n,v,0}}{L(\log \sigma_n)} &\le \alpha^{-1/r} \inf_{\Pi} \left\{ \max_{i=1}^l \left[ (1-\delta_i)^{1/r} \tilde{\alpha}_m + \delta_{i-1}^{1/r} \right] \right\} \\ &\le \alpha^{-1/r} \inf_{\Pi} \left\{ \max_{i=1}^l \left[ (1-\delta_i)^{1/r} \tilde{\alpha}_m + \delta_i^{1/r} \right] + \|\Pi\|_r \right\} \\ &\le \alpha^{-1/r} \left\{ \sup_{s \in [0,1]} \left\{ (1-s)^{1/r} \tilde{\alpha}_m + s^{1/r} \right\} + \inf_{\Pi} \|\Pi\|_r \right\} \\ &\le \alpha^{-1/r} \sup_{s \in [0,1]} \left\{ (1-s)^{1/r} \tilde{\alpha}_m + s^{1/r} \right\}. \end{aligned} $$

Solving the optimization and using (4.15) completes the proof of the lemma. $\square$

**Proof of Theorem 4.2, upper bound.** In the proof, all almost sure statement are to be understood as almost surely on $(W > 0)$. Fix any $k \ge 1$. Consider the tree only from generation $(n-k)$. This is a BRW, started with $|D_{n-k}|$ vertices and grown up to $k$ generations, with progeny distribution $G$ and displacement distribution $F$ satisfying Assumption (F1). Since
$\liminf_{n \to \infty} n^{-1} \log \log |D_{n-k}| = -\log \alpha > 0$ almost surely, using Lemma 4.7, we obtain the following upper bound.

$$ \limsup_{n \to \infty} \frac{\max_{v \in D_n} S_{v,n-k}}{L(\log |D_{n-k}|)} \le \tilde{\alpha}_k, \text{ almost surely,} $$

where $S_{v,n-k}$ denotes the displacement of the vertex $v \in D_n$ from its ancestor in generation $(n-k)$. Here we have applied Lemma 4.7 with $\sigma_n = |D_{n-k}|$, $V_{n,q} = D_{n-k+q}$ for $0 \le q \le k$ and $H_n$ being the $\sigma$-algebra generated by the information of the process upto generation $n-k$. Since $\log |D_{n-k}| = \log Z_{n-k} \stackrel{a.s.}{\sim} \alpha^k \log Z_n$, we have

$$ \limsup_{n \to \infty} \frac{\max_{v \in D_n} S_{v,n-k}}{L(\log Z_n)} \le \alpha^{k/r} \tilde{\alpha}_k = \left( \sum_{t=0}^{k-1} \alpha^{t/(r-1)} \right)^{1-1/r} \vee 1. $$

On the other hand, using (4.12), we get

$$ \limsup_{n \to \infty} \frac{M_{n-k}}{L(\log Z_{n-k})} \le \frac{A_2 W^{1/r}}{1 - \alpha^{1/r}}, \text{ almost surely.} $$

Combining the above two estimates with the observation that $M_n \le M_{n-k} + \max_{v \in D_n} S_{v,n-k}$, we get, almost surely,

$$ \limsup_{n \to \infty} \frac{M_n}{L(\log Z_n)} \le \frac{\alpha^{k/r}}{1 - \alpha^{1/r}} A_2 W^{1/r} + \left[ \left( \sum_{t=0}^{k-1} \alpha^{t/(r-1)} \right)^{1-1/r} \vee 1 \right]. $$

Letting $k$ tend to $\infty$ concludes the proof. $\square$

## 5. BRW with very rapidly varying tails

This section is devoted to the analysis of the situation when the right tail of the displacement distribution function $F$ decays more rapidly than those which satisfy Assumption 4.1. In particular, it considers the cases where the function $L$, as defined in (4.1), is slowly varying at $\infty$. An example will be $L(x) = \log x$ for all $x > 0$, i.e. $F(x) = 1 - \exp(-e^x)$, for all $x \in \mathbb{R}$.

We have observed in Theorems 3.2 and 4.2 that, if $F$ satisfies Assumption 3.1 or Assumption 4.1 with $r \in (0, 1]$, only the last generation effectively contributes in determining the right-most position in the $n$th generation, whereas if $F$ satisfies Assumption 4.1 with $r \in (1, \infty)$, then previous generations also contribute albeit with a geometrically decaying weight. In both cases though, the right-most position in the $n$th generation is asymptotically of the same order as the largest displacement incurred in the $n$th generation. In sharp contrast to these, the case which we shall analyse in this section demonstrates a situation where the right tail of $F$ is so small that each generation contributes equally in determining the right-most position in the last generation. In particular, we expect $M_n$ to be $O(\sum_{k=1}^n L(\log Z_k))$, since $L(\log Z_n)$ is the asymptotic order of the largest displacement in the $n$th generation. If we assume that the right-tail of $F$ decays sufficiently fast, this is indeed the situation as stated in Theorem 5.2. Also in this situation, $M_n \gg L(\log Z_n)$, a stark difference from those in previous sections.

We would, though, like to point out that there are some examples of $F$ which lie the twilight zone between those satisfying Assumptions 4.1 and 5.1. It may be interesting to try to think of what happens in those cases, but we will not further concern ourselves regarding that matter in this paper.
**Assumption 5.1.** F is a distribution function on $\mathbb{R}$ with the following properties. Recall that L is the left-continuous inverse of $K = -\log(1-F)$.

(L1) $F(x) < 1, \forall x \in \mathbb{R}$, and L is slowly varying at $\infty$ with $K(L(x)) \sim x$, as $x \to \infty$.

(L2) There exists $\eta_0 \in (0, 1-\alpha)$ such that for any $\eta \in (0, \eta_0)$, there exists a sequence of non-negative real numbers $\{\kappa_n(\eta)\}_{n \ge 1}$ satisfying the following conditions.

$$ \lim_{\eta \downarrow 0} \liminf_{n \to \infty} \frac{L(\alpha^{-n} e^{-\kappa_n(\eta)})}{L(\alpha^{-n})} \ge 1, \quad \text{and} \quad \sum_{n \ge 1} e^{-\kappa_n(\eta)} < \infty, \forall \eta \in (0, \eta_0). $$

**Theorem 5.2.** Let Assumptions 2.1 and 5.1 hold. Then almost surely conditional on survival of the tree, we have

$$ \lim_{n \to \infty} \frac{M_n}{\sum_{k=1}^{n} L(\alpha^{-k})} = 1. $$

**Theorem 5.2** confirms the intuition described above. Heuristically, this means that the maximum is achieved by a path such that at each generation, the displacement is essentially the maximum of the displacements of that generation.

Before diving into the proof of Theorem 5.2, let us first make some sense of the complicated and apparently artificial conditions presented in Assumption 5.1. It is evident from (L1) that L is non-decreasing, slowly varying at $\infty$ with $L(\infty) = \infty$. We shall now explore some simpler assumptions on L which guarantees (L2). In the process, we shall explore some examples of displacement distribution F which satisfies these conditions.

**Corollary 5.3.** Assume that L satisfies (L1) and further suppose that there exists $a > 1$ such that $x \mapsto L(a^x)$ is regularly varying at $\infty$ with index $\gamma \ge 0$. Then L satisfies Assumption 5.1 and we have

$$ \lim_{n \to \infty} \frac{M_n}{nL(\alpha^{-n})} = \frac{1}{\gamma+1}, \quad \text{almost surely on survival.} $$

**Proof.** We shall start by establishing the fact that $x \mapsto L(b^x)$ is regularly varying at $\infty$ with index $\gamma$, for any $b > 1$. Fix $t > 0$. Then

$$ \lim_{x \to \infty} \frac{L(b^{tx})}{L(b^x)} = \lim_{x \to \infty} \frac{L(a^{tx \log b / \log a})}{L(a^x \log b / \log a)} = t^\gamma, $$

establishing our claim. To establish (L2), we make the choice $\kappa_n(\eta) = -n \log(1-\eta)$ for all $n \ge 1$ and $0 < \eta < \eta_0 = 1-\alpha$. Summability of the sequence $\{e^{-\kappa_n(\eta)}\}_{n \ge 1}$ is obvious. Using regularly varying property of $x \mapsto L(\alpha^{-x})$, we obtain

$$ \lim_{n \to \infty} \frac{L(\alpha^{-n} e^{-\kappa_n(\eta)})}{L(\alpha^{-n})} = \lim_{n \to \infty} \frac{L(e^{n(\log(1-\eta)-\log \alpha)})}{L(e^{-n \log \alpha})} = \left( \frac{\log \alpha - \log(1-\eta)}{\log \alpha} \right)^{\gamma}, $$

and hence

$$ \lim_{\eta \downarrow 0} \lim_{n \to \infty} \frac{L(\alpha^{-n} e^{-\kappa_n(\eta)})}{L(\alpha^{-n})} = 1. $$
These prove that $L$ satisfies **Assumption 5.1** and hence we can apply **Theorem 5.2**. All we have to show now is the fact that

$$ \sum_{k=1}^{n} L(\alpha^{-k}) \sim (\gamma + 1)^{-1} n L(\alpha^{-n}), \quad \text{as } n \to \infty. \qquad (5.1) $$

In order to do so, we first apply monotonicity of $L$ to conclude that

$$ \begin{aligned} (\gamma + 1)^{-1} n L(\alpha^{-n}) &\sim \int_{0}^{n} L(\alpha^{-x}) dx \le \sum_{k=1}^{n} L(\alpha^{-k}) \\ &\le \int_{0}^{n+1} L(\alpha^{-x}) dx \sim (\gamma + 1)^{-1} (n+1) L(\alpha^{-n-1}), \end{aligned} \qquad (5.2) $$

where the first and the last asymptotics in (5.2) follows from Karamata's Theorem (see [37, Theorem 0.6]) and the fact that $x \mapsto L(\alpha^{-x})$ is regularly varying with index $\gamma \ge 0$. This regularly varying property, along with monotonicity, also implies that $nL(\alpha^{-n}) \sim (n+1)L(\alpha^{-n-1})$ and thus (5.1) is established. $\square$

**Example 5.4.** The condition on $L$ assumed in **Corollary 5.3** is satisfied for all the distribution functions $F$ for which $K = -\log(1-F)$, for large enough $x$, has the form $K(x) = \exp(c x^\beta)$, for some $c, \beta > 0$ or $K(x) = \exp(c_1 e^{c_2 x})$, for some $c_1, c_2 > 0$. In the first case, $L(x) = (\log(x)/c)^{1/\beta}$ and hence satisfies **Corollary 5.3** with $\gamma = 1/\beta$. In the second set of examples, clearly $\gamma = 0$.

The next set of examples of $L$, that we shall consider, will allow for $L$ to be increasing in a much slower rate than required by **Corollary 5.3**.

**Corollary 5.5.** Suppose that $L$ satisfies (L1) and there exists $\{\kappa_n : n \ge 1\}$, positive real numbers, such that

$$ L(\alpha^{-n} e^{-\kappa_n}) \sim L(\alpha^{-n}), \quad \text{as } n \to \infty, \quad \text{and} \quad \sum_{n \ge 1} \exp(-\kappa_n) < \infty. \qquad (5.3) $$

Then $L$ satisfies **Assumption 5.1** and therefore the conclusion of **Theorem 5.2** holds true.

**Proof.** The statement is immediate from **Theorem 5.2** if we take $\kappa_n(\eta) = \kappa_n$, for all $n \ge 1$ and $\eta \in (0, 1 - \alpha)$. $\square$

The $L$ in **Assumption (L1)** is a slowly varying function and for such a function we have a Karamata's representation theorem (see [13, Section 1.3] for more details on Karamata Representation). We now impose some conditions on this representations that allows us to verify **Assumption 5.1**.

**Corollary 5.6.** Suppose that $L$ satisfies (L1) and the following is a Karamata Representation of $L$ for some $a > 0$.

$$ L(x) = c(x) \exp \left( \int_a^x \frac{\varepsilon(t)}{t} dt \right), \quad \forall x > a, $$

where $c, \varepsilon: \mathbb{R}^+ \mapsto \mathbb{R}^+$ and $\lim_{x \to \infty} c(x) = c \in (0, \infty)$, $\lim_{t \to \infty} \varepsilon(t) = 0$. Further assume that $\varepsilon(t) \log \log t = o(1)$, as $t \to \infty$. Then $L$ satisfies **Assumption 5.1** and therefore the conclusion of **Theorem 5.2** holds true.
**Proof.** We shall show that $L$ satisfies the conditions required to apply Corollary 5.5 for the choice $\kappa_n = 2 \log n$. Clearly, $\sum_{n \ge 1} \exp(-\kappa_n) < \infty$. Setting

$$v_n := (\log \log \alpha^{-n}) \sup_{t \in [\alpha^{-n} e^{-\kappa_n}, \alpha^{-n}]} \varepsilon(t) = o(1),$$

we note that for large enough $n$,

$$\begin{aligned} \frac{L(\alpha^{-n} e^{-\kappa_n})}{L(\alpha^{-n})} &= \frac{c(\alpha^{-n} e^{-\kappa_n})}{c(\alpha^{-n})} \exp \left( - \int_{\alpha^{-n} e^{-\kappa_n}}^{\alpha^{-n}} \frac{\varepsilon(t)}{t} dt \right) \\ &\ge \frac{c(\alpha^{-n} e^{-\kappa_n})}{c(\alpha^{-n})} \exp \left( - \frac{v_n}{\log \log \alpha^{-n}} \log \frac{\alpha^{-n}}{\alpha^{-n} e^{-\kappa_n}} \right) \\ &= \frac{c(\alpha^{-n} e^{-\kappa_n})}{c(\alpha^{-n})} \exp \left( - \frac{2v_n \log n}{\log n + \log \log \alpha^{-1}} \right), \end{aligned}$$

and hence $L(\alpha^{-n} e^{-\kappa_n}) \sim L(\alpha^{-n})$. This concludes the proof. $\square$

**Corollary 5.7.** Suppose that $L$ satisfies (L1) and of the form $L(x) = \exp(h(\log x) + o(1))$ as $x \to \infty$ where $h$ is differentiable for all $x > x_0$ and satisfies $\lim_{x \to \infty} h'(x) \log x = 0$. Then $L$ satisfies Assumption 5.1 and therefore the conclusion of Theorem 5.2 holds true. A sufficient condition implying $\lim_{x \to \infty} h'(x) \log x = 0$ is that $h$ is regularly varying with index $\rho \in [0, 1)$ with $h'$ being ultimately monotone.

**Proof.** Assuming without loss of generality that $L(x_0) > 0$, we have a Karamata Representation of $L$ as follows.

$$\begin{aligned} L(x) = c(x) \exp(h(\log x) - h(x_0)) &= c(x) \exp \left( \int_{x_0}^{\log x} h'(t) dt \right) \\ &= c(x) \exp \left( \int_{\exp(x_0)}^{x} \frac{h'(\log u)}{u} du \right) \end{aligned}$$

where $c(x) \to e^{h(x_0)}$ as $x \to \infty$. Application of Corollary 5.6, along with the condition that $h'(x) \log x = o(1)$, implies the first assertion.

If $h$ is regularly varying with index $\rho \in [0, 1)$ and $h'$ is ultimately monotone, we can apply Monotone Density Theorem [13, Theorem 1.7.2] to guarantee that $h'(x) \sim \rho x^{\rho-1} l(x)$ as $x \to \infty$, for some slowly varying function $l$. Clearly,

$$h'(x) \log x = \frac{x^{1-\rho} h'(x) l(x) \log x}{l(x) x^{1-\rho}} \to 0, \text{ as } x \to \infty,$$

since $x \mapsto l(x) \log x$ is also slowly varying and $\rho < 1$. This proves the second assertion. $\square$

**Example 5.8.** A class of distribution functions $F$ for which the criteria stated in Corollary 5.7 holds is as follows. We take $K(x) = e^{g(\log x)}$, where $g$ is regularly varying with index $\beta > 1$, with monotone derivative $g'$ which is then regularly varying with index $\beta - 1 > 0$. Then $L(x) = e^{h(\log x)}$ with $h = g^{-1}$, the inverse of $g$, regularly varying with index $1/\beta$. It is easy to see that members of this class do not satisfy the conditions stated in Corollary 5.3, but satisfy the conditions stated in Corollary 5.7. Moreover, following similar arguments as presented while establishing (5.2), we can show that in this case,

$$\sum_{k=1}^{n} L(\alpha^{-k}) \sim \int_{0}^{n} L(\alpha^{-t}) dt = \int_{0}^{n} e^{h(t \log(1/\alpha))} dt = \frac{1}{\log(1/\alpha)} \int_{h(0)}^{h(n \log(1/\alpha))} g'(u) e^{u} du$$
$$ 
\begin{aligned}
& \sim \frac{1}{\log(1/\alpha)} g'(h(n \log(1/\alpha))) e^{h(n \log(1/\alpha))} \\
& \sim \log^{-1/\beta}(1/\alpha) g'(h(n)) L(\alpha^{-n}).
\end{aligned}
$$

The last asymptotic equivalence is due to the fact that $g' \circ h$ is regularly varying with index $1 - 1/\beta$. Therefore, almost surely on $(W > 0)$,

$$ \lim_{n \to \infty} \frac{M_n}{g'(g^{\leftarrow}(n))L(\alpha^{-n})} = \frac{1}{\log^{1/\beta}(1/\alpha)}. $$

For instance, taking $g(x) = cx^\beta$ with $\beta > 1$ and setting $\tau = (\log(1/\alpha)/c)^{1/\beta}$ yields

$$ \lim_{n \to \infty} \frac{M_n}{n^{1-1/\beta} \exp(\tau n^{1/\beta})} = \frac{\beta}{\tau}, \text{ almost surely on } (W > 0). $$

Before delving into the details, we briefly describe the strategy we are going to adopt to prove **Theorem 5.2**. The upper bound to the maximum is quite straight-forward, as the right-most position is always bounded above by the sum of the maximum displacements over generations. In order to establish the lower bound, we extract a subtree with nth generation being denoted $A_n$ which consists of those particles whose displacements from their parents are approximately among the largest $O(|B_n|^{1-\delta_n})$ many, where $B_n$ is the set of children of $A_{n-1}$ in the original tree. Choosing the sequence $\{\delta_n\}$ to be converging to 0 at an appropriate speed as dictated by (L2), we can in effect guarantee the existence of an infinite ray, starting from the root, along which displacements from the parents are among the largest in the corresponding generations. This obviously gives a matching lower bound.

**Proof of upper bound in Theorem 5.2.** Fix $\varepsilon > 0$. Note that $M_n \le \sum_{i=1}^n \tilde{M}_{Z_i}$, where $\tilde{M}_{Z_i} = \max_{v \in D_i} X_{ev}$, as was defined in the proof of **Lemma 4.6**. We get the following for all large enough n almost surely.

$$ 
\begin{aligned}
\mathbb{P}\left[\tilde{M}_{Z_i} > L((1 + \varepsilon) \log Z_i) \middle| \mathbb{T}\right] &= 1 - (F \circ L((1 + \varepsilon) \log Z_i))^{Z_i} \\
&= 1 - (1 - \exp(-K \circ L((1 + \varepsilon) \log Z_i)))^{Z_i} \\
&\le 1 - (1 - \exp(-(1 + \varepsilon) \log Z_i))^{Z_i} \\
&= 1 - (1 - Z_i^{-1-\varepsilon})^{Z_i} \le Z_i^{-\varepsilon}.
\end{aligned}
$$

Since the last expression is summable, we have by Borel–Cantelli Lemma, almost surely conditioned on survival,

$$ M_n \le \sum_{i=1}^n \tilde{M}_{Z_i} \le \sum_{i=1}^n L((1 + \varepsilon) \log Z_i) + \sum_{i=1}^{\infty} (\tilde{M}_{Z_i} \vee 0) \mathbf{1}(\tilde{M}_{Z_i} > L((1 + \varepsilon) \log Z_i)), \quad (5.4) $$

where the second expression in the right hand side of (5.4) is finite almost surely. Since the last expression is summable, we have by Borel–Cantelli Lemma,

$$ \limsup_{n \to \infty} \frac{M_n}{\sum_{k=1}^{n} L(\alpha^{-k})} \le \limsup_{n \to \infty} \frac{\sum_{k=1}^{n} L((1 + \varepsilon) \log Z_k)}{\sum_{k=1}^{n} L(\alpha^{-k})} \le \limsup_{n \to \infty} \frac{L((1 + \varepsilon) \log Z_n)}{L(\alpha^{-n})} = 1, $$

almost surely on $(W > 0)$. The last limit follows from slowly varying property of L and the fact that $(1 + \varepsilon)\alpha^n \log Z_n \to (1 + \varepsilon)W$, almost surely. $\square$
**Proof of lower bound in Theorem 5.2.** Fix $\eta \in (0, \eta_0)$, such that $L(\alpha^{-j} \exp(-\kappa_j(\eta))) \to \infty$, as $j \to \infty$. Indeed, the first condition in (L2) and the fact that $L(\infty) = \infty$ guarantee that the previously mentioned property holds true for all small enough $\eta$. Set $c(\eta) = \sum_{n \ge 1} \exp(-\kappa_n(\eta)) < \infty$. Fix $v \in (0, 1 - \alpha)$. Define the following sequences.

$$ \gamma_n(\eta) := 1 - \frac{1}{2c(\eta)} \sum_{k=1}^{n} \exp(-\kappa_k(\eta)), \quad \delta_n(\eta) := \frac{v(\gamma_{n-1}(\eta) - \gamma_n(\eta))}{\gamma_{n-1}(\eta)}, \quad \forall n \ge 1, $$

with $\gamma_0(\eta) := 1$. By construction, $\delta_n(\eta) \in (0, v)$, $\gamma_n(\eta) = \prod_{k=1}^n (1 - v^{-1}\delta_k(\eta)) \in [1/2, 1]$ and hence

$$ \begin{aligned} e^{\kappa_n(\eta)} \delta_n(\eta) \prod_{k=1}^{n-1} (1 - \delta_k(\eta)) &> e^{\kappa_n(\eta)} \delta_n(\eta) \prod_{k=1}^{n-1} (1 - v^{-1}\delta_k(\eta)) \\ & = e^{\kappa_n(\eta)} v (\gamma_{n-1}(\eta) - \gamma_n(\eta)) = \frac{v}{2c(\eta)} > 0, \quad \forall n \ge 1. \end{aligned} \quad (5.5) $$

Recursively define the following sets of vertices. Set $B_{0,\eta} = A_{0,\eta} := D_0$, which contains only the root. For any $j \ge 1$, set $B_{j,\eta}$ to be the set children of the vertices in $A_{j-1,\eta}$. Recall the notation $C(v)$ which denotes the set of children for any particle $v$. Define $A_{j,\eta}$ to be the those particles in $B_{j,\eta}$ whose displacement from their parents are among the maximum $|A_{j,\eta}|$ many of those in $B_{j,\eta}$; break the ties uniformly at random if needed. Here

$$ |A_{j,\eta}| := \sum_{v \in A_{j-1,\eta}} \lfloor |C(v)|^{1-\delta_j(\eta)} \rfloor. $$

It is immediately observed that the sequence $\{|A_{j,\eta}| : j \ge 0\}$ has the same law as $\{Z_{j,\eta}^* : j \ge 0\}$, where $Z_{j,\eta}^*$ is the size of the $j$th generation of the inhomogeneous branching process, started from one particle, and where the particles in $n$th generation produces i.i.d. many off-springs (independent of the structure of the tree until that generation) having distribution $G_{(1-\delta_{n+1}(\eta))}$, as defined at the end of Section 1. Since $\delta_j(\eta) \in (0, v)$ for $v < 1 - \alpha$, we apply Theorem 2.6 and Lemma A.1 to obtain the following.

$$ \mathbb{P} \left[ \lim_{n \to \infty} \left( \prod_{j=1}^{n} \frac{\alpha}{1 - \delta_j(\eta)} \right) \log |A_{n,\eta}| = W^* > 0 \right] =: q(\eta) > 0. $$

Let $E_\eta$ denote the event in the above equation. In particular, almost surely on $E_\eta$,

$$ \liminf_{n \to \infty} n^{-1} \log \log |A_{n,\eta}| \ge \liminf_{n \to \infty} \frac{1}{n} \sum_{k=1}^{n} \log \left( \frac{1 - \delta_j(\eta)}{\alpha} \right) \ge \log \left( \frac{1 - v}{\alpha} \right) > 0. $$

A standard application of Lemma 4.5 then implies that $\log |B_{j,\eta}| \stackrel{\text{a.s.}}{\sim} \alpha^{-1} \log |A_{j-1,\eta}|$ as $j \to \infty$, on $E_\eta$. Here we have applied Lemma 4.5 with $\mathcal{F}_j$ being the $\sigma$-algebra containing all the information (tree structure and displacement of the particles) upto generation $j$, $\zeta_j = |A_{j,\eta}|$ and $G_j = G$ for all $j \ge 0$. In particular, $|B_{j,\eta}|$ also grows double-exponentially almost surely on $E_\eta$. Another similar application of Lemmas 4.5 and A.1 guarantees that $\log |A_{j,\eta}| \stackrel{\text{a.s.}}{\sim} (1 - \delta_j(\eta))\alpha^{-1} \log |A_{j-1,\eta}|$ as $j \to \infty$, on $E_\eta$. Here we have applied Lemma 4.5 with the same choice of $\mathcal{F}_j$ and $\zeta_j$ as earlier but with $G_j = G_{(1-\delta_{j+1}(\eta))}$, for all $j \ge 0$. Combining these two, we have $\log |A_{j,\eta}| \stackrel{\text{a.s.}}{\sim} (1 - \delta_j(\eta)) \log |B_{j,\eta}|$ as $j \to \infty$, on $E_\eta$.
Assumption (L1) guarantees that $L$ satisfies the assumptions required to apply Lemma 4.3. Since, on the event $E_\eta$, $|B_{j,\eta}|$ grows double-exponentially almost surely, we can employ Lemma 4.3 to yield the following.

$$ \frac{\min_{v \in A_{j,\eta}} X_{ev}}{L(\delta_j(\eta) \log |B_{j,\eta}|)} \xrightarrow{a.s.} 1, \text{ on } E_\eta. \quad (5.6) $$

The application of Lemma 4.3 is valid indeed, since on the event $E_\eta$,

$$ \begin{aligned} \delta_j(\eta) \log |B_{j,\eta}| &\stackrel{\text{a.s.}}{\sim} \frac{\delta_j(\eta)}{1 - \delta_j(\eta)} \log |A_{j,\eta}| \\ &\stackrel{\text{a.s.}}{\sim} \frac{\delta_j(\eta)}{1 - \delta_j(\eta)} W^* \alpha^{-j} \prod_{i=1}^j (1 - \delta_i(\eta)) \ge W^* \alpha^{-j} e^{-\kappa_j(\eta)} \frac{\nu}{2c(\eta)} \to \infty, \end{aligned} $$

where the last line follows from the fact that $L(\alpha^{-j}e^{-\kappa_j(\eta)}) \to \infty$ and $K(x) < \infty$ for all $x$ with $K(\infty) = \infty$.

By the slowly varying property of $L$, we also have for large enough $j$,

$$ \begin{aligned} L(\delta_j(\eta) \log |B_{j,\eta}|) &\stackrel{\text{a.s.}}{\sim} L \left( \frac{\delta_j(\eta)}{1 - \delta_j(\eta)} \log |A_{j,\eta}| \right) \stackrel{\text{a.s.}}{\sim} L \left( \frac{W^* \delta_j(\eta)}{1 - \delta_j(\eta)} \prod_{k=1}^j \frac{1 - \delta_k(\eta)}{\alpha} \right) \\ &\ge L \left( \alpha^{-j} W^* \frac{\nu e^{-\kappa_j(\eta)}}{2c(\eta)} \right) \stackrel{\text{a.s.}}{\sim} L \left( \alpha^{-j} e^{-\kappa_j(\eta)} \right), \end{aligned} \quad (5.7) $$

on $E_\eta$. Here we have used the definition of $E_\eta$, monotonicity of $L$ and (5.5) to obtain the inequality above. Therefore,

$$ \liminf_{j \to \infty} \frac{\min_{v \in A_{j,\eta}} X_{ev}}{L(\alpha^{-j} e^{-\kappa_j(\eta)})} \ge 1, \text{ almost surely on } E_\eta. \quad (5.8) $$

By construction,

$$ M_n \mathbb{1}(|A_{n,\eta}| > 0) \ge \mathbb{1}(|A_{n,\eta}| > 0) \max_{v \in A_{n,\eta}} S_v \ge \mathbb{1}(|A_{n,\eta}| > 0) \sum_{j=1}^n \min_{v \in A_{j,\eta}} X_{ev}. $$

The logic behind the above inequality is same as the one used in the proof of lower bound in Theorem 4.2. Since, $|A_{n,\eta}|$ converges to infinity almost surely on $E_\eta$, we can apply (5.8) and Lemma A.5 to conclude that

$$ \liminf_{n \to \infty} \frac{M_n}{\sum_{j=1}^n L(\alpha^{-j})} \ge \liminf_{n \to \infty} \frac{L(\alpha^{-n} e^{-\kappa_n(\eta)})}{L(\alpha^{-n})} =: \varphi(\eta), \text{ almost surely on } E_\eta. $$

Set $c_n := \sum_{j=1}^n L(\alpha^{-j})$, for all $n \ge 1$. Monotonicity, slowly varying property of $L$ and Lemma A.5 implies that $c_n \sim c_{n-k}$, as $n \to \infty$, for any $k \in \mathbb{N}$. Fix any $k \ge 1$ and let $S_{v,n,n-k}$ be the displacement of particle $v \in D_n$ from its ancestor in generation $k$. For any $u \in D_k$, let $D_{u,n,n-k}$ be the particles in $D_n$ with $u$ as an ancestor. Our previous analysis shows that, conditioned on $D_k$, there exists independent events $\{E_{\eta,u} : u \in D_k\}$, having same probability as $E_\eta$, such that

$$ \begin{aligned} \liminf_{n \to \infty} c_n^{-1} M_{u,n,n-k} &= \liminf_{n \to \infty} c_{n-k}^{-1} M_{u,n,n-k} \\ &:= \liminf_{n \to \infty} c_{n-k}^{-1} \max_{v \in D_{u,n,n-k}} S_{v,n,n-k} \ge \varphi(\eta), \text{ a.s. on } E_{\eta,u}. \end{aligned} $$
Since, $M_n = \max_{u \in D_k} (S_u + M_{u,n,n-k})$, we can argue that

$$ 
\begin{aligned}
\mathbb{P} \left( \liminf_{n \to \infty} c_n^{-1} M_n < \varphi(\eta) \middle| \mathbb{T} \right) &= \lim_{k \to \infty} \mathbb{P} \left( \liminf_{n \to \infty} c_n^{-1} M_n < \varphi(\eta) \middle| \{D_j\}_{1 \le j \le k} \right) \\
&= \lim_{k \to \infty} \mathbb{P} \left( \bigcap_{u \in D_k} E_{\eta,u}^c \middle| \{D_j\}_{1 \le j \le k} \right) \\
&= \lim_{k \to \infty} (1 - q(\eta))^{Z_k} \\
&= 1(\mathbb{T} \text{ extincts}) = 1(W = 0).
\end{aligned}
$$

Therefore, almost surely on the event ($W > 0$), we have $\liminf_{n \to \infty} c_n^{-1} M_n \ge \varphi(\eta)$. Taking $\eta \downarrow 0$ and using the first condition in (L2), yields $\liminf_{n \to \infty} c_n^{-1} M_n \ge 1$. Since we have already proved that the corresponding limsup is less than or equal to 1, this concludes the proof. □

## 6. Speed of BRW with infinite progeny mean

There exists different ways to define a speed for the BRW. In [5,32,36], three notions of speed were introduced; namely *Cloud speed*, *Burst speed* and *Sustainable speed*. In order to define them, we introduce the following notations. Rays of the tree $\mathbb{T}$ are formally defined as infinite paths starting from the root which do not backstep. We denote the rays of the tree $\mathbb{T}$ by $\mathcal{R}$ and the set of all rays by $\partial\mathbb{T}$. The aforementioned three notions are defined as follows.

$$ \text{Cloud speed : } s_{\text{cloud}} := \limsup_{n \to \infty} \max_{v : |v| = n} \frac{S_v}{|v|} = \limsup_{n \to \infty} \frac{M_n}{n}; \qquad (6.1) $$

$$ \text{Burst speed : } s_{\text{burst}} := \sup_{\mathcal{R} \in \partial \mathbb{T}} \limsup_{v \in \mathcal{R}} \frac{S_v}{|v|}, \quad \text{Sustainable speed : } s_{\text{sust}} := \sup_{\mathcal{R} \in \partial \mathbb{T}} \liminf_{v \in \mathcal{R}} \frac{S_v}{|v|}. \qquad (6.2) $$

Here $|v|$ denotes the distance of the vertex $v$ from the root, i.e., the generation to which $v$ belongs. We refer to [36] for a detailed exposition on these concepts. By Kolmogorov 0–1 law the speeds are almost surely constant when the displacements are i.i.d, though they might be different from each other. The following relation holds trivially,

$$ s_{\text{cloud}} \ge s_{\text{burst}} \ge s_{\text{sust}}. \qquad (6.3) $$

It is a well-known fact that for BRW the notions of cloud speed, burst speed and sustainable speed coincide, established by [11,27,30]. This statement was proved under the assumptions that the progeny variables have finite mean and the displacement variables have finite moment generating function. The later condition was removed by [25] for displacement variables with semi-exponential tails, accommodating the changing rate of growth in the definition of the speeds. Since the rate of growth for the maximum displacement are drastically different from one another for the cases we considered in Section 3, Section 4 and Section 5; we need to properly modify our definition of speeds in those cases. In all these cases our target is to choose a correct rate of growth to get almost surely constant finite and non-zero speed, which is same for all three notions. The following three results serve this purpose. In (6.4)–(6.6), the three terms correspond to cloud speed, burst speed and sustainable speed, respectively, for the corresponding cases. They are also trivially in non-increasing order similar to (6.3).
**Proposition 6.1.** Under Assumptions 2.1 and 3.1, the following holds almost surely conditional on the survival of the tree.

$$ \limsup_{n \to \infty} \max_{v:|v|=n} \frac{\log \log S_v}{|v|} = \sup_{\mathcal{R} \in \partial \mathcal{T}} \limsup_{v \in \mathcal{R}} \frac{\log \log S_v}{|v|} = \sup_{\mathcal{R} \in \partial \mathcal{T}} \liminf_{v \in \mathcal{R}} \frac{\log \log S_v}{|v|} = -\log \alpha. \quad (6.4) $$

**Proposition 6.2.** Under Assumptions 2.1 and 4.1, the following holds almost surely conditional on the survival of the tree.

$$ \limsup_{n \to \infty} \max_{v:|v|=n} \frac{\log S_v}{|v|} = \sup_{\mathcal{R} \in \partial \mathcal{T}} \limsup_{v \in \mathcal{R}} \frac{\log S_v}{|v|} = \sup_{\mathcal{R} \in \partial \mathcal{T}} \liminf_{v \in \mathcal{R}} \frac{\log S_v}{|v|} = -\frac{1}{r} \log \alpha. \quad (6.5) $$

**Proposition 6.3.** Under Assumptions 2.1 and 5.1, the following holds almost surely conditional on the survival of the tree.

$$ \begin{aligned} \limsup_{n \to \infty} \max_{v:|v|=n} \frac{S_v}{\sum_{k=1}^{|v|} L(\alpha^{-k})} &= \sup_{\mathcal{R} \in \partial \mathcal{T}} \limsup_{v \in \mathcal{R}} \frac{S_v}{\sum_{k=1}^{|v|} L(\alpha^{-k})} \\ &= \sup_{\mathcal{R} \in \partial \mathcal{T}} \liminf_{v \in \mathcal{R}} \frac{S_v}{\sum_{k=1}^{|v|} L(\alpha^{-k})} = 1. \end{aligned} \quad (6.6) $$

Note that for heavy tailed displacements, the speed is of linear order in log-log scale; whereas for rapidly decaying displacements satisfying Assumption 4.1, the speed is of linear order in log-scale. For very rapidly decaying displacements, the speed depends on the nature of the function $L$. As for example, under Corollary 5.3 the speed is of some polynomial order.

The proofs of these three results are very similar in flavour. The upper bound on the corresponding notion of the cloud speed follows from the asymptotics of the maximum displacement, investigated in the previous sections; whereas lower bound on the sustainable speed follows from constructing a ray along which most of the displacements are very large. This construction is very similar to what we did in the proof of lower bound in Theorem 5.2.

**Proof of Proposition 6.1.** Taking logarithm on both sides of the main assertion of Theorem 3.5, we obtain $n^{-1} \log \log M_n \xrightarrow{a.s.} -\log \alpha$. It is therefore enough to show that

$$ \sup_{\mathcal{R} \in \partial \mathcal{T}} \liminf_{v \in \mathcal{R}} \frac{\log \log S_v}{|v|} \geq -\log \alpha. $$

Fix $\delta \in (0, 1 - \alpha)$ and recursively define the following sets of vertices. Set $B_0 = A_0 := D_0$, which contains only the root. For any $j \ge 1$, set $B_j$ to be the set children of the vertices in $A_{j-1}$. Define $A_j$ to be the those particles in $B_j$ whose displacement from their parents are among the maximum $|A_j|$ many of those in $B_j$; break the ties uniformly at random if needed. Here

$$ |A_j| := \sum_{v \in A_{j-1}} |C(v)|^{1-\delta}. $$

It is immediately observed that the sequence $\{|A_j| : j \ge 0\}$ has the same law as $\{\tilde{Z}_j : j \ge 0\}$, where $\tilde{Z}_j$ is the size of the jth generation of the homogeneous branching process, started from one particle, and where the particles in nth generation produces i.i.d. many off-springs (independent of the structure of the tree until that generation) having distribution $G_{(1-\delta)}$, as
defined at the end of Section 1. We apply Theorem 2.3 to obtain the following.

$$ \mathbb{P}\left[\lim_{n \to \infty} \left(\frac{\alpha}{1-\delta}\right)^n \log |A_n| = \tilde{W} > 0\right] =: \tilde{q} > 0. $$

Let $\tilde{E}$ denote the event in the above equation. A standard application of Lemma 4.5 implies that $\log |B_j| \stackrel{a.s.}{\sim} \alpha^{-1} \log |A_{j-1}| \stackrel{a.s.}{\sim} (1-\delta)^{-1} \log |A_j|$ as $j \to \infty$, on $\tilde{E}$. We can then employ Lemma A.3 to yield the following.

$$ \begin{aligned} \min_{v \in A_j} \log X_{e_v} &\stackrel{a.s.}{\sim} \delta \beta^{-1} \log |B_j| \stackrel{a.s.}{\sim} \delta (1-\delta)^{-1} \beta^{-1} \log |A_j| \\ &\stackrel{a.s.}{\sim} \delta \beta^{-1} (1-\delta)^{j-1} \alpha^{-j} \tilde{W}, \quad \text{as } j \to \infty, \text{ on } \tilde{E}. \end{aligned} \quad (6.7) $$

Now take any infinite ray $\mathcal{R}^*$ whose vertices lie in the sets $A_j$s. This is possible on the event $\tilde{E}$ by construction and hence on this event,

$$ \begin{aligned} \liminf_{v \in \mathcal{R}} \frac{\log \log S_v}{|v|} &\ge \liminf_{v \in \mathcal{R}} \frac{1}{|v|} \log \log \sum_{k=1}^{|v|} \min_{u \in A_k} X_{e_u} \\ &\ge \liminf_{v \in \mathcal{R}} \frac{1}{|v|} \log \log \min_{u \in A_{|v|}} X_{e_u} = \frac{(1-\delta)}{\alpha} \end{aligned} $$

Therefore,

$$ \begin{aligned} \mathbb{P}\left[ \sup_{\mathcal{R} \in \partial \mathcal{T}} \liminf_{v \in \mathcal{R}} \frac{\log \log S_v}{|v|} \ge \log \frac{1-\delta}{\alpha} |\mathcal{T} \text{ survives}] \ge \mathbb{P}(\tilde{E} | \mathcal{T} \text{ survives}) \right. \\ \left. = \frac{\tilde{q}}{\mathbb{P}(\mathcal{T} \text{ survives})} > 0. \right] \end{aligned} $$

Since, conditioned on $\mathcal{T}$, the event inside the left-most term above lies in the tail $\sigma$-algebra generated by the i.i.d. displacement variables, we can invoke Kolmogorov 0–1 law to conclude that almost surely conditioned on survival of the tree $\mathcal{T}$,

$$ \sup_{\mathcal{R} \in \partial \mathcal{T}} \liminf_{v \in \mathcal{R}} \frac{\log \log S_v}{|v|} \ge \log \frac{1-\delta}{\alpha}. $$

Taking $\delta \downarrow 0$, we complete the proof. $\square$

**Proof of Proposition 6.2.** Taking logarithm on both sides on (4.3) and using the fact that $\log L(\alpha^{-n}) \sim (-n/r) \log \alpha$ as $n \to \infty$, a fact which follows from the regular variation of $L$, we can conclude the upper bound:

$$ \limsup_{n \to \infty} \frac{\log M_n}{n} = -\frac{1}{r} \log \alpha, \quad \text{almost surely on survival of the tree.} $$

For the lower bound on burst speed, we use the same construction as in the proof of Proposition 6.1. (6.7) here changes to the following asymptotics by virtue of Lemma 4.3.

$$ \min_{v \in A_j} X_{e_v} \stackrel{a.s.}{\sim} L(\delta \log |B_j|) \stackrel{a.s.}{\sim} \left(\frac{\delta}{1-\delta}\right)^{1/r} \tilde{W}^{1/r} L((1-\delta)^j \alpha^{-j}), \quad \text{on } \tilde{E}, \quad (6.8) $$

where we used the fact that $L$ is regularly varying at $\infty$ with index $1/r$. Lemmas A.4 and A.5 can now be applied to obtain the following.

$$ \sum_{j=1}^{n} \min_{v \in A_j} X_{e_v} \stackrel{a.s.}{\sim} \sum_{j=1}^{n} \left(\frac{\delta}{1-\delta}\right)^{1/r} \tilde{W}^{1/r} L((1-\delta)^j \alpha^{-j}) $$
$$ \sim \left( \frac{\delta}{1-\delta} \right)^{1/r} \tilde{W}^{1/r} \frac{L((1-\delta)^n \alpha^{-n})}{1-\alpha^{1/r} (1-\delta)^{-1/r}}, \text{ on } \tilde{E}, $$

Hence as $|v| \to \infty$ via $\mathcal{R}^*$, we have

$$ \begin{aligned} \frac{\log S_v}{|v|} &\ge \frac{1}{|v|} \log \sum_{k=1}^{|v|} \min_{u \in A_k} X_{e_u} \stackrel{\text{a.s.}}{\sim} \frac{1}{|v|} \log L((1-\delta)^{|v|} \alpha^{-|v|}) \\ &\sim \frac{1}{r} \frac{\log ((1-\delta)^{|v|} \alpha^{-|v|})}{|v|} = \frac{1}{r} \log \left( \frac{1-\delta}{\alpha} \right). \end{aligned} $$

We can now finish the proof by the same argument as used in Proposition 6.1. $\square$

**Proof of Proposition 6.3.** This proof basically is a corollary of Theorem 5.2 as all the work had already been done there. The upper bound on the cloud speed follows directly from the assertion of Theorem 5.2. Continuing with the notation introduced during its proof, note that for any ray $\mathcal{R}^*$ in the subtree formed by the subsets $\{A_{j,\eta} : j \ge 0\}$, we have the following almost surely on $E_\eta$.

$$ \begin{aligned} \liminf_{v \in \mathcal{R}} \frac{S_v}{\sum_{k=1}^{|v|} L(\alpha^{-k})} &\ge \liminf_{v \in \mathcal{R}} \frac{\sum_{k=1}^{|v|} \min_{u \in A_{k,\eta}} X_{e_u}}{\sum_{k=1}^{|v|} L(\alpha^{-k})} \\ &\ge \liminf_{k \to \infty} \frac{\min_{u \in A_{k,\eta}} X_{e_u}}{L(\alpha^{-k})} \ge \liminf_{k \to \infty} \frac{L(\alpha^{-k} e^{-\kappa_k(\eta)})}{L(\alpha^{-k})} = \varphi(\eta). \end{aligned} $$

The rest of the proof follows by arguments similar to those applied in the proof of Proposition 6.1 and then taking $\eta \downarrow 0$. $\square$

## Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

## Acknowledgements

The authors would like to thank Remco van der Hofstad for first pointing out the article by [18] and also many useful discussions throughout the project. We also thank Ayan Bhattacharya for helpful comments during the progress of the article. A significant portion of the research was carried out the visit of P.R. to Université Paris Nanterre, and the visit of P.S. to Indian Statistical Institute, Bangalore. We acknowledge all of these institutions for their support and hospitality. The research of R.S.H. and P.R. are both partially funded by MATRICS Grants from the Science and Engineering Research Board, Govt. of India. P.R. is also partially supported by a SwarnaJayanti Fellowship from the Department of Science and Technology, Govt. of India. R.S.H.'s research was supported by NWO Gravitation Grant 024.002.003-NETWORKS. We thank two anonymous referees for their helpful suggestions and comments. We also thank the referee for asking the question on the rapidly varying tails which this lead to some new results in Section 5.

## Appendix

In the Appendix we provide proofs for Lemma 4.5, Theorem 2.6 and Lemma 4.3. We did not employ Theorem 2.6 and Lemma 4.5 in its full generality, rather for a particularly
engineered choice of the progeny sequence. Consider the progeny distribution G of the original homogeneous tree, satisfying Assumption 2.1 with moment index $\alpha \in (0, 1)$. We applied Theorem 2.6 with $G_n = G(\psi_n)$ where $\{\psi_n : n \ge 0\}$ is a sequence in $[0, 1]$, bounded away from 0. The validity of such choice is justified by Lemma A.1, which is stated and proved here.

First we prove Lemma 4.5 which was used in the proof of Theorem 4.2.

**Proof of Lemma 4.5.** Define $\alpha_{max} := \sup_{n \ge 0} \alpha_n < 1$. By Assumption 2.5 and [18, Lemma 1], there exists positive constants $0 < c_1, c_2 < \infty$ and $\lambda_0 \in (0, 1)$ such that for all $\lambda \in (0, \lambda_0)$ the following holds.

$$c_1 \lambda^{\alpha_n + \gamma(1/\lambda)} \le 1 - \Psi_n(\lambda) \le c_2 \lambda^{\alpha_n - \gamma(1/\lambda)}, \quad \forall n \ge 0, \quad (A.1)$$

where $\Psi_n$ is the Laplace transform of the distribution function $G_n$ and $\gamma$ is some function satisfying (D1), (D2) and (D3).

The assumption (D3) and monotonicity of $\gamma$ guarantees that

$$\sum_{n \ge 1} \gamma (e^{c_3 e^{c_4 n}}) \le \int_0^\infty \gamma (e^{c_3 e^{c_4 x}}) dx = \frac{1}{c_4} \int_{\log c_3}^\infty \gamma (e^{e^x}) dx < \infty, \quad (A.2)$$

for any $c_3, c_4 > 0$. By our assumption $\zeta := \liminf_{n \to \infty} n^{-1} \log \log \zeta_n > 0$, almost surely and hence (A.2), applied for $c_3 = (\alpha_{max}^{-1} - 1)$ and $c_4 = \zeta/2$, implies that

$$\sum_{n \ge 0} \gamma \left( \zeta_n^{(\alpha^{-1}-1)} \right) < \infty, \quad \text{almost surely.}$$

Set $\varepsilon_n = \alpha_n^{-2} \max(4\gamma(\zeta_n^{(\alpha_{max}^{-1}-1)}), (n+1)^{-2})$ and $\upsilon_n = \varepsilon_n \alpha_n^2/4$, for all $n \ge 0$. These choices, along with the fact that $\alpha_n$ is bounded away from 0, guarantee that almost surely, $\sum_{n \ge 1} \alpha_n \varepsilon_n < \infty$ and for all large enough $n$, $\upsilon_n/\alpha_n - \varepsilon_n \upsilon_n < \upsilon_n/\alpha_n + \varepsilon_n \upsilon_n < \varepsilon_n \alpha_n/2$. By construction, $\upsilon_n \ge \gamma(\zeta_n^{(\alpha_{max}^{-1}-1)})$ for all $n$ and hence, using monotonicity of $\gamma$, we obtain the following almost surely for all large $n$.

$$\gamma(\zeta_n^{(\alpha_n^{-1} + \varepsilon_n)}) \le \gamma(\zeta_n^{(\alpha_n^{-1} - \varepsilon_n)}) \le \gamma(\zeta_n^{(\alpha_{max}^{-1}-1)}) \le \upsilon_n,$$

where we have used the observation that $\varepsilon_n \to 0$ almost surely. The fact that $(\alpha_n^{-1} - \varepsilon_n) \log \zeta_n \xrightarrow{a.s.} \infty$ guarantee that $\zeta_n^{-\alpha_n^{-1}-\varepsilon_n}, \zeta_n^{-\alpha_n^{-1}+\varepsilon_n} < \lambda_0$, for all large enough $n$ almost surely. Combining this observation with (A.1) yields the following. Almost surely, for all large enough $n$,

$$c_1 \left( \zeta_n^{-\alpha_n^{-1} + \varepsilon_n} \right)^{\alpha_n + \upsilon_n} \le 1 - \Psi_n \left( \zeta_n^{-\alpha_n^{-1} + \varepsilon_n} \right), \quad 1 - \Psi_n \left( \zeta_n^{-\alpha_n^{-1} - \varepsilon_n} \right) \le c_2 \left( \zeta_n^{-\alpha_n^{-1} - \varepsilon_n} \right)^{\alpha_n - \upsilon_n}. \quad (A.3)$$

With this preliminary set-up, we claim that, almost surely for all large enough $n$,

$$(\alpha_n^{-1} - \varepsilon_n) \log \zeta_n \le \log \sum_{i=1}^{\zeta_n} L_{n,i} \le (\alpha_n^{-1} + \varepsilon_n) \log \zeta_n. \quad (A.4)$$

Before proving the claim, let us first see how this claim helps us to achieve our target. Denote by $E_n$ the intersection of $(\zeta_n > 1)$ and the event in (A.4). Clearly, (A.4) implies
$N := \sup \{n \ge 0 : \mathbb{I}_{E_n} = 0\} < \infty$, almost surely. Therefore,

$$ \sum_{n \ge N+1} \left| \alpha_n \frac{\log \sum_{i=1}^{\zeta_n} L_{n,i}}{\log \zeta_n} - 1 \right| \le \sum_{n \ge N+1} \alpha_n \varepsilon_n < \infty, $$

almost surely. A standard analysis fact now yields that

$$ 0 < \prod_{n \ge N+1} \left( \alpha_n \frac{\log \sum_{i=1}^{\zeta_n} L_{n,i}}{\log \zeta_n} \right) < \infty, \text{ almost surely.} $$

Let us now proceed to prove the lower bound in (A.4). The following series of inequalities hold true for large enough $n$, almost surely.

$$ \begin{aligned} \mathbb{P} \left[ \log \sum_{i=1}^{\zeta_n} L_{n,i} \le (\alpha_n^{-1} - \varepsilon_n) \log \zeta_n \middle| \mathcal{F}_n \right] &= \mathbb{P} \left[ \exp \left( -\zeta_n^{-\alpha_n^{-1}+\varepsilon_n} \sum_{i=1}^{\zeta_n} L_{n,i} \right) \ge 1/e \middle| \mathcal{F}_n \right] \\ &\le e \left( \Psi_n \left( \zeta_n^{-\alpha_n^{-1}+\varepsilon_n} \right) \right)^{\zeta_n} \\ &\le \exp \left( 1 + \zeta_n \log \left( 1 - c_1 \zeta_n^{(-\alpha_n^{-1}+\varepsilon_n)(\alpha_n+\upsilon_n)} \right) \right) \\ &\le \exp \left( 1 + \zeta_n \log \left( 1 - c_1 \zeta_n^{-1+\varepsilon_n \alpha_n/2} \right) \right) \\ &\le \exp \left( 1 - c_1 \zeta_n^{\varepsilon_n \alpha_n/2} \right), \end{aligned} \quad (A.5) $$

where the penultimate inequality follows from the fact that $\varepsilon_n \alpha_n/2 > \upsilon_n/\alpha_n - \varepsilon_n \upsilon_n$ and the last one from the bound $-\log(1-x) \ge x$. Observe that, almost surely,

$$ \begin{aligned} \liminf_{n \to \infty} n^{-1} \log \zeta_n^{\varepsilon_n \alpha_n/2} &= \frac{1}{2} \liminf_{n \to \infty} n^{-1} \varepsilon_n \alpha_n \log \zeta_n \\ &\ge \frac{1}{2 \inf_{n \ge 0} \alpha_n} \liminf_{n \to \infty} \frac{1}{n(n+1)^2} \log \zeta_n = \infty, \end{aligned} \quad (A.6) $$

and hence the last expression in (A.5) is summable almost surely. Applying Levy's extension of Borel-Cantelli Lemma we conclude the proof of the lower bound.

To prove the upper bound in (A.4), we establish similar kind of inequalities which hold almost surely for large enough $n$.

$$ \begin{aligned} \mathbb{P} \left[ \log \sum_{i=1}^{\zeta_n} L_{n,i} \ge (\alpha_n^{-1} + \varepsilon) \log \zeta_n \middle| \mathcal{F}_n \right] &= \mathbb{P} \left[ 1 - \exp \left( -\zeta_n^{-\alpha_n^{-1}-\varepsilon_n} \sum_{i=1}^{\zeta_n} L_{n,i} \right) \ge 1 - 1/e \middle| \mathcal{F}_n \right] \\ &\le (1 - 1/e)^{-1} \left[ 1 - \left( \Psi_n \left( \zeta_n^{-\alpha_n^{-1}-\varepsilon_n} \right) \right)^{\zeta_n} \right] \\ &\le (1 - 1/e)^{-1} \left[ 1 - \left( 1 - c_2 \left( \zeta_n^{-\alpha_n^{-1}-\varepsilon_n} \right)^{\alpha_n-\upsilon_n} \right)^{\zeta_n} \right] \\ &\le (1 - 1/e)^{-1} \left[ 1 - \left( 1 - c_2 \zeta_n^{-1-\varepsilon_n \alpha_n/2} \right)^{\zeta_n} \right] \end{aligned} \quad (A.7) $$

$$ \le (1 - 1/e)^{-1} c_2 \zeta_n^{-\varepsilon_n \alpha_n/2}, \quad (A.8) $$

where (A.7) is implied by the fact that $\upsilon_n/\alpha_n + \varepsilon_n \upsilon_n < \varepsilon_n \alpha_n/2$, and (A.8) uses the estimate $1 - (1-x)^\kappa \le \kappa x$ for all $x \in (0, 1]$ and $\kappa > 0$. Almost sure summability of the expression in
(A.8) follows from (A.6). Applying Levy's extension of Borel-Cantelli Lemma we conclude the proof of the upper bound. □

**Lemma A.1.** Let G be a distribution function, supported on non-negative real line but not necessarily on the set of non-negative integers, satisfying (D1) to (D4) with moment index $\alpha \in (0, 1)$. Fix $\delta_0 \in (0, 1]$. Then there exists $\gamma_1 : \mathbb{R}^+ \to \mathbb{R}^+$, satisfying (D1), (D2) and (D3), such that for some $x_1 > 1$ and for any $x \ge x_1$, we have

$$x^{-\gamma_1(x)} \le x^{\alpha/\delta}(1 - G_{(\delta)}(x)) \le x^{\gamma_1(x)}, \forall \delta \in [\delta_0, 1].$$

Recall that $G_{(\delta)}$ is the distribution function of $\lfloor Z^\delta \rfloor$ where $Z \sim G$ In particular, $G_{(\delta_0)}$ also satisfies Assumption 2.1 with moment index $\alpha/\delta_0$, provided $\delta_0 > \alpha$.

**Proof of Lemma A.1.** We have, by assumption, $\gamma : \mathbb{R}^+ \to \mathbb{R}^+$, satisfying (D1), (D2) and (D3), such that

$$x^{-\gamma(x)} \le x^{\alpha}(1 - G(x)) \le x^{\gamma(x)}, \forall x \ge x_0,$$

for some $x_0 \in (1, \infty)$. Fix $\delta \in [\delta_0, 1]$. For any $x \ge x_0 > 1$, we have $x^{1/\delta} > x_0^{1/\delta} \ge x_0$ and therefore can write the following.

$$1 - G_{(\delta)}(x) = \mathbb{P}(\lfloor Z^\delta \rfloor > x) \le \mathbb{P}(Z > x^{1/\delta}) = 1 - G(x^{1/\delta}) \\ \le x^{-\alpha/\delta} x^{\gamma(x^{1/\delta})/\delta} \le x^{-\alpha/\delta} x^{\gamma(x)/\delta}, \quad (A.9)$$

where the last inequality follows from non-monotonicity of $\gamma$ and the fact that $\delta \le 1$. Monotonicity of $\gamma$ also implies that

$$1 > \eta := \inf_{\delta \in [\delta_0, 1]} \inf_{x \ge 1} ((x+1)/x)^{-\alpha/\delta - \gamma(x)/\delta} \ge \inf_{\delta \in [\delta_0, 1]} \inf_{x \ge 1} ((x+1)/x)^{-\alpha/\delta - \gamma(1)/\delta} \\ = 2^{-\alpha/\delta_0 - \gamma(1)/\delta_0} > 0,$$

and hence for all $x \ge x_0$,

$$1 - G_{(\delta)}(x) = \mathbb{P}(\lfloor Z^\delta \rfloor > x) \ge \mathbb{P}(Z^\delta > x + 1) = 1 - G((x+1)^{1/\delta}) \\ \ge (x+1)^{-\alpha/\delta} (x+1)^{-\gamma((x+1)^{1/\delta})/\delta} \\ \ge (x+1)^{-\alpha/\delta} x^{-\gamma(x)/\delta}, \quad (A.10) \\ \ge \eta x^{-\alpha/\delta} x^{-\gamma(x)/\delta}, \quad (A.11)$$

where (A.10) uses monotonicity of the map $y \mapsto y^{\gamma(y)}$. Combining (A.9) and (A.11), we can write the following for any $x \ge x_0$ and $\delta \in [\delta_0, 1]$.

$$x^{-\gamma(x)/\delta_0} \eta \le x^{\alpha/\delta} (1 - G_{(\delta)}(x)) \le x^{\gamma(x)/\delta} \le x^{\gamma(x)/\delta_0} \eta^{-1}. \quad (A.12)$$

Defining $\gamma_1 : (0, \infty) \to (0, \infty)$ to be

$$\gamma_1(x) := \begin{cases} \frac{\gamma(x)}{\delta_0} - \frac{\log \eta}{\log x}, & \text{if } x \ge x_0, \\ \gamma_1(x_0), & \text{if } x < x_0, \end{cases}$$

it follows immediately that for all $x \ge x_0$ and $\delta \in [\delta_0, 1]$,

$$x^{-\alpha/\delta - \gamma_1(x)} \le 1 - G_{(\delta)}(x) \le x^{-\alpha/\delta + \gamma_1(x)}.$$
It is now enough to show that (D1), (D2) and (D3) are also satisfied if we replace $\gamma$ by $\gamma_1$. The monotonicity of $\gamma$ implies that $\gamma_1$ is also non-increasing. On the other hand, for $x \ge x_0$, $x^{\gamma_1(x)} = \eta^{-1}x^{\gamma(x)/\delta_0}$ which guarantees that $x \mapsto x^{\gamma_1(x)}$ is non-decreasing. Furthermore,

$$ \int_{\log \log x_0}^{\infty} \gamma_1(e^{e^x}) dx = \frac{1}{\delta_0} \int_{\log \log x_0}^{\infty} \gamma(e^{e^x}) dx - \log \eta \int_{\log \log x_0}^{\infty} \exp(-x) dx < \infty, $$

as $\int_0^\infty \gamma(e^{e^x}) dx < \infty$. Therefore, $\int_0^\infty \gamma_1(e^{e^x}) dx < \infty$ and this proves the lemma. $\square$

**Lemma A.2.** Let {$G_n : n \ge 0$} satisfies Assumption 2.5. Then for any $\beta \in (\sup_{n \ge 0} \alpha_n, 1)$, there exists $G_{max}$, a distribution function supported on the set of non-negative integers, such that $G_{max}$ satisfies Assumption 2.1 with moment index $\beta$ and $G_{max} \ge G_n$, pointwise, for all $n \ge 0$.

**Proof.** Let $\alpha_{max} := \sup_{n \ge 0} \alpha_n < 1$ and fix $\beta \in (\alpha, 1)$. Get $x_1$ large enough such that $\beta > \alpha_{max} + \gamma(x)$, for all $x \ge x_1$. This is possible since $\gamma$ satisfies (D1) and (D3); and hence $\gamma(x) \downarrow 0$ as $x \uparrow \infty$. Set $\tilde{x} = x_0 \vee x_1 \vee 1$ and define

$$ G^*(x) := \begin{cases} \sup_{n \ge 0} G_n(x), & \text{if } x < \tilde{x}, \\ 1 - x^{-\beta}, & \text{if } x \ge \tilde{x}. \end{cases} $$

Clearly, $G^*(0) = 0$ and $G^*(\infty) = 1$. Right continuity of $G^*$ on $[\tilde{x}, \infty)$ is obvious whereas on $(-\infty, \tilde{x})$ it is guaranteed by the fact that $G_n$ is supported on the set of integers for all $n \ge 0$. Moreover,

$$ G^*(\tilde{x}) - \sup_{n \ge 0} G_n(\tilde{x}) \le \sup_{n \ge 0} (1 - \tilde{x}^{-\alpha_n - \gamma(\tilde{x})}) \le 1 - \tilde{x}^{-\alpha_{max} - \gamma(\tilde{x})} \le 1 - \tilde{x}^{-\beta} = G^*(\tilde{x}), $$

implying that $G^*$ is indeed a distribution function, supported on the non-negative real line. It is obvious from the definition that $G^*$ satisfies (D4) with moment index $\beta$. Finally, for any $x \ge \tilde{x}$,

$$ 1 - G^*(x) = x^{-\beta} \le x^{-\alpha_n - \gamma(x)} \le 1 - G_n(x), $$

guaranteeing that $G^* \ge G_n$ for all $n \ge 0$, pointwise. Let $G_{max}$ be the distribution function of $[Z]$ where $Z \sim G^*$. $G_{max}$ is clearly supported on the set of non-negative integers; $G_{max} \ge G^* \ge G_n$ for all $n \ge 0$ and Lemma A.1 guarantees that $G_{max}$ satisfies Assumption 2.1 with moment index $\beta$. This completes the proof. $\square$

**Proof of Theorem 2.6.** Assumption 2.5 guarantees that $\alpha_n \le \alpha_{max} < 1$, for all $n \ge 0$. By Lemma A.2, it is possible to get hold of a distribution function $G_{max}$, supported on non-negative integers, that satisfies Assumption 2.1 with moment index $\beta \in (\alpha_{max}, 1)$ and $G_{max} \ge G_n$, pointwise, for all $n \ge 0$. Therefore, we can get a coupling measure $v_n$ on $\mathbb{Z}^2$ such that

$$ (Z_{1,1}, Z_{1,2}) \sim v_n \Rightarrow Z_{1,1} \sim G_{max}, Z_{1,2} \sim G_n, Z_{1,1} \le Z_{1,2} \text{ almost surely.} $$

Consider the following triangular array of pairs of random variables $\{(Z_{n,i,1}, Z_{n,i,2}) : n \ge 0, i \ge 1\}$ where $(Z_{n,i,1}, Z_{n,i,2}) \sim v_n$, independent of every other pair in this array. Define,

$$ Z_{0,j} := 1, \; Z_{n,j} := \sum_{i=1}^{Z_{n-1,j}} Z_{n-1,i,j}, \quad \forall n \ge 1, \; j = 1, 2. $$

The following observations are immediate from the construction.
(1) $\{Z_{n,1}: n \ge 0\}$ is the generation sizes of a homogeneous branching tree with progeny distribution $G_{max}$, starting with one particle in 0th generation. Since $G_{max}$ satisfies Assumption 2.1 with moment index $\beta$, we can apply Theorem 2.3 to conclude that there exists a non-negative non-degenerate random variable $W_1$ such that $n^{-1} \log \log Z_{n,1}$ converges almost surely to $-\log \beta > 0$, on the event ($W_1 > 0$). Note that $\mathbb{P}(W_1 > 0) > 0$.

(2) The sequence $\{Z_{n,2}: n \ge 0\}$ is the generation sizes of an in-homogeneous branching process with progeny distribution for the particles in the nth generation being $G_n$. In other words, $\{Z_{n,2}: n \ge 0\} \stackrel{d}{=} \{Z_n: n \ge 0\}$, as defined in the statement of Theorem 2.6 and hence it is enough to prove the assertion of the theorem for $\{Z_{n,2}: n \ge 0\}$.

(3) $(Z_{n,i,1}, Z_{n,i,2}) \sim v_n \Rightarrow Z_{n,i,1} \le Z_{n,i,2}, \forall i, n \Rightarrow Z_{n,1} \le Z_{n,2}, \forall n \ge 0$. Therefore,
$$ \liminf_{n \to \infty} \frac{1}{n} \log \log Z_{n,2} \ge \liminf_{n \to \infty} \frac{1}{n} \log \log Z_{n,1} = -\log \beta > 0, \text{ on } (W_1 > 0). $$

We can now apply Lemma 4.5 with $\mathcal{F}_n$ being the $\sigma$-algebra generated by the collection of random variables $\{Z_{k,i,1}, Z_{k,i,2}: 0 \le k \le n-1\}$ with $\zeta_n = Z_{n,2}$ and $L_{n,i} = Z_{n,i,2}$, for all $n \ge 0$. We conclude that there exists a non-negative integer valued random variable $N$, satisfying $\mathbb{P}(N = \infty, W_1 > 0) = 0$, such that the following occurs

$$ \left( \prod_{m=N+1}^{n} \alpha_m \right) \log Z_{n+1,2}(\omega) = \log Z_{N+1,2}(\omega) \prod_{m=N+1}^{n} \left( \frac{\alpha_m \log Z_{m+1,2}(\omega)}{\log Z_{m,2}(\omega)} \right) \rightarrow W_2(\omega) \in (0, \infty), \text{ as } n \rightarrow \infty, $$

for almost all $\omega \in (W_1 > 0)$. Here $W_2$ is some positive almost surely finite random variable. This implies our final assertion after we take $E := (W_1 > 0)$ and define $W^*$ as follows.

$$ W^*(\omega) = \begin{cases} W_2(\omega) \prod_{m=0}^{N(\omega)} \alpha_m, & \text{if } N(\omega) < \infty, W_1(\omega) > 0, \\ 1, & \text{otherwise.} \end{cases} \quad \square $$

**Proof of Lemma 4.3.** Consider the case of $\psi_n$ being bounded away from 1. Fix any positive $0 < \varepsilon < 1$, small enough. Let us first prove the lower bound of the limit.

$$ \begin{aligned} \mathbb{P}\left[G_{l_n; \zeta_n} \le L \left((1-\varepsilon)\psi_n \log \zeta_n\right) \middle| \mathcal{F}_n\right] &\le \mathbb{P}\left[\sum_{i=1}^{\zeta_n} 1 \left(G_{n,i} \ge L \left((1-\varepsilon)\psi_n \log \zeta_n\right)\right) \le l_n \middle| \mathcal{F}_n\right] \\ &= \mathbb{P}\left[\text{Binomial } (\zeta_n, p_n) \le l_n \middle| \mathcal{F}_n\right] \end{aligned} $$

where $p_n := \bar{F}(L((1-\varepsilon)\psi_n \log \zeta_n)) = \exp(-K \circ L((1-\varepsilon)\psi_n \log \zeta_n))$. By assumption on $F$, we have $K(L(x)) \sim x$ as $x \to \infty$. Therefore, almost surely, for large enough $n$, we can say $\exp(-(1-\varepsilon/2)\psi_n \log \zeta_n) \le p_n \le \exp(-(1-2\varepsilon)\psi_n \log \zeta_n)$, and hence $l_n \le \zeta_n^{1-\psi_n(1-\varepsilon/4)} \le \zeta_n^{1-\psi_n(1-\varepsilon/2)} \le \zeta_n p_n \le \zeta_n^{1-\psi_n(1-2\varepsilon)}$. Using Chebyshev's Inequality, we now obtain the following almost surely for all large enough $n$.

$$ \begin{aligned} \mathbb{P}\left[G_{l_n; \zeta_n} \le L \left((1-\varepsilon)\psi_n \log \zeta_n\right) \middle| \mathcal{F}_n\right] &\le \frac{\zeta_n p_n (1-p_n)}{(\zeta_n p_n - l_n)^2} \\ &\le \frac{\zeta_n^{1-\psi_n(1-2\varepsilon)}}{(\zeta_n^{1-\psi_n(1-\varepsilon/2)} - \zeta_n^{1-\psi_n(1-\varepsilon/4)})^2} \le 4\zeta_n^{1+\psi_n(1+\varepsilon)}. \end{aligned} $$
The fact that almost surely $\zeta_n^{\psi_n} = e^{\psi_n \log \zeta_n} \to \infty$ was crucial in deriving the last inequality in the above line. The last term being summable almost surely (since $\liminf_{n \to \infty} n^{-1} \log \zeta_n > 0$) for small enough $\varepsilon$, we use Levy's extension of Borel-Cantelli Lemma to conclude that for small enough $\varepsilon$,

$$ \liminf_{n \to \infty} \frac{G_{l_n; \zeta_n}}{L((1-\varepsilon)\psi_n \log \zeta_n)} \ge 1, \quad \text{almost surely.} \quad (A.13) $$

Since $\psi_n \log \zeta_n \sim \log l_n \to \infty$, almost surely, we have

$$ \lim_{\varepsilon \downarrow 0} \lim_{n \to \infty} \frac{L(\psi_n \log \zeta_n)}{L((1-\varepsilon)\psi_n \log \zeta_n)} = 1, \quad \text{almost surely.} \quad (A.14) $$

Here we have made use of the assumption that $\lim_{l \to 1} \lim_{\varepsilon \to \infty} L(tx)/L(x) = 1$. Combining (A.13) and (A.14), we conclude this case after taking $\varepsilon \downarrow 0$. Similarly for the upper bound, we have the following,

$$ \begin{aligned} \mathbb{P}\left[G_{l_n; \zeta_n} \ge L((1+\varepsilon)\psi_n \log \zeta_n) \middle| \mathcal{F}_n\right] &\le \mathbb{P}\left[\sum_{i=1}^{\zeta_n} 1\left(G_{n,i} \ge L((1+\varepsilon)\psi_n \log \zeta_n)\right) \ge l_n \middle| \mathcal{F}_n\right] \\ &= \mathbb{P}\left[\text{Binomial}(\zeta_n, q_n) \ge l_n \middle| \mathcal{F}_n\right], \end{aligned} $$

where $q_n := \bar{F}(L((1+\varepsilon)\psi_n \log \zeta_n)) = \exp(-K \circ L((1+\varepsilon)\psi_n \log \zeta_n))$. Therefore, almost surely, for large enough $n$, we can say $\exp(-(1+2\varepsilon)\psi_n \log \zeta_n) \le q_n \le \exp(-(1+\varepsilon/2)\psi_n \log \zeta_n)$, and hence $l_n \ge \zeta_n^{1-\psi_n(1+\varepsilon/4)} \ge \zeta_n^{1-\psi_n(1+\varepsilon/2)} \ge \zeta_n q_n$. Using Chebyshev's Inequality again, we obtain the following almost surely for all large enough $n$.

$$ \begin{aligned} \mathbb{P}\left[G_{l_n; \zeta_n} \ge L((1+\varepsilon)\psi_n \log \zeta_n) \middle| \mathcal{F}_n\right] &\le \frac{\zeta_n q_n (1-q_n)}{(l_n - \zeta_n q_n)^2} \\ &\le \frac{\zeta_n^{1-\psi_n(1+\varepsilon/2)}}{\left(\zeta_n^{1-\psi_n(1+\varepsilon/4)} - \zeta_n^{1-\psi_n(1+\varepsilon/2)}\right)^2} \le 4\zeta_n^{-1+\psi_n}. \end{aligned} $$

The last term being summable almost surely, we use arguments similar to what were used for lower bound and complete the proof for the upper bound.

For $l_n \equiv \psi_n \equiv 1$, we observe that, for any $\kappa \in (0, 1)$, we have $G_{l_n; \zeta_n} \ge G_{\lfloor \zeta_n^{1-\kappa} \rfloor; \zeta_n}$, for all large enough $n$, almost surely. Hence,

$$ \liminf_{n \to \infty} \frac{G_{l_n; \zeta_n}}{L(\log \zeta_n)} \ge \liminf_{n \to \infty} \frac{G_{\lfloor \zeta_n^{1-\kappa} \rfloor; \zeta_n}}{L(\log \zeta_n)} = \liminf_{n \to \infty} \frac{L(\kappa \log \zeta_n)}{L(\log \zeta_n)}, \quad \text{almost surely.} $$

The lower bound then follows from taking $\kappa \uparrow 1$. On the other hand, for any $\varepsilon > 0$,

$$ \begin{aligned} \mathbb{P}\left[G_{1; \zeta_n} \ge L((1+\varepsilon)\log \zeta_n) \middle| \mathcal{F}_n\right] &\le \mathbb{P}\left[\sum_{i=1}^{\zeta_n} 1\left(G_{n,i} \ge L((1+\varepsilon)\log \zeta_n)\right) \ge 1 \middle| \mathcal{F}_n\right] \\ &\le \zeta_n \bar{F}(L((1+\varepsilon)\log \zeta_n)) \\ &= \zeta_n \exp(-K \circ L((1+\varepsilon)\log \zeta_n)) \le \zeta_n^{-\varepsilon/2}, \end{aligned} $$

for large enough $n$, almost surely. The rest of the argument follows similarly as the previous one. $\square$
**Lemma A.3.** Consider the same set-up as in **Lemma 4.3**, but assume that the distribution function F satisfies **Assumption 3.1**. Then,

$$ \frac{\log G_{I_n; \zeta_n}}{\psi_n \log \zeta_n} \xrightarrow{a.s.} \frac{1}{\beta}, \quad \text{as } n \to \infty. $$

**Proof of Lemma A.3.** Note that, conditioned on $\mathcal{F}_n$, the random variable $\log G_{n,i}$ have distribution function given by $\tilde{F}(x) = \mathbb{P}(\log G_{n,1} \le x) = F(e^x)$, for all $x$. In light of **Remark 4.4**, it is enough to prove that $\tilde{K} := -\log(1 - \tilde{F})$ is regularly varying at $\infty$ with index $r = 1$ and $\tilde{L}(x) \sim \beta^{-1}x$ as $x \to \infty$, where $\tilde{L}$ is the left-continuous inverse of $\tilde{K}$.

Since $1 - F$ is regularly varying at $\infty$ with index $-\beta < 0$, we can apply [37, Proposition 0.8(i)] to conclude that $\log(1 - F(x)) \sim -\beta \log x$, as $x \to \infty$. Therefore, for any $t > 0$,

$$ \frac{\tilde{K}(tx)}{\tilde{K}(x)} = \frac{-\log(1 - F(e^{tx}))}{-\log(1 - F(e^x))} \sim \frac{\beta t x}{\beta x} \sim t, \quad \text{as } x \to \infty, $$

and hence $\tilde{K}$ is regularly varying at $\infty$ with index 1. On the other hand,

$$ \tilde{K}(x) = -\log(1 - F(e^x)) \sim \beta x, \quad \text{as } x \to \infty. $$

As mentioned in **Remark 4.4**, we have $\tilde{K}(\tilde{L}(x)) \sim x$ as $x \to \infty$; hence $x \sim \tilde{K}(\tilde{L}(x)) \sim \beta \tilde{L}(x)$. This completes the proof. $\square$

**Lemma A.4.** If $h$ is regularly varying at $\infty$ with index $\rho > 0$ and $a \in (0, 1)$, then

$$ \lim_{n \to \infty} \frac{1}{h(a^{-n})} \sum_{i=1}^{n} h(a^{-i}) = \frac{1}{1 - a^{\rho}}. $$

**Proof.** For each fixed $m$, we have, by regular variation

$$ \begin{aligned} \lim_{n \to \infty} \frac{1}{h(a^{-n})} \sum_{i=n-m}^{n} h(a^{-i}) &= \lim_{n \to \infty} \frac{1}{h(a^{-n})} \sum_{i=n-m}^{n} h(a^{n-i} a^{-n}) \\ &= \lim_{n \to \infty} \frac{1}{h(a^{-n})} \sum_{i=0}^{m} h(a^i a^{-n}) = \sum_{i=0}^{m} a^{i\rho}. \end{aligned} $$

The last sum tends to $(1 - a^{\rho})^{-1}$ as $m$ tends to infinity, thus the lemma will be proved if we check that

$$ \lim_{m \to \infty} \lim_{n \to \infty} \frac{1}{h(a^{-n})} \sum_{i=1}^{n-m} h(a^{-i}) = 0. \quad (A.15) $$

We have $h(x) = \ell(x)x^\rho$ with $\ell$ being a slowly varying function. Using [37, Theorem 0.6], for $x > 0$, $\ell(x) = c(x) \exp\left(\int_1^x t^{-1}\xi(t)dt\right)$, where $\lim_{x \to \infty} c(x) = c \in (0, \infty)$ and $\lim_{x \to \infty} \xi(x) = 0$. Hence, for every $\varepsilon > 0$, for large enough $x < y$,

$$ \frac{x^{\varepsilon}\ell(x)}{y^{\varepsilon}\ell(y)} = \frac{c(x)}{c(y)} \exp\left(-\int_x^y t^{-1}(\xi(t) + \varepsilon)dt\right) \le \frac{c(x)}{c(y)} \le \Lambda, $$

for some finite constant $\Lambda$. Thus, we can find finite constant $A_\varepsilon \ge 1$ such that for large enough $n$,

$$ \sup_{1 \le i \le n} \frac{a^{\varepsilon(i-n)} \ell(a^{i-n})}{a^{-\varepsilon n} \ell(a^{-n})} \le \sup_{1 \le x \le a^{-n}} \frac{x^{\varepsilon} \ell(x)}{a^{-\varepsilon n} \ell(a^{-n})} \le \frac{\sup_{1 \le x \le A_{\varepsilon}} x^{\varepsilon} \ell(x)}{a^{-\varepsilon n} \ell(a^{-n})} + \Lambda. $$
Thus, for $\varepsilon \in (0, \rho)$ and large $n$,

$$ \sup_{1 \le i \le n} \frac{a^{\varepsilon(i-n)} \ell(a^{i-n})}{a^{-\varepsilon n} \ell(a^{-n})} \le 2\Lambda, $$

and

$$ \frac{1}{h(a^{-n})} \sum_{i=1}^{n-m} h(a^{-i}) = \sum_{i=m}^{n-1} \frac{h(a^{-n}a^{i})}{h(a^{-n})} = \sum_{i=m}^{n-1} a^{(\rho-\varepsilon)i} \frac{a^{\varepsilon(i-n)} \ell(a^{i-n})}{a^{-\varepsilon n} \ell(a^{-n})} \\ \le 2\Lambda \sum_{i=m}^{\infty} a^{(\rho-\varepsilon)i} = \frac{2\Lambda a^{m(\rho-\varepsilon)}}{1-a^{\rho-\varepsilon}}. $$

Taking $n, m \to \infty$, (A.15) follows. □

**Lemma A.5.** Take two sequence $\{a_n\}_{n \ge 1}$ and $\{b_n\}_{n \ge 1}$ of real numbers such that $\sum_{k=1}^n b_k \uparrow \infty$. Then

$$ \liminf_{n \to \infty} a_n \le \liminf_{n \to \infty} \frac{\sum_{i=1}^{n} a_i b_i}{\sum_{i=1}^{n} b_i} \le \limsup_{n \to \infty} \frac{\sum_{i=1}^{n} a_i b_i}{\sum_{i=1}^{n} b_i} \le \limsup_{n \to \infty} a_n. $$

**Proof.** The proof is a straightforward analysis exercise. □

## References

[1] L. Addario-Berry, B. Reed, Minima in branching random walks, Ann. Probab. (2009) 1044–1079.

[2] E. Aidékon, Convergence in law of the minimum of a branching random walk, Ann. Probab. 41 (3A) (2013) 1362–1426.

[3] S. Asmussen, E. Hashorva, P.J. Laub, T. Taimre, Tail asymptotics of light-tailed Weibull-like sums, Probab. Math. Statist. 37 (2) (2017) 235–256.

[4] A.A. Balkema, C. Klüppelberg, S.I. Resnick, Densities with Gaussian tails, Proc. Lond. Math. Soc. (3) 66 (3) (1993) 568–588.

[5] I. Benjamini, Y. Peres, Tree-indexed random walks and first-passage percolation, Probab. Theory Related Fields 98 (1994) 91–112.

[6] J. Bérard, P. Maillard, The limiting process of n-particle branching random walk with polynomial tails, Electron. J. Probab. 19 (22) (2014) 1–17.

[7] A. Bhattacharya, Large deviation for extremes of branching random walk with regularly varying displacements, 2018, arXiv preprint arXiv:1802.05938.

[8] A. Bhattacharya, A note on randomly scaled scale-decorated Poisson point processes, 2018, arXiv preprint a rXiv:1802.04842.

[9] A. Bhattacharya, R.S. Hazra, P. Roy, Point process convergence for branching random walks with regularly varying steps, Ann. Inst. Henri Poincaré Probab. Stat. 53 (2) (2017) 802–818.

[10] A. Bhattacharya, R.S. Hazra, P. Roy, Branching random walks, stable point processes and regular variation, Stochastic Process. Appl. 128 (1) (2018) 182–210.

[11] J. Biggins, The first-and last-birth problems for a multitype age-dependent branching process, Adv. Appl. Probab. (1976) 446–459.

[12] P. Billingsley, Convergence of Probability Measures, Wiley, New York, 1968.

[13] N.H. Bingham, C.M. Goldie, J.L. Teugels, Regular variation, in: Encyclopedia of Mathematics and Its Applications, Cambridge University Press, 1987.

[14] M. Bramson, O. Zeitouni, Tightness of the recentered maximum of the twodimensional discrete gaussian free field, Comm. Pure Appl. Math. 65 (1) (2012) 1–20.

[15] É. Brunet, B. Derrida, A branching random walk seen from the tip, J. Stat. Phys. 143 (3) (2011) 420–446.

[16] D.B.H. Cline, Convolution tails, product tails and domains of attraction, Probab. Theory Related Fields 72 (1986) 529–557.

[17] D. Darling, The Galton–Watson process with infinite mean, J. Appl. Probab. 7 (2) (1970) 455–456.
[18] P.L. Davies, The simple branching process: A note on convergence when the mean is infinite, J. Appl. Probab. 15 (3) (1978) 466–480.

[19] L. de Haan, A. Ferreira, Extreme Value Theory: An Introduction, in: Springer Series in Operations Research and Financial Engineering, Springer, New York, 2006.

[20] M. Deijfen, R. van der Hofstad, G. Hooghiemstra, Scale-free percolation, Ann. Inst. Henri Poincaré Probab. Stat. 49 (3) (2013) 817–838.

[21] P. Dey, E.C. Waymire, On normalized multiplicative cascades under strong disorder, Electron. Commun. Probab. 20 (32) (2015) 13.

[22] R. Durrett, Maxima of branching random walks vs. independent random walks, Stochastic Process. Appl. 9 (2) (1979) 117–135.

[23] R. Durrett, Maxima of branching random walks, Z. Wahrscheinlichkeits-theor. Verwandte Geb. 62 (2) (1983) 165–170.

[24] P. Embrechts, C. Klüppelberg, T. Mikosch, Modelling Extremal Events, Springer-Verlag, Berlin, 1997.

[25] N. Gantert, The maximum of a branching random walk with semiexponential increments, Ann. Probab. (2000) 1219–1229.

[26] D.R. Grey, Almost sure convergence in Markov branching processes with infinite mean, J. Appl. Probab. 14 (4) (1977) 702–716.

[27] J.M. Hammersley, Postulates for subadditive processes, Ann. Probab. (1974) 652–680.

[28] Y. Hu, Z. Shi, Minimal position and critical martingale convergence in branching random walks, and directed polymers on disordered trees, Ann. Probab. 37 (2) (2009) 742–789.

[29] O. Kallenberg, Random Measures, fourth ed., Akademie-Verlag, Berlin; Academic Press, Inc., London, 1986.

[30] J.F.C. Kingman, The first birth problem for an age-dependent branching process, Ann. Probab. (1975) 790–801.

[31] J. Komjáthy, B. Lodewijks, Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs, Stochastic Process. Appl. (2019).

[32] R. Lyons, R. Pemantle, Random walks in a random environment and firstpassage percolation on trees, Ann. Probab. 20 (1992) 125–136.

[33] T. Madaule, Convergence in law for the branching random walk seen from its tip, J. Theoret. Probab. (2015) 1–37.

[34] P. Maillard, A note on stable point processes occurring in branching Brownian motion, Electron. Commun. Probab. (ISSN: 1083-589X) 18 (5) (2013) 9.

[35] P. Maillard, The maximum of a tree-indexed random walk in the big jump domain, ALEA Lat. Am. J. Probab. Math. Stat. 13 (2016) 545–561.

[36] Y. Peres, Probability on trees: an introductory climb, in: Lectures on Probability and Statistics, in: Lecture Notes in Math, vol. 1717, Springer, New York, 2000.

[37] S.I. Resnick, Extreme values, regular variation and point processes, in: Applied Probability, in: A Series of the Applied Probability Trust, vol. 4, Springer-Verlag, New York, 1987.

[38] S.I. Resnick, Heavy-tail phenomena, Springer Series in Operations Research and Financial Engineering, Springer, New York, 2007, Probabilistic and statistical modeling.

[39] H.-J. Schuh, A.D. Barbour, On the asymptotic behaviour of branching processes with infinite mean, Adv. Appl. Probab. 9 (4) (1977) 681–723.

[40] E. Seneta, The simple branching process with infinite mean. i, J. Appl. Probab. 10 (1) (1973) 206–212.

[41] Z. Shi, Branching Random Walks, Springer, 2015.

[42] E. Subag, O. Zeitouni, The extremal process of critical points of the pure p-spin spherical spin glass model, Probab. Theory Related Fields 168 (3-4) (2017) 773–820.

[43] H. Van Den Esker, R. Van Der Hofstad, G. Hooghiemstra, D. Znamenski, Distances in random graphs with infinite mean degrees, Extremes 8 (3) (2005) 111–141.

[44] R. van der Hofstad, G. Hooghiemstra, D. Znamenski, Distances in random graphs with finite mean and infinite variance degrees, Electron. J. Probab. 12 (2007) 703–766.

[45] R. van der Hofstad, J. Komjáthy, Explosion and distances in scale-free percolation, 2017, arXiv preprint arXiv:1706.02597.

[46] M.J. Wichura, Functional laws of the iterated logarithm for the partial sums of i.i.d. random variables in the asymmetric stable law, Ann. Probab. 2 (1974) 1108–1138.