# The limiting process of *N*-particle branching random walk with polynomial tails

Jean Bérard, Pascal Maillard

<figure><img src="image_1.png" /></figure>

## To cite this version:

Jean Bérard, Pascal Maillard. The limiting process of *N*-particle branching random walk with polynomial tails. Electronic Journal of Probability, 2014, 19 (22), 10.1214/ejp.v19-3111. hal-04853661

HAL Id: hal-04853661

https://hal.science/hal-04853661v1

Submitted on 7 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The limiting process of N-particle branching random walk with polynomial tails

JEAN BÉRARD *,‡

Université de Strasbourg
67400 Strasbourg, France

PASCAL MAILLARD †,‡

Weizmann Institute of Science
76100 Rehovot, Israel

November 4, 2018

## Abstract

We consider a system of $N$ particles on the real line that evolves through iteration of the following steps: 1) every particle splits into two, 2) each particle jumps according to a prescribed displacement distribution supported on the positive reals and 3) only the $N$ right-most particles are retained, the others being removed from the system. This system has been introduced in the physics literature as an example of a microscopic stochastic model describing the propagation of a front. Its behavior for large $N$ is now well understood – both from a physical and mathematical viewpoint – in the case where the displacement distribution admits exponential moments. Here, we consider the case of displacements with regularly varying tails, where the relevant space and time scales are markedly different. We characterize the behavior of the system for two distinct asymptotic regimes. First, we prove convergence in law of the rescaled positions of the particles on a time scale of order $\log N$ and give a construction of the limit based on the records of a space-time Poisson point process. Second, we determine the appropriate scaling when we let first the time horizon, then $N$ go to infinity.

**Keywords.** branching random walk; heavy-tailed distribution; selection

MSC2010. 60K35; 60J80

# 1 Introduction

## 1.1 Definitions

**The N-BRW.** Let $X$ be a random variable taking values in $\mathbb{R}_+$ and define $h(x)$ by

$$ \mathbb{P}(X > x) = 1/h(x), \quad x \ge 0. \qquad (1.1) $$

We assume throughout the paper that the function $h(x)$ is regularly varying at $+\infty$ with index $\alpha > 0$ (see e.g. [4] for a definition of regular variation). For every integer $N \ge 1$, we

<footnote>*e-mail: jean DOT berard AT univ-lyon1 DOT fr</footnote>

<footnote>†e-mail: pascal DOT maillard AT weizmann DOT ac DOT il</footnote>

<footnote>‡Partially supported by ANR project MEMEMO2. PM is partially supported by a grant from the Israel Science Foundation.</footnote>
define the following N-particle system. At the beginning, all N particles are located at the origin. At each time step, each of the N particles branches into two, and all 2N particles then perform independent jumps according to the law of X. After this, only the N particles at the maximal positions are retained. We call this system the N-branching random walk or N-BRW.

More formally, we define a sequence $(\mathcal{X}(n))_{n \ge 0}$ of N-tuples of real numbers that represent the successive populations of N particles, with

$$ \mathcal{X}(n) = \{\mathcal{X}_1(n) \le \dots \le \mathcal{X}_N(n)\}. $$

Let $(X_{n,i})_{n \ge 0, i \in [2N]}$ denote i.i.d. random variables distributed as X. Initially, one sets $\mathcal{X}_i(0) = 0$ for all $i \in [N] := \{1, \dots, N\}$. Then, for each integer $n \ge 0$, one inductively defines $\mathcal{X}(n+1) = \{\mathcal{X}_1(n+1) \le \dots \le \mathcal{X}_N(n+1)\}$ to be the N largest numbers from the collection $(\mathcal{X}_i(n) + X_{n,2i+j})_{i \in [N], j \in \{0,1\}}$, sorted in ascending order.

**The stairs process.** We now define the *stairs process*, a real-valued stochastic process which will be shown to approximate the N-BRW when N is large. We first define a *stairs measure* to be a non-zero measure $\mu$ on $(0, \infty)$ such that $\mu([a, +\infty)) < +\infty$ for every $a > 0$ (in particular, $\mu$ is $\sigma$-finite). The $\mu$-stairs process then is the real-valued stochastic process $\mathcal{R}(t)$ defined as follows: Given a Poisson point process on $\{(t, x) : t, x > 0\}$ with intensity $dt \otimes \mu$, define a process $(\xi_t)_{t \ge 0}$ by $\xi_t = x$ if $(t, x)$ is an atom of the process and $\xi_t = 0$ otherwise. Now define $\mathcal{R}(t)$ inductively as follows: For $t \le 0$, $\mathcal{R}(t) = 0$. For integer $n = 0, 1, 2, \dots$, knowing the value of $\mathcal{R}(t)$ for $t \le n$, define $\mathcal{R}(t)$ for $t \in (n, n+1]$ by

$$ \mathcal{R}(t) = \max_{s \in [0,1]} (\mathcal{R}(t-s) + \xi_{t-s}). \qquad (1.2) $$

<figure><img src="image_3.png" /><figcaption>Figure 1: Graphical representation of the stairs process.</figcaption></figure>
This definition is equivalent to the following construction: Suppose the process $\mathcal{R}(t)$ is defined for $t \le n \in \mathbb{N}$. Now generate points in the interval $(n, n+1]$ according to the above Poisson process and translate every atom $(t, x)$ by $\mathcal{R}(t-1)$ in the $x$-direction (note that the graph of $\mathcal{R}(t-1)$ is the graph of $\mathcal{R}(t)$ shifted by 1 to the right). Then define $\mathcal{R}(t)$ for $t \in (n, n+1]$ to be the record process of these points. See Figure 1 for a graphical representation.

One easily verifies that $\mathcal{R}(t)$ is a non-decreasing càdlàg process and that the following representation holds for $t \ge 0$:

$$ \mathcal{R}(t) = \max \left\{ \sum_{i=1}^{k} \xi_{t_i} : k \in \mathbb{N}, 0 \le t_1 < \dots < t_k \le t, |t_i - t_{i-1}| \ge 1 \quad \forall i \right\} \quad (1.3) $$

*Remark.* The process $\max_{s \in [0,t]} \xi_s$ is known in the literature as a Poisson paced record process [11]. The stairs process can be interpreted as a self-interacting version of it. Its long-term behaviour is quite different: While a Poisson paced record process usually grows logarithmically in $t$, the stairs process grows like a random walk, due to the existence of regeneration times (see Section 2).

## 1.2 Statements of the results

Define $\mu_\alpha$ to be the measure on $(0, \infty)$ defined by $\mu_\alpha([x, \infty)) = x^{-\alpha}$ and let $\mathcal{R}^\alpha(t)$ denote a realisation of the $\mu_\alpha$-stairs process. Define a sequence $(c_N)_{N \ge 1}$ by $c_N = h^{-1}(2N \log_2 N)$, where $h^{-1}$ is the generalized inverse of $h$. Note that by the regular variation of $h$, we have $h(c_N) \sim 2N \log_2 N$ as $N \to \infty$.

Our first theorem gives convergence in law of the maximum and the minimum of the $N$-BRW to a certain stairs process, after rescaling of space and time. For a definition of Skorokhod's $J_1$ and $SM_1$ topologies appearing in the statement of the theorem, see [26, Chapter 12]. Note that the former topology is also commonly called the Skorokhod topology.

**Theorem 1.1.** We have the following convergences in law, as $N \to \infty$:

$$ \begin{array}{l} (c_N^{-1} \chi_N(\lfloor t \log_2 N \rfloor))_{t \ge 0} \implies (\mathcal{R}^\alpha(t))_{t \ge 0}, \qquad \text{in the } J_1\text{-topology} \\ (c_N^{-1} \chi_N(\lfloor t \log_2 N \rfloor), c_N^{-1} \chi_1(\lfloor t \log_2 N \rfloor))_{t \ge 0} \implies (\mathcal{R}^\alpha(t), \mathcal{R}^\alpha(t-1))_{t \ge 0}, \qquad \text{in the } SM_1\text{-topology.} \end{array} $$

*Remark.* One cannot expect convergence of $c_N^{-1} \chi_1(\lfloor t \log_2 N \rfloor)_{t \ge 0}$ in the $J_1$-topology, since for some values of $N$, it may have two consecutive macroscopic jumps.

For a random variable $Y$, denote by $\mathcal{L}(Y)$ the law of $Y$. Denote by $d(\cdot, \cdot)$ the Prokhorov metric on the space of probability measures on $\mathbb{R}$. For two positive sequences $a_N$ and $b_N$, write $a_N \sim b_N$ if $a_N/b_N \to 1$ as $N \to \infty$.

The next theorem is our main theorem. It studies the limiting behaviour of the $N$-BRW, when we let first the time horizon, then $N$ go to infinity.

**Theorem 1.2.** We distinguish between the following cases:

* $\alpha > 1$: The limit $v_N = \lim_{n \to \infty} \chi_N(n)/n = \lim_{n \to \infty} \chi_1(n)/n$ exists almost surely and in $L^1$ and satisfies $v_N \sim \rho_\alpha c_N / \log_2 N$. Here, the limit $\rho_\alpha = \lim_{t \to \infty} \mathcal{R}^\alpha(t)/t$ exists almost surely and in $L^1$ and is a positive and finite constant.
• $\alpha = 1$, $\mathbb{E}[X] < \infty$: The limit $v_N = \lim_{n \to \infty} \chi_N(n)/n = \lim_{n \to \infty} \chi_1(n)/n$ exists almost surely and in $L^1$ and satisfies $v_N \sim (c_N/\log_2 N) \int_1^\infty h(c_N)/h(c_N x) dx$.

• $\alpha = 1$, $\mathbb{E}[X] = \infty$: Set $b_n^N = \int_1^{h^{-1}(n)} h(c_N)/h(c_N x) dx$. Then, for $i \in \{1, N\}$,

$$ \lim_{N \to \infty} \limsup_{n \to \infty} d \left( \mathcal{L} \left( \frac{\log_2 N}{c_N} \frac{\chi_i(n)}{nb_n^N} \right), \delta_1 \right) = 0. $$

• $0 < \alpha < 1$: Let $W_\alpha$ be a random variable with Laplace transform

$$ \mathbb{E}[e^{-\lambda W_{\alpha}}] = \exp(-\alpha \int_{0}^{\infty} (1 - e^{-\lambda x}) x^{-\alpha-1} dx). \quad (1.4) $$

Then, for $i \in \{1, N\}$,

$$ \lim_{N \to \infty} \limsup_{n \to \infty} d \left( \mathcal{L} \left( (2N)^{-\alpha} \frac{\chi_i(n)}{h^{-1}(n)} \right), \mathcal{L}(W_{\alpha}) \right) = 0. $$

## 1.3 Heuristics and proof strategy

The global heuristic picture of the N-BRW is the following: At a typical time and viewed on the space scale $c_N$, the particles are divided into one big “tribe” located near the left-most particle and containing all but $o(N)$ particles, the remaining particles to the right being split into a $O(1)$ number of smaller tribes. At each time step, the number of particles in every small tribe is multiplied by two, which eventually leads to extinction of the big tribe and another tribe taking over. Furthermore, new tribes are formed by particles performing (rightward) jumps of magnitude $c_N$ out of the big tribe. The value of $c_N$ has been chosen so that these events occur on the time scale $\log_2 N$, which is precisely the time it takes for a new tribe to grow to size $N$.

As $N \to \infty$, the jumps leading to new tribes are described by a space-time Poisson point process shifted in space by the position of the big tribe. This leads to the definition of the stairs process from Section 1.1 and illustrated in Figure 1. Note that the record points of that process exactly correspond to the creation of tribes which will eventually take over the population, the other points representing tribes which get extinct before reaching a size of order $N$.

In order to render this picture rigorous, we will couple the N-BRW with a discretized version of the stairs process, see (3.1), in such a way that the error is bounded in $L^p$ for $p < 2\alpha$. Ideally, we would have liked to use a single coupling between both processes to derive Theorems 1.1 and 1.2 and say something about the empirical measure of the N-BRW. However, it turned out to be more convenient to use separate couplings for upper and lower bounds for the positions of the right- and left-most particles. The trickier part here consisted in the upper bound, the key to which is Proposition 3.2. An important ingredient consists of large deviation estimates for sums of iid variables with regularly varying tails.

Theorem 1.2 is then derived from the above coupling and Theorem 2.5 below. In order to prove the latter, we define a regeneration structure for the stairs process, which permits to use classical results on random walks with regularly varying tails.

Note that analogues of the above theorems should remain valid if one allows $X$ to take on negative values or if one considers more general reproduction laws. Since this increases the technical difficulties without leading to new phenomena, we chose to keep to our setting for simplicity.
1.4 Discussion

For light-tailed displacement distributions, i.e. satisfying an exponential moment assumption, the N-BRW model has been studied in the physics literature as a microscopic stochastic model describing the propagation of a front, along with several variants [6, 8, 8, 10]. In the limit as $N \to \infty$, the dynamics of the model is described by an analog of the Fisher–Kolmogorov–Petrovskii–Piskounov (FKPP) equation, which is a prototypical example of a reaction-diffusion equation admitting travelling wave solutions [19, 21] (see [17] for a rigorous result of this type). One is then interested in understanding how the behaviour of the model for large but finite N reflects that of the limiting equation. The main results are the following:

• The cloud of particles propagates with a finite asymptotic velocity $v_N$. As $N \to \infty$, $v_N$ converges to the velocity $v$ of a travelling wave solution to the corresponding FKPP-type equation, which is also the speed of the right-most particle in the BRW without selection. Moreover, this convergence takes place at the unusually slow rate of $(\log N)^{-2}$ [6, 2].

• The relevant time scale both for macroscopic fluctuations of the cloud and for coalescence of ancestral lineages is $(\log N)^3$ [9, 10, 3, 22]. The genealogy is asymptotically described by the Bolthausen–Sznitman coalescent [3].

By contrast, in our heavy-tailed setting, the following happens:

• The particles propagate either linearly or superlinearly (but still at most polynomially) in time. In both cases, the scaling factor due to the number of particles in the system grows roughly polynomially in $N$. Without selection (i.e. for the classical BRW), the right-most particle would propagate exponentially fast in time [15] due to the exponential growth of the number of particles<fnref n="1" />. Note that a similar behavior is observed in reaction-diffusion equations with fractional Laplacian or other non-local operators [12], which play the role of the FKPP equation in this context.

• The relevant time scale both for macroscopic fluctuations of the cloud and for coalescence of ancestral lineages is $\log N$. The genealogy is trivial<fnref n="2" />. Moreover, the fluctuations come from large jumps of single particles, in contrast to the more complex mechanism leading to the fluctuations in the light-tailed setting [22].

A natural question and possibility for future research is now to investigate what happens in between the two scenarios of light-tailed displacement distributions (satisfying an exponential moment assumption) and the polynomial tails considered in the present article.

1.5 Organisation of the paper

In Section 2, we first derive some basic properties of the stairs process and prove Theorem 2.5, which gives its long-time behaviour. In Section 3, we bound the N-BRW from below and from above by a discretised version of the stairs process. The main work here lies in the upper bound, which is contained in Proposition 3.2. In the short Section 4, we couple the stairs process with its discretised version. Sections 2, 3 and 4 can be read independently of

<footnote n="1">¹For the stretched exponential case, see [20].</footnote>

<footnote n="2">²Here, *trivial* means that the genealogy is given by the “star-shaped coalescent”. This follows from the heuristic picture described above, although we haven’t worked out a full proof of this fact.</footnote>
one another. Finally, Section 5 contains the proofs of Theorems 1.1 and 1.2, relying on the results obtained in the previous sections.

## 2 Properties of the stairs process

Throughout this section, we assume that $\mu$ is a stairs measure as defined in the last section (i.e., $\mu$ is a non-zero measure on $(0, \infty)$ such that $\mu([a, +\infty]) < +\infty$ for every $a > 0$). We regard $\mu$ as an element in the space of $\sigma$-finite measures on $(0, \infty)$ endowed with the vague topology, i.e. the weak topology with respect to the space of continuous functions supported on a compact subset of $(0, \infty)$. Statements such as “as $\mu$ varies” always refer to this topology. We further denote by $\mathcal{R}(t)$ a realization of the $\mu$-stairs process.

We define a regeneration structure for $\mathcal{R}(t)$ as follows: Let $\tau_0 = 0$ and for $n \ge 1$, let $\tau_n = \inf\{t > \tau_{n-1} + 1 : \mathcal{R}(t) = \mathcal{R}(t-1)\}$. By the definition of the stairs process, the random times $(\tau_n)_{n \in \mathbb{N}}$ are regeneration times, i.e. the collection of pairs $(\mathcal{R}(\tau_n)-\mathcal{R}(\tau_{n-1}), \tau_n-\tau_{n-1})_{n \ge 1}$ are i.i.d. Furthermore, we have the following lemma:

**Proposition 2.1.** There exists a constant $C > 0$ (depending on $\mu$), such that $\mathbb{P}(\tau_1 > t) \le C^{-1}e^{-Ct}$ for all $t > 0$. This constant can be chosen to vary continuously with $\mu$.

*Proof.* By definition of $\mu$, there exists $m \in (0, \infty)$, such that $\mu([m, \infty)) < \infty$ and $\mu((2m, \infty)) > 0$. Let $M_n^1 \ge M_n^2 \ge \dots$ be the $x$-coordinates of the atoms of the Poisson process from the definition of the $\mu$-stairs process in the time-interval $[n, n+1)$, arranged in decreasing order. We then have for each $n \ge 0$,

$$ \mathbb{P}(\tau_1 \le n + 3 | \mathcal{F}_n) \ge \mathbb{P}(M_n^1 < m, M_{n+1}^1 > 2m, M_{n+1}^2 < m, M_{n+2}^1 < m), \quad (2.1) $$

because the event on the right-hand side ensures that there is a time $T \in [n+1, n+2)$ with $\mathcal{R}(T) - \mathcal{R}(T-) > m$ and with $\mathcal{R}(T+s) = \mathcal{R}(T)$ for all $s \in [0, 1]$. This implies $\tau_1 \le T+1 \le n+3$. Now, the right-hand side of (2.1) is positive, independent of $n$ and continuous in $\mu$. The proposition is immediate. $\square$

**Proposition 2.2.** Suppose $\int_1^\infty x\mu(dx) < \infty$. Then the limit $\rho = \lim_{t \to \infty} \mathcal{R}(t)/t$ exists almost surely and in $L^1$ and satisfies $\rho = \mathbb{E}[\mathcal{R}(\tau_1)]/\mathbb{E}[\tau_1] > 0$.

*Remark 2.3.* Proposition 2.2 implies in particular that for every $\alpha > 1$, the limit $\rho_\alpha = \lim_{t \to \infty} \mathcal{R}^\alpha(t)/t$ exists almost surely and in $L^1$ and is a positive and finite constant.

*Proof of Proposition 2.2.* Let $\xi_t$ be as in the definition of the $\mu$-stairs process. For $n \ge 0$, define the process $\xi_t^n = \xi_t 1_{t>n}$ and let $(\mathcal{R}(n, t))_{t \in \mathbb{R}}$ be the $\mu$-stairs process defined from $\xi^n$ as in (1.2). One easily checks from the definition or by (1.3) that $\mathcal{R}(0, m) \le \mathcal{R}(0, n) + \mathcal{R}(n, m)$ for every $n \le m$. Moreover, by the hypothesis on $\mu$, $\mathcal{R}(1)$ is positive and integrable, since $\mathbb{P}(\mathcal{R}(1) > x) = 1 - \exp(-\mu((x, \infty)))$. Kingman's subadditive ergodic theorem [16, Theorem 6.6.1], whose remaining conditions are readily verified, now yields almost sure and $L^1$-convergence of $\mathcal{R}(n)/n$ to a non-negative, finite constant $\rho$, and by the monotonicity of $\mathcal{R}(t)$, this convergence also holds for $\mathcal{R}(t)/t$.

Now note that $\mathbb{E}[\tau_1] < \infty$ by Proposition 2.1, so that $\tau_n/n$ converges almost surely to $\mathbb{E}[\tau_1]$ by the law of large numbers. The almost sure convergence of $\mathcal{R}(t)/t$ established above then yields almost sure convergence of $\mathcal{R}(\tau_n)/n$ to $\mathbb{E}[\tau_1]\rho$. By the converse to the law of large numbers, this implies that $\mathbb{E}[\mathcal{R}(\tau_1)]$ is finite and that $\rho = \mathbb{E}[\mathcal{R}(\tau_1)]/\mathbb{E}[\tau_1]$. Moreover, $\mathbb{E}[\mathcal{R}(\tau_1)]$
is positive, because the measure $\mu$ is non-zero by definition and $\mathcal{R}(\tau_1) \ge \mathcal{R}(1)$. This shows $\rho > 0$.

We remark that we could have proven Proposition 2.2 without applying Kingman's sub-additive ergodic theorem; using only the regeneration structure and an argument involving Fatou's lemma and the converse to the law of large numbers to get finiteness of $\mathbb{E}[\mathcal{R}(\tau_1)]$. $\square$

**Proposition 2.4.** Let $\mu_N$ be a sequence of stairs measures converging to $\mu$ and denote by $\mathcal{R}^N(t)$ and $(\tau_n^N)_{n \ge 0}$ the corresponding stairs process and regeneration times. Then the following holds:

1. The sequence of processes $(\mathcal{R}^N(t))_{t \ge 0}$ converges in law to $(\mathcal{R}(t))_{t \ge 0}$ w.r.t. the $J_1$-topology ("Skorokhod's topology"), as $N \to \infty$.

2. The sequences of random variables $\tau_1^N$ and $\mathcal{R}^N(\tau_1^N)$ converge in law to $\tau_1$ and $\mathcal{R}(\tau_1)$, respectively, as $N \to \infty$.

3. The sequence $\tau_1^N$ is uniformly integrable in $N$.

*Proof.* We can assume w.l.o.g. that $\mu$ has no atoms and has full support in $(0, \infty)$. Moreover, we can assume that $\mu_N((0, \infty)) \le \mu((0, \infty))$ for every $N$, otherwise we truncate $\mu_N$ near the origin. Let $\xi_t^N$ and $\xi_t$ be the processes used to construct $\mathcal{R}^N$ and $\mathcal{R}$. Define the functions $F, F_N: \mathbb{R}_+^* \to \mathbb{R}_+$ by $F(x) = \mu([x, \infty))$ and $F_N(x) = \mu_N([x, \infty))$ and let $F_N^{-1}(x) = \inf\{y \ge 0 : F_N(y) \le x\}$ be the generalised inverse of $F_N$. Defining the function $f_N := F_N^{-1} \circ F$, we can then couple the processes $\xi_t^N$ and $\xi_t$ by setting $\xi_t^N = f_N(\xi_t)$ (here we implicitly used the above-mentioned assumptions on $\mu$). Note that for every $N \ge 1$, the function $f_N$ is non-decreasing and the sequence $(f_N)_{N \ge 1}$ converges pointwise to the identity function on $[0, \infty)$. Using (1.3), we can now show that almost surely,

$$ \forall T \ge 0: \limsup_{N \to \infty} \sup_{0 \le t \le T} |\mathcal{R}^N(t) - \mathcal{R}(t)| = 0, \quad \lim_{N \to +\infty} \tau_1^N = \tau_1, \quad \lim_{N \to +\infty} \mathcal{R}^N(\tau_1^N) = \mathcal{R}(\tau_1). $$

This proves the first two claims. The third follows from Proposition 2.1. $\square$

<figure><img src="image_4.png" /></figure>

For the next results, we suppose that $\mu_N$ is a sequence of stairs measures given by

$$ \mu_N([x, \infty)) = -\gamma_N \log(1 - h(c_N x)^{-1}), $$

where $(\gamma_N)_{N \ge 1}$ is a sequence such that $\gamma_N/(2N \log_2 N) \to 1$ as $N \to \infty$. Here, $h$ is the function given in the introduction, in particular, $h(x)$ varies regularly at infinity with index $\alpha > 0$. The sequence $\mu_N$ therefore converges to $\mu_\alpha$.

The following theorem gives the long-time behaviour of the $\mu_N$-stairs process. It will be important for the proof of Theorem 1.2.

**Theorem 2.5.** We distinguish between the following cases:

* $\alpha > 1$: The limits $\rho_N = \lim_{t \to \infty} \mathcal{R}^N(t)/t$ and $\rho_\alpha = \lim_{t \to \infty} \mathcal{R}^\alpha(t)/t$ exist almost surely and in $L^1$. Moreover, $\rho_N \to \rho_\alpha$ as $N \to \infty$.

* $\alpha = 1$, $\mathbb{E}[X] < \infty$: The limit $\rho_N = \lim_{t \to \infty} \mathcal{R}^N(t)/t$ exists almost surely and in $L^1$ and satisfies $\rho_N \sim \int_1^\infty h(c_N)/h(c_N x) dx$, as $N \to \infty$.
• $\alpha = 1$, $\mathbb{E}[X] = \infty$: Set $b_t^N = \int_1^{h^{-1}(t)} h(c_N)/h(c_N x) \, dx$. Then, for every $N$,
$$ \mathcal{R}^N(t)/tb_t^N \to 1, \quad \text{in probability as } t \to \infty. $$

• $0 < \alpha < 1$: Let $W_\alpha$ be a random variable with Laplace transform given by (1.4). Then,

$$ \lim_{N \to \infty} \limsup_{t \to \infty} d \left( \mathcal{L} \left( \frac{c_N}{h(c_N)^{1/\alpha}} \frac{\mathcal{R}^N(t)}{h^{-1}(t)} \right), \mathcal{L}(W_\alpha) \right) = 0 $$

A few remarks on Theorem 2.5: In the case $\alpha > 1$, its proof is almost immediate from Propositions 2.2 and 2.4 and Remark 2.3. Indeed, since $\rho_N = \mathbb{E}[\mathcal{R}^N(\tau_1^N)]/\mathbb{E}[\tau_1^N]$ and $\rho_\alpha = \mathbb{E}[\mathcal{R}^\alpha(\tau_1^\alpha)]/\mathbb{E}[\tau_1^\alpha]$, it remains to show that the sequence of random variables $\mathcal{R}^N(\tau_1^N)$ is uniformly integrable in $N$, which can easily be done through fractional moment estimates using Hölder's inequality and Proposition 2.1. It will also follow directly from Proposition 2.6 below. This proposition yields a precise estimate of the tail of $\mathcal{R}^N(\tau_1^N)$, which is the key to proving Theorem 2.5 in the more delicate case $\alpha \le 1$. Indeed, armed with Proposition 2.6, the theorem directly follows from classic results on random walks applied to $(\mathcal{R}^N(\tau_n^N))_{n \ge 0}$.

We furthermore remark that the uniformity in $N$ in the statement of Proposition 2.6 is only needed in the case $\mathbb{E}[X] < \infty$. In the case $\mathbb{E}[X] = \infty$, estimates not uniform in $N$ would suffice.

**Proposition 2.6.** For every $\varepsilon > 0$, there exists $x_0 = x_0(\varepsilon)$, such that for all $N$,

$$ \sup_{x \ge x_0} \left| \frac{\mathbb{P}(\mathcal{R}^N(\tau_1^N) > x)}{\mathbb{E}[\tau_1^N] \mu_N([x, \infty))} - 1 \right| < \varepsilon. $$

Write $\Delta\mathcal{R}^N(t) = \mathcal{R}^N(t) - \mathcal{R}^N(t-)$ for the jump of $\mathcal{R}^N$ at time $t$. As part of the proof of Proposition 2.6, we will show that if $\mathcal{R}^N(\tau_1^N)$ is large, then it is approximately equal to $\Delta\mathcal{R}^N(\tau_1^N - 1)$. We therefore first prove the following lemma:

**Lemma 2.7.** For every $\varepsilon > 0$, there exists $x_0 = x_0(\varepsilon)$, such that for all $N$,

$$ \sup_{x \ge x_0} \left| \frac{\mathbb{P}(\Delta\mathcal{R}^N(\tau_1^N - 1) > x)}{\mathbb{E}[\tau_1^N] \mu_N([x, \infty))} - 1 \right| < \varepsilon. $$

*Proof.* For better readability, write $\mu = \mu_N$, $\mathcal{R} = \mathcal{R}^N$, $\tau_1 = \tau_1^N$, $\Delta\mathcal{R}(t) = \mathcal{R}(t) - \mathcal{R}(t-)$, $\xi_t = \xi_t^N$. We further set $M_t = \max_{s \in (t-1, t]} \xi_s$ and $M_{t-} = \max_{s \in (t-1, t]} \xi_s$.

Bounding $\mathbb{P}(\Delta\mathcal{R}(\tau_1 - 1) > x)$ from above is easy: Let $\mathcal{P}$ be the Poisson point process used to construct $\mathcal{R}$. We have

$$ \mathbb{P}(\Delta\mathcal{R}(\tau_1 - 1) > x) = \mathbb{E} \left[ \sum_{(t, \xi_t) \in \mathcal{P}} \mathbb{1}_{\tau_1 = t+1, \Delta\mathcal{R}(t) > x} \right] \le \mathbb{E} \left[ \sum_{(t, \xi_t) \in \mathcal{P}} \mathbb{1}_{\tau_1 \ge t, \xi_t > x} \right]. $$

Now, since $\tau_1$ is a stopping time for $\mathcal{R}$, the event $\{\tau_1 \ge t\} = \{\tau_1 < t\}^c$ is measurable w.r.t. the $\sigma$-field generated by $\mathcal{P} \cap \{[0, t) \times \mathbb{R}_+\}$ for every $t \ge 0$. By the projection theorem for Poisson processes [5, Theorem VIII.T3], the previous equation now yields

$$ \mathbb{P}(\Delta\mathcal{R}(\tau_1 - 1) > x) \le (1 - e^{-\mu([x, \infty))}) \int_0^\infty \mathbb{P}(\tau_1 \ge t) \, dt = (1 - e^{-\mu([x, \infty))}) \mathbb{E}[\tau_1], $$
which proves the upper bound of $\mathbb{P}(\Delta\mathcal{R}(\tau_1 - 1) > x)$.

As for the lower bound, we note that for every $t \ge 0$, on the event $\{\Delta\mathcal{R}(t) > 0\}$, we have $\tau_1 \ge t + 1$ iff $\tau_1 \ge t$. This gives for every $\varepsilon > 0$, $x > 0$ and $t \ge 0$,

$$ \{\tau_1 = t+1, \Delta\mathcal{R}(t) > x\} \supset \{\tau_1 \ge t, M_{t+1} \le x, \Delta\mathcal{R}(t) > x\} \\ \supset \{\tau_1 \ge t, M_{t+1} \le x, \xi_t > (1+\varepsilon)x, M_{t-} \le \varepsilon x\}. $$

By the independence properties of the Poisson process and the above-mentioned projection theorem, this gives,

$$ \begin{aligned} \mathbb{P}(\Delta\mathcal{R}(\tau_1 - 1) > x) &\ge \mathbb{E}\left[ \sum_{(t, \xi_t) \in \mathcal{P}} \mathbb{1}_{\tau_1 \ge t, M_{t+1} \le x, \xi_t > (1+\varepsilon)x, M_{t-} \le \varepsilon x} \right] \\ &\ge \mathbb{P}(M_1 \le x)\mathbb{E}\left[ \sum_{(t, \xi_t) \in \mathcal{P}} \mathbb{1}_{\tau_1 \ge t, \xi_t > (1+\varepsilon)x} - \mathbb{1}_{\tau_1 \ge t-1, \xi_t > (1+\varepsilon)x, M_{t-} > \varepsilon x} \right] \\ &= \mathbb{P}(M_1 \le x)(1 - e^{-\mu((1+\varepsilon)x, \infty)})(\mathbb{E}[\tau_1] - (1 + \mathbb{E}[\tau_1])\mathbb{P}(M_1 > \varepsilon x)). \end{aligned} $$

(in the second line, we used the fact that $\tau_1 \ge t$ trivially implies $\tau_1 \ge t - 1$). Now, since $\mu_N$ converges to $\mu_\alpha$, the variables $M_1 = M_1^N$ converge in law as well. Together with the fact that $\mathbb{E}[\tau_1] \ge 1$ by definition, this gives for $x \ge x_0(\varepsilon)$, for every $N$,

$$ \mathbb{P}(\Delta\mathcal{R}^N(\tau_1^N - 1) > x) \ge (1 - \varepsilon)(1 - e^{-\mu_N((1+\varepsilon)x, \infty)}). $$

Now, by the regular variation of $h(x)$, we have for every $N$, for large $x$, $\mu_N((1+\varepsilon)x, \infty)) \ge (1+2\varepsilon)^{-\alpha}\mu_N([x, \infty))$. Since $\varepsilon$ was arbitrary, this proves the lemma. $\square$

*Proof of Proposition 2.6.* For better readability, we use the same notation as in the proof of Lemma 2.7. Note that we trivially have $\mathbb{P}(\Delta\mathcal{R}(\tau_1 - 1) > x) \le \mathbb{P}(\mathcal{R}(\tau_1) > x)$, such that the lower bound on $\mathbb{P}(\mathcal{R}(\tau_1) > x)$ directly follows from Lemma 2.7.

For the upper bound, fix $\varepsilon > 0$. By the definition of the process $\mathcal{R}$, for every $x > 0$, the event $\{\Delta\mathcal{R}(\tau_1 - 1) \le (1 - \varepsilon)x, \mathcal{R}(\tau_1) > x\}$ implies the event $\{\mathcal{R}^-(\tau_1 - 1) > \varepsilon x\}$, such that

$$ \mathbb{P}(\mathcal{R}(\tau_1) > x) \le \mathbb{P}(\Delta\mathcal{R}(\tau_1 - 1) > (1 - \varepsilon)x) + \mathbb{P}(\mathcal{R}^-(\tau_1 - 1) > \varepsilon x). \quad (2.2) $$

In order to bound the second term on the right-hand side, let $C$ be large enough, such that with $L_x = \lceil C \log x \rceil$, we have $\mathbb{P}(\tau_1 > L_x) \le \mu([x, \infty))^2$ for large $x$ and every $N$ (this is possible by Proposition 2.1 and Potter's bounds for regularly varying functions [4, Theorem 1.5.6]). We then have for large $x$, with $\mathcal{R}^-(t) = \mathcal{R}(t-)$,

$$ \mathbb{P}(\mathcal{R}^-(\tau_1 - 1) > x) \le \mu([x, \infty))^2 + \mathbb{P}(\mathcal{R}^-(\tau_1 - 1) > x, \tau_1 \le L_x) \quad (2.3) $$

We furthermore split the second term on the right-hand side of (2.3) into two, according to whether $\max_{t<\tau_1-1} \xi_t > x/2$ or not. Now first note that if $\xi_t > x/2$ for some $t < \tau_1 - 1$, then necessarily $\xi_{t'} > x/4$ for some $t' < \tau_1 - 1$, otherwise $\tau_1 \le t + 1$, which is a contradiction (this is the same reasoning as the one used in the proof of Proposition 2.1). As a consequence, for some numerical constant $c$ we have for large $x$,

$$ \mathbb{P}(\max_{t<\tau_1-1} \xi_t > x/2, \tau_1 \le L_x) \le c(L_x \mu([x, \infty)))^2. \quad (2.4) $$
On the other hand, by (1.3),

$$ \mathbb{P}(\mathcal{R}^{-}(\tau_1 - 1) > x, \max_{t<\tau_1-1} \xi_t \le x/2, \tau_1 < L_x) \le \mathbb{P}(M_1 + \dots + M_{L_x} > x | \forall i: M_i \le x/2), $$

and by the proof of Lemma 3 of [14] (see also the lemma stated on p. 168 of [15]), the last quantity is less than $K_\alpha x^{-3\alpha/2}$ for a constant $K_\alpha$. Together with (2.3) and (2.4) and Potter's bounds [4, Theorem 1.5.6], this gives for large $x$,

$$ \mathbb{P}(\mathcal{R}^{-}(\tau_1 - 1) > x) \le \mu([x, \infty))x^{-\alpha/3}, $$

and the regular variation of $h(x)$ then yields existence of $x_0$ (depending on $\varepsilon$), such that $\mathbb{P}(\mathcal{R}^{-}(\tau_1 - 1) > \varepsilon x) \le \varepsilon\mu([x, \infty))$ for $x \ge x_0$. Together with (2.2) and Lemma 2.7, as well as the regular variation of $h(x)$ and the fact that $\mathbb{E}[\tau_1] \ge 1$ by definition, this finishes the proof. $\square$

**Proof of Theorem 2.5.** Case $\alpha > 1$: Here, $\int_1^\infty x\mu_\alpha(dx) < \infty$ and for every $N$, $\int_1^\infty x\mu_N(dx) < \infty$ by Potter's bounds [4, Theorem 1.5.6]. By Proposition 2.2, the limits $\rho_N = \lim_{t\to\infty} \mathcal{R}^N(t)/t$ and $\rho_\alpha = \lim_{t\to\infty} \mathcal{R}^\alpha(t)/t$ exist almost surely and in $L^1$ and satisfy $\rho_N = \mathbb{E}[\mathcal{R}^N(\tau_1^N)]/\mathbb{E}[\tau_1^N]$ and $\rho_\alpha = \mathbb{E}[\mathcal{R}^\alpha(\tau_1^\alpha)]/\mathbb{E}[\tau_1^\alpha]$. Furthermore, by Propositions 2.1 and 2.4, we have $\mathbb{E}[\tau_1^N] \to \mathbb{E}[\tau_1^\alpha]$ and $\mathcal{R}^N(\tau_1^N)$ converges in law to $\mathcal{R}^\alpha(\tau_1^\alpha)$, as $N \to \infty$. In order to show that $\rho_N \to \rho_\alpha$ as $N \to \infty$, it therefore remains to show that the sequence of random variables $\mathcal{R}^N(\tau_1^N)$ is uniformly integrable in $N$. But this follows from Proposition 2.6 and the fact that the restrictions of the measures $\mu_N$ to $[1, \infty)$ are uniformly integrable in $N$, again by Potter's bounds [4, Theorem 1.5.6]. This finishes the proof of the case $\alpha > 1$.

Case $\alpha = 1$, $\mathbb{E}[X] < \infty$: As in the previous case, the limit $\rho_N = \lim_{t\to\infty} \mathcal{R}^N(t)/t$ exists almost surely and in $L^1$ by Proposition 2.2 and satisfies $\rho_N = \mathbb{E}[\mathcal{R}^N(\tau_1^N)]/\mathbb{E}[\tau_1^N]$. Furthermore, since the measures $\mu_N$ converge to $\mu_1(dx) = x^{-2}dx$ which satisfies $\int_1^\infty x\mu_1(dx) = \infty$, we have $\int_1^\infty x\mu_N(dx) \to \infty$, as $N \to \infty$. Proposition 2.6 now yields as $N \to \infty$ (note that here we need the fact that $x_0$ in the statement of Proposition 2.6 is independent of $N$),

$$ \rho_N \sim \int_1^\infty \mu_N([x, \infty)) dx \sim \int_1^\infty \frac{h(c_N)}{h(c_N x)} dx, $$

which yields the theorem in the case $\alpha = 1$, $\mathbb{E}[X] < \infty$.

Case $\alpha = 1$, $\mathbb{E}[X] = \infty$: For each $N \in \mathbb{N}$, define the random variable $S^N = \mathcal{R}^N(\tau_1^N)/\mathbb{E}[\tau_1^N]$ and set $a_n^N = \inf\{x : \mathbb{P}(S^N > x) > n^{-1}\}$. We introduce the relation $a_n^N \asymp b_n^N$ between two positive double sequences meaning that $\lim_{N\to\infty} \limsup_{n\to\infty} |a_n^N/b_n^N - 1| = 0$. By Proposition 2.6,

$$ a_n^N \asymp (c_N \mathbb{E}[\tau_1^N])^{-1} h^{-1}(\mathbb{E}[\tau_1^N] h(c_N) n) \asymp c_N^{-1} h(c_N) h^{-1}(n), $$

where the last relation follows from the fact that $h^{-1}$ is regularly varying with index 1 [4, Theorem 1.5.12]. Now define $\beta_n^N = \mathbb{E}[S^N 1_{S^N \le a_n^N}]$. By Proposition 2.6, and the “boundary case” of Karamata’s theorem [4, Proposition 1.5.9a], we have

$$ \begin{aligned} \beta_n^N &= \int_0^{a_n^N} \mathbb{P}(S^N > x) dx - a_n^N \mathbb{P}(S^N > a_n^N) \\ &\sim \int_1^{a_n^N} \frac{h(c_N)}{h(c_N x)} dx \sim \int_1^{h^{-1}(n)} \frac{h(c_N)}{h(c_N x)} dx, \quad \text{as } n \to \infty. \end{aligned} $$
Furthermore, again by [4, Proposition 1.5.9a], we have $n\beta_n^N/a_n^N \to \infty$ and $\beta_n^N \sim b_{cn}^N$ for every constant $c > 0$, as $n \to \infty$. Now, if $(S_n^N)_{n \ge 0}$ is a random walk with increments distributed according to $S^N$, then standard results on random walks (see e.g. [16, Theorem 2.7.7], note that $\mathbb{P}(S^N > x)$ is regularly varying for every $N$, by Proposition 2.6) imply that $(S_n^N - n\beta_n^N)/a_n^N$ converges in law to a non-degenerate random variable, as $n \to \infty$. With the above, this implies that $S_n^N/n\beta_n^N \to 1$ in probability, as $n \to \infty$. Together with the fact that $\tau_n^N/n \to \mathbb{E}[\tau_1^N]$ almost surely as $n \to \infty$ and the monotonicity of $\mathcal{R}^N(t)$, this readily yields the theorem in the case $\alpha = 1$, $\mathbb{E}[X] = \infty$.

**Case $\alpha \in (0, 1)$:** This case is similar to the previous one. Let $(S_n^N)_{n \ge 0}$ be a random walk with increments distributed as $\mathcal{R}^N(\tau_1^N)$ and set $a_n^N = \inf\{x : \mathbb{P}(S_1^N > x) > n^{-1}\}$. Again by standard results on random walks (see e.g. [18, Theorem XVII.5.3] or [16, Theorem 2.7.7]), since, by Proposition 2.6, $\mathbb{P}(S^N > x)$ is regularly varying for every $N$, the sequence $S_n^N/a_n^N$ converges in law to $W_\alpha$, as $n \to \infty$, for every $N$. By Proposition 2.6,

$$a_n^N \asymp \frac{h(c_N)^{1/\alpha}}{c_N} h^{-1}(\mathbb{E}[\tau_1^N]n).$$

Together with the fact that $\tau_n^N/n \to \mathbb{E}[\tau_1^N]$ almost surely as $n \to \infty$ and the monotonicity of $\mathcal{R}^N(t)$, this finishes the proof. $\square$

We finish this section with an easy lemma which will be used in the proof of Theorem 1.1.

**Lemma 2.8.** The process $(\mathcal{R}(t))_{t \ge 0}$ is stochastically continuous. Furthermore, the processes $(\mathcal{R}(t))_{t \ge 0}$ and $(\mathcal{R}(t+1))_{t \ge 0}$ almost surely do not have common jumps.

*Proof.* For every $t \ge 0$ and $\delta > 0$, $\mathcal{R}(t+\delta)$ is by definition stochastically dominated by $\mathcal{R}(t) + \mathcal{R}'(\delta)$, for an independent copy $\mathcal{R}'$ of $\mathcal{R}$. This easily yields the first claim. For the second claim, we note that for every stopping time $T$ of the process $(\mathcal{R}(t))_{t \ge 0}$, by the independence properties of the Poisson process, $T+1$ is almost surely not a jump time of $\mathcal{R}$. Fix $\varepsilon > 0$ and define $T_k$ to be the time of the $k$-th jump of size greater than $\varepsilon$. Then $T_k \to \infty$ almost surely as $k \to \infty$ and almost surely, $T_k+1$ is not a jump time of $\mathcal{R}$ for every $k$. Letting $\varepsilon \to 0$ yields the lemma. $\square$

# 3 Coupling the BRW with a discretised stairs process

Recall the definition of $X$, $(X_{n,i})_{n \ge 0, i \in [2N]}$ and $\mathcal{X}(n) = \{\mathcal{X}_1(n) \le \dots \le \mathcal{X}_N(n)\}$ from the introduction and define the rescaled variables $Y := c_N^{-1}X$, $Y_{n,i} := c_N^{-1}X_{n,i}$ and $\mathcal{Y}(n) := c_N^{-1}\mathcal{X}(n)$. For $n \ge 1$, let $\mathcal{F}_n$ be the sigma-algebra generated by the variables $Y_{k,i}$ for $0 \le k \le n-1$, $i \ge 1$ and set $\mathcal{F}_n$ to the trivial $\sigma$-field for all $n \ge 0$. Note that $\mathcal{X}(n)$ and $\mathcal{Y}(n)$ are adapted to the filtration $(\mathcal{F}_n)_{n \ge 0}$. For integers $N, \ell \ge 1$, the $(N, \ell)$-discretised stairs process (DSP) is the process $(R^{N, \ell}(n))_{n \in \mathbb{Z}}$ defined inductively by $R^{N, \ell}(n) = 0$ for all $n \le 0$ and

$$R^{N, \ell}(n+1) = R^{N, \ell}(n) \vee \max_{i=1, \dots, 2N} (R^{N, \ell}(n-\ell) + Y_{n,i}). \quad (3.1)$$

## 3.1 Lower bound

**Proposition 3.1.** Let $\ell_N = \lceil \log_2 N \rceil$. Then $R^{N, \ell_N}(n - \ell_N) \le \mathcal{Y}_1(n)$ and $R^{N, \ell_N}(n) \le \mathcal{Y}_N(n)$ for all $n \ge 0$.
Proof. Writing $R(n) = R^{N, \ell_N}(n)$ for short, define the random time

$$ \tau = \inf\{n \ge 0 : \mathcal{Y}_1(n) < R(n - \ell_N) \text{ or } \mathcal{Y}_N(n) < R(n)\}. $$

We shall prove by contradiction that $\tau$ is infinite almost surely. Assume that $\tau$ is finite for some realisation of the variables $Y_{n,i}$. Set $\mathcal{Y}_i(-n) = 0$ for all $n > 0$. By definition of $\tau$, one has $\mathcal{Y}_1(\tau - 1) \ge R(\tau - 1 - \ell_N)$, so that by definition of $\mathcal{Y}(n)$ and $R(n)$, we then have $\mathcal{Y}_N(\tau) \ge R(\tau)$. We therefore must have $\mathcal{Y}_1(\tau) < R(\tau - \ell_N)$. But now, by the definition of $\tau$, we have $\mathcal{Y}_N(\tau - \ell_N) \ge R(\tau - \ell_N)$. Hence, at time $\tau$, there are no particles below $R(\tau - \ell_N)$, otherwise the particle at position $\mathcal{Y}_N(\tau - \ell_N)$ at time $\tau - \ell_N$ would have $2^{\ell_N} \ge N$ descendants at time $\tau$, all above $R(\tau - \ell_N)$, whence the total number of particles would be larger than $N$, which is a contradiction. Thus, $\mathcal{Y}_1(\tau) \ge R(\tau - \ell_N)$, but this contradicts the definition of $\tau$. $\square$

## 3.2 Upper bound

The main result in this section is Proposition 3.2. One should not be fooled by its apparent simplicity, its proof is more intricate than it looks at first sight (and took us quite some time to come up with). Let $\delta_N$ be a positive sequence which tends to zero as $N \to \infty$ but such that $\delta_N N^\varepsilon \to \infty$ for all $\varepsilon > 0$. Set $m_N = \log_2 N + \log_2 \delta_N$ and assume that $m_N \in \mathbb{N}$ and $m_N \ge 1$ for all $N$. Define the process $(\theta_n)_{n \ge 0}$ by $\theta_0 = 0$ and

$$ \theta_n = \max_{0 \le k \le n} \{\mathcal{Y}_N(k) - R^{N,m_N}(k)\}. $$

**Proposition 3.2.** For all $\varepsilon > 0$, for all large enough $N$ and for all $(1/2) \log_2 N \le m \le 2 \log_2 N$ and $x \ge m^{(1+\alpha^{-1})+\varepsilon}/c_N$, for all $n \ge 0$,

$$ \mathbb{P}(\theta_{n+1} - \theta_n > x | \mathcal{F}_{n-m}) \le Nm2^{m+1}/h(c_Nx)^2. $$

Proof. Let $n \in \mathbb{N}$ and $x > 0$. Set $\mathcal{Y}_i^{(n)}(k) = \mathcal{Y}_i(k) - \theta_n$, $k = 0, 1, \dots$ and note that $\mathcal{Y}_N^{(n)}(k) \le R^{N,m}(k)$ for all $0 \le k \le n$. From the definitions, one checks that the event $\theta_{n+1} - \theta_n > x$ implies that there exists $i \in [N]$ and $j \in \{0, 1\}$, such that on the one hand $Y_{n+1,2i+j} > x$ and on the other hand $\mathcal{Y}_i^{(n)}(n) > x+R^{N,m}(n-m) \ge x+\mathcal{Y}_N^{(n)}(n-m)$, whence $\mathcal{Y}_i(n) > x+\mathcal{Y}_N(n-m)$ (this is best seen by a picture).

If we denote by $M_x(n)$ the number of particles above $x + \mathcal{Y}_N(n-m)$ at time $n$ (i.e. $M_x(n) = \#\{i \in [N] : \mathcal{Y}_i(n) > x + \mathcal{Y}_N(n-m)\}$), then a union bound gives,

$$ \mathbb{P}(\theta_{n+1} - \theta_n > x | \mathcal{F}_{n-m}) \le \mathbb{E}(M_x(n) | \mathcal{F}_{n-m}) \mathbb{P}(Y > x) \le \mathbb{E}[M_x(m)]/h(c_Nx). \quad (3.2) $$

Let $(S_n)_{n \ge 0}$ be a random walk with increments distributed according to $Y$. Bounding $M_x(m)$ by the number of particles above $x$ at time $m$ in $N$ branching random walks without selection, we get

$$ \mathbb{E}[M_x(m)] \le N2^m \mathbb{P}(S_m > x). \quad (3.3) $$

Now, for all $\varepsilon > 0$, for all large enough $N$ and for all $(1/2) \log_2 N \le m \le 2 \log_2 N$ and $x \ge m^{(1+\alpha^{-1})+\varepsilon}/c_N$, we have $\mathbb{P}(S_m > x) \le 2m \mathbb{P}(Y > x)$ (see e.g. [13, Theorem 3.3]). The statement follows. $\square$
**Corollary 3.3.** Let $p \in [0, 2\alpha)$. Then for every $0 < \varepsilon \le (2\alpha - p)/2$, there exists $N_\varepsilon$, such that for $N > N_\varepsilon$ and $n \ge 0$, we have

$$ \mathbb{E}[(\theta_{n+1} - \theta_n)^p | \mathcal{F}_{n-m_N}] \le \left(1 + \frac{4p}{2\alpha - p}\right) \left(\frac{\delta_N}{\log_2 N}\right)^{\frac{p}{2\alpha + \varepsilon}}. $$

*Proof.* Write $\mathbb{E}_n = \mathbb{E}[\cdot | \mathcal{F}_{n-m_N}]$ and set $\delta'_N = \delta_N / \log_2 N$. By Proposition 3.2, we have for every $x > \gamma m_N / c_N$ and every $n \ge 0$:

$$ \mathbb{E}_n[(\theta_{n+1} - \theta_n)^p] \le x + \frac{Nm_N 2^{m_N+1}}{h(c_N)^2} \int_x^\infty \frac{h(c_N)^2}{h(c_N y^{1/p})^2} dy. $$

By definition, we have $2^{m_N} = N\delta_N$ and $h(c_N) \sim 2N \log_2 N$ as $N \to \infty$. By Potter's bounds [4, Theorem 1.5.6], there now exists $x_\varepsilon$, such that for $c_N \ge x_\varepsilon$ and $x^{1/p}c_N \ge x_\varepsilon$, we have

$$ \mathbb{E}_n[(\theta_{n+1} - \theta_n)^p] \le x + \delta'_N I_x, \quad I_x = \int_x^\infty y^{-2\alpha/p} \max(y^{\varepsilon/p}, y^{-\varepsilon/p}) dy. \quad (3.4) $$

By the hypothesis on $\varepsilon$, we have for $x \le 1$: $I_x \le 4(p/(2\alpha - p))x^{1-(2\alpha+\varepsilon)/p}$. Setting now $x = x_N = (\delta'_N)^{p/(2\alpha+\varepsilon)}$ in (3.4) yields the lemma (note that $x_N^{1/p}c_N \ge x_\varepsilon$ and $x_N > m_N^{(1+\alpha^{-1})+\varepsilon}/c_N$ for large $N$, by the hypothesis on $\delta_N$). $\square$

# 4 Coupling the discretised stairs process and the stairs process

Let $N, \ell \in \mathbb{N}$ and define the measure $\mu_{N,\ell}$ on $\mathbb{R}_+$ by

$$ \mu_{N,\ell}([x, \infty)) = -2N\ell \log(1 - h(c_N x)^{-1}). $$

Let $\mathcal{R}^{\mu_{N,\ell}}(t)$ be the $\mu_{N,\ell}$-stairs process as defined in the introduction. Furthermore, let $\mathbb{R}^{N,\ell}(t)$ be the $(N, \ell)$-DSP defined in (3.1).

**Proposition 4.1.** We have $(\mathcal{R}^{\mu_{N,\ell}}(n/\ell))_{n \ge 0} \stackrel{st}{\ge} (R^{N,\ell}(n))_{n \ge 0} \stackrel{st}{\ge} (\mathcal{R}^{\mu_{N,\ell}}(n/(\ell+1)))_{n \ge 0}$, where $(X(n))_{n \ge 0} \stackrel{st}{\ge} (Y(n))_{n \ge 0}$ means that there exists a coupling, such that $X(n) \ge Y(n)$ for all $n \ge 0$.

*Proof.* Let $\xi_t$ be the function used to define the process $\mathcal{R}^{\mu_{N,\ell}}(t)$. By the definition of the measure $\mu_{N,\ell}$, the variables $\max\{\xi_t : t \in [0, 1/\ell]\}$ and $\max\{Y_{1,i} : i \in [2N]\}$ have the same distribution, a fact which is also known as Serfling's coupling after [24] (see also [23]). We can therefore construct the process $\mathbb{R}^{N,\ell}(n)$ using $\xi_t$ by

$$ \mathbb{R}^{N,\ell}(n+1) = \mathbb{R}^{N,\ell}(n) \vee \max_{t \in [0,1/\ell)} (\mathbb{R}^{N,\ell}(n-\ell) + \xi_{(n+1)/\ell-t}). \quad (4.1) $$

In comparison, the processes $\mathcal{R}^{\mu_{N,\ell}}(t)$ and $\mathcal{R}^{\mu_{N,\ell}}(t)$ satisfy by definition

$$ \mathcal{R}^{\mu_{N,\ell}}(\frac{n+1}{\ell}) = \mathcal{R}^{\mu_{N,\ell}}(\frac{n}{\ell}) \vee \max_{t \in [0,1/\ell)} (\mathcal{R}^{\mu_{N,\ell}}(\frac{n+1-\ell}{\ell} - t) + \xi_{(n+1)/\ell-t}). \quad (4.2) $$

$$ \mathcal{R}^{\mu_{N,\ell}}(\frac{n+1}{\ell+1}) = \mathcal{R}^{\mu_{N,\ell}}(\frac{n}{\ell+1}) \vee \max_{t \in [0,1/(\ell+1))} (\mathcal{R}^{\mu_{N,\ell}}(\frac{n-\ell}{\ell+1} - t) + \xi_{(n+1)/(\ell+1)-t}). \quad (4.3) $$
Equations (4.1) and (4.2) and the monotonicity of $\mathcal{R}^{\mu_{N,\ell}}(t)$ now directly yield the first inequal-
ity in the statement of the proposition. As for the second inequality, if we take (4.3) as the
definition of the process $(\mathcal{R}^{\mu_{N,\ell}}(\frac{n}{\ell+1}))_{n\ge 0}$, then exchanging $\xi_{(n+1)/((\ell+1))-t}$ by $\xi_{(n+1)/\ell}-t$ does
not change its law, and we obviously have $\max_{t\in[0,1/((\ell+1))-t} \xi_{(n+1)/\ell}-t \le \max_{t\in[0,1/\ell)} \xi_{(n+1)/\ell}-t$
for every $n$. Together with (4.1) and the monotonicity of $\mathcal{R}^{\mu_{N,\ell}}(t)$, this yields the state-
ment. $\square$

5 Proof of Theorems 1.1 and 1.2

The following lemma will be needed in the proof of Theorem 1.1.

**Lemma 5.1.** We have for every $n_0 \ge 0$ and $\varepsilon > 0$,

$$
\mathbb{P}(\mathcal{Y}_1(n_0 + \lfloor(1-\varepsilon)\log_2 N\rfloor) < \mathcal{Y}_N(n_0) + \varepsilon \mid \mathcal{F}_{n_0}) \to 1, \quad \text{as } N \to \infty.
$$

Proof. Since we can bound the configuration of particles at time $n_0$ from above by moving all
particles to the position of the maximum $\mathcal{Y}_N(n_0)$, it is clearly enough to show the lemma for
$n_0 = 0$. Let $\varepsilon > 0$ and set $\gamma_N = \varepsilon / \log_2 N$. Denote by $J_n$ the number of particles which jump
by at least $\gamma_N$ between times $n$ and $n+1$. Then $\mathbb{E}[J_n] = 2N\mathbb{P}(Y > \gamma_N) = 2Nh(c_N\gamma_N)$, such
that $\mathbb{E}[J_n] \le N^{\varepsilon/2}$ for large $N$, by Potter's bounds [4, Theorem 1.5.6]). Now, if a particle
is at a position strictly greater than $n\gamma_N$ at a time $n$, it must have an ancestor which has
jumped by more than $\gamma_N$ between times $k-1$ and $k$ for some $k \le n$. This ancestor then has
at most $2^{n-k}$ descendants at time $n$. Altogether, this gives for large $N$,

$$
\mathbb{E}[\#\{i : \mathcal{Y}_i(n) > n\gamma_N\}] \le \sum_{k=1}^{n} 2^{n-k} \mathbb{E}[J_k] \le 2^{n+1} N^{\varepsilon/2},
$$

which now implies with $n_N = \lfloor(1 - \varepsilon) \log_2 N\rfloor$, for large $N$,

$$
\mathbb{P}(\mathcal{Y}_1(n_N) \ge \varepsilon) \le \mathbb{P}(\#\{i : \mathcal{Y}_i(n_N) > n_N \gamma_N\} \ge N) \le 2N^{-\varepsilon/2},
$$

by Markov's inequality. This yields the lemma.

Proof of Theorem 1.1. Set $(\mathcal{Y}'_N(t))_{t \ge 0} = (\mathcal{Y}_N(\lfloor t \log_2 N \rfloor))_{t \ge 0}$. We will first show that the finite-dimensional distributions of $(\mathcal{Y}'_N(t), \mathcal{Y}'_1(t))_{t \ge 0}$ converge to those of $(\mathcal{R}^\alpha(t), \mathcal{R}^\alpha(t-1))_{t \ge 0}$. Recall the definitions of $\ell_N$ and $m_N$ from Sections 3.1 and 3.2 and note that $\ell_N \sim m_N \sim \log_2 N$ as $N \to \infty$. For an upper bound, let $p = 1$ if $\alpha \ge 1$ and $p \in (\alpha, \min(1, 2\alpha))$ if $\alpha < 1$. Write $x_+ = \max(x, 0)$ for $x \in \mathbb{R}$. We then have by Corollary 3.3, for every $\varepsilon > 0$ and some $c > 0$, for large $N$,

$$
\forall n \ge 0 : \mathbb{E}[(\mathcal{Y}_N(n) - R^{N,m_N}(n))^p_+] \le \mathbb{E}[\theta_n^p] \le \sum_{k=1}^n \mathbb{E}[(\theta_k - \theta_{k-1})^p] \le cn \left(\frac{\delta_N}{\log_2 N}\right)^{p/(2\alpha+\epsilon)}. \tag{5.1}
$$

Fix $K > 0$. If we choose $\delta_N = o((\log_2 N)^{1-(2\alpha+\epsilon)/p})$, then for all $n \le K \log_2 N$, the right-
hand side in the last inequality tends to zero as $N \to \infty$. Together with Propositions 2.4
and 4.1 as well as Lemmas 2.8 and 5.1, this shows that the finite-dimensional distributions
of $(\mathcal{Y}'_N(t), \mathcal{Y}'_1(t))$ are tight in $N$ and are in the limit as $N \to \infty$ dominated by those of
$(\mathcal{R}^\alpha(t), \mathcal{R}^\alpha(t-1))$.
For a lower bound, note that by Propositions 3.1 and 4.1, we have for every $n \ge 0$,

$$ (\mathcal{Y}_N(n), \mathcal{Y}_1(n)) \stackrel{\text{st}}{\ge} (R^{N, \ell_N}(n), R^{N, \ell_N}(n - \ell_N)) \stackrel{\text{st}}{\ge} (\mathcal{R}^{\mu_N, \ell_N}(\frac{n}{\ell_N+1}), \mathcal{R}^{\mu_N, \ell_N}(\frac{n-\ell_N}{\ell_N+1})), \quad (5.2) $$

with the coordinate-wise order on $\mathbb{R}^2$ (i.e. $(x, y) \le (v, w)$ iff $x \le v$ and $y \le w$). Together with the first part of Proposition 2.4 and Lemma 2.8, this proves that as $N \to \infty$, every limit point of the finite-dimensional distributions of $(\mathcal{Y}'_N(t), \mathcal{Y}'_1(t))_{t \ge 0}$ dominates those of $(\mathcal{R}^\alpha(t), \mathcal{R}^\alpha(t-1))_{t \ge 0}$. Together with the upper bound established above, this proves the convergence.

In order to prove tightness of $(\mathcal{Y}'_N(t))_{t \ge 0}$ in Skorokhod's $J_1$-topology, we will use Aldous' criterion [1, Theorem 1]: Let $T_N$ be a sequence of stopping times for $\mathcal{Y}'_N$. Suppose for simplicity that $T_N$ only takes on values which are multiples of $(\log_2 N)^{-1}$. Let $\varepsilon_N$ be a sequence of positive numbers converging to 0. We then have for every $x > 0$,

$$ \mathbb{P}(\mathcal{Y}'_N(T_N + \varepsilon_N) - \mathcal{Y}'_N(T_N) > x) \le \mathbb{P}(\mathcal{Y}'_N(\varepsilon_N) > x), $$

because we can bound the configuration of particles at time $T_N \log_2 N$ from above by moving all particles to the position of the maximum. The right-hand side of the last inequality now converges to 0 by the convergence in finite-dimensional distributions established above together with the monotonicity of $\mathcal{Y}'_N(t)$ and Lemma 2.8. By Aldous' criterion, this yields tightness in Skorokhod's $J_1$-topology.

As for the convergence of $(\mathcal{Y}'_N(t), \mathcal{Y}'_1(t))_{t \ge 0}$ in the $SM_1$-topology, we note that by Skorokhod's representation theorem for stochastic processes [25, §3.1.2] and the convergence of the finite-dimensional distributions established above, we can transfer the processes $\mathcal{Y}'_N$, $\mathcal{Y}'_1$ and $\mathcal{R}^\alpha$ onto a common probability space, such that almost surely, $(\mathcal{Y}'_N(t), \mathcal{Y}'_1(t)) \to (\mathcal{R}^\alpha(t), \mathcal{R}^\alpha(t-1))$ for every $t \in \mathbb{Q}_+$. The monotonicity of $\mathcal{Y}'_N$ and $\mathcal{Y}'_1$ then implies that almost surely, both $\mathcal{Y}'_N$ and $\mathcal{Y}'_1$ converge w.r.t. the $SM_1$-topology [26, Corollary 12.5.1]. Convergence of the pair now follows from the second part of Lemma 2.8, by [26, Theorem 12.6.1]. $\square$

*Proof of Theorem 1.2.* We first cover the case $\mathbb{E}[X] < \infty$ (which includes the case $\alpha > 1$). The existence of the limit $v_N = \lim_{N \to \infty} \mathcal{X}_N(n)/n = \lim_{N \to \infty} \mathcal{X}_1(n)/n$ is easily proven using subadditivity (see [2, Proposition 2]) with the convergence holding almost surely and in $L^1$. The asymptotic for $v_N$ now easily follows from (5.2) and (5.1), together with Theorem 2.5 and Proposition 4.1. Indeed, (5.2) immediately gives a lower bound on $v_N$ and for the upper bound, we note that with $\delta_N = o(\log N)^{1-2\alpha-\varepsilon}$, the second term on the right-hand side of 5.1, multiplied by $(\log_2 N)/n$, vanishes in the limit as $N$ goes to infinity.

In the case $\mathbb{E}[X] = \infty$, set $\beta_n = nb_n^N$ if $\alpha = 1$ and $\beta_n = h^{-1}(n)$ if $\alpha < 1$ and let $p = 1$ if $\alpha = 1$ and $p \in (\alpha, \min(1, 2\alpha))$ if $\alpha < 1$. Then $n/\beta_n^p \to 0$ as $n \to \infty$, by Potter's bounds [4, Theorem 1.5.6]) and the fact that $h^{-1}(n)$ is regularly varying with index $1/\alpha$ [4, Theorem 1.5.12]. Letting $\delta_N$ be any sequence satisfying the hypotheses of Corollary 3.3, we get for every $N$ and every $\varepsilon > 0$, for some constant $C_N$, by (5.1),

$$ \mathbb{P}(\mathcal{Y}_N(n) - R^{N, m_N}(n) > \varepsilon\beta_n) \le \varepsilon^{-p}\beta_n^{-p}\mathbb{E}[(\mathcal{Y}_N(n) - R^{N, m_N}(n))_+^p] \le C_N\varepsilon^{-p}n/\beta_n^p \to 0, $$

as $n \to \infty$. This, together with Theorem 2.5 and Propositions 3.1 and 4.1, implies the statement about $\mathcal{X}_N(n)$. The statement about $\mathcal{X}_1(n)$ follows from the fact that $\mathcal{X}_N(n - \lfloor \log_2 N \rfloor) \le \mathcal{X}_1(n) \le \mathcal{X}_N(n)$ for all $n$. $\square$
References

[1] David Aldous. Stopping times and tightness. *The Annals of Probability*, 6(2):335–340, November 1978.

[2] Jean Bérard and Jean-Baptiste Gouéré. Brunet-Derrida behavior of branching-selection particle systems on the line. *Communications in Mathematical Physics*, 298(2):323–342, June 2010.

[3] Julien Berestycki, Nathanaël Berestycki, and Jason Schweinsberg. The genealogy of branching Brownian motion with absorption. arXiv:1001.2337, January 2010.

[4] N H Bingham, C M Goldie, and J L Teugels. *Regular variation*, volume 27 of *Encyclopedia of Mathematics and its Applications*. Cambridge University Press, Cambridge, 1987.

[5] Pierre Brémaud. *Point processes and queues: martingale dynamics*. Springer-Verlag, New York, 1981.

[6] Éric Brunet and Bernard Derrida. Shift in the velocity of a front due to a cutoff. *Physical Review E*, 56(3):2597–2604, September 1997.

[7] Éric Brunet and Bernard Derrida. Microscopic models of traveling wave equations. *Computer Physics Communications*, 121-122:376–381, September 1999.

[8] Éric Brunet and Bernard Derrida. Effect of microscopic noise on front propagation. *Journal of Statistical Physics*, 103(1):269–282, 2001.

[9] Éric Brunet, Bernard Derrida, A. Mueller, and S. Munier. Phenomenological theory giving the full statistics of the position of fluctuating pulled fronts. *Physical Review E*, 73(5):056126, May 2006.

[10] Éric Brunet, Bernard Derrida, A. H. Mueller, and S. Munier. Noisy traveling waves: Effect of selection on genealogies. *Europhysics Letters (EPL)*, 76(1):1–7, October 2006.

[11] John Bunge and Charles M. Goldie. Record sequences and their applications. In D.N. Shanbhag and C.R. Rao, editor, *Stochastic Processes: Theory and Methods*, volume 19 of *Handbook of Statistics*, volume 19, pages 277–308. Elsevier, 2001.

[12] Xavier Cabré and Jean-Michel Roquejoffre. The Influence of Fractional Diffusion in Fisher-KPP Equations. *Communications in Mathematical Physics*, 320(3):679–722, June 2013.

[13] Darren B. H. Cline and Tailen Hsing. Large deviation probabilities for sums of random variables with heavy or subexponential tails. Technical report, Statistics Department, Texas A&M University, available online at http://www.stat.tamu.edu/~dcline/Papers/large5.pdf, 1998.

[14] Richard Durrett. Maxima of branching random walks vs. independent random walks. *Stochastic Processes and their Applications*, 9(2):117–135, November 1979.

[15] Richard Durrett. Maxima of branching random walks. *Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete*, 62(2):165–170, June 1983.
[16] Richard Durrett. *Probability: theory and examples*. Wadsworth Publishing Company, Belmont, California, second edition, 1995.

[17] Rick Durrett and Daniel Remenik. Brunet-Derrida particle systems, free boundary problems and Wiener-Hopf equations. *The Annals of Probability*, 39(6):2043-2078, November 2011.

[18] William Feller. *An introduction to probability theory and its applications. Vol II*. John Wiley & Sons Inc., New York, second edition, 1971.

[19] R. A. Fisher. The wave of advance of advantageous genes. *Annals of Eugenics*, 7(4):355-369, June 1937.

[20] Nina Gantert. The maximum of a branching random walk with semiexponential increments. *The Annals of Probability*, 28(3):1219-1229, June 2000.

[21] Andrei N Kolmogorov, I.G. Petrovskii, and N.S. Piskunov. Étude de l'équation de la diffusion avec croissance de la quantite de matière et son application à un problème biologique. *Bulletin de l'Université d'État à Moscou : Série internationale. Section A, Mathématiques et mécanique*, 1(6):1-25, 1937.

[22] Pascal Maillard. Speed and fluctuations of $N$-particle branching Brownian motion with spatial selection. *arXiv:1304.0562*, April 2013.

[23] D. Pfeifer. Coupling methods in connection with Poisson process approximation. *Zeitschrift für Operations Research*, 29(5):217-223, November 1985.

[24] R. J. Serfling. Some elementary results on Poisson approximation in a sequence of Bernoulli trials. *SIAM Review*, 20(3):567-579, July 1978.

[25] A. V. Skorokhod. Limit theorems for stochastic processes. *Theory of Probability and its Applications*, 1(3):261-290, January 1956.

[26] Ward Whitt. *Stochastic-process limits*. Springer Series in Operations Research. Springer-Verlag, New York, 2002.