# Last passage percolation and limit theorems in Barak-Erdős directed random graphs and related models

SERGEY FOSS

TAKIS KONSTANTOPOULOS

BASTIEN MALLEIN

SANJAY RAMASSAMY

17 July 2024

## Abstract

We consider directed random graphs, the prototype of which being the Barak-Erdős graph $\vec{G}(\mathbb{Z}, p)$, and study the way that long (or heavy, if weights are present) paths grow. This is done by relating the graphs to certain particle systems that we call Infinite Bin Models (IBM). A number of limit theorems are shown. The goal of this paper is to present results along with techniques that have been used in this area. In the case of $\vec{G}(\mathbb{Z}, p)$ the last passage percolation constant $C(p)$ is studied in great detail. It is shown that $C(p)$ is analytic for $p > 0$, has an interesting asymptotic expansion at $p = 1$ and that $C(p)/p$ converges to $e$ like $1/(\log p)^2$ as $p \to 0$. The paper includes the study of IBMs as models on their own as well as their connections to stochastic models of branching processes in continuous or discrete time with selection. Several proofs herein are new or simplified versions of published ones. Regenerative techniques are used where possible, exhibiting random sets of vertices over which the graphs regenerate. When edges have random weights we show how the last passage percolation constants behave and when central limit theorems exist. When the underlying vertex set is partially ordered, new phenomena occur, e.g., there are relations with last passage Brownian percolation. We also look at weights that may possibly take negative values and study in detail some special cases that require combinatorial/graph theoretic techniques that exhibit some interesting non-differentiability properties of the last passage percolation constant. We also explain how to approach the problem of estimation of last passage percolation constants by means of perfect simulation.

## Contents

1 Introduction 2

2 From the Barak-Erdős graph to the infinite bin model 6

2.1 Ergodic arguments 6

2.2 The infinite bin model corresponding to the Barak-Erdős graph. 10

3 The general infinite bin model 11

3.1 Definition and first properties of the infinite bin model 11

3.2 The speed of the general infinite bin model 14

3.3 Coupling words 18

3.4 Construction of a stationary version and coupling 20

3.5 New expressions for the speed 22

4 Analytic properties of the asymptotic length of the longest path 25

4.1 First formulas for $C$ 25

4.2 Analyticity of $C$ 26

4.3 Power series expansion of $C(p)$ around $p = 1$ 27
<table><thead><tr><th></th><th></th><th></th></tr></thead><tbody><tr><td>5</td><td>Longest path of the Barak-Erdős graph in the sparse regime</td><td>30</td></tr><tr><td>5.1</td><td>Heuristics on the sparse limit</td><td>31</td></tr><tr><td>5.2</td><td>The PWIT and some of its properties</td><td>31</td></tr><tr><td>5.3</td><td>Coupling of the PWIT and the Barak-Erdős graph</td><td>35</td></tr><tr><td>5.4</td><td>Longest chain issued from the initial vertex</td><td>39</td></tr><tr><td>5.5</td><td>Extension to stochastic ordered graphs with geometry</td><td>42</td></tr><tr><td>5.6</td><td>Longest path in the Barak-Erdős graph</td><td>43</td></tr><tr><td>5.7</td><td>Shortest path</td><td>45</td></tr><tr><td>6</td><td>Regenerative properties of directed random graphs</td><td>45</td></tr><tr><td>6.1</td><td>Breaking the graph into independent cycles</td><td>46</td></tr><tr><td>6.2</td><td>Moments of auxiliary stopping times</td><td>47</td></tr><tr><td>6.3</td><td>Moments of skeleton points and a central limit theorem</td><td>49</td></tr><tr><td>7</td><td>Directed random graphs on partially ordered sets</td><td>52</td></tr><tr><td>7.1</td><td>Brownian last passage percolation</td><td>52</td></tr><tr><td>7.2</td><td>Generalization to partially ordered vertex sets and distance-dependent probabilities</td><td>53</td></tr><tr><td>7.3</td><td>Convergence to the Tracy-Widom distribution</td><td>54</td></tr><tr><td>8</td><td>Weighted Barak-Erdős graphs</td><td>56</td></tr><tr><td>8.1</td><td>Finite variance weights</td><td>56</td></tr><tr><td>8.2</td><td>Infinite variance weights</td><td>58</td></tr><tr><td>9</td><td>Analytic properties of charged graphs</td><td>59</td></tr><tr><td>9.1</td><td>The two-weights model</td><td>60</td></tr><tr><td>9.2</td><td>Further structure of inter-skeleton pieces</td><td>61</td></tr><tr><td>9.3</td><td>Criticality and nondifferentiability</td><td>62</td></tr><tr><td>9.4</td><td>Y ⊂ X<sub>crit</sub></td><td>63</td></tr><tr><td>9.5</td><td>X<sub>crit</sub> ⊂ Y</td><td>64</td></tr><tr><td>10</td><td>Perfect simulation aspects of charged graphs</td><td>65</td></tr><tr><td>10.1</td><td>The Max Growth System (MGS)</td><td>66</td></tr><tr><td>10.2</td><td>The MGS of a random charged graph, coupling and stationarity</td><td>68</td></tr><tr><td>10.3</td><td>Perfect simulation</td><td>70</td></tr><tr><td>11</td><td>Additional remarks and open problems</td><td>73</td></tr></tbody></table>

# 1 Introduction

The well-known Erdős-Rényi graph [18] admits a loopless directed version where an edge is oriented according to an a priori order on the set of vertices (see Figure 1). We call this a Barak-Erdős graph due to the 1984 paper [10] by Amnon Barak and Paul Erdős that studied the size of the maximal subset of vertices with the property that no two of them are connected by a directed path and showed that it grows like the square root of the number of vertices of the graph. One of the most well-studied questions regarding of the Barak-Erdős graph and related models is the maximum path length or the maximum path weight if edges and vertices are given random weights. As such, the question is closely related to last passage percolation (LPP) problems appearing in statistical physics dealing with maximum weight paths in random environments.
Motivations for such a quantity come from performance evaluation of computer systems [53, 60], from biology [87, 30, 29] and from physics [61, 62]. In the latter field, especially in mathematical ecology, one is interested in the survival of a species based on information of food chains. The graphs we study are also models of food chains. In computer networking applications, the maximum time for an information packet to reach a destination can also be approached by random directed graphs. Likewise, the growth of a network can also be modeled via directed random graphs. What is interesting is the connections of the Barak-Erdős graph with models in random geometry, in the theory of random matrices (originating from the study of Schrödinger’s equation in a very complex “random” potential), and in statistical physics. The class of models exhibiting convergence to Tracy-Widom distribution is growing and, in this paper, we point out yet another one that falls in this category. Therefore, we believe that the reader interested in theoretical or applied research will find something of interest in this paper. We strive to explain some connections, as above, but also present concrete results with full proofs in most cases.

<figure><img src="image_1.png" /><figcaption>Figure 1: Realisation of a Barak-Erdős graph with seven edges. For every pair $i < j$, a directed edge from $i$ to $j$ is present with probability $p$, independently from the presence of every other edge. The main objective of this survey is to describe the asymptotic properties of the longest path in this graph (here marked in red).</figcaption></figure>

This paper offers a survey of results on the Barak-Erdős graph and related models. Starting from a relatively simple static model, we will see how it relates to discrete and continuous time particle systems and Markov processes and, in particular, to the Infinite Bin Model (introduced in [44]) that has also appeared in several papers, often in disguise [4], and often arising as a byproduct of other random models. We shall also explore connections with branching processes and random walks. In particular, we will see the emergence of a continuous time branching random walk that is often known as a Poisson-weighted infinite random tree [5] or Poisson cascade model [62] in the statistical physics literature. The growth of the longest path will be explained and various analytical properties of it will be studied. In particular, we will see how the rate of convergence relates to questions around the F-KPP equation [24].

We will deal with several stochastic models and notation will be introduced little by little. For now, given an ordered (or partially ordered) set $V$, let us define $\vec{G}(V, p)$ to be a random graph on a set of vertices $V$ such that each edge $(i, j)$, where $i$ is smaller than $j$ in the order of $V$, exists with probability $p$, independently from edge to edge. Having said that, we shall have the occasion to make $p$ depend on the edge and we shall discuss situations where independence is replaced by invariance under translations.

The paper offers a survey of results aiming at exposing the main ideas. We often (but not always) give proofs, sometimes sketches of them. Our aim is not to provide an exhaustive bibliographical survey but rather an exposition of results, ideas, and main proof techniques, sometimes compromising with a simpler than a more general model.

The first part of Section 2 deals with a random directed graph on $\mathbb{Z}$ where the edge probabilities are not even independent but, rather, stationary and ergodic, in some sense. The aim is to show right from the start that the maximum length of all paths from 1 to $n$ satisfies a law of large numbers (LLN), that is, it has a deterministic linear growth rate, denoted by the letter $C$, and referred to as the last passage percolation constant; this is due to a subadditive ergodic theorem. Throwing in some independence assumptions (but still remaining at a level more general than that of $\vec{G}(\mathbb{Z}, p)$) shows that a regenerative structure can be obtained: the random graph can be split into independent pieces that occur at a computable rate. The set of the end-vertices of these pieces is called skeleton of the graph. For $\vec{G}(\mathbb{Z}, p)$, the rate $\lambda(p)$ of the skeleton (plotted in Figure 2) equals $\varphi(1-p)^2$, where $\varphi(x) = (1-x)(1-x^2)\dots$, a well-known function that bears Euler’s name and has a wealth of combinatorial and number-theoretic interpretations.
The second part of Section 2 explains how to grow $\vec{G}(\mathbb{Z}, p)$ little by little. If we let $\vec{G}_n$ be $\vec{G}(\{1, \dots, n\}, p)$ then the sequence $(\vec{G}_n)$ is mapped into a Markovian particle system $(X_n)$, where $X_n$ can be thought of as a configuration of particles on $\mathbb{Z}$ (a balls-in-bins model) that we call Infinite Bin Model (IBM). This was introduced in [44] where it was shown that it converges in distribution to a stationary state, say $X_\infty$, a particle configuration supported on the whole of $\mathbb{Z}$. Paper [44] was mostly concerned with an extension of Borovkov's theory of renovating events [19, 20, 22, 43]. This approach enabled facilitate good explicit bounds for $C = C(p)$, the LPP constant for $\vec{G}(\mathbb{Z}, p)$.

Rather than repeating the arguments of [44] we use the IBM derived from $\vec{G}(\mathbb{Z}, p)$ as a motivation for the more general IBM($\mu$) that is introduced in Section 3: particles are placed on integers so that there is always a front, that is, a largest bin after which there are no particles. A particle is selected according to the distribution $\mu$ and the configuration changes by placing a daughter particle one position to its right. This simple particle system and was introduced and studied in detail in [79, 80]. The techniques and results of these papers are exposed in Sections 3, 4 and 5. A particular instance of the general IBM was considered by Aldous and Pitman [4]. The IBM($\mu$) travels to the right at asymptotic speed $v_\mu$ and this is shown in Section 3. If $\mu$ is geometric random variable with parameter $p$ then $v_\mu = C(p)$. The view of the IBM in this part of the survey is that of a symbolic dynamical system. Successive draws of integers from $\mu$ are viewed as words from the alphabet of positive integers. Such words can be "k-coupling" in that the content of the k rightmost bins forgets the initial configuration. These are used to show, by coupling, the existence of a stationary version of the IBM($\mu$). By delving into the structure of specific sets of words, new expressions for $v_\mu$ can be obtained. Specializing to the $\mu$=geometric($p$) case, Section 4 uses these expressions to obtain sharp upper and lower bounds for $C(p)$, which are sequences rational functions that converge to $C(p)$ uniformly over $\varepsilon \le p \le 1$ for all $\varepsilon > 0$. Moreover, it is shown that $C(p)$ is analytic away from $p=0$ and its power series expansion at $p=1$ has integer coefficients that admit some combinatorial interpretation.

We then examine the behavior of $C(p)$ in a neighborhood of 0. One one hand, we have that $C(p)/p \to e$, as $p \to 0$, that is $C'(0) = e$. On the other hand, $C''(0)$ does not exist. In fact, the convergence of $C(p)/p$ to $e$ is very slow. It was shown in [79] that $C(p)/p = e - \frac{1}{2}\pi^2 e (\log p)^{-2}(1+o(1))$, as $p \to 0$. This is explained in Section 5 using somewhat different proofs. We refer to this as "Brunet-Derrida behavior" as this slow convergence phenomenon appeared in the physics literature [24] in the following form. Consider the classical F-KPP partial differential equation [42, 67] arising in the modeling of reaction-diffusion systems. This has a traveling wave solution with asymptotically constant speed $v_\infty$, say. An $N$-particle stochastic approximation to it is described by a certain model that moves with constant speed $v_N$, say. It was first observed in [24] that $v_N \approx v_\infty - c(\log N)^{-2}$, and this was later proved rigorously in [12]. The similarity of the two results is not fortuitous. Indeed, the IBM is compared to a branching random walk with selection, that is, by killing particles. Results for the speed and rate of convergence were obtained in [78] and these can be used to establish the rate of convergence of $C(p)/p \to e$. We use the so-called Poisson-weighted infinite tree (PWIT) of Aldous and Steele [5] which, if interpreted time-wise, is a Markovian branching process of immortal particles that reproduce in continuous time. We then produce a novel embedding of the IBM in the PWIT (or, rather, a coupling between the two) which is used to obtain the rate of convergence. In the last part of Section 5 we also take a first look at LPP on random graphs with geometry and present, in passing, some results on shortest paths as well for $\vec{G}(\{1, \dots, n\}, p_n)$. We also note that [86] proved among other results, using branching processes, that if $L_n$ is the maximum length of all paths in $\vec{G}(\{1, \dots, n\}, p_n)$ with $p_n \to 0$ and $np_n \to \infty$, then $L_n/np_n \to e$, as $n \to \infty$, in probability.

In Section 6 we move on to graphs $\vec{G}(\mathbb{Z}, p_k)$ where the probability that an edge between $i$ and $i+k$ exists equals $p_k$, $k \in \mathbb{N}$. We take a closer look at the skeleton $\mathcal{S}$ and the regeneration properties, exhibiting a construction of elements of $\mathcal{S}$ that allows us to study moment properties. In particular, we show that the distance between successive points has a $p$-th moment if and only if $\sum_{k=1}^\infty k^p Q_k < \infty$, where $Q_k = (1-p_1)\cdots(1-p_k)$. We thus obtain necessary and sufficient conditions for a central limit theorem for the quantity $L_n$ in terms of the $p_k$. In particular, a CLT always holds when the $p_k$ are identical. The results of 6 have been obtained in [39].

Disclaimer: the term CLT (Central Limit Theorem) in this article will refer to a limit obtained
by considering deviations from an average behavior of a random sequence, regardless of whether
the limit is Gaussian or not.

In Section 7 we consider the graph $\vec{G}(\mathbb{Z} \times I, p)$, where $I$ is a partially ordered set, say a finite set $I = \{1, \dots, M\}$. Then order $\mathbb{Z} \times I$ in component-wise fashion and place an edge directed from $(u, i)$ to $(v, j)$ with probability $p$ if $(u, i)$ is below $(v, j)$. More general conditions are studied in [39]. We show, in particular, that if $L_n$ is the maximum of all paths in $[1, n] \times I$ then a CLT holds but the limit is not Gaussian if $I$ has at least 2 points. A functional central limit theorem for the sequence $(L_{[nt]}, t \ge 0)$ of processes establishes convergence to the Brownian LPP process whose marginal has a distribution proportional to the largest eigenvalue of a random $M \times M$ GUE matrix. When $M = \infty$, we have, in particular, the graph $\vec{G}(\mathbb{Z} \times \mathbb{Z}, p)$. It was shown in [72] that a certain scaling of $L_{[nt]}$ yields convergence, in distribution to the Tracy-Widom law $F_2$. The proofs here are technical and we only outline the results and refer the reader to [72] for details. We point out that in the finite $I$ case there is a way to obtain a skeleton for the graph (by taking the intersection of $|I|$ skeleton sets), whereas in the infinite $I$ case this is not possible.

Section 8 takes a look at a version of the Barak-Erdős graph when random weights are introduced. The material is taken from [49] and [45]. Even though negative weights on both edges and vertices can be allowed, we focus only in the positive weights case in order to make ideas clear. We measure the weight of a path by the sum of the weights of its edges (and, if vertices have weights too, we add those weights as well; see [45]). If $u$ is a random variable representing an edge weight, then we show that $Eu^2$ is required for the law of large numbers, that is, the convergence of $W_n/n$, where $W_n$ is the maximum weight of all paths from 1 to $n$, to a constant $C = C(F)$ that depends on the distribution $F$ of $u$. For the CLT, we need $Eu^3 < \infty$. When $Eu^2 = \infty$ some new phenomena occur because $W_n$ grows faster than linearly. When we put the graph on $(1/n)\mathbb{Z}$ we show convergence to a certain random graph whose vertices are constructed by means of i.i.d. uniform random variables.

When weights are introduced one can ask the question of the behavior of $C(F)$. Deep properties of it have been investigated when $F = \delta_p + (1-p)\delta_{-\infty}$. (the case of the standard Barak-Erdős graph) and exposed in earlier sections. Continuity of $C(F)$ for a large set of distributions $F$ has been investigated in a recent paper by Terlat [94]. In this section we focus exclusively on very simple weight distributions with 2 atoms: $F = p\delta_1 + (1-p)\delta_x$. That is, every pair $(i,j)$, with $i < j$, of integers is given a weight that has distribution $F$, independently. What can we say about $C(p,x) \equiv C(p\delta_1 + (1-p)\delta_x)$ as a function of $x$? We refer to this graph as “random charged graph” because we allow $x$ to be negative (and hence a charge rather than weight). We still want to maximize total charge. Paths with negative charge exist, however, $C(p,x) > 0$. The results in this section have been obtained in [47] and show some interesting behavior: whereas $C(p,x)$ is a convex increasing function of $x$, it is not everywhere differentiable. A number of combinatorial arguments allow us to establish that $C(p,x)$ is nondifferentiable if and only if $x$ is a negative rational or equal to $n$ or $1/n$ for some positive integer $n \ge 2$. Due to lack of space, the section only offers an outline of the results.

In Section 10 we ask how to obtain more information about $C(F)$ experimentally, that is, by simulation. When $F = \delta_p + (1-p)\delta_{-\infty}$ (the standard Barak-Erdős graph) we can employ Markovian methods (MCMC). But we want to do better and devise a perfect simulation method, that is, a way to perfectly (and not approximately) simulate a random variable whose expectation is $C(F)$. To deal with the general $F$ case, we first assume that that $F$ is supported on a semi-infinite interval $(-\infty, 1]$, say, such that it places positive mass to any left neighborhood of 1. Using this assumption, we generalize the IBM particle system to something that we call Max Growth System (MGS) that is a Markovian process in a space of point measures (configurations of particles) on the real line. We then construct renovation events, use them to construct a stationary process, and then extract a random variable that can be perfectly simulated and which has expectation $C(F)$. Based on this, we offer a method for experimenting with various weight distributions. We only ran simulations in a simple case, and even present the algorithm for it.

We conclude the paper by an overview and some open problems.
## 2 From the Barak-Erdős graph to the infinite bin model

Consider a loopless directed graph $\vec{G}$ on the set $\mathbb{Z}$ of integers whose edges are oriented in a way compatible with the ordering of the integers: if $\{i, j\}$ is an edge then it is oriented from $\min(i, j)$ to $\max(i, j)$. Fix two integers $i, j$ such that $j - i = n > 0$. There are four maximal quantities of interest:

$$ 
\begin{align} 
L_{i,j}^{\mathrm{L,R}} &:= \text{the maximal length of all paths from } i \text{ to } j; \tag{2.1} \\ 
L_{i,j}^{\mathrm{L}} &:= \text{the maximal length of all paths from } i \text{ to some } j' \le j; \notag \\ 
L_{i,j}^{\mathrm{R}} &:= \text{the maximal length of all paths from some } i' \ge i \text{ to } j; \notag \\ 
L_{i,j} &:= \text{the maximal length of all paths from some } i' \ge i \text{ to some } j' \le j. \notag 
\end{align} 
$$

(Superscripts L, R indicate left-tied, right-tied paths, respectively.) Clearly, the first quantity is the smallest and the last the largest, while the other two are in-between.

### 2.1 Ergodic arguments

If $\vec{G}$ is the Barak-Erdős graph $\vec{G}(\mathbb{Z}, p)$, it will be seen that all these quantities satisfy the same strong law of large numbers (SLLN). But it is easier to see that the largest of these quantities satisfies a SLLN, as a consequence of Kingman's subadditive ergodic theorem [65]. This has nothing to do with independence per se and this becomes more general in the context of the following lemma. Instead of insisting that the edge-defining random variables are i.i.d. we merely assume stationarity and ergodicity. In what follows, we shall consider a collection $\alpha$ of random variables $\alpha_{i,j}$, indexed by pairs $(i, j)$ of integers with $i < j$, and taking values in $\{1, -\infty\}$. We shall then speak of the random graph $\vec{G}(\mathbb{Z}, \alpha)$ with whose set edges is

$$ \{(i, j) : i < j, \alpha_{i,j} = 1\}. \tag{2.2} $$

Choosing $-\infty$ rather than 0 is convenient because if we take any sequence $i_0 < i_1 < \dots < i_\ell$ of integers, for some $\ell \in \mathbb{N}$, then the quantity $(\alpha_{i_0, i_1} + \alpha_{i_1, i_2} + \dots + \alpha_{i_{\ell-1}, i_\ell})^+$ takes values 0 or $\ell$; it takes value $\ell$ if and only if $(i_0, i_1, \dots, i_\ell)$ forms a path in $\vec{G}(\mathbb{Z}, \alpha)$. Using this trick, we can easily express the maximal lengths (2.1) as maxima of these quantities over deterministic increasing sequences of integers. For example, $L_{1,3}^{\mathrm{L,R}} = \max\{\alpha_{1,3}, (\alpha_{1,2} + \alpha_{2,3})^+\}$. By saying that a probability measure $\mathbb{P}$ is defined on the canonical space $\Omega$ we mean that $\mathbb{P}$ is defined on the set $\Omega$ consisting of all collections $\alpha = (\alpha_{i,k})_{i,k \in \mathbb{Z}}$.

**Lemma 2.1.** Let $\alpha = (\alpha_{i,j}, i < j, i, j \in \mathbb{Z})$, be a collection of random variables with values in $\{1, -\infty\}$ with distribution $\mathbb{P}$ on its canonical space $\Omega$. Define $\theta: \Omega \to \Omega$ by

$$ (\theta\alpha)_{i,j} = \alpha_{i+1,j+1}. \tag{2.3} $$

Assume that $(\theta, \mathbb{P})$ is stationary and ergodic. Let

$$ L_{i,j} := \max_{\substack{i \le i_0 < i_1 < \dots < i_\ell \le j \\ \ell \in \mathbb{N}}} (\alpha_{i_0, i_1} + \alpha_{i_1, i_2} + \dots + \alpha_{i_{\ell-1}, i_\ell})^+. $$

Then there is a deterministic $C$ such that

$$ C = \lim_{n \to \infty} L_{0,n}/n \quad \text{as } n \to \infty \text{ P-a.s. and in } L^1, \quad C = \inf_n \mathbb{E}L_{0,n}/n. $$

*Proof.* Noticing that $L_{i,j}$ is the maximum length of all paths in $\vec{G}(\mathbb{Z}, \alpha)$ with endpoints between $i$ and $j$ (consistent with the last of (2.1)) we have

$$ L_{i,k} \le L_{i,j} + L_{j,k} + 1, \quad i < j < k, $$

<footnote n="1">¹Note that $\theta$ is a bijection from $\Omega$ onto itself with both $\theta$ and $\theta^{-1}$ measurable when $\Omega$ is given its natural product $\sigma$-algebra. Let $\theta^0$ be the identity. Then $\theta^n$, $n \in \mathbb{Z}$, is a group. We say that $(\theta, \mathbb{P})$ is stationary if $\mathbb{P}(\theta A) = \mathbb{P}(A)$ for all measurable $A$. In this case, we say that it is ergodic if every set $A$ such that $\theta A = A$ a.s., actually has $\mathbb{P}(A)$ equal to 0 or 1.</footnote>
for if we consider a maximum length path between two vertices on $[i, k]$ then its length is at most the length of its restriction on $[i, j]$ plus the length of its restriction on $[j, k]$ plus 1 if $j$ is not a vertex of the maximum length path. The stationarity and ergodicity of $(\theta, \mathbb{P})$ together with the last inequality shows that the $L_{i,j} + 1$ satisfy the assumptions of Kingman's subadditive ergodic theorem [65] and so $\lim_{n \to \infty} L_{i,i+n}/n$ exists P-a.s. and in $L^1$ and equals $C = \inf_n \mathbb{E}L_{0,n}/n$. $\square$

**Remark 2.2.** It will turn out that all four quantities in (2.1) have the same growth rate as the largest of them. This is not entirely obvious at this moment because, for example, attempting to establish that $\lim_{n \to \infty} L_{0,n}^{L,R}/n$ exists a.s., one might be tempted to use the obvious superadditivity

$$L_{i,k}^{L,R} \geq L_{i,j}^{L,R} + L_{j,k}^{L,R},$$

But, according to the extension of the subadditive ergodic theorem of Liggett, see [73, Theorem 2.6] this would require that $\mathbb{E}L_{i,j}^{-} < \infty$ which is false here. The fact that $C^{L,R} = C^{L} = C^{R} = C$ is discussed below; see Corollary 2.8.

Returning to the graph $\vec{G}(\mathbb{Z}, \alpha)$, whose edge set is as in (2.2), let us define

$$i \rightsquigarrow j \iff \text{there is a path in } \vec{G}(\mathbb{Z}, \alpha) \text{ from } i \text{ to } j$$

and identify a certain random subset of $\mathbb{Z}$, that we shall refer to as the skeleton of the graph, as follows. For each $j \in \mathbb{Z}$ let

$$A_j = \{\alpha \in \Omega : \text{ for all } i \in \mathbb{Z} \text{ there is a path in } \vec{G}(\mathbb{Z}, \alpha) \text{ from } \min(i, j) \text{ to } \max(i, j)\}. \quad (2.4)$$

The skeleton $\mathcal{S}$ is the random set of all $j$ such that $A_j$ occurs:

$$\mathcal{S} = \mathcal{S}(\alpha) = \{j \in \mathbb{Z} : \alpha \in A_j\}. \quad (2.5)$$

The elements of $\mathcal{S}$ are called skeleton points or skeleton vertices of the graph $\vec{G}(\mathbb{Z}, \alpha)$. Notice that $\theta A_j = A_{j+1}$ for all $j \in \mathbb{Z}$. Hence, if $(\theta, \mathbb{P})$ is stationary we have $\mathbb{P}(A_0) = \mathbb{P}(A_n)$ for all $n \in \mathbb{Z}$ and the random sets $\mathcal{S} \circ \theta^n$ have all the same law.

**Definition 2.3 (rate of skeleton).** Assume that $(\theta, \mathbb{P})$ is stationary. Then the quantity

$$\lambda := \mathbb{P}(A_0) \quad (2.6)$$

is referred to as the *rate* or *density* of the skeleton $\mathcal{S}$.

**Lemma 2.4.** Assume that $(\theta, \mathbb{P})$ is stationary and ergodic. Then $\mathcal{S}^+ := \mathcal{S} \cap [0, \infty)$ and $\mathcal{S}^- := \mathcal{S} \cap (-\infty, 0]$ are both infinite sets P-a.s. if and only if $\lambda > 0$. Moreover, conditional on $A_0$, the expected distance between two successive elements of $\mathcal{S}$ is $1/\lambda$.

*Sketch of proof.* The first claim is due to the Poincaré recurrence theorem [26]. The second claim is from basic properties of stationary point processes. $\square$

**Remark 2.5.** If $\mathcal{S}^+$ and $\mathcal{S}^-$ are both infinite then any two far apart vertices $i$ and $j$ will contain a skeleton point between them. This implies that there is at least one path from $i$ to $j$ (and this path passes through the skeleton point).

The following is taken from [39].

**Lemma 2.6.** Consider $\vec{G}(\mathbb{Z}, \alpha)$ and assume that $\alpha_{i,j}, i < j, i, j \in \mathbb{Z}$, are all independent with

$$\mathbb{P}(\alpha_{i,j} = 1) = p_{j-i},$$

where $p_n, n \in \mathbb{N}$, is a sequence of probabilities such that

$$\sum_{n=1}^{\infty} (1 - p_1) \cdots (1 - p_n) < \infty. \quad (2.7)$$

Then the rate $\lambda$, defined by (2.6), of the skeleton $\mathcal{S}$ is positive and given by

$$\lambda = \prod_{j>0} (1 - (1 - p_1) \cdots (1 - p_j))^2. \quad (2.8)$$
Proof. The independence assumption implies that $(\theta, \mathbb{P})$ is stationary and ergodic, where $\theta$ is as in (2.3). We will argue that the summability assumption (2.7) implies that $\lambda > 0$ which, by Lemma 2.4, will imply that $\mathcal{S}^{-}$ is an infinite set. Consider the random variables

$$ \ell(j) := \max\{k > 0 : \alpha_{j-k, j} = 1\}, \quad j \in \mathbb{Z}, $$

which have the same distribution:

$$ \mathbb{P}(\ell(j) > k) = (1 - p_1) \cdots (1 - p_k). $$

Condition (2.7) implies that $\ell(j) < \infty$ a.s. Consider also the event

$$ A_{0,m}^{+} = \{0 \rightsquigarrow j, \text{ for all } j = 1, \dots, m\}, $$

noticing that

$$ A_{0,m}^{+} = \bigcap_{j=1}^{m} \bigcup_{i=0}^{j-1} \{i \rightsquigarrow j\} = \bigcap_{j=1}^{m} \{\ell(j) \le j\}. $$

Therefore,

$$ A_{0}^{+} := \{0 \rightsquigarrow 1, 0 \rightsquigarrow 2, \dots\} = \bigcap_{j=1}^{\infty} \{\ell(j) \le j\}, $$

and so

$$ \mathbb{P}(A_0^+) = \prod_{j=1}^{\infty} (1 - (1 - p_1) \cdots (1 - p_j)) > 0. $$

Similarly,

$$ A_0^- := \{-1 \rightsquigarrow 0, -2 \rightsquigarrow 0, -3 \rightsquigarrow 0, \dots\} $$

has the same probability as $A_0^+$. Noticing that the event $A_0$, defined by (2.4), is the intersection of $A_0^+$ and $A_0^-$, two independent events, we obtain

$$ \lambda = \mathbb{P}(A_0) = \mathbb{P}(A_0^+)\mathbb{P}(A_0^-) = \prod_{j>0} (1 - (1 - p_1) \cdots (1 - p_j))^2. $$

□

Remark 2.7. If one of the $p_j$ equals 1 then letting $k = \min\{j : p_j = 1\}$ we have $\lambda = \prod_{j=1}^{k-1} (1 - (1 - p_j)) \cdots (1 - p_1)^2$. The case $p_1 = 1$ is uninteresting.

Combining all of the above we conclude that the length of longest paths in Barak-Erdős graphs grows linearly, a result first observed by Newman [86].

**Corollary 2.8.** Consider the four quantities defined by (2.1) for a Barak-Erdős graph $\vec{G}(\mathbb{Z}, p)$. Then there is a constant $C = C(p)$ such that

$$ \lim_{n \to \infty} \frac{L_{0,n}}{n} = \lim_{n \to \infty} \frac{L_{0,n}^{\mathrm{L}}}{n} = \lim_{n \to \infty} \frac{L_{0,n}^{\mathrm{R}}}{n} = \lim_{n \to \infty} \frac{L_{0,n}^{\mathrm{L,R}}}{n} = C(p) \quad \text{a.s.} $$

Sketch of proof. If $p = 0$ then the graph has no edges and the above limits hold trivially with $C(0) = 0$. Assume $p > 0$ and note that condition (2.7) of Lemma 2.6 holds because (2.7) holds: $\sum_{n=1}^{\infty} (1 - p)^n < \infty$. We thus have $\lambda > 0$. By Lemma 2.4, the random sets $\mathcal{S}^+$, $\mathcal{S}^-$ are a.s. infinite with positive rate $\lambda$. We can easily see that $L_{0,n} = L_{0,n}^{\mathrm{L,R}} + o(n)$, as $n \to \infty$, a.s. The conclusion now follows from Lemma 2.1. □

Remark 2.9. For a $\vec{G}(\mathbb{Z}, p)$ with $0 \le p \le 1$, we have that the rate of its skeleton is given by

$$ \lambda = \prod_{j=1}^{\infty} (1 - (1 - p)^j)^2 \qquad (2.9) $$
This follows from (2.8). We now give a number-theoretic interpretation. Consider Euler's function

$$ \varphi(q) := \prod_{k=1}^{\infty} (1 - q^k), \quad |q| < 1. $$

Clearly,

$$ \lambda(p) = \varphi(1 - p)^2. $$

It is easy to see that $1/\varphi(q)$ is the generating function of the sequence $p(n)$ of integer partitions of the positive integer $n$, that is,

$$ \sum_{n=1}^{\infty} p(n)q^n = \frac{1}{\varphi(q)}. $$

To see this, recall that $p(n)$ is defined as the number of ways to write $n = \ell_1 + 2\ell_2 + 3\ell_3 + \dots$, where the $\ell_i$ are nonnegative integers. So $\sum_{n=1}^{\infty} q^n p(n) = \sum_{n=1}^{\infty} q^n \sum_{\ell_1, \ell_2, \dots} \mathbf{1}_{n=\ell_1+2\ell_2+\dots} = \sum_{\ell_1} q^{\ell_1} \sum_{\ell_2} q^{2\ell_2} \dots = (1-q)^{-1}(1-q^2)^{-2}\dots = 1/\varphi(q)$. Euler's pentagonal number theorem relates Euler's function to pentagonal numbers, that is numbers of the form $(3n^2 - n)/2$ (pentagonal numbers are "Pythagorean" numbers in the sense that they can be represented using pentagons, analogously to triangular and square numbers that were actually known by Pythagoras). The theorem says that

$$ \varphi(q) = \sum_{n=-\infty}^{\infty} (-1)^n q^{\frac{3n^2-n}{2}}, \quad |q| < 1. $$

A beautiful bijective proof of this is due to Franklin (1881) [51]; see Andrews [8] for a more modern account. Other algebraic proofs are due to Jacobi, Euler, and others; see Pólya and Szegő [89, §4, 50-54] for these proofs.

*Remark 2.10.* It is interesting to see that for a sparse $\vec{G}(\mathbb{Z}, p)$ graph, the average distance between two successive skeleton points is huge, whereas for a dense graph every second point is a skeleton point. For the symmetric $p = 0.5$ case, roughly every 12th point is a skeleton point. We used

<table><caption>Table 1: Average distance between two successive skeleton points in the infinite Barak-Erdős graph with parameter $p$.</caption><tr><td>p</td><td>0.01</td><td>0.1</td><td>0.3</td><td>0.5</td><td>0.6</td><td>0.8</td><td>0.9</td></tr><tr><td>1/λ</td><td>10<sup>139</sup></td><td>6 × 10<sup>11</sup></td><td>558.46</td><td>11.99</td><td>4.9</td><td>1.73</td><td>1.26</td></tr></table>

<figure><img src="image_2.png" /><figcaption>Figure 2: Plot of the rate $\lambda(p)$ of skeleton points against the connectivity probability $p$</figcaption></figure>

the formula $\lambda(p) = (\sum_{n=-\infty}^{\infty} (-1)^n (1-p)^{\frac{3n^2-n}{2}})^2$ to perform these computations, since the series converges much faster than the product. This, together with the regenerative properties (Section 6) provides a method for constructing an accurate picture of $\vec{G}(\mathbb{Z}, p)$.
## 2.2 The infinite bin model corresponding to the Barak-Erdős graph.

The general Infinite Bin Model (IBM) is a particle system that will be introduced in Section 3. In the current section, we will motivate the need to study it by explaining how to obtain an IBM by growing a Barak-Erdős $\vec{G}(\mathbb{Z}, p)$ graph dynamically. For the construction, we shall keep in mind that we are interested in longest paths.

Suppose that we have created

$$ \vec{G}_n = \vec{G}(\{1, \dots, n\}, p). $$

To construct $\vec{G}_{n+1}$ we need to add all edges $(i, n+1)$ for which $\alpha_{i,n+1} = 1$. Conditional on $\vec{G}_n$, the distribution of $\vec{G}_{n+1}$ will not change if we permute the variables $\alpha_{1,n+1}, \dots, \alpha_{n,n+1}$. We choose to order the variables $\alpha_{1,n+1}, i = 1, \dots, n$ by ordering the vertices $i = 1, \dots, n$, according to decreasing values of $(L_{1,i}^R)_{1 \le i \le n}$:

$$ j \le i \iff L_{1,j}^R \ge L_{1,i}^R, $$

with ties resolved arbitrarily. Introduce a state (or configuration) vector $X_n = (X_n(0), X_n(1), \dots)$ for $\vec{G}(\{1, \dots, n\}, p)$ by letting

$$ X_n(\ell) := |\{1 \le j \le n : L_{1,j}^R = \ell\}|. $$

In particular, $X_n(0)$ is the number of vertices $j$ for which none of the edges $(i, j)$ exist, for any $1 \le i < j$, and $X_n(1)$ is the number of vertices $j$ such that there exists an edge $(i, j)$ for some $i$ that is counted in $X_n(0)$ and there are no other incoming edges to $j$. We now let

$$ L_n := \max_{1 \le j \le n} L_{1,j}^R, $$

for notational convenience. Hence $X_n(L_n)$ is the number of vertices $1 \le i \le n$ such that $L_{1,i}^R$ is maximal. For technical reasons, we shall extend $X_n(\ell)$ on negative integers $\ell$ too and let $X_n(\ell) = \infty$ if $\ell < 0$. Therefore, our state vector is of the form

$$ X_n = [\dots, \infty, \infty, X_n(0), X_n(1), \dots, X_n(L_n), 0, 0, \dots]. \qquad (2.10) $$

Note that $X_1 = [\dots, \infty, \infty, 1, 0, 0, \dots]$, that is, $X_1(0) = 1$, $X_1(\ell) = \infty$ for $\ell < 0$, and $X_1(\ell) = 0$ for $\ell > 0$. We observe that the sequence $(X_n)$ of state vectors is a Markov chain.

Indeed, changing the point of view, we shall think of $X_n$ as a configuration of a number of identical balls (corresponding to the vertices) into labeled bins, so that $X_n(k)$ is the number of balls in bin $k$. The Markovian evolution is then easily obtained. When we add a new vertex $n+1$ then the state will change by the addition of a new ball into a bin. Recalling the ordering $\prec$ of the vertices of $\vec{G}_n$, we remark that the balls are placed in the bin in an increasing fashion. In other words, for all $i < j$, if the ball corresponding to vertex $i$ is in a bin to the left of the ball corresponding to vertex $j$, then $i \prec j$.

To construct $X_{n+1}$ we only need to monitor the largest vertex $i$, for that order, such that $\alpha_{i,n+1} = 1$. We then add a new ball to the bin immediately to the right of the bin containing ball $i$. If such an $i$ does not exist we are in the situation that vertex $n+1$ is not the endpoint of a path starting from vertex 1 and, in this case, a ball is added in bin 0: $X_{n+1}(0) = X_n(0) + 1$. Thus, first let $B_n$ be the nonnegative integer uniquely specified by

$$ X_n(B_n + 1) + \dots + X_n(L_n) \le I < X_n(B_n) + X_n(B_n + 1) + \dots + X_n(L_n), \qquad (2.11) $$

where $I$ is the rank of the largest vertex $i$ for $\prec$ such that $\alpha_{i,n+1} = 1$, or $I = n+1$ if there is no such vertex. Then, we construct $X_{n+1}$ as $X_n + \delta_{B_n}$, where $\delta_k$ is the configuration with a single ball in bin $k$, so that $\delta_k(\ell) = \mathbf{1}_{\{k=\ell\}}$. Noting the form of the state (2.10) we see that such a $B_n$ always exists and, because negative bins contain an infinite number of balls we have $B_n \ge 0$.

We can equivalently describe the transition from $X_n$ to $X_{n+1}$ by the stochastic recursion

$$ X_{n+1} = X_n + \delta_{B_n(X_n, \xi_{n+1})}, \qquad (2.12) $$
where $\xi_{n+1}$ is a geometric random variable with parameter $p$, i.e. $\mathbb{P}(\xi_{n+1} = i) = (1-p)^{i-1}p$, $i \in \mathbb{N}$, independent of $X_n$ and

$$ B(X_n, z) = \inf \left\{ k \in \mathbb{Z} : \sum_{p=k+1}^{\infty} X_n(p) < z \right\}, \qquad (2.13) $$

i.e. $B(X_n, \xi_{n+1})$ is the $B_n$ satisfying (2.11) with $\xi_{n+1}$ in place of $I$. The stochastic recursion (2.12) then proves that $(X_n)$ is a Markov chain.

The process $(X_n)$ is a particular case of an infinite bin model that will be studied in more detail in the next section. This bin model was introduced in [44] even under more general stationary and ergodic assumptions. It was shown that a stationary version of a spatially-shifted version of it exists. Under independence assumptions, it was possible to write balance equations for the stationary version. These led to sharp bounds on $C(p)$ showing, in particular, the asymptotics of $C(p)$ as $p \to 0$ that had previously obtained by Newman [86]. Moreover, it became possible to obtain analytically expressible upper and lower bounds for the whole function $p \mapsto C(p)$.

We study in the next section the infinite bin model as a stochastic process per se, dropping the geometric distribution assumption. This allows us to obtain general formula for the speed at which the index of the rightmost occupied bin is growing. Specifying these formulas for the geometric distribution will allow us to obtain the precise analytic properties of the function $C$ in Section 4.

# 3 The general infinite bin model

We consider in this section the infinite bin model as a “ball in bins” process. It can be constructed as a Markov chain in which at each step, a new ball is added in one of the bins similarly to the process defined in Section 2.2, but with an arbitrary law for the placement of the new ball. This model has appeared in different forms in several areas of probability. Among others, Aldous and Pitman [4] took interest in an infinite bin model in which at each step, a new ball is added to the right of one of the $N$ rightmost balls, chosen uniformly at random. The present general setting was introduced by Foss and Konstantopoulos [44], however in this article a stationary version of the process (defined in Section 3.4) is considered.

This section is organized as follows: we first introduce a formal definition of the generalized infinite bin model in Section 3.1 as a Markov chain on the space of functions $\mathbb{Z} \to \mathbb{Z}_+$ with support of the form $\{n \le a\}$ for some $a \in \mathbb{Z}$. In Section 3.2, we show that the index of the rightmost occupied bin in an infinite bin model grows linearly over time, at a certain speed $v$. The rest of the section is devoted to various ways to compute this constant.

We introduce the notion of coupling words in Section 3.3, which allows us to introduce renewal events in the evolution of infinite bin model. Thanks to these renewal events, we can define a stationary version of the infinite bin model in Section 3.4, which allows us to obtain several analytic formulas for its speed in Section 3.5.

## 3.1 Definition and first properties of the infinite bin model

In order to give a general description of infinite bin models, we first describe the state space on which this Markov chain will evolve. A configuration (or state) $X$ is a map $k \mapsto X(k)$ from $\mathbb{Z}$ (the set of bins) into

$$ \bar{\mathbb{Z}}_+ := \{0, 1, 2, \dots\} \cup \{\infty\} $$

such that $X(k) = 0$ eventually. We let

$$ \mathbb{S} := \{ X \in \bar{\mathbb{Z}}_+^\mathbb{Z} : \text{ there is } f \in \mathbb{Z} \text{ such that } (X(k) = 0 \text{ iff } k > f) \} $$

be the set of configurations. We think of $k \in \mathbb{Z}$ as a bin and of $X(k)$ as a number of indistinguishable balls placed in this bin. Given $X \in \mathbb{S}$ we let

$$ F(X) = \max \{k \in \mathbb{Z} : X(k) > 0\}, $$
a quantity called *the front* (bin) of $X$. Thus, each bin contains some balls (either no ball or a positive finite number of balls or an infinite number of balls) such that every bin to the right of $F(X)$ is empty and every bin to the left of $F(X)$ is nonempty. <fnref n="2" />.

**System dynamics.** Consider a configuration $X$ and a positive integer $\xi$ that we will refer to as the selection number. The rightmost nonempty bin is $F(X)$. Enumerate the balls in the nonempty bins of $X$ starting from the right and moving to the left, select the $\xi$-th ball, and let $B(X, \xi)$ be the bin containing it. The next state is obtained by simply adding a single ball to the bin to its right, indexed $B(X, \xi) + 1$.

<figure><img src="image_3.png" /><figcaption>Figure 3: Representation of the state $X = [\dots, 2, 1, 4, 2, 0, 0, \dots]$ in terms of balls in bins. Balls are enumerated from right to left.</figcaption></figure>

*Example 3.1.* Let $X = [\dots, 2, 1, 4, 2, 0, 0, \dots]$ be the configuration pictured in Figure 3. If $\xi = 1$ then the next state is $X = [\dots, 2, 1, 4, 2, 1, 0, \dots]$. If $\xi = 3$ then the bin that contains the third ball from the right is the second bin from the right, so the next state is $X = [\dots, 2, 1, 4, 3, 0, 0, \dots]$. The new ball will be placed in the second bin from the right if $\xi = 7$, in the third bin from the right if $\xi \in \{8, 9\}$, etc.

For technical reasons, we will also allow for the possibility that $\xi = 0$ or $\xi = \infty$. If $\xi = \infty$, the bin that contains the $\xi$-th ball is formally at $-\infty$, so no ball is added. If $\xi = 0$, the new configuration is obtained by shifting the position of every ball in the configuration one step to its right, i.e. replacing $X$ by $k \mapsto X(k-1)$.

In symbols, we let

$$B(X, \xi) := \inf \left\{ k \in \mathbb{Z} : \sum_{j>k} X(j) < \xi \right\}, \qquad (3.1)$$

writing $B(X, \infty) = -\infty$ by convention. This definition generalizes the one given in (2.13). Then, for $\xi \in \mathbb{N} \cup \{\infty\}$, we define $\Phi_{\xi} : \mathbb{S} \to \mathbb{S}$ by

$$\Phi_{\xi}(X) := X + \delta_{B(X, \xi)+1}, \qquad (3.2)$$

similarly to (2.12), where $\delta_k$ is the element of $\mathbb{Z}_+^k$ with $\delta_k(i) = 1$ if $i = k$ and 0 otherwise, so that $\delta_{-\infty} \equiv 0$ (in particular $\Phi_{\infty}(X) = X$). We also define $\Phi_0$ via

$$\Phi_0(X)(k) := X(k-1), \quad k \in \mathbb{Z},$$

corresponding to shifting $X$ by a unit step to the right. We notice that $B = B(X, \xi)$ is uniquely specified by the inequality

$$X(B+1) + \dots + X(F) < \xi \le X(B) + X(B+1) + \dots + X(F), \text{ where } F = F(X).$$

We also have, for all $1 \le \xi \le \infty$,

$$F(X) - \xi + 1 \le B(X, \xi) \le F(X) = B(X, 1).$$

<footnote n="2">²This last assumption may be relaxed, allowing empty bins to the left of the front, in which case the proofs become more technical, with some absorbing states being created. However, the main results stated in this section still hold true under quite general conditions.</footnote>
**Definition 3.2** (infinite bin model). Given a probability measure $\mu$ on $\bar{\mathbb{Z}}_+ = \{0, 1, 2, \dots, \infty\}$, and an i.i.d. random sequence $(\xi_n)_{n \ge 1}$ with common law $\mu$, we define IBM($\mu$) to be the Markov process $(X_n)$ with values in $\mathbb{S}$ given by

$$X_{n+1} = \Phi_{\xi_{n+1}}(X_n).$$

We leave the initial configuration $X_0$ unspecified.

*Remark 3.3.* In Section 3.3 we will write $\Phi_{\xi}(X)$ simply as $\xi X$ or $\xi(X)$ for reasons that will become apparent there. Keeping this in mind, we refer the reader to the Example 3.14 below.

Note that $X_0$ does not reflect in the notation IBM($\mu$). This is justified by the fact that the asymptotic properties of the IBM that we are interested in are independent of the choice of $X_0$. In relation with the Barak-Erdős graphs, we will be mostly interested in the case when $\mu$ is a geometric random variable on $\mathbb{N}$, but it will be useful to consider more general measures on $\bar{\mathbb{Z}}_+$ in order to obtain estimates on some quantities of interest. However, as several lemmas are easier to prove under the assumption that $\mu$ is supported on $\mathbb{N}$, let us first remark that this condition is usually enough to study the asymptotic properties of the infinite bin model.

**Lemma 3.4.** Let $\mu$ be a probability distribution on $\bar{\mathbb{Z}}_+$ with $\mu(\mathbb{N}) > 0$. We denote by $\nu$ the law $\mu$ conditioned to be on $\mathbb{N}$, i.e.

$$\forall k \in \mathbb{N}, \quad \nu(\{k\}) = \frac{\mu(\{k\})}{\mu(\mathbb{N})}.$$

There exists a coupling between the IBM($\mu$) ($X_n$) and a couple $(Y_n, (A_n, B_n))$, where $(Y_n)$ is an IBM($\nu$) started from $X_0$ and $(A_n, B_n)$ is an independent $\mathbb{Z}^2$-valued random walk with step distribution

$$\mathbb{P}(A_{n+1} = A_n + 1, B_{n+1} = B_n) = \mu(0), \quad \mathbb{P}(A_{n+1} = A_n, B_{n+1} = B_n + 1) = \mu(\infty) \\ \text{and } \mathbb{P}(A_{n+1} = A_n, B_{n+1} = B_n) = \mu(\mathbb{N})$$

such that

$$\forall n \in \bar{\mathbb{Z}}_{+}, \forall k \in \mathbb{Z}, X_n(k) = Y_{n-A_n-B_n}(k-A_n) \quad \text{a.s.}$$

*Proof.* Letting $(\xi_n, n \ge 0)$ be a sequence of i.i.d. random variables with law $\mu$, we set

$$A_n = \sum_{k=1}^{n} \mathbf{1}_{\{\xi_k=0\}} \quad \text{and} \quad B_n = \sum_{k=1}^{n} \mathbf{1}_{\{\xi_k=\infty\}},$$

and observe that $(A_n, B_n)$ is the same random walk as defined in the lemma. Then, we relabel $(\zeta_n)$ the random sequence $(\xi_n)$ removing all terms equal to 0 or $\infty$, in increasing order of their indices. We observe that $(\zeta_n)$ is a sequence of i.i.d. random variables with law $\nu$, independent from $(A_n, B_n)$.

We define $X_n$ and $Y_n$ by setting $Y_0 = X_0$ and

$$X_{n+1} = \Phi_{\xi_{n+1}}(X_n) = \Phi_{\xi_{n+1}} \circ \dots \circ \Phi_{\xi_1}(X_0) \quad \text{and} \quad Y_{n+1} = \Phi_{\zeta_{n+1}}(Y_n) = \Phi_{\zeta_{n+1}} \circ \dots \circ \Phi_{\zeta_1}(X_0).$$

Observing that $\Phi_0$ and $\Phi_\infty$ both commute with all $\Phi_k$ for $k \in \mathbb{N}$, we can rewrite

$$X_n = \Phi_0^{A_n} \Phi_{\zeta_{n-A_n-B_n}} \circ \dots \circ \Phi_{\zeta_1}(X_0) = Y_{n-A_n-B_n}(k-A_n),$$

using that there are exactly $A_n$ elements of $(\xi_1, \dots, \xi_n)$ equal to 0 and $B_n$ equal to $-\infty$, the rest being given, in the same order, by $(\zeta_1, \dots, \zeta_{n-A_n-B_n})$, which completes the proof. $\square$

**Theorem 3.5** (Speed of the IBM [[44, 79]]). Let $\mu$ be a probability measure on $\bar{\mathbb{Z}}_+$. Let $(X_n)$ be an IBM($\mu$) with initial configuration $X_0$. Then there exists a constant $0 \le v_\mu \le 1$, not dependent of $X_0$, such that

$$\lim_{n \to \infty} \frac{F(X_n)}{n} = v_\mu \quad \text{a.s.}$$
The quantity $v_μ$ is called the speed of the IBM($μ$). This theorem is proved in Section 3.2 by bounding the IBM($μ$) by two sequences of IBMs with laws having finite supports and using an increasing coupling between these processes.

**Remark 3.6.** Applying Lemma 3.4, we observe that if $μ$ is a probability distribution on $\bar{\mathbb{Z}}_+$ with $μ(\mathbb{N}) > 0$, then setting $ν = μ(\cdot|\mathbb{N})$, we have (by law of large numbers)

$$v_μ = μ(0) + μ(\mathbb{N})v_ν.$$

In particular, it is enough to prove Theorem 3.5 for measures supported by $\mathbb{N}$.

Beyond the position of the front, we will generally be interested in the content of a finite number of bins at a fixed distance from the front. In the case of an IBM($μ$) where $μ$ has finite support, one can reduce the study of the IBM to a finite state space Markov chain having a stationary distribution, by considering some finite-dimensional projection of the process, see Section 3.2. For a general $μ$ the content of the rightmost $K$ non-empty bins also has a stationary distribution but the arguments are more involved, see Section 3.4.

**Definition 3.7 (partial order on $\mathbb{S}$).** For any $X, Y \in \mathbb{S}$, we set $X \preceq Y$ if for every $ξ \in \mathbb{N}$, $B(X, ξ) \preceq B(Y, ξ)$, that is, if for every $ξ$ the $ξ$-th ball of $X$ is to the left of the $ξ$-th ball of $Y$.

**Lemma 3.8.** The relation $\preceq$ is a partial order that is preserved by addition. Moreover,

$$\text{if } 0 \leq \xi \leq \xi' \leq \infty \text{ and } X \preceq Y \text{ then } \Phi_{\xi'}(X) \preceq \Phi_{\xi}(Y). \qquad (3.3)$$

*Proof.* Simply notice that

$$X \preceq Y \iff \sum_{k=\ell}^{\infty} X(k) \leq \sum_{k=\ell}^{\infty} Y(k) \text{ for all } \ell \in \mathbb{Z}.$$

This implies that $X \preceq Y$ and $X' \preceq Y'$ implies $X + X' \preceq Y + Y'$.

For the second assertion, assume first that $1 \leq \xi \leq \xi' \leq \infty$. We then have, by (3.1), $B(X, \xi') \leq B(X, \xi)$ and so $\delta_{B(X, \xi')} + 1 \preceq \delta_{B(X, \xi')} + 1$; and if $X \preceq Y$ then $X + \delta_{B(X, \xi')} + 1 \preceq Y + \delta_{B(X, \xi')} + 1$, and so $\Phi_{\xi'}(X) \preceq \Phi_{\xi}(Y)$ by (3.2).

The case $ξ = ξ' = 0$ being straightforward, we are left with the case $ξ = 0 < \xi' \leq \infty$. Assume again $X \preceq Y$. Then, by the argument above, and since $ξ' \geq 1$, we have $\Phi_{\xi'}(X) \leq \Phi_{\xi'}(Y) \leq \Phi_1(Y)$ and we can easily see that $\Phi_1(Y) \leq \Phi_0(Y)$. $\square$

This partial order can be used to define an increasing coupling between two IBMs when the step distribution of the first IBM is dominated by the step distribution of the second IBM.

**Proposition 3.9 (increasing coupling).** Let $μ$ and $ν$ be two probability measures on $\bar{\mathbb{Z}}_+$ such that for every $i \geq 0$ we have $μ([0, i]) \leq ν([0, i])$. Then if $X_0 \preceq Y_0$ are two configurations in $S$, we can construct a coupling of $(X_n) \sim \text{IBM}(μ)$ and $(Y_n) \sim \text{IBM}(ν)$ such that $X_n \preceq Y_n$ for every $n \geq 0$ a.s.

*Proof.* The assumption that $μ([0, i]) \leq ν([0, i])$ for all $i$ allows us to define random $ξ, ξ'$, with laws $μ, ν$, respectively, such that $ξ' \leq ξ$ a.s. Hence we can build an i.i.d. sequence of pairs $(ξ_n, ξ'_n)_{n \geq 1}$ such that $ξ_n$ has law $μ$, $ξ'_n$ has law $ν$ and $ξ'_n \leq ξ_n$ for all $n \geq 1$. Defining the IBM($μ$) $(X_n)$ using $(ξ_n)$ and the IBM($ν$) $(Y_n)$ using $(ξ'_n)$, we obtain that $X_n \preceq Y_n$ for every $n \geq 0$ a.s. by applying (3.3) inductively. $\square$

## 3.2 The speed of the general infinite bin model

This section is devoted to the proof of Theorem 3.5 for the existence of the speed $v_μ$ for IBM($μ$). We first examine the case where $μ$ has finite support and then develop a coupling technique to deal with the general case.
**The finite support case.** Let $\xi$ be a random element of $\mathbb{Z}_+$, distributed according to the law $\mu$. Assume there is an integer $k$ such that

$$ \xi \in \{0, 1, \dots, k\} \cup \{\infty\} \text{ a.s.} \qquad (3.4) $$

If $k=1$ then, by the definition of $\Phi_\xi$, the front of $\Phi_\xi(X)$ is one unit to the front of $X$ iff $\xi \in \{0, 1\}$. Hence, in this case, $F(X_n) - F(X_0) = \sum_{m=1}^n \mathbf{1}_{\xi_m \in \{0,1\}}$ and so $v_\mu = \mu(0) + \mu(1) = 1 - \mu(\infty)$.
We now assume in the rest of the section that

there exists $k \ge 2$ such that $\mu(k) > 0$.

Given a configuration $X$ define

$$ \tilde{\Pi}_k(X) := [X(B(X, k) + 1), \dots, X(F(X))], \qquad (3.5) $$

which is interpreted as a finite word$^3$ in $\mathbb{N}$. Let $|\tilde{\Pi}_k(X)|$ be its length and $\|\tilde{\Pi}_k(X)\|$ its content, that is, the total number of balls, corresponding to the sum of the letters of that word. We have

$$ 0 \le |\tilde{\Pi}_k(X)| = F(X) - B(X, k) \le k - 1, \quad 0 \le \|\tilde{\Pi}_k(X)\| = \sum_{j=X(B,k)+1}^{F(X)} X(j) \le k - 1, $$

and $|\tilde{\Pi}_k(X)| = 0$ if and only if $\|\tilde{\Pi}_k(X)\| = 0$. The set

$$ \tilde{\Pi}_k(\mathbb{S}) = \{\tilde{\Pi}_k(X) : X \in \mathbb{S}\} \\ = \{\emptyset\} \cup \{[a_1, \dots, a_\ell] : 1 \le \ell \le k-1, a_1, \dots, a_\ell \ge 1, a_1 + \dots + a_\ell \le k-1\} $$

is finite$^4$.

We think of $\tilde{\Pi}_k$ as a projection of $\mathbb{S}$ on $\tilde{\Pi}_k(\mathbb{S})$ a set of finite cardinality. We observe that an IBM $X$ with step distribution satisfying (3.4) is compatible with this projection, in the sense that $\tilde{\Pi}_k(X)$ remains a Markov chain.

**Lemma 3.10.** Let $k \ge 2$ be an integer, and assume that the law $\mu$ is supported in $\{0\} \cup \{1, \dots, k\} \cup \{\infty\}$ with $\mu(\{k\}) > 0$. Consider the IBM defined by $X_{n+1} = \Phi_{\xi_{n+1}}(X_n)$, where the $(\xi_n)$ are i.i.d. random variables with law $\mu$. Then $Z_n = \tilde{\Pi}_k(X_n)$, $n \ge 0$, is an irreducible Markov chain with values in the set $\tilde{\Pi}_k(\mathbb{S})$. In particular, the chain is positive recurrent and has a unique stationary probability measure.

**Intuition of the proof.** The reason that the function $\tilde{\Pi}_k$ preserves the Markov property is because each of the states $a \in \tilde{\Pi}_k(\mathbb{S})$ conveys just enough information about the state $X \in \mathbb{S}$ with $a = \tilde{\Pi}_k(X)$ that is enough to decouple the past from the future.

For example, if $a = \emptyset$ then we know that any $X \in \mathbb{S}$ with $a = \tilde{\Pi}_k(X)$ must satisfy $B(X, k) = F(X)$ (because $a$ has length 0) and so the front bin $F(X)$ contains at least $k$ balls. This means that regardless of the value of $\xi$, $1 \le \xi \le k$, we have $\Phi_\xi(X)$ is $X$ together with a single ball in the bin to the right of $F(X)$. So $\Phi_\xi(X)$ has a front at $F(X) + 1$ with a single ball and so $\tilde{\Pi}_k(\Phi_\xi(X)) = [1]$. On the other hand, if $\xi = 0$ or $\infty$ then the next state remains $a$. A complete proof of this fact being available in [79, Lemma 3.1], it is perhaps best to work out two examples and leave the formal details to the reader.

It is easy to see that the Markov chain $\tilde{\Pi}_k(X_n)$ has an irreducible class connected to the state $\emptyset$ (by producing a sequence of moves that takes the chain from any state to $\emptyset$; the assumption that $P(\xi = k) > 0$ is required at this step). Since the state space is finite, the chain is positive recurrent and has a unique invariant probability measure. $\square$

<footnote>$^3$A finite word in an alphabet $A$ is a finite (possibly empty) sequence of elements of $A$. We denote by $A^* = \bigcup_{\ell=0}^\infty A^\ell$ the set of finite words in $A$, with the convention $A^0 = \{\emptyset\}$. We denote by $|w|$ the length of the word $w \in A^*$, defined as the unique $\ell \in \mathbb{Z}_+$ such that $w \in A^\ell$. In particular, $\emptyset$ is the only word with length 0.</footnote>

<footnote>$^4$More precisely $|\tilde{\Pi}_k(\mathbb{S})| = 2^{k-1}$. Indeed, recall that the set of $\ell$-tuples $(a_1, \dots, a_\ell)$ of strictly positive integers summing to $m$ has cardinality $\binom{m-1}{\ell-1}$. Thus the number of $\ell$-tuples of positive integers summing at most to $k-1$ is given by $\sum_{m=\ell}^{k-1} \binom{m-1}{\ell-1} = \binom{k-1}{\ell}$. Summing over all possible values of $\ell$ yields that $\tilde{\Pi}_k(\mathbb{S})$ has cardinality $\sum_{\ell=0}^{k-1} \binom{k-1}{\ell} = 2^{k-1}$.</footnote>
<figure><img src="image_4.png" /><figcaption>Figure 4: This figure describes the projected Markov chain, with $k = 2$ on the left picture, and $k = 3$ on the right one. The integers over the directed edges represent the values of $\xi$ corresponding to the transitions. For example, if $\mu$ is the law of $\xi$, the transition probability for state [1] to state [2] on right equals $\mu(2) + \mu(3)$. The thick arrows represent transitions that move the front by one unit. Note that if $\xi \in \{0, \infty\}$, the projected Markov chain remains at the same state, moving the front by 1 if and only if $\xi = 0$.</figcaption></figure>

Given $a = [a_1, \dots, a_\ell] \in \tilde{\Pi}_k(\mathbb{S})$ let $L(a) = a_\ell$ with the convention that $L(a) = k$ if $a = \emptyset$. So if $Z_n = \tilde{\Pi}_k(X_n)$ then $L(Z_n)$ corresponds to the number of balls in the front bin of $X_n$ (or $k$ if this number is larger than $k$).

**Proposition 3.11.** Let $(X_n)$ be an IBM($\mu$) where $\mu$ is supported on $\{0\} \cup \{1, \dots, k\} \cup \{\infty\}$ where $k \ge 2$ and $\mu(k) > 0$. Then there exists a constant $v_\mu \in [0, 1]$, that does not depend on $X_0$, such that

$$ \lim_{n \to \infty} \frac{F(X_n)}{n} = v_\mu \quad \text{a.s.} $$

*Proof.* Let $Z_n = \tilde{\Pi}_k(X_n)$. Notice that

$$ F(X_j) > F(X_{j-1}) \iff F(X_j) - F(X_{j-1}) = 1 \iff L(X_{j-1}) \ge \xi_j, \quad (3.6) $$

using that a ball is added in the leftmost empty bin if $\xi$ is either equal to 0 or smaller than the number of balls in the rightmost bin, see Figure 4. Setting $b_j$ for the indicator of the event on the right of the last equivalence, we have

$$ F(X_n) - F(X_0) = \sum_{j=1}^{n} b_j. $$

By the ergodic theorem $\frac{1}{n} \sum_{j=1}^n b_j$ converges to a constant $v_\mu$ a.s. which completes the proof. $\square$

**Remark 3.12.** Observe that $v_\mu$ can be computed from the knowledge of the invariant distribution $\pi$ of the Markov chain $\tilde{\Pi}_k(X_n)$. More precisely, writing $Z$ for a random word distributed according to $\pi$ and $\xi$ an independent random variable with law $\mu$, we have

$$ v_\mu = \mathbb{P}(L(Z) \ge \xi). $$

For example, if $k = 2$, we have $v_\mu = \pi(\emptyset)\mu(\{0, 1, 2\}) + \pi([1])\mu(\{0, 1\}) = (\mu(1)+\mu(2))^2/(\mu(1)+2\mu(2))$; see Figure 4. However, since the size of $\Pi_k(\mathbb{S})$ grows exponentially with $k$, this exact formula can be computed for small values of $k$ only.

**The general $\mu$ case.** In order to extend the existence of the speed to the case when $\mu$ may have infinite support, we compare $\mu$ to three distributions with finite supports and use the increasing coupling of Proposition 3.9. Let $\xi$ be a random element of $\bar{\mathbb{Z}}_+$ with distribution $\mu$. Fix $k \ge 1$ and define

$$ \xi_k^j := \xi \mathbf{1}_{\xi \le k} + j \mathbf{1}_{\xi > k}, $$

and let $\mu_k^j$ be the distribution of $\xi_k^j$. We are only interested in the cases where $j = 0, k$ or $\infty$ (noticing that $\xi_k^\infty = \xi$ when $\xi \le k$ or $\infty$ when $\xi > k$). Clearly,

$$ \xi_k^0 \le \xi_k^k \le \xi \le \xi_k^\infty. $$
Let $(\xi_{k,n}^0, \xi_{k,n}^k, \xi_n, \xi_{k,n}^\infty)$, $n \in \mathbb{N}$, be i.i.d. copies of $(\xi_k^0, \xi_k^k, \xi, \xi_k^\infty)$. Define 4 coupled IBMs, $(X_{k,n}^0)$, $(X_{k,n}^k)$, $(X_n)$ and $(X_{k,n}^\infty)$, as in Definition 3.2, using the 4 coupled sequences $(\xi_{k,n}^0)$, $(\xi_{k,n}^k)$, $(\xi_n)$ and $(\xi_{k,n}^\infty)$ of selection numbers, respectively. By (3.3) and Proposition (3.9) we have

$$ \forall n \ge 0 \quad X_{k,n}^\infty \le X_n \le X_{k,n}^k \le X_{k,n}^0 \quad \text{a.s.} \qquad (3.7) $$

We next observe that

$$ \tilde{\Pi}_k(X_{k,n}^\infty) = \tilde{\Pi}_k(X_{k,n}^0) \quad \text{for all } n \ge 0, \qquad (3.8) $$

where $\tilde{\Pi}_k$ was defined in (3.5).

*Proof of (3.8).* It follows immediately from its definition that $\Phi_0$ commutes with $\Phi_k$ for all $k \in \bar{\mathbb{Z}}_+$. Using that $\xi_{k,n}^\infty \neq \xi_{k,n}^0$ if and only if $\xi_k \in (k, \infty)$, in which case the former takes value $\infty$ while the latter take value 0, we have

$$ X_{k,n}^0 = \Phi_{\xi_{k,n}^0} \circ \dots \circ \Phi_{\xi_{1,n}^0} (X_0) = \Phi_0^{I_n} \circ \Phi_{\xi_{k,n}^\infty} \circ \dots \circ \Phi_{\xi_{1,n}^\infty} (X_0) = \Phi_0^{I_n} (X_{k,n}^\infty), $$

where $I_n = \sum_{j=0}^{n-1} \mathbf{1}_{\{\xi_k \in (k, \infty)\}}$. Consequently, $X_{k,n}^0(\ell) = X_{k,n}^\infty(\ell - I_n)$ for all $\ell \in \mathbb{Z}$, from which we deduce that $\tilde{\Pi}_k(X_{k,n}^\infty) = \tilde{\Pi}_k(X_{k,n}^0)$, completing the proof. $\square$

We are now able to complete the proof of Theorem 3.5.

*Proof of Theorem 3.5.* Let $k \ge 1$ be an integer. By Proposition 3.11, there exist $v_{\mu_k^\infty}$ and $v_{\mu_k^0}$ in $[0, 1]$ such that

$$ \lim_{n \to \infty} \frac{F(X_{k,n}^\infty)}{n} = v_{\mu_k^\infty}, \quad \lim_{n \to \infty} \frac{F(X_{k,n}^0)}{n} = v_{\mu_k^0} \quad \text{a.s.} $$

Using that $F(X_{k,n}^0) = F(X_{k,n}^\infty) + I_n$, as observed above, and that $I_n/n \to \mu([k+1, \infty))$ a.s. by law of large numbers, we conclude that

$$ v_{\mu^{0,k}} = v_{\mu^{\infty,k}} + \mu([k+1, \infty)). \qquad (3.9) $$

Furthermore, we have that for every $n \ge 1$,

$$ F(X_{k,n}^\infty) \le F(X_n) \le F(X_{k,n}^0) \quad \text{a.s.} \qquad (3.10) $$

Combining (3.9) and (3.10) we deduce that

$$ v_{\mu_k^\infty} \le \lim_{n \to \infty} \frac{F(X_n)}{n} \le \overline{\lim}_{n \to \infty} \frac{F(X_n)}{n} \le v_{\mu_k^\infty} + \mu([k+1, \infty)) \quad \text{a.s.} \qquad (3.11) $$

Since for every $i \ge 0$ and $k \ge 1$, we have $\mu^{\infty,k}([0, i]) \le \mu^{\infty,k+1}([0, i])$, we have by Proposition 3.9 that $X_n^{\infty,k} \le X_n^{\infty,k+1}$ thus the sequence $(v_{\mu^{\infty,k}})_{k \ge 1}$ is nondecreasing. Since it is upper-bounded by 1, we have that

$$ \lim_{k \to \infty} v_{\mu^{\infty,k}} = v_\mu, $$

for some $v_\mu \in [0, 1]$. Letting $k$ go to infinity in (3.11) we conclude that

$$ \lim_{n \to \infty} \frac{F(X_n)}{n} = v_\mu \quad \text{a.s.} \qquad \square $$

*Remark 3.13.* If $\nu$ is another probability distribution on $\bar{\mathbb{Z}}_+$ such that $\nu([0, i]) \le \mu([0, i])$ for all $i \ge 0$, then it follows from Proposition 3.9 that $v_\nu \le v_\mu$.
## 3.3 Coupling words

We assume, throughout this section, that $\mu$ is a probability measure on the set $\mathbb{N}$ of positive integers, in other words that $\mu(\{0\}) = \mu(\{\infty\}) = 0$. The IBM($\mu$) is the Markov process introduced in Definition 3.2 and aims to describe a stationary version of this process$^5$. Since $F(X_{n+1}) - F(X_n) \ge 0$, and is positive with positive probability, it is easy to see that $(X_n)$ has no stationary version. But this is an illusion! To remedy it, we simply modify $X_n$ by shifting the origin of space to the front bin $F(X_n)$. This will be done in Section 3.4.

Recall that $X_n$ is defined by the repeated application of maps of type $\Phi_\xi$ several times. To simplify notation, we write $\xi X$ instead of $\Phi_\xi(X)$, so that $\eta\xi X$ corresponds to $\Phi_\eta(\Phi_\xi(X))$. Applying a finite number of these maps is thus identified by a “selection word”.

Let $\mathbb{N}^*$ be the set of words from $\mathbb{N}$. A selection word (or, simply, word when no confusion arises) is a nonempty word in $\mathbb{N}$. Let

$$ \mathcal{U} = \bigcup_{n \ge 1} \mathbb{N}^n = \mathbb{N}^* \setminus \{\emptyset\} $$

be the set of selection words. If $\alpha \in \mathcal{U}$ then we write it, rather unconventionally, from right to left

$$ \alpha = \alpha_{\ell} \cdots \alpha_1 $$

(or $(\alpha_\ell, \dots, \alpha_1)$ when confusion arises) as we made the identification

$$ \Phi_{\alpha_\ell \circ \dots \circ \alpha_1} \equiv \alpha_\ell \cdots \alpha_1. \qquad (3.12) $$

*Example 3.14.* Take $X = [\dots, 5, 3, 2, 1, 2, 0, 0, \dots]$, with $F(X) = 0$, and consider the selection word $\alpha = (2, 4, 5, 1)$. To compute $\alpha(X)$ we first apply 1 (that is, $\Phi_1$), then 5, then 4 and then 2. We have $1(X) = \Phi_1(X) = X + \delta_1 = [\dots, 5, 3, 2, 1, 2, 1, 0, \dots]$, $5(1X) = \Phi_5 \circ \Phi_1(X) = X + \delta_1 + \delta_{-1}$, $4(5(1X)) = \Phi_4 \circ \Phi_5 \circ \Phi_1(X) = X + \delta_1 + \delta_{-1} + \delta_0$, and, finally, $\alpha(X) = 2(4(5(1(X)))) = X + 2\delta_1 + \delta_{-1} + \delta_0$.

Recall that we denote by $|\alpha|$ the length of the word $\alpha$. An element of a selection word is a selection number and is sometimes referred to as a letter. There is only one word of length 0, the empty word $\emptyset$, which is not considered as a selection word. However, we can formally define $\Phi_\emptyset$ as the identity on $\mathbb{S}$.

If $\alpha = \alpha_\ell \cdots \alpha_1$ is a selection word and $k \le \ell$ then $\alpha_k \cdots \alpha_1$ is a prefix of $\alpha$, while $\alpha_\ell \cdots \alpha_k$ is a suffix. The number of occurrences of letter $n$ in a word $\alpha$ is written

$$ \vartheta_n(\alpha) := |\{1 \le k \le |\alpha|, \alpha_k = n\}|. $$

The concatenation of $\alpha = \alpha_\ell \cdots \alpha_1$ with $\beta = \beta_k \cdots \beta_1$ is the word $\beta\alpha = \beta_k \cdots \beta_1\alpha_\ell \cdots \alpha_1$, again keeping in mind the right-to-left convention. Of course, $\emptyset\alpha = \alpha\emptyset = \alpha$. For $m, \ell \in \mathbb{N}$, the word $m^\ell$ is the length-$\ell$ word whose letters are all equal to $m$.

For $k \in \mathbb{N}$ define

$$ \Pi_k : \begin{array}{ccc} \mathbb{S} & \to & \mathbb{N}^k \\ X & \mapsto & (X(F(X) - k + 1), \dots, X(F(X))) \end{array} $$

which isolates the content of the rightmost $k$ non-empty bins. The definition can be extended to $k = 0$ by setting $\Pi_0(X)$ to be the empty vector.

**Definition 3.15 (k-coupling words).** We say that a selection word $\alpha$ is k-coupling if

$$ \forall X, Y \in \mathbb{S} \quad \Pi_k(\alpha X) = \Pi_k(\alpha Y). $$

Let $C_k$ be the set of all k-coupling words. A word $\alpha$ is called coupling if it is k-coupling for some positive integer $k$.

<footnote>$^5$Observe that the restriction made in this section remains tame, as a selection number of 0 moves the whole configuration to the right by 1 while a selection number of $\infty$ leaves the configuration unchanged. A generic IBM($\nu$) $X$ can thus be coupled with an IBM($\mu$) $Y$, where $\mu(\cdot) = \nu(\cdot|\mathbb{N})$, in such a way that the configuration $X_n$ is obtained as a random shift of $Y_{Z_n}$, where $(Z_n)$ is a random walk independent of $Y$. See Lemma 3.4.</footnote>
In other terms, a word $\alpha$ is said to be $k$-coupling if the action of $\alpha$ on any configuration always give the same values in the $k$ rightmost non-empty bins. For example, 1 is a 1-coupling word, as the rightmost non-empty bin in $1X$ always contain exactly one ball. More generally, for $k \in \mathbb{N}$, the word $1^k$ is a $k$-coupling word.

Note that $C_1 \supset C_2 \supset \dots$. Hence $C_1$ is the set of all coupling words. Note that $C_1$ is the set of all words $\alpha$ such that the number of balls in the bin at the front of $\alpha X$ is the same as for $\alpha Y$ for any other configuration $Y$. The words in $U \setminus C_1$ are non-coupling.

**Definition 3.16 (Coupling number).** The coupling number of $\alpha$ is defined by

$$K(\alpha) = \sup\{k \ge 0 : \forall X, Y \in \Pi_k(\alpha X) = \Pi_k(\alpha Y)\}.$$

In particular, for a word $\alpha$, $K(\alpha) = 0$ is equivalent to $\alpha \in U \setminus C_1$, i.e. to the fact that $\alpha$ is non-coupling. More generally, for $k \ge 1$, we have

$$K(\alpha) = k \iff \alpha \in C_k \setminus C_{k+1}.$$

Hence, $\alpha$ is $k$-coupling if and only if $K(\alpha) \ge k$. We naturally let $K(\emptyset) = 0$.

*Example 3.17.* We have that $K(1) = 1$, $K(1, 1) = 2$, and more generally, if $1^\ell = (1, \dots, 1)$ is the word consisting of $\ell$ letters all equal to 1, then $K(1^\ell) = \ell$. Indeed, as previously observed, $1^\ell$ is an $\ell$-coupling word. But $1^\ell \notin C_{\ell+1}$ because the $\ell+1$st rightmost nonempty bins contains the number of balls in the rightmost non-empty bin of $X$.

Consider next the word $(2, 2, 1)$. We see that, for any $X$, we have $\Pi_2((2, 2, 1)X) = (2, 1)$; but the three rightmost bins of $(2, 2, 1)X$ depend on the content of the front of $X$. Hence $(2, 2, 1) \in C_2 \setminus C_3$. As a third example, one can check that $(2, 2)$ is a non-coupling word.

We now define a class of words which will provide useful examples of coupling words.

**Definition 3.18 (Triangular words).** A word $\alpha = (\alpha_\ell, \dots, \alpha_1) \in U$ is called *triangular* if for every $1 \le i \le \ell$ we have $\alpha_i \le i$. We denote by $\mathcal{T}$ the set of triangular words. An infinite sequence $(\dots, \alpha_3, \alpha_2, \alpha_1)$ of positive integers is called an *infinite triangular word* if $\alpha_i \le i$ for all $i$. Let $\mathcal{T}_\infty$ be the set of infinite triangular words.

We claim that every triangular word is a coupling word. More precisely, if $\alpha$ is a triangular word with $k$ occurrences of the letter 1, we show that $\alpha$ is $k$-coupling.

**Lemma 3.19.** Let $k \ge 1$ and let $\alpha$ be a triangular word with $\vartheta_1(\alpha) = k$. Then $\alpha$ is $k$-coupling.

*Proof.* Write $\alpha = (\alpha_\ell, \dots, \alpha_1) \in \mathcal{T}$ and let $X_0, Y_0 \in \mathbb{S}$. Without loss of generality, we assume that $F(X_0) = F(Y_0) = 0$. For every $1 \le i \le n$, define $X_i = \alpha_i \cdots \alpha_1(X_0)$ and $Y_i = \alpha_i \cdots \alpha_1(Y_0)$.

We show by induction on $0 \le i \le \ell$ that $X_i$ and $Y_i$ coincide for all bins of positive indices and have $i$ balls in these bins. In other words, we show that for every $k \ge 1$, $X_i(k) = Y_i(k)$ and $\sum_{j \ge 1} X_i(j) = \sum_{j \ge 1} Y_i(j) = i$. This is trivially true when $i = 0$.

If $1 \le i \le \ell$, by induction hypothesis, we know that $X_{i-1}$ and $Y_{i-1}$ have $i-1$ balls in the same positions in bins of positive indices and at least one ball in the bin of index 0, thus $B(X_i, \alpha_i) = B(Y_i, \alpha_i) \ge 0$. Hence $\Phi_{\alpha_i}$ adds a ball to $X_{i-1}$ and $Y_{i-1}$ in the same bin of positive index, completing the proof of that statement.

Next, setting $f := F(X_\ell) = F(Y_\ell)$, we have $f \ge 1$ (since $\alpha_1 = 1$). As $X_{|Z_+} = Y_{|Z_+}$, we have $\Pi_f(\alpha(X_0)) = \Pi_f(\alpha(Y_0))$, so $K(\alpha) \ge f$. Since each transition $\Phi_1$ adds a balls to a previously empty bin, we have that $f \ge \vartheta_1(\alpha) = k$, which shows that $\alpha \in C_k$. $\square$

More generally, an *infinite triangular word* allows the coupling of IBM with arbitrary initial conditions.

**Lemma 3.20.** Let $\alpha \in \mathcal{T}_\infty$ and let $X_0, Y_0 \in \mathbb{S}_0$. For every $n \ge 1$, denote by $X_n = \alpha_n \cdots \alpha_1(X_0)$ and by $Y_n = \alpha_n \cdots \alpha_1(Y_0)$. Then for every $n \ge 0$ we have $X_{n|\mathbb{N}} = Y_{n|\mathbb{N}}$ (both configurations have identical contents in all bins with positive indices).

The proof follows from an induction similar to the one used above in the proof of Lemma 3.19.
## 3.4 Construction of a stationary version and coupling

In order to construct a stationary version of the infinite bin model, we first define a variant of the IBM where the front is pinned at position 0. Denote by $S_0$ the set of all $X \in S$ such that $F(X) = 0$. For $X \in \mathbb{Z}^\mathbb{Z}$ and $u \in \mathbb{Z}$, we introduce the map

$$ \Theta_u X(k) := X(k - u). $$

In other words, $\Theta_u$ shifts $X$ to the right by $u$. We remark immediately that $\Theta_u = (\Phi_0)^u$.

Next, let

$$ \Theta X: \begin{array}{rcl} \mathbb{S} & \to & S_0 \\ X & \mapsto & \Theta_{-F(X)}X \end{array} $$

be the projection $\mathbb{S} \to S_0$ which “pins the front” at position 0.

**Definition 3.21 (Pinned infinite bin model).** Given a probability measure $\mu$ on $\mathbb{N}$, and a sequence $(\xi_n)_{n \ge 1}$ of i.i.d. random variables with law $\mu$, we define the pinned IBM($\mu$) to be the Markov process $(\hat{X}_n)$ with values in $S_0$ given by

$$ \hat{X}_{n+1} = \Theta \circ \Phi_{\xi_{n+1}}(\hat{X}_n), \quad n \ge 0. $$

We leave the initial configuration $\hat{X}_0 \in S_0$ unspecified.

Let $(\hat{X}_n)$ be the pinned IBM as above. Using the same sequence of selection numbers, and recalling the convention (3.12), we define an unpinned IBM by setting $X_0 = \hat{X}_0$ and $X_n = \xi_n \cdots \xi_1 X_0$ for $n \ge 1$. We observe that for any selection word $\alpha$ and $X \in S$, we have $\Theta(\alpha X) = \Theta(\alpha(\Theta X))$. Therefore, for each $n \in \mathbb{N}$, we have

$$ \hat{X}_n = \Theta X_n. $$

As a result, $\hat{X}_n$ can be thought of as the pinned version of the IBM $X$.

**Definition 3.22 (Stationary pinned IBM).** Given a stationary sequence $(\xi_n)_{n \in \mathbb{Z}}$ we say that $(Y_n)_{n \in \mathbb{Z}}$ is a stationary pinned IBM if

$$ Y_{n+1} = \Theta(\xi_{n+1}Y_n), \quad n \in \mathbb{Z}. \qquad (3.13) $$

If $(\xi_n)_{n \in \mathbb{Z}}$ is an i.i.d. sequence with common law $\mu$ then we refer to (the law) of $(Y_n)$ as a stationary version of IBM($\mu$).

We show the existence and uniqueness of this stationary version under a first moment condition on $\mu$.

**Theorem 3.23.** Let $\mu$ be a probability distribution on $\mathbb{N}$ such that

$$ \sum_{k \in \mathbb{N}} k \mu(k) < \infty \quad \text{and} \quad \sup_{k \in \mathbb{N}} \mu(k) < 1. \qquad (3.14) $$

Let $(\xi_n)_{n \in \mathbb{Z}}$ be a sequence of i.i.d. random variables with law $\mu$. Write $\mathcal{F}_n := \sigma(\xi_k, -\infty < k \le n)$. Then a.s. there exists a unique process $(Y_n)_{n \in \mathbb{Z}}$ on $S_0$ satisfying the recursion (3.13) and such that $Y_n$ is $\mathcal{F}_n$-measurable for all $n \in \mathbb{Z}$.

We observe that the condition $\sup_{k \in \mathbb{N}} \mu(k) < 1$ is only here to avoid considering the case when $\mu$ is a Dirac mass $\delta_k$ for some $k \ge 1$. In that case, there would be $k$ processes $(Y_n^j)_{n \in \mathbb{Z}, 1 \le j \le k}$ on $S_0$ satisfying (3.13), given by

$$ Y_n^k(\ell) = \begin{cases} k & \text{if } \ell \le -1 \\ 0 & \text{if } \ell \ge 1 \\ ((j+n) \mod k) + 1 & \text{if } \ell = 0 \end{cases}. $$
The proof of Theorem 3.23 relies on the existence of infinitely many $\infty$-coupling words embedded in the bi-infinite sequence $(\xi_n)_{n \in \mathbb{Z}}$. These words induce renewal events for the stationary IBM($\mu$).

In order to avoid unnecessary technicalities, we prove Theorem 3.23 under the additional condition $\mu(1) > 0$. Under this condition, we prove the existence of infinitely many infinite triangular words in Lemma 3.25. These triangular words induce renovation events for the IBM($\mu$), in the sense that conditionally on their realisation at time $k$, the only algebraic dependence of the future (starting from time $k$) on the past (before time $k$) is given by the position of the front at time $k$. For the concept of renovation events see [19, 21, 22, 44].

*Remark 3.24.* To extend Theorem 3.23 to measure $\mu$ such that $\mu(0) = 1$, one can use [28] in which for all $a \neq b \in \mathbb{N}$, a coupling word $\alpha$ with letters in $\{a, b\}$ with arbitrary $K(\alpha)$ is constructed. An analogue of Lemma 3.25 can be stated replacing a triangular word by $\alpha$ followed by an infinite coupling word $\beta$. The rest of the proof would follow straightforwardly; see [80].

With Lemma 3.20 in mind, we show almost surely, there exist infinitely many triangular words in the infinite sequence $(\xi_n, n \in \mathbb{Z})$. This result (and its proof) should be compared and contrasted with Lemma 2.4.

**Lemma 3.25.** Let $(\xi_n)_{n \in \mathbb{Z}}$ be an i.i.d. sequence with $\mathbb{E}\xi_0 < \infty$. Then the law of the random set

$$ \mathcal{R} = \{k \in \mathbb{Z} : (\cdots \xi_{k+2} \xi_{k+1} \xi_k) \in \mathcal{T}_{\infty}\}. \qquad (3.15) $$

is invariant under translations and $\mathcal{R} \cap [0, \infty)$ and $\mathcal{R} \cap (-\infty, 0]$ are infinite sets a.s.

*Proof.* The invariance by translation is obvious. Observe that

$$ \mathbb{P}((\cdots \xi_{k+2} \xi_{k+1} \xi_k) \in \mathcal{T}_{\infty}) = \mathbb{P}(\xi_k \le 1, \xi_{k+1} \le 2, \xi_{k+2} \le 3, \dots) = \prod_{j=1}^{\infty} (1 - \mathbb{P}(\xi_0 > j)). $$

According to the assumptions (3.14) we have $\mathbb{P}(\xi_0 = 1) > 0$ and hence all terms in this product are positive. We also have $\sum_{j=0}^{\infty} \mathbb{P}(\xi_0 > j) = \mathbb{E}\xi_0 < \infty$ and so the whole product is positive. As a result, $\mathcal{R}$ possesses a positive density on $\mathbb{Z}$. Just as in Lemma 2.4 we conclude that $\mathcal{R}$ contains infinitely many positive and infinitely many negative integers a.s. $\square$

We write $\mathcal{R} = \{T_0, T_{\pm 1}, T_{\pm 2}, \dots\}$ and arrange the indexing so that

$$ \cdots < T_{-1} < T_0 \le 0 < T_1 < \cdots $$

For each $n$ in $\mathbb{Z}$, let $s(n)$ be the unique (random) integer such that $T_{s(n)} \le n < T_{s(n)+1}$.

**Proof of Theorem 3.23.** We shall construct $(Y_n)$ as a measurable function of $(\xi_n)$ by constructing $\Pi_k(Y_n)$ for all $k$. Fix $n \in \mathbb{Z}$ and $k \ge 1$. Consider the selection word

$$ \xi_n \cdots \xi_{T_{s(n)-k+1}}. $$

Since $T_{s(n)-k+1} \in \mathcal{R}$, the word $\xi_n \cdots \xi_{T_{s(n)-k+1}}$ is triangular. Note that the number of elements of $\mathcal{R}$ in the interval $[T_{s(n)-k+1}, T_{s(n)}]$ is $k$. For each $T_j$ we have $\xi_{T_j} = 1$, by the definition of $\mathcal{R}$. Hence the selection word $\xi_n \cdots \xi_{T_{s(n)-k+1}}$ contains at least $k$ letters equal to 1. Thus by Lemma 3.19 it is $k$-coupling. Hence the vector $\Pi_k(\xi_n \cdots \xi_{T_{s(n)-k+1}}(X))$ is the same for all $X \in \mathbb{S}$.

Fix an $X$ and define the rightmost $k$ bins of $Y_n$ to be equal to this vector. This definition is consistent for different values of $k$, hence defines $Y_n$ up to a global shift. Requiring $F(Y_n) = 0$ yields a unique definition of $Y_n$ a.s. By construction, for every $n \in \mathbb{Z}$, $Y_n \in \mathcal{F}_n$ and the sequence $(Y_n)_{n \in \mathbb{Z}}$ satisfies (3.13). Conversely, any sequence of configurations in $\mathbb{S}_0$ satisfying (3.13) has to coincide with the sequence $(Y_n)$ constructed above. $\square$

It follows from Theorem 3.23 that every finite-dimensional marginal of the pinned IBM started at time 0 converges and even gets coupled to the corresponding marginal of the stationary version.
**Corollary 3.26 (Coupling-convergence).** Let $(\xi_n)_{n \in \mathbb{Z}}$ be an i.i.d. sequence of law $\mu$ satisfying conditions (3.14). Let $\hat{X}_0 \in \mathbb{S}_0$ and let $(\hat{X}_n)_{n \ge 0}$ be a pinned IBM($\mu$) constructed using the variables $\xi_n, n \ge 1$. Let $(Y_n)$ be the stationary version of the pinned IBM. Then for every $k \ge 1$, there exists $n_k \ge 1$ such that for every $n \ge n_k$, we have

$$ \Pi_k(\hat{X}_n) = \Pi_k(Y_n). \qquad (3.16) $$

*Proof.* Let $k \ge 1$ and set $n_k = T_k$ which is finite a.s. If $n \ge n_k$, we have $\vartheta_1(\xi_n \cdots \xi_1) \ge k$ and (3.16) follows from Lemma 3.19. $\square$

A second consequence of Theorem 3.23 is a simple expression for the speed $v_\mu$ in terms of the stationary version of the pinned IBM($\mu$).

**Corollary 3.27.** Let $(Y_n)$ be the stationary version of the pinned IBM constructed using the i.i.d. variables $(\xi_n)_{n \in \mathbb{Z}}$ of law $\mu$ satisfying conditions (3.14). Then

$$ v_{\mu} = \mathbb{P}(\xi_1 \le Y_0(0)). \qquad (3.17) $$

*Proof.* Let $(X_n)$ be an IBM constructed using the random variables $(\xi_n, n \ge 0)$ such that $X_0 = Y_0(0)$ a.s. We recall that

$$ v_{\mu} = \lim_{n \to \infty} \frac{F(X_n)}{n} \quad \text{a.s.} $$

Therefore, using the dominated convergence theorem, we have

$$ v_{\mu} = \lim_{n \to \infty} \frac{\mathbb{E}(F(X_n))}{n} = \lim_{n \to \infty} \frac{1}{n} \sum_{j=1}^{n} \mathbb{E}(F(X_j) - F(X_{j-1})) = \lim_{n \to \infty} \frac{1}{n} \sum_{j=1}^{n} \mathbb{P}(\xi_j \le L(X_{j-1})), $$

using (3.6) (recall that $L(X)$ is the number of balls in the rightmost non-empty bin of $X$). Then, as $L(X_n) = L(Y_n) = Y_n(0)$ a.s. for all $n \in \mathbb{N}$, we have

$$ \mathbb{P}(\xi_j \le L(X_{j-1})) = \mathbb{P}(\xi_j \le Y_{j-1}(0)) = \mathbb{P}(\xi \le Y_0(0)), $$

using that $Y$ is a stationary adapted sequence. This result immediately implies (3.17). $\square$

## 3.5 New expressions for the speed

Using Corollary 3.27, we deduce in this section new formulas for the speed $v_\mu$ as infinite sums over some special classes of selection words. In constructing the stationary regime, we were interested in renovation events, that is events that resulted in decoupling the future from the past. In computing the speed, we are merely interested in whether the front advances or not at time 1.

Words that manage to advance the front of any configuration at their last selection index are called good. Words that never do this are called bad. Bad is not the opposite of good: there are selection words that sometimes move the front at the last step and sometimes do not. In what follows recall that, for integers $\xi, \eta, \dots$ and $X \in \mathbb{S}$, the symbol $\eta\xi X$ stands for $\Phi_\eta(\Phi_\xi(X))$.

**Definition 3.28 (Good/bad words).** Define the following sets of selection words:

$$ \mathcal{G} := \{\alpha_\ell \cdots \alpha_1 \in \mathcal{U} : \forall X \in \mathbb{S} F(\alpha_\ell \alpha_{\ell-1} \cdots \alpha_1 X) = F(\alpha_{\ell-1} \cdots \alpha_1 X) + 1\}, $$

$$ \mathcal{B} := \{\alpha_\ell \cdots \alpha_1 \in \mathcal{U} : \forall X \in \mathbb{S} F(\alpha_\ell \alpha_{\ell-1} \cdots \alpha_1 X) = F(\alpha_{\ell-1} \cdots \alpha_1 X)\}, $$

$$ \text{and } \mathcal{A} := \mathcal{U} \setminus (\mathcal{G} \cup \mathcal{B}). $$

We call the words in $\mathcal{G}$ good, those in $\mathcal{B}$ bad, and those in $\mathcal{A}$ ambivalent.

*Example 3.29.* The word 1 is good. More generally every word $\alpha_\ell \cdots \alpha_1$ ending with $\alpha_\ell = 1$ is good.

The word (2, 1) is bad. To see this, let $X$ have $F(X) = 0$. We observe that $1X = X + \delta_1$ and $2(1X) = X + 2\delta_1$ as the second ball of $1X$ is at bin 0. Hence, $F(2(1X)) = F(1X) = 1$. As this relation holds regardless of $X$, the word (2, 1) is bad.

The word 2 is ambivalent. Indeed, if $X$ has $F(X) = 0$ and $X(0) = 1$ then $2X = X + \delta_0$, so $F(2X) = 0$, but if $X(0) \ge 2$ then $2X = X + \delta_1$, so $F(2X) = 1$.
Coupling words can be used to generate a large class of good and bad words. More precisely, the following result holds.

**Lemma 3.30.** If $\alpha \in C_1$ and $\xi \in \mathbb{N}$ then either $\xi\alpha \in \mathcal{G}$ or $\xi\alpha \in \mathcal{B}$. In particular, every triangular word is either good or bad.

*Proof.* Since $\alpha$ is in $C_1$, the front of $\alpha X$ contains exactly the same number of balls as the front of $\alpha Y$ for any configuration $Y$; see forthcoming Definition 3.15. Let $b$ be this number of balls. Then $F(\xi\alpha X) = F(\alpha X) + 1$ if and only if $\xi \le b$. Since neither $\xi$ nor $b$ depend on $X$, it follows that the word is good if $\xi \le b$, or bad otherwise.

By Lemma 3.19 every triangular word is in $C_1$. Hence the previous argument applies. $\square$

To apply Corollary 3.27 to compute the speed $v_\mu$ of the IBM($\mu$), we have to detect, based on the sequence $(\xi_n, n \le 1)$, if the front of $Y$ will increase at time 1. To this end, we introduce the notion of minimal good and bad words.

**Definition 3.31** (V-minimal words). For every $\mathcal{V} \subset \mathcal{U}$ define the set of $\mathcal{V}$-minimal words as the set of words in $\mathcal{V}$ with no strict suffix belonging to $\mathcal{V}$, i.e.

$$ \mathcal{V}_{\min} := \{\alpha = \alpha_{\ell} \cdots \alpha_1 \in \mathcal{V} : \alpha_{\ell} \cdots \alpha_i \notin \mathcal{V}, i = 2, \dots, \ell\}. $$

Observe that if $\alpha \in \mathcal{V}$ satisfies $|\alpha| = \min\{|\beta|, \beta \in \mathcal{V}\}$, then $\alpha \in \mathcal{V}_{\min}$.

*Example 3.32.* First consider $\mathcal{V} = \mathcal{T}$ the set of triangular words. We see that $(2, 2, 1) \in \mathcal{T}_{\min}$ (because $(2, 2, 1)$ is in $\mathcal{T}$ but $(2, 2)$ and $(2)$ are not in $\mathcal{T}$). On the other hand, the triangular word $(2, 2, 1, 3, 2, 1)$ is not in $\mathcal{T}_{\min}$ because its suffix $(2, 2, 1)$ is triangular.

Let us now consider minimal good and bad words. We have obviously $1 \in \mathcal{G}_{\min}$, but $(1, 1) \notin \mathcal{G}_{\min}$. Similarly, we observe that $(3, 2, 1) \in \mathcal{B}$ as $3(2(1X)) = X + 3\delta_1$ and $2(1X) = X + 2\delta_1$, but both (3) and (3, 2) are ambivalent words (hence not bad). Therefore $(3, 2, 1) \in \mathcal{B}_{\min}$.

We next observe that

$$ (\mathcal{G} \cup \mathcal{B})_{\min} = \mathcal{G}_{\min} \cup \mathcal{B}_{\min}. \qquad (3.18) $$

This follows from the fact that a suffix of a good word cannot be bad and a suffix of a bad word cannot be good.

**Definition 3.33** (Weight of a word). The weight of $\alpha = (\alpha_\ell, \dots, \alpha_1) \in \mathcal{U}$ under the probability measure $\mu$ is defined to be

$$ w_{\mu}(\alpha) := \prod_{i=1}^{\ell} \mu(\alpha_i). $$

We are now ready to explain how to get new formulas for the speed $v_\mu$.

**Proposition 3.34.** Let $\mu$ be any probability measure on $\mathbb{N}$ and $(\xi_n)_{n \in \mathbb{Z}}$ a sequence of i.i.d. random variables with law $\mu$. Let $\mathcal{V}$ be a class of selection words (recalling that $\emptyset$ is not a selection word) and define

$$ T_{\mathcal{V}}^* := \sup\{-\infty < \ell \le 1 : \xi_1 \xi_0 \cdots \xi_\ell \in \mathcal{V}\}. $$

Assume that

(i) $\mathcal{V} \subset \mathcal{G} \cup \mathcal{B}$ ($\mathcal{V}$ contains no ambivalent words)

(ii) $\mathbb{P}(T_{\mathcal{V}}^* > -\infty) = 1$.

Then

$$ v_{\mu} = \sum_{\alpha \in \mathcal{V}_{\min} \cap \mathcal{G}} w_{\mu}(\alpha) = 1 - \sum_{\alpha \in \mathcal{V}_{\min} \cap \mathcal{B}} w_{\mu}(\alpha). \qquad (3.19) $$

*Proof.* Fix the set $\mathcal{V} \subset \mathcal{G} \cup \mathcal{B}$ and let $T = T_{\mathcal{V}}^*$ for brevity. Let $(Y_n)$ be the stationary version of the pinned IBM constructed from $(\xi_n)_{n \in \mathbb{Z}}$. From Corollary 3.27 we have $v_\mu = \mathbb{P}(\xi_1 \le Y_0(0))$. Observe that

$$ \{\xi_1 \le Y_0(0)\} = \{F(\xi_1 \xi_0 \cdots \xi_T Y_{T-1}) - F(\xi_0 \cdots \xi_T Y_{T-1}) = 1\}. \qquad (3.20) $$
Since $\xi_1\xi_0\cdots\xi_T \notin \mathcal{A}$, it follows that

$$F(\xi_1\xi_0\cdots\xi_T Y_{T-1}) - F(\xi_0\cdots\xi_T Y_{T-1}) = F(\xi_1\xi_0\cdots\xi_T X) - F(\xi_0\cdots\xi_T X) \text{ for all } X \in \mathbb{S}.$$

And so the event of (3.20) is equal to

$$\{\xi_1\xi_0\cdots\xi_T \in \mathcal{G}\}.$$

On the other hand, $\xi_1\xi_0\cdots\xi_T \in \mathcal{V}$ but $\xi_1\xi_0\cdots\xi_{T+j} \notin \mathcal{V}$ if $j > 0$. Hence

$$\xi_1\xi_0\cdots\xi_T \in \mathcal{V}_{\min} \text{ a.s.}$$

We conclude that

$$v_{\mu} = \mathbb{P}(\xi_1\xi_0\cdots\xi_T \in \mathcal{V}_{\min} \cap \mathcal{G}) = \sum_{\alpha \in \mathcal{V}_{\min} \cap \mathcal{G}} \mathbb{P}(\xi_1\xi_0\cdots\xi_T = \alpha). \quad (3.21)$$

The length of the word $\xi_1\xi_0\cdots\xi_T$ is $2-T$, so

$$\begin{aligned} \mathbb{P}(\xi_1\xi_0\cdots\xi_T = \alpha) &= \mathbb{P}(\xi_1\xi_0\cdots\xi_{2-|\alpha|} = \alpha, T = 2-|\alpha|) \\ &= \mathbb{P}(\xi_1\xi_0\cdots\xi_{2-|\alpha|} = \alpha) = \mathbb{P}(\xi_1\cdots\xi_{|\alpha|} = \alpha) = \mu(\alpha_1)\cdots\mu(\alpha_{|\alpha|}) = w_{\mu}(\alpha), \end{aligned}$$

where the second equality follows from the fact that we calculate this probability for $\alpha \in \mathcal{V}_{\min}$. Thus the first identity in (3.19) is proved. The second identity follows from $\mathcal{V}_{\min} \setminus (\mathcal{V}_{\min} \cap \mathcal{G}) = \mathcal{V}_{\min} \cap \mathcal{B}$. $\square$

By taking special choices for the class $\mathcal{V}$ we obtain the following useful formulas when $\mu$ satisfies assumptions (3.14):

**Theorem 3.35** (speed as a sum over words, [80]). Let $\mu$ be a probability measure on $\mathbb{N}$ satisfying assumptions (3.14). Then

$$v_{\mu} = \sum_{\alpha \in \mathcal{T}_{\min} \cap \mathcal{G}} w_{\mu}(\alpha) \quad (3.22)$$

$$v_{\mu} = \sum_{\alpha \in \mathcal{G}_{\min}} w_{\mu}(\alpha). \quad (3.23)$$

**Remark 3.36.** As observed in Proposition 3.34, the number of possible formulas for the speed $v_{\mu}$ is equal to the number of subset of $\mathcal{V} \subset \mathcal{G} \cup \mathcal{B}$ such that $T_{\mathcal{V}}^* > -\infty$ a.s. However, the two formulas (3.22) and (3.23) will be the more useful for our purpose. It should be apparent that setting $\mathcal{V} = \mathcal{G} \cup \mathcal{B}$ gives a formula such that $|T_{\mathcal{V}}^*|$ is minimal. However, for an algorithmic purpose, it is much easier to verify that a word is triangular than to verify that it is not ambivalent. Therefore, (3.22) is particularly efficient when estimating $v_{\mu}$ via Monte-Carlo methods, see forthcoming Section 10.

**Proof.** We first apply Proposition 3.34 with $\mathcal{V} = \mathcal{T}$ and make sure that (i) and (ii) in that proposition hold. By Lemma 3.30 we have $\mathcal{T} \subset \mathcal{G} \cup \mathcal{B}$, so (i) holds. Recall that $T_{\mathcal{T}}^* = \sup\{\ell \le 1 : (\xi_1\xi_0\xi_{-1}\cdots\xi_{\ell+1}\xi_{\ell}) \in \mathcal{T}\}$. By Lemma 3.25 all the points of $\mathcal{R}$ are finite in absolute value a.s. Hence there are points $-\infty < \ell \le 0$ such that $(\cdots\xi_{\ell+1}\xi_{\ell}) \in \mathcal{T}_{\infty}$. Any such point certainly satisfies $(\xi_1\xi_0\cdots\xi_{\ell+1}\xi_{\ell}) \in \mathcal{T}$, so $T_{\mathcal{T}}^* > -\infty$ a.s., therefore (ii) holds as well. As a consequence (3.22) follows from (3.19).

We next apply Proposition 3.34 with $\mathcal{V} = \mathcal{G} \cup \mathcal{B}$, so (i) holds immediately. Moreover, we have $T_{\mathcal{G}\cup\mathcal{B}}^* = \sup\{\ell \le 1 : \xi_1\cdots\xi_{\ell} \in \mathcal{G} \cup \mathcal{B}\} \ge T_{\mathcal{T}}^*$ as $\xi_1\xi_0\cdots\xi_{T_{\mathcal{T}}^*} \in \mathcal{G} \cup \mathcal{B}$, hence $T_{\mathcal{G}\cup\mathcal{B}}^* > -\infty$ a.s. Additionally, thanks to (3.18) we have

$$(\mathcal{G} \cup \mathcal{B})_{\min} \cap \mathcal{G} = (\mathcal{G}_{\min} \cup \mathcal{B}_{\min}) \cap \mathcal{G} = (\mathcal{G}_{\min} \cap \mathcal{G}) \cup (\mathcal{B}_{\min} \cap \mathcal{G}) = \mathcal{G}_{\min} \cup \emptyset = \mathcal{G}_{\min},$$

which yields to (3.23), by using the first equality of (3.19) with $\mathcal{V} = \mathcal{G} \cup \mathcal{B}$. $\square$

**Remark 3.37.** Note that there is no inclusion relation between $\mathcal{T}_{\min} \cap \mathcal{G}$ and $\mathcal{G}_{\min}$. For example

$$(2, 4, 2, 1) \in \mathcal{G}_{\min} \setminus (\mathcal{T}_{\min} \cap \mathcal{G}) \text{ and } (2, 4, 2, 1, 1) \in (\mathcal{T}_{\min} \cap \mathcal{G}) \setminus \mathcal{G}_{\min}.$$

**Remark 3.38.** In [80], Theorem 3.23 is showed to hold for any infinite bin model, under the condition that $\mu$ is not a Dirac mass. As a result, Corollary 3.27 also holds without any assumption on the first of $\mu$. In fact, [80, Theorem 1.2] states that (3.23) holds for any non-degenerated measure $\mu$. However, observe that (3.22) does not necessarily holds, as $\mathbb{E}(\xi) < \infty$ is a necessary condition for the existence of infinite triangular words.
# 4 Analytic properties of the asymptotic length of the longest path

In this section we use the results of the previous section on the infinite bin model to derive properties of the asymptotic length of the longest path in Barak-Erdős graphs by coupling the latter to an infinite bin model in the case when $\mu$ is a geometric distribution. Let $\mu_p(k) = (1-p)^{k-1}p$, $k \in \mathbb{N}$. Let $(X_n)$ be the Markov process constructed in Section 2.2 from $\vec{G}(\mathbb{Z}, p)$. Then $(X_n)$ is an IBM($\mu_p$). Looking at (2.10) we see that

$$F(X_n) = L_n, \qquad (4.1)$$

where $L_n$ is the maximum of all paths in $\vec{G}(\mathbb{Z}, p)$ with endpoints in $[1, n]$. By Corollary 2.8, we have that $L_n/n \to C(p)$ a.s. whereas Theorem 3.5 shows that $F(X_n)/n \to v_{\mu_p}$ a.s. We conclude that

$$C(p) = v_{\mu_p}. \qquad (4.2)$$

We now make use of the results and formula obtained in Section 3.5 to prove the analyticity of $C$ on $(0, 1]$ in Section 4.2, and to express its power series expansion in Section 4.3. But first, we rephrase the results of Section 3.5 for a geometrically distributed infinite bin model.

## 4.1 First formulas for $C$

Using Corollary 3.27 and the geometric distribution of $\xi$, we observe that $C(p)$ can be computed rather explicitly in terms of the stationary version $Y$ of the IBM($\mu_p$).

**Corollary 4.1.** Let $0 < p \le 1$, we denote by $R_p$ a random variable distributed as the content of the front bin in the stationary IBM($\mu_p$). Then

$$C(p) = 1 - \mathbb{E}((1-p)^{R_p}). \qquad (4.3)$$

*Proof.* Let $\xi$ be a random variable with geometric distribution $\mu_p$ which is independent of the stationary IBM($\mu_p$) $Y$. It follows from Corollary 3.27 that

$$v_{\mu_p} = \mathbb{P}(\xi \le Y_0(0)) = 1 - \mathbb{P}(\xi > R_p).$$

Conditioning on the value of $R_p$ and using formula (4.2) yields formula (4.3). $\square$

We also apply Theorem 3.35 to obtain formulas for $C(p)$ as the sum of weights of well-chosen set of words. To this end we need the notion of height of a word.

**Definition 4.2 (Height).** The height of $\alpha = \alpha_\ell \cdots \alpha_1 \in \mathcal{U}$ is defined as

$$H(\alpha) := \sum_{i=1}^{\ell} (\alpha_i - 1) = \sum_{i=1}^{\ell} \alpha_i - |\alpha|.$$

With this notation, we observe that

$$w_{\mu_p}(\alpha) = \prod_{j=1}^{\alpha} \mu_p(\alpha_j) = p^{|\alpha|} (1-p)^{H(\alpha)}.$$

We immediately obtain the following restatement of Theorem 3.35 for the special case $\mu = \mu_p$.

**Theorem 4.3.** Let $0 < p \le 1$. Then

$$C(p) = \sum_{\alpha \in \mathcal{T}_{\min} \cap \mathcal{G}} p^{|\alpha|} (1-p)^{H(\alpha)} \qquad (4.4)$$

$$C(p) = \sum_{\alpha \in \mathcal{G}_{\min}} p^{|\alpha|} (1-p)^{H(\alpha)}. \qquad (4.5)$$
**Precise bounds.** We use Theorem 3.35 to obtain precise bounds on $C(p)$. Let $k \ge 1$ and let $0 < p \le 1$. Recalling the notation $\xi_k^j = \xi \mathbf{1}_{\xi \le k} + j \mathbf{1}_{\xi > k}$ from Section 3.2, and assuming that $\xi$ has geometric law $\mu_p$, we let $\mu_{p,k}^j$ be the law of $\xi_k^j$.

Recall that IBM($\mu_{p,k}^\infty$) bounds IBM($\mu$) from below, and that IBM($\mu_{p,k}^k$) bounds IBM($\mu$) from above, in the sense of (3.7). Denote by $\underline{C}_k(p)$, $\bar{C}_k(p)$, the speeds of the IBM($\mu_{p,k}^\infty$), IBM($\mu_{p,k}^k$), respectively. We then have

$$ \forall p \in [0, 1], \quad \underline{C}_k(p) \le C(p) \le \bar{C}_k(p). \qquad (4.6) $$

As the IBM($\mu_{p,k}^\infty$) and the IBM($\mu_{p,k}^k$) can be constructed using Markov chains on a finite state space, with transition probabilities that are polynomial functions of $p$, their speeds $\underline{C}_k(p)$ and $\bar{C}_k(p)$ are rational functions in $p$ that can be computed explicitly. For example, with $k = 3$, performing such computations yields

$$ \begin{aligned} \underline{C}_3(p) &= \frac{p(p^2 - 3p + 3)^2(p^4 - 6p^3 + 14p^2 - 16p + 8)}{3p^6 - 26p^5 + 96p^4 - 196p^3 + 235p^2 - 158p + 47} \\ \bar{C}_3(p) &= \frac{p^3 - 2p^2 + p - 1}{p^5 - 4p^4 + 8p^3 - 9p^2 + 6p - 3}. \end{aligned} $$

It is worth noting that (3.9) implies that

$$ 0 \le \bar{C}_k(p) - \underline{C}_k(p) \le (1-p)^k, $$

therefore the sequences of functions $(\bar{C}_k(p))_{k \ge 1}$ and $(\underline{C}_k(p))_{k \ge 1}$ converge exponentially fast to $C(p)$, uniformly on every interval of the form $[\varepsilon, 1]$ with $\varepsilon > 0$. As we will see in Section 4.3, this convergence is so fast when $p$ is close to 1 that they provide many coefficients of the power series expansion of $C(p)$ at $p = 1$. In fact, comparing the asymptotic expansions of $\underline{C}_3$ and $\bar{C}_3$ around $p = 1$ already give

$$ C(p) = 1 - (1-p) + (1-p)^2 - 3(1-p)^3 + 7(1-p)^4 + O((1-p)^5) \quad \text{as } p \to 1. $$

<figure><img src="image_5.png" /><figcaption>Figure 5: Successive bounds on the function $C$ (in red) by $\bar{C}_k$ (in orange) and $\underline{C}_k$ (in blue). Observe that if these bounds appear very sharp for $p$ close to 1, the approximation (in particular the upper bound) remains quite crude for $p$ close to 0.</figcaption></figure>

**Remark 4.4.** Writing the balance equations for the stationary version $Y$ of the IBM($\mu_p$), Foss and Konstantopoulos [44] obtained a different upper and lower bound for $C(p)$. This result on a more precise upper bound for $C(p)$ for $p$ close to 0, however this bound still does not allow the capture of the asymptotic behavior of $C$ as $p \to 0$.

## 4.2 Analyticity of $C$

Using the formulas obtained above for the function $C$ resulting from the coupling with the infinite bin model, we can show that the function $C$ is analytic on $(0, 1]$.
**Theorem 4.5.** The function $p \mapsto C(p)$ is analytic on $\in (0, 1]$.

*Proof.* For every $p, q \ge 0$ define

$$D(p, q) = \sum_{\alpha \in \mathcal{T}_{\min} \cap \mathcal{G}} p^{\alpha} q^{H(\alpha)}. \qquad (4.7)$$

By formula (4.4), we have that $C(p) = D(p, 1-p)$ for every $0 < p \le 1$. Let $0 < p_0 \le 1$. The rest of the proof consists in the construction of $(p', q')$ such that $p' > p_0$, $q' > 1-p_0$ and the series (4.7) for $D(p', q')$ converges. This will imply the normal convergence of $D(p, q)$ on $[0, p'] \times [0, q']$, therefore of the series of derivatives of (4.4) around $p_0$, which in turn will imply the analyticity of $C$ in a neighborhood of $p_0$.

Let $0 < p \le 1$ and let $(\xi_n)_{n \in \mathbb{Z}}$ be i.i.d. of law $\mu_p$. We claim that, for all $r > 1$,

$$D(rp, 1-p) \le \mathbb{E}(r^{2-T_0}),$$

where $T_0$ is the largest nonpositive point of the set $\mathcal{R}$ defined in (3.15). To see this, recall the time $T_T^* = \sup\{-\infty \le t \le 1 : \xi_1\xi_0 \cdots \xi_t \in \mathcal{T}\}$ and recall that $\mathbb{P}(T_T^* > -\infty) = 1$ (as in the proof of Theorem 3.35) and that $\mathbb{P}(T_T^* \ge T_0) = 1$. For brevity, set $T = T_T^*$. Arguing as in (3.21) we have

$$\begin{aligned}
\mathbb{E}(r^{2-T_0}) &\ge \mathbb{E}(r^{2-T}) \ge \mathbb{E}(r^{2-T}; \xi_1\xi_0 \cdots \xi_T \in \mathcal{T}_{\min} \cap \mathcal{G}) = \sum_{\alpha \in \mathcal{T}_{\min} \cap \mathcal{G}} \mathbb{E}(r^{2-T}; \xi_1\xi_0 \cdots \xi_T = \alpha) \\
&= \sum_{\alpha \in \mathcal{T}_{\min} \cap \mathcal{G}} \mathbb{E}\left(r^{\lvert\alpha\rvert}; \xi_1\xi_0 \cdots \xi_{2-\lvert\alpha\rvert} = \alpha, 2-T = \lvert\alpha\rvert\right) = \sum_{\alpha \in \mathcal{T}_{\min} \cap \mathcal{G}} r^{\lvert\alpha\rvert} \mathbb{P}(\xi_1\xi_0 \cdots \xi_{2-\lvert\alpha\rvert} = \alpha) \\
&= \sum_{\alpha \in \mathcal{T}_{\min} \cap \mathcal{G}} r^{\lvert\alpha\rvert} p^{\alpha_1} (1-p)^{\alpha_1-1} \cdots p^{\alpha_\ell} (1-p)^{\alpha_\ell-1} = D rp, 1-p).
\end{aligned}$$

We now observe that $|T_0|$ has some finite exponential moments. Indeed, $|T_0|$ can be seen as the first return time to 1 of the Markov chain defined by $Z_0 = 1$ and $Z_{n+1} = \max(Z_n - 1, \xi_{1-n})$. This Markov chain can straightforwardly be dominated by a downward-skip free random walk with negative drift, yielding the existence of these exponential moments. We refer to [80, p14, proof of Theorem 1.1] for extra details on this proof.

As a consequence, there exists $r > 1$ such that for all $\frac{p_0}{2} < p < 1$, we have $\mathbb{E}(r^{|T_0|}) < \infty$. Choose $p$ such that $\max(\frac{p_0}{2}, \frac{p_0}{r}) < p < p_0$. Then setting $p' = rp$ and $q' = 1-p$ we have that $p' > p_0$, $q' > 1-p_0$ and the series (4.7) for $D(p', q')$ converges. $\square$

*Remark 4.6.* We observe that $C'(0) = e$ and $C''(0) = \infty$ (see forthcoming Section 5). Therefore the analyticity of $C$ cannot be extended up to $p = 0$.

## 4.3 Power series expansion of $C(p)$ around $p = 1$

We use in this section Formula (4.5) to prove that the power series expansion of $p \mapsto C(p)$ around $p = 1$ only consists of integer coefficients. We write $q = 1-p$, and expand $C(1-q)$ as a power series in the variable $q$. Recall that $H(\alpha) = \sum_{i=1}^{\alpha} (\alpha_i - 1)$ is the “height” of the word $\alpha$. We begin with the following observation.

**Lemma 4.7.** For every $\alpha \in \mathcal{G}_{\min}$, we have $|\alpha| \le H(\alpha) + 1$.

*Proof.* Let us assume that there exists $\alpha \in \mathcal{G}_{\min}$ such that $|\alpha| > H(\alpha) + 1$. We obtain a contradiction by showing that $\alpha$ will possess a strict suffix in $\mathcal{T}$ (hence in $\mathcal{G} \cup \mathcal{B}$), which violates the assumption that $\alpha$ is $\mathcal{G}$-minimal.

Let $S(k) := \sum_{i=1}^k (\alpha_i - 2)$, $1 \le k \le |\alpha|$, we remark that $S(|\alpha|) = H(\alpha) - |\alpha| < -1$. We denote by $n = \max\{1 \le k \le |\alpha| : S(k) < -1\}$, and remark that $S(k) \le -2$ for all $n \le k \le |\alpha|$. In particular, as $S(1) = \alpha_1 - 2 \ge -1$, we have $n \ge 2$.

As $\alpha_k \ge 1$, we have $S(k) - S(k-1) \ge -1$ for all $2 \le k \le |\alpha|$. Therefore, $S(n) = -2$ and for all $k \le n - |\alpha|$, we have $S(n+k) \ge -k-2$. As a result, $\alpha_{n+k} = 2 + S_{n+k} - S_{n+k-1} \le 2 - 2 - ((-k-1) - 2) \le k+1$. As a result, we now have proved that $\alpha_{|\alpha|} \cdots \alpha_n$ is a triangular word which is a strict suffix of $\alpha$, completing the proof by contradiction as mentioned above. $\square$
We adopt the convention that for $\ell \in \mathbb{N}$ and $k \in \mathbb{Z}$, the binomial coefficient $\binom{\ell}{k}$ vanishes whenever $k < 0$ or $k > \ell$. We now use (4.5), and show that the power series expansion obtained around $p = 1$ by rearranging its terms has positive radius of convergence, which completes the proof of the main result of the section.

**Theorem 4.8 ([79]).** For every $n \ge 0$, define

$$a_n := \sum_{\alpha \in \mathcal{G}_{\min}} \binom{|\alpha|}{n - H(\alpha)} (-1)^{H(\alpha)}. \quad (4.8)$$

Then for every $0 \le q < \frac{\sqrt{2}-1}{2}$ we have

$$C(1-q) = \sum_{n \ge 0} (-1)^n a_n q^n. \quad (4.9)$$

The fact that $a_n$ introduced in (4.8) is well-defined for all $n \in \mathbb{Z}_+$ is a consequence of Lemma 4.7. Indeed, for every $h \ge 0$ and $\ell \ge 1$ define

$$\mathcal{U}_{\ell}^{h} := \{\alpha \in \mathcal{U}, |\alpha| = \ell \text{ and } H(\alpha) = h\}.$$

We can consider this as the number of arrangements of $h$ unlabelled balls into $\ell$ labelled boxes. Therefore, its cardinal is given by

$$|\mathcal{U}_{\ell}^{h}| = \binom{h + \ell - 1}{\ell - 1}. \quad (4.10)$$

Any word $\alpha$ having a non-zero contribution in the sum defining $a_n$ must satisfy $H(\alpha) \le n$ and $|\alpha| \le H(\alpha) + 1 \le n + 1$, where the latter condition follows from Lemma 4.7. An equivalent formulation of (4.8) is

$$a_n = \sum_{h=0}^{n} \sum_{\ell=1}^{n+1} (-1)^h \binom{\ell}{n-h} |\mathcal{G}_{\min} \cap \mathcal{U}_{\ell}^{h}| \quad (4.11)$$

which is in particular clearly finite.

**Proof of Theorem 4.8.** Let $n \ge 0$ and let $0 \le q < 1$. Rewrite formula (4.5) as

$$\begin{align}
C(1-q) &= \sum_{h \ge 0} \sum_{\ell=1}^{h+1} \sum_{\alpha \in \mathcal{G}_{\min} \cap \mathcal{U}_{\ell}^{h}} q^{h} (1-q)^{\ell} = \sum_{h \ge 0} \sum_{\ell=1}^{h+1} |\mathcal{G}_{\min} \cap \mathcal{U}_{\ell}^{h}| \sum_{i=0}^{\ell} \binom{\ell}{i} (-1)^{i} q^{i+h} \nonumber \\
&= \sum_{h \ge 0} \sum_{n \ge 0} \sum_{\ell=1}^{h+1} |\mathcal{G}_{\min} \cap \mathcal{U}_{\ell}^{h}| \binom{\ell}{n-h} (-1)^{n-h} q^{n}, \tag{4.12}
\end{align}$$

For all $q$ such that (4.12) absolutely converges, we can apply Fubini's theorem to obtain that (4.9) holds, where $a_n$ given by (4.11) or equivalently by (4.8). Taking absolute values inside the sums of (4.12) we obtain

$$I_q := \sum_{h \ge 0} \sum_{n \ge 0} \sum_{\ell=1}^{h+1} |\mathcal{G}_{\min} \cap \mathcal{U}_{\ell}^{h}| \binom{\ell}{n-h} q^n = \sum_{h \ge 0} \sum_{\ell=1}^{h+1} |\mathcal{G}_{\min} \cap \mathcal{U}_{\ell}^{h}| q^h (1+q)^{\ell}. \quad (4.13)$$

By (4.10), we have

$$I_q \le (1+q) \sum_{h \ge 0} \sum_{\ell=0}^{h} \binom{h+\ell}{\ell} q^h (1+q)^{\ell}.$$

We use a random walk representation to find some values of $q$ for which this is finite. Let $(S_N)_{N \ge 0}$ be a random walk on $\mathbb{Z}$ starting at 0 and taking a step $+1$ (resp. $-1$) with probability $\frac{q}{1+2q}$ (resp. $\frac{1+q}{1+2q}$). Performing the change of variables $N = h + \ell$, we have

$$\sum_{h \ge 0} \sum_{\ell=0}^{h} \binom{h+\ell}{\ell} q^h (1+q)^{\ell} = \sum_{N \ge 0} (1+2q)^N \mathbb{P}(S_N \le 0). \quad (4.14)$$
Applying Chernoff's bound, we get

$$ \mathbb{P}(S_N \le 0) \le \inf_{t \ge 0} (\mathbb{E}(e^{-tS_1}))^N \le \inf_{t \ge 0} \left( \frac{qe^t + (1+q)e^{-t}}{1+2q} \right)^N \le \left( \frac{2\sqrt{q(1+q)}}{1+2q} \right)^N . $$

Thus, when $0 \le q < \frac{\sqrt{2}-1}{2}$, the series in (4.14) converges and the series in (4.12) converges absolutely. □

*Remark 4.9.* Lemma 4.7 and Theorem 4.8 hold true with the same proofs if one replaces $\mathcal{G}_{\min}$ by $\mathcal{T}_{\min} \cap \mathcal{G}$, thus for every $n \ge 0$ we also have the formula

$$ a_n = \sum_{\alpha \in \mathcal{T}_{\min} \cap \mathcal{G}} \binom{|\alpha|}{n - H(\alpha)} (-1)^{H(\alpha)}. \quad (4.15) $$

The power series expansion being unique, we observe that (4.8) and (4.15) give the same values.

*Remark 4.10.* Note that the radius of convergence of $\frac{\sqrt{2}-1}{2} \approx 0.207$ obtained in Theorem 4.8 is far from optimal, being obtained by the crude bound $|\mathcal{G}_{\min} \cap \mathcal{U}_{\ell}^h| \le |\mathcal{U}_{\ell}^h|$. Based on the numerical computation of the first few terms of $\frac{a_{n+1}}{a_n}$ and $a_n^{1/n}$, it is reasonable to expect that the radius of convergence of this power series is greater than 0.5, but strictly smaller than 1.

In order to compute the first terms of the sequence $(a_n)$, three methods have mainly been used so far. The first method is to use the bounds (4.6) for some small values of $k$. Both $\underline{C}_k(p)$ and $\overline{C}_k(p)$ arise as speeds of infinite bin models associated to probability measures supported on $[0, k] \cup \{\infty\}$, which are Markov chains on finite state spaces with a stationary distribution that can be computed explicitly. A finite number of coefficients of the Taylor expansion of $\underline{C}_k(p)$ and $\overline{C}_k(p)$ at $p = 1$ coincide, hence are coefficients of the Taylor expansion of $C(p)$ at $p = 1$. The first 17 values of $a_n$ are computed in [79]. However, the size of the state space of the Markov chain grows exponentially fast with $k$, and the computations have to be made analytically, this method quickly becomes computationally challenging.

The second method to compute $a_n$ consists in constructing the sets $\mathcal{U}_{\ell}^h$ for small values of $h$ then using formula (4.11). One may combine both methods, using a formula analogous to (4.11) to obtain the beginning of the power series expansions $\underline{C}_k(p)$ and $\overline{C}_k(p)$. They are expressed as sums over words constrained to have letters at most equal to $k$. Retaining the terms that coincide for the lower and upper bounds give terms for $C(p)$. This last method was used in [94] to obtain the first 24 values of $a_n$. See Table 2 for the first few values of $a_n$. This sequence is referenced as A321309 in the On-Line Encyclopedia of Integer Sequences [92].

<table><caption>Table 2: The values of $a_n$ for $0 \le n \le 12$.</caption><tr><td>n</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td><td>11</td><td>12</td></tr><tr><td>a<sub>n</sub></td><td>1</td><td>1</td><td>1</td><td>3</td><td>7</td><td>15</td><td>29</td><td>54</td><td>102</td><td>197</td><td>375</td><td>687</td><td>1226</td></tr></table>

From the observation of the first terms of the sequence, it was conjectured in [79] that the sequence $(a_n)$ was non-decreasing and non-negative. Very recently, during the revision stage of this survey, Terlat [95] found a third method to compute this sequence. This new method yields a dozen new terms and disproves the above conjectures.

This third method is based on an efficient algorithm to compute the Taylor expansion around $p = 1$ of the maximal path growth rate $C(p, x)$ for the two-weights model presented in Subsection 9.1, in the case when $x$ is a finite negative integer. This two-weight model corresponds to last passage percolation on the complete directed graph on $\mathbb{Z}$ where each edge has weight 1 with probability $p$ or $x$ with probability $1-p$. Terlat [95] shows that the functions $C(p)$ and $C(p, x)$ have the same Taylor expansions around $p = 1$ up to order $k$, as soon as $0 \le k < \binom{3-x}{2}$. Applying this to $x = -6$, one computes the values of $a_n$ up to $n = 35$. One observes in particular that $a_{26} = 683794$, $a_{27} = 487644$ and $a_{28} = -425932$. This disproves both conjectures about non-decreasing absolute values and non-negativity.
## 5 Longest path of the Barak-Erdős graph in the sparse regime

In this section we explore the asymptotic properties of the length of long paths in a Barak-Erdős graph $\vec{G}(\mathbb{N}, p)$ in the sparse graph limit, that is, when $p \to 0$. It can be seen that, in this limit, $\vec{G}(\mathbb{N}, p)$ is well-approximated by a branching random walk, a discrete-time particle system on the positive half-line $\mathbb{R}_+$. Through this section, we will let $G$ denote the $\vec{G}(\mathbb{N}, p)$.

Let $L_n(p)$ be the maximum length of all paths in $\vec{G}(\mathbb{N}, p)$ from 1 to $n$. Using branching random walk approximation, Newman [86] obtained the lead order of the asymptotic behavior of $L_n(p_n)$ when $p_n \to 0$ as $n \to \infty$. He showed in particular that

$$ \lim_{n \to \infty} \frac{L_n(p_n)}{np_n} = e \quad \text{in probability,} \qquad (5.1) $$

as long as $p_n \to 0$ and $np_n \to \infty$. He also obtained the asymptotic behavior of the overall longest path in that graph ($L_{0,n}$ with the notation of (2.1)).

Recalling that $C(p)$ is the limit of $L_n(p)/n$ as $n \to \infty$, Mallein and Ramassamy [80] obtained the precise asymptotic behavior of $C(p)$ as $p \to 0$ by comparing IBM($\nu_p$) (the infinite bin model with geometric distribution $\nu_p$ with small $p$) to a continuous-time branching random walk with selection. Precisely, [80] states that

$$ \frac{C(p)}{p} = e - \frac{\pi^2 e}{2} (\log p)^{-2} (1 + o(1)), \quad \text{as } p \to 0, \qquad (5.2) $$

using the so-called Brunet-Derrida behavior [24, 12] of the speed of branching random walks with selection that we now describe.

A branching-selection process is a particle system in which each particle moves and reproduces independently, but an exterior selection mechanism keeps the size of the total population close to $N$ by killing particles.<fnref n="6" />

Brunet and Derrida [24] conjectured, through numerical simulations and the study of exactly solvable models, that for a large class of branching-selection processes, the speed of the cloud of particles $v_N$ converges to its limit $v_\infty$ at a slow rate, such that

$$ v_\infty - v_N = \frac{C(1 + o(1))}{(\log N)^2}. \qquad (5.3) $$

**Remark 5.1.** Belief in this conjecture was increased by the study of an exactly solvable model [25, 33]. This type of behavior was observed by Berestycki, Berestycki and Schweinsberg [13] for branching Brownian motions with absorption, Bérard and Gouéré [12] for branching random walks, and for noisy F-KPP<fnref n="7" /> equations modeling e.g. directed polymers [85] among many other examples.

We present in the current paper an alternative, possibly simpler, construction of the coupling used by Mallein and Ramassamy [80] between the IBM($\nu_p$) and an $N$-branching random walk, a discrete analog of the $N$-BBM. We give in Section 5.1 some heuristics motivating the kind of limit that sparse Barak-Erdős graph has. This limit, being interpreted as a particular branching random walk sometimes called PWIT (Poisson-weighted infinite tree) is discussed in Section 5.2. In Section 5.3 we introduce a coupling between the Barak-Erdős graph, and the PWIT. This enables us to explain and describe the results of [86] and [80]. We also extend these results to some other stochastic ordered graphs in Section 5.5. We then turn to computations of the length of the longest path of the Barak-Erdős graph in Section 5.6 and the shortest path in Section 5.7.

<footnote n="6">⁶The most classical model is the $N$-branching Brownian motion (N-BBM) defined as follows. At each time $t > 0$, there are $N$ particles on the real line. The particles move according to i.i.d. Brownian motions. At independent exponential times of parameter $N$, the leftmost particle is killed and one of the $N-1$ other particles gives birth to a new particle at its currently occupied position. This model was notably studied in [76] in which the speed and fluctuation of the cloud if particles as $N \to \infty$ is obtained.</footnote>

<footnote n="7">⁷Equations of this type are partial differential equations of the form $v_t = v_{xx} + F(v)$ were introduced by Kolmogorov, Petrovsky and Piscounov [67] as models for a reaction-diffusion systems. The name Fisher was added to these three names, whence the acronym F-KPP, owing to Fisher's infamous work [42], a paper cited in [67] also. A duality relationship between the F-KPP equation, in the $F(v) = v(1-v)$ case, and the branching Brownian motion was established by McKean [83]. Connections between the noisy F-KPP equation and the branching Brownian motion with selection were obtained in [40, 38].</footnote>
## 5.1 Heuristics on the sparse limit

It is now commonly known that the neighborhoods in many sparse random graphs, among which Erdős-Rényi graphs and configuration models, are well-approximated by branching processes. See [98] and references therein. For example, let $G(n, \lambda/n)$ be an Erdős-Rényi random graph. That is, on the set $\{1, \dots, n\}$ a pair of points forms an indirected edge with probability $\lambda/n$, independently from pair to pair. Using the graph distance of the Erdős-Rényi random graph, we can observe that the set of points within finite distance from any fixed vertex converges weakly, as $n \to \infty$, to a Galton-Watson tree with Poisson($\lambda$) offspring distribution; see e.g. [34].

Indeed, the number of neighbors of a given vertex $v^*$ is given by a binomial distribution with parameters $n$ and $\lambda/n$ that converges to a Poisson($\lambda$) distribution as $n \to \infty$. In turn, the number of neighbors of a given neighbor, excluding the vertex $v^*$, is given by an independent binomial distribution with parameters $n-1$ and $\lambda/n$, which also converges to a Poisson($\lambda$) distribution. Moreover, as there is with large probability a bounded number of vertices in the ball of radius $k$ of the vertex $v^*$, the probability of observing a non-trivial cycle of bounded size goes to 0 as $n \to \infty$. This proves that any finite neighborhood of the vertex $v^*$ converges in distribution to a Galton-Watson tree.

Consider now a Barak-Erdős graph on $\mathbb{N}$ rather than on $\mathbb{Z}$, as we are interested in paths from fixed root, the vertex 1 in this case. Denote this by

$$G := \vec{G}(\mathbb{N}, p),$$

letting $E(G)$ be the random set of its edges. Assume that it is sparse; that is, we are interested in the limit as $p \to 0$. We are able to obtain a similar description of the neighborhoods of the vertex 1 in terms of a branching process. However, to take into account the directed structure of the graph, we have to record in the limiting branching process the label of the vertices we consider. To achieve this, consider instead the graph $\vec{G}(p\mathbb{N}, p)$, where $p\mathbb{N} := \{pk : k \in \mathbb{N}\}$. Think of the immediate neighbors of the root as a point process on $(0, \infty)$ and let $N$ be a standard Poisson point process on $(0, \infty)$. We then have

$$\sum_{k \in \mathbb{N}} \mathbf{1}_{(1,k) \in E(G)} \delta_{pk} \xrightarrow{d} N, \quad \text{as } p \to 0.$$

where $\xrightarrow{d}$ denotes convergence in distribution. Similarly, for any $x > 0$, the set of immediate neighbors of vertex $\lfloor x/p \rfloor p$, considered as a point process, also converges to $N$ in distribution. It was shown in [52, 45] that the connected component of the root converges weakly, as $p \to 0$, to the *Poisson-weighted infinite tree* (PWIT). This process is a branching random walk in which at each generation, all particles in the system give birth to children independently, such that the children of a particle at position $x$ are positioned according to a Poisson point process with unit intensity on $[x, \infty)$.

## 5.2 The PWIT and some of its properties

The terminology PWIT was introduced by Aldous and Steele [5]. We describe it as a Markovian particle system that we call *immortal particles process*. At time 0 an immortal particle is born. The particle produces a child at each epoch of a standard Poisson process; and, recursively, each of the offspring has the same reproduction law, independently. A convenient way to capture the system, together with all connection information, is by letting

$$N^* := \bigcup_{n=0}^{\infty} \mathbb{N}^n,$$

where $\mathbb{N}^0 = \{\emptyset\}$ be the vertex set of a tree with edges $(u, v) \in \mathbb{N}^* \times \mathbb{N}^*$ only when $v = uk$, the concatenation of $u$ with a single integer $k$. Recall that $\mathbb{N}^*$ is the set of words (=finite sequences) of positive integers equipped with the concatenation operation. The trivial word $\emptyset$ is the identity of the concatenation operation. We do not give a special symbol to the edges of $\mathbb{N}^*$ as they are
immediately fixed through $\mathbb{N}^*$. The resulting object is a tree that is now known as the Ulam-Harris tree. To encode the PWIT, simply add weights to the edges by letting,

$$X(\emptyset) = 0,$$

and then, for each $u \in \mathbb{N}^*$,

$$0 < X(u1) - X(u) < X(u2) - X(u) < X(u3) - X(u) < \dots$$

be the epochs of an independent copy of a Poisson(1) point process on $(0, \infty)$. In our immortal particles interpretation, $\mathbb{N}^*$ is the set of (names of) all particles that are born to the end of time and $X(u)$ is simply the time at which particle $u$ is born. Thus, for example, $X(2, 5, 3)$ is the time at which the 3rd offspring of the 5th offspring of the 2nd offspring of $\emptyset$ is born, and has the distribution of the sum of $2+5+3=10$ i.i.d. exponential random variables. If we let $|u|$ be the length of the word $u$ and $\|u\|$ the sum of its elements as integers then particle $u$ is born at generation $|u|$ and has Gamma($\|u\|$) distribution.⁸⁹

Let $\Pi = (\mathbb{N}^*, X)$ denote the standard (unit rate) PWIT. Note that for any particle $u \in \mathbb{N}^*$ the subtree rooted at $u$ is also a PWIT after relabeling and time-shifting. We let

$$V_t := \{u \in \mathbb{N}^* : X(u) \le t\}, \quad X_t := \{X(u) : X(u) \le t\}, \quad \Pi_t = (V_t, X_t),$$

be the induced subgraph of $\Pi$ on the set of vertices $u$ with $X(u) \le t$. Hence $\Pi_t$ describes the immortal particles process up to time $t$. Note that $\Pi_t, t \ge 0$, is Markovian. If we forget the connections between particles and only keep the information of the lengths of their labels, then we obtain an IBM-type of model. Indeed, letting

$$Z_t(\ell) := |\{u \in \mathbb{N}^* : X(u) \le t, |u| = \ell\}|, \qquad (5.4)$$

then

$$Z_t = (Z_t(0), Z_t(1), \dots), \quad t \ge 0,$$

is a continuous-time IBM model whose evolution is as follows. Let, for each $t$, each of the particles $u$ in $\Pi(t)$ possess an independent exponential(1) clock. One of the clocks expires first; say that this clock is possessed by a particle in bin $\ell$; then we add a new particle in bin $\ell+1$. Note that $Z_t, t \ge 0$, is also Markovian. This process is an Uchiyama-type continuous-time branching random walk [97] on $\mathbb{Z}_+$, initiated from a single particle at position 0 at time 0. Also note that

$$|V_t| := |\{u \in \mathbb{N}^* : X(u) \le t\}| = \sum_{\ell \ge 0} Z_t(\ell), \quad t \ge 0,$$

is also Markovian with state space $\{1, 2, \dots\}$ and transition rate $y$ from state $y$ to $y+1$ (the Yule-Furry pure birth process). Finally note that there is a front bin, namely

$$F_t = \max\{|u| : X(u) \le t\} = \max\{\ell \in \mathbb{Z}_+ : Z_t(\ell) > 0\}, \qquad (5.5)$$

<footnote n="8">⁸ There are other ways to visualize the PWIT. First, recall that a branching random walk BRW($N$) in discrete time with parameter (the distribution of) a (finite or infinite) point process $N$ on the real line, is created by letting a single particle at stage 0, located at point $x$, die at stage 1 and immediately be replaced by children located at the points of $N+x$ (that is, the set of points of $N$ all translated by $x$). All children behave exactly in the same manner, independently. If $N$ is a standard Poisson process (whose points are interpreted as spatial points here) is the parameter of a branching random walk, then this branching random walk is the PWIT; this is the first interpretation. In this interpretation, $X(u)$ is the spatial location of particle $u$. The second interpretation of a PWIT is as a so-called “Poisson cascade” in the physics literature [62]: Let $N_t, t \ge 0$, be a collection of i.i.d. standard Poisson processes. Interpreting $N$ as a set of points, we let $V = \bigcup_{t \ge 0} N_t$ be a set of vertices, letting $(s, t)$ be an edge if $t \in N_s + s$. The corresponding graph is a random forest and the connected component of 0 is distributed like the PWIT. A third interpretation [5] is as a random metric space $(\mathbb{N}^*, d)$ where the metric $d$ is as follows. First let $d(u, uk) = X(uk) - X(u)$ and then, for each $u, v \in \mathbb{N}^*$, let $u = w_0, w_1, \dots, w_\ell = v$ be the necessarily unique path between $u$ and $v$, and let $d(u, v) = \sum_{i=1}^\ell d(w_{i-1}, w_i)$.</footnote>

<footnote n="9">⁹ The reason that we discuss different interpretations of the PWIT is because there exist results in the literature referring to seemingly different, but in essence identical stochastic models around the PWIT. For instance, if we consider the continuous-time Markovian branching process with offspring distribution $\delta_2$ (the Yule process) then we can construct the PWIT as a deterministic function of it. We shall not explain this here.</footnote>
which is the largest generation particle present in $\Pi_t$. $^{10}$ So $Z_t(\ell) = 0$ for all $\ell > F_t$. We use the abbreviation PWIT-IBM for $Z_t$, $t \ge 0$ and note that it differs from $\Pi_t$, $t \ge 0$, only by the absence of the connections information.

The total number of particles in every bin $\ell$, with $\ell \ge 1$, of the PWIT-IBM at time $t$ grows exponentially fast.

**Lemma 5.2.** Let $f$ be a nonnegative measurable function on $\mathbb{R}$. Then, for all $\ell \in \mathbb{N}$,

$$ \mathbb{E} \sum_{|u|=\ell} f(X(u)) = \mathbb{E} \sum_{|v|=\ell-1} \int_0^\infty f(X(v) + t)dt = \int_0^\infty f(x) \frac{x^{\ell-1}}{(\ell-1)!}dx. $$

Let us stress at this point that, with our encoding, particles live forever. In particular, $\{|u|=1\}$ is the set of children of the ancestor $\emptyset$ of the population, which arise at the epoch of a Poisson process of intensity 1. This set is a.s. infinite, and $\mathbb{E}\sum_{|u|=1} f(X(u)) = \int f(x)dx$ by Campbell's formula, as stated above.

*Proof.* Let $u \in \mathbb{N}^\ell$. Then $u = vk$ for some $v \in \mathbb{N}^{\ell-1}$ and some $k \in \mathbb{N}$. So

$$ \begin{aligned} \mathbb{E} \sum_{|u|=\ell} f(X(u)) &= \mathbb{E} \sum_{|v|=\ell-1} \mathbb{E}[f(X(v) + X(vk) - X(v))|X(v)] \\ &= \mathbb{E} \sum_{|v|=\ell-1} \mathbb{E} \left[ \int_0^\infty f(X(v) + t)N(dt) \middle| X(v) \right] = \mathbb{E} \sum_{|v|=\ell-1} \int_0^\infty f(X(v) + t)dt, \end{aligned} $$

where the $N$ above is a Poisson(1) point process on $(0, \infty)$, independent of $X(v)$. Iterating this we obtain

$$ \mathbb{E} \sum_{|u|=\ell} f(X(u)) = \int_{[0, \infty)^\ell} f(t_1 + \cdots + t_\ell) dt_1 \cdots dt_\ell, $$

and the last expression follows by a change of variables. $\square$

**Corollary 5.3.** We have the following formulas for the expected number $\mathbb{E}Z_t(\ell)$ of particles in bin $\ell$ as well as the total number $\mathbb{E}|V_t|$ of the PWIT-IBM at time $t$:

$$ \mathbb{E}Z_t(\ell) = \frac{t^\ell}{\ell!}, \quad \mathbb{E}|V_t| = e^t. $$

*Proof.* From (5.4) and Lemma 5.2 with $f(x) = \mathbf{1}_{x \le t}$ we have

$$ \mathbb{E}Z_t(\ell) = \int_0^t \frac{x^{\ell-1}}{(\ell-1)!}dx = \frac{t^\ell}{\ell!}. $$

The second claim follows by summation or by remembering that $|V_t|$, $t \ge 0$, is the Yule-Furry process. $\square$

We are interested in the PWIT since, as motivated in Section 5.1, the PWIT appears as the limit of a sparse Barak-Erdős graph. We thus proceed in outlining some results concerning the PWIT. In Section 5.3 we will couple the PWIT together with the Barak-Erdős graph for all $p$ (or more specifically with an appropriate spanning tree of the connected component of the root of $G$). This coupling will be such that

$$ M_{\ell} = \inf_{|u|=\ell} X(u), \qquad (5.6) $$

the first time that bin $\ell$ of the PWIT-IBM becomes nonempty, will give a lower bound for the index of any vertex of $G$ linked to the vertex 1 by a path of length $\ell$. It will be enough to obtain the upper bound for (5.1). This lower bound will be sharp enough in very sparse graphs, but some additional approximations will be needed when the density of edges becomes too large, yielding

<footnote>$^{10}$The word “generation” may be confusing, especially in the immortal particles process interpretation of the PWIT. To avoid confusion, simply interpret the phrase “generation of particle $u$” as $|u|$.</footnote>
the estimate (5.2). In terms of the BRW($N$) interpretation–see footnote 8–the quantity $M_\ell$ is the minimal displacement (position of the leftmost particle) at stage $\ell$ and this has been the subject of a large body of work. These asymptotic properties of the minimal displacement for a BRW($N$) depend on the quantity

$$ \kappa(\theta) := \log \int_{\mathbb{R}} e^{-\theta x} \mathbb{E}N(dx) $$

the logarithm of the Laplace transform of the mean measure of $N$. The speed $v$ of BRW($N$) is then expressed as

$$ v = \sup_{\theta>0} \frac{-\kappa(\theta)}{\theta}. $$

Indeed, Hammersley [58], Kingman [66] and Biggins [15] proved under increasing generality that

$$ \lim_{n \to \infty} \frac{M_n}{n} = v \quad \text{a.s. and in L}^1. \qquad (5.7) $$

In our case, $N$ being standard Poisson process, we have

$$ \kappa(\theta) = \log \int_{0}^{\infty} e^{-\theta x} dx = -\log \theta, \quad v := \sup_{\theta>0} \frac{\log \theta}{\theta} = \frac{1}{e}, $$

This is the same $1/e$ that appears in the limit (5.1).

Addario-Berry and Reed [2] and Hu and Shi [59] independently proved that $M_n - n/e$ increases at logarithmic rate; more precisely in our case that

$$ \lim_{n \to \infty} \frac{M_n - n/e}{\log n} = \frac{3}{2e}, \quad \text{in probability,} \qquad (5.8) $$

with almost sure fluctuation occurring on that logarithmic scale. The convergence in distribution of the minimal displacement of a branching random walk, when centered around its median, was then obtained by Aïdékon [3]. Using that

$$ D_n = \sum_{|u|=n} (n/e - X(u))e^{-eX(u)} $$

is a non-uniformly integrable signed martingale that converges almost surely to a positive limit $D_\infty$, he proved that there exists $c_* > 0$ such that for all $x \ge 0$,

$$ \mathbb{P}(M_n \ge n/e + \frac{3}{2e} \log n + x) = \mathbb{E}(\exp(-c_* D_\infty e^{ex})) \qquad (5.9) $$

The result was independently obtained in [1] in the specific case of the PWIT.

Recalling the PWIT-IBM interpretation of $Z_t$, $t \ge 0$, we note that the functions $t \mapsto F_t$ and $\ell \mapsto M_\ell$, defined in (5.5) and (5.6), respectively, are generalized inverses of one another. Indeed, it is clear that, for all $t \ge 0$ and all $\ell \in \mathbb{Z}_+$,

$$ Z_t(\ell) > 0 \iff \exists u \in \mathbb{N}^\ell X(u) \le t \iff M_\ell \le t, $$

which implies that the front bin $F_t$ in the PWIT-IBM, as defined by (5.5), satisfies

$$ F_t = \max\{\ell \in \mathbb{Z}_+ : M_\ell \le t\}. \qquad (5.10) $$

Hence, from the asymptotic behavior of $M_\ell$ as $\ell \to \infty$ we are able to obtain the asymptotic behavior of $F_t$ as $t \to \infty$. This method as already been used by Corre in [32] in this purpose. However, note that in his description of the Yule process, at each birthing event particles were dying giving birth to two new children. Therefore our result does not align exactly with the one of Corre.

**Lemma 5.4** (Corre [32]). For all $t \ge 1$, we set

$$ n_t = \left\lfloor et - \frac{3}{2} \log t \right\rfloor \in \mathbb{N} \quad \text{and} \quad y_t = et - \frac{3}{2} \log t - n_t \in (0, 1). $$

For all $k \in \mathbb{Z}$, we have

$$ \lim_{t \to \infty} \mathbb{P}(F_t \le n_t + k) - \mathbb{E}(\exp(-c_* D_\infty e^{y_t - k - 1})) = 0. $$
Remark 5.5. Lemma 5.4 shows that as $t \to \infty$, $F_t$ remains tight around its median but does not converge in distribution, due to the fluctuations of $\log t - \lfloor \log t \rfloor$.

*Proof of Lemma 5.4.* By definition of $F_t$, and the fact that $M_\ell$ is atomless and increases as $\ell$ increases, we have

$$ \mathbb{P}(F_t \le n_t + k) = \mathbb{P}(M_{n_t+k+1} > t) = \mathbb{P}(M_{n_t+k+1} \ge t), \quad k \in \mathbb{N}. $$

In addition, since $x \mapsto \mathbb{P}(M_n \ge n/e + \frac{3}{2e} \log n + x)$ converges pointwise to a monotone decreasing continuous function from $\mathbb{R}$ into $[0, 1]$, we deduce from Dini's theorem that this convergence is uniform. In particular, for any bounded sequence $(x_n)$, we have

$$ \lim_{n \to \infty} \mathbb{P}(M_n \ge n/e + \frac{3}{2e} \log n + x_n) - \mathbb{E}(\exp(-c_* D_\infty e^{ex_n})) = 0. $$

Fix $k \in \mathbb{Z}$ and observe that

$$ \frac{1}{e}(n_t + k + 1) + \frac{3}{2e}\log(n_t + k + 1) = t + \frac{1}{e}(k + 1 - y_t) + o(1), \quad \text{as } t \to \infty. $$

As a result we obtain that, for all $k \in \mathbb{Z}$,

$$ \lim_{t \to \infty} \mathbb{P}(M_{n_t+k+1} \ge t) - \mathbb{E}(\exp(-c_* D_\infty e^{y_t-k-1})) = 0, $$

which completes the proof. $\square$

## 5.3 Coupling of the PWIT and the Barak-Erdős graph

We construct a coupling between the PWIT and the Barak-Erdős graph such that the heuristic convergence of neighborhoods of vertex 1 described in Section 5.1 is more explicit as $p \to 0$. Recall that $G$ denotes the $\overline{G}(\mathbb{N}, p)$ Barak-Erdős graph. We will describe the laws of two random subgraphs, the connected component $C$ of vertex 1 (the root of $G$) and a special spanning tree $B$ of $C$ that has the property that the path from every of its vertices to the root has maximal length. We will then change the vertex set of $C$ and, in a sense, put $C$ in continuous time, explaining the “correct” time scale. Having done this, we will explain how to construct $B$ and the PWIT on the same probability space. We will embed $B$ into the PWIT making sure that the edge-relationships are preserved and that the locations (in continuous time) of vertices are also correct.

### The law of the set of vertices of $C$

Let $q = 1-p$. Define $C$ as the subgraph of $G$ containing the root, i.e. vertex 1, and all vertices $k \ge 1$ such that $1 \rightsquigarrow k$ (i.e. there is a path in $G$ between 1 and $k$). We define these vertices recursively, letting

$$ \kappa_0 = 1, \quad \kappa_i = \min\{k > \kappa_{i-1} : 1 \rightsquigarrow k\}, \quad i \in \mathbb{N}. $$

Clearly,

$$ \kappa_1 - \kappa_0, \kappa_2 - \kappa_1, \dots \text{ are independent,} \quad (5.11) $$

and, for all $i \in \mathbb{N}$

$$ \kappa_i - \kappa_{i-1} \text{ is geometric}(1-q^i); \quad \mathbb{P}(\kappa_i - \kappa_{i-1} > m) = (q^i)^m, \quad m \ge 0. \quad (5.12) $$

This describes the law of the random set

$$ \mathbb{K} = \{\kappa_0, \kappa_1, \kappa_2, \dots\} = V(C) $$

of vertices of $C$ (and hence of any spanning tree of $C$). We can think of $\mathbb{K}$ as an inhomogeneous renewal process on $\mathbb{N}$ that quickly converges to a homogeneous one. Indeed, $q^i \to 0$ as $i \to \infty$, so fast that the Borel-Cantelli lemma ensures that, eventually, $\mathbb{K}$ contains all positive integers. This is another manifestation of the existence of skeleton points, as described in Section 2.1. Note that the rates of the above geometric random variables are increasing with $i$, indicating that, initially, $\mathbb{K}$ is a sparse set (the smaller the $p$ the sparser the $\mathbb{K}$ is initially).
## The spanning tree B and its law

Let $L_k = L_{1,k}^{L,R}$, the maximum length of all paths from 1 to $k$ in $G$. A spanning tree of $C$ is a tree whose set of vertices is $\mathbb{K}$. We say that a spanning tree of $C$ is a maximal length spanning tree if for all $\kappa_i \in \mathbb{K}$, the length of the (necessarily unique) path from 1 to $\kappa_i$ equals $L_{\kappa_i}$. To define the special maximal length spanning tree $B$ we need a definition of ordering on the set

$$ \mathbb{K}_{i-1} := \{\kappa_0, \dots, \kappa_{i-1}\} $$

of the first $i$ vertices of $C$. Roughly speaking, we order the elements of $\mathbb{K}_{i-1}$ in decreasing length, breaking ties in some way.

**Definition 5.6 (Vertex ranking).** Fix $i \in \mathbb{N}$ and let $a, b$ be distinct elements of $\{0, 1, \dots, i-1\}$. We say that $\kappa_a \triangleleft \kappa_b$ (or $\kappa_b \triangleright \kappa_a$), if either $L_{\kappa_a} > L_{\kappa_b}$ or $L_{\kappa_a} = L_{\kappa_b}$ and $a > b$. Note that $(\mathbb{K}_{i-1}, \triangleleft)$ is a totally ordered set and that $\triangleleft$ depends on $i$ (that is, the order on $\mathbb{K}_i$ is different from the order on $\mathbb{K}_{i-1}$). Let now

$$ \sigma : \{1, \dots, i\} \to \{0, \dots, i-1\} $$

be the unique bijection so that

$$ \kappa_{\sigma(1)} \triangleleft \kappa_{\sigma(2)} \triangleleft \dots \triangleleft \kappa_{\sigma(i)}. $$

The domain of $\sigma$ is the set of ranks and $\kappa_{\sigma(1)}$ is the vertex of rank 1, $\kappa_{\sigma(2)}$ the vertex of rank 2, etc. We always have $\kappa_{\sigma(i)} = \kappa_0$ and $\kappa_{\sigma(i-1)} = \kappa_1$. We also let

$$ \rho := \sigma^{-1} $$

denote the inverse function.

**Definition 5.7 (Special spanning tree B).** The special spanning tree $B$ of $C$ is defined as being the maximal-length spanning tree with the property that, for all $i$, the unique parent of $\kappa_i$ in $B$ is the minimal element $\kappa_j$ for the order $\triangleleft$ among the elements such that $(\kappa_j, \kappa_i)$ is an edge in $G$.

Figure 6 gives an example of the definitions.

<figure><img src="image_6.png" /><figcaption>Figure 6: The first 9 vertices of $C$ are shown, together with the edges between them. Vertices of $G$ not connected to 1 via a path are not shown. The number above each vertex $\kappa_j$ is the maximal path length $L_{\kappa_j}$. The number below each vertex is its rank. The thick edges are the edges of the special spanning tree $B$. To explain this, consider, e.g., vertex $\kappa_6$ and observe that is connected to $\kappa_4$ with $L_{\kappa_4} = 2$ and to $\kappa_3$ with $L_{\kappa_3} = 1$; so we choose $\kappa_4$ as the parent of $\kappa_6$ in $B_5$. Consider vertex $\kappa_8$. It is connected to vertices $\kappa_2$ and $\kappa_1$ with $L_{\kappa_2} = L_{\kappa_1} = 2$. Since $\kappa_2$ has lower rank than $\kappa_1$ we declare that $\kappa_2$ is the parent of $\kappa_8$ in $B$. Finally, the quantities on the lower line are proportional to the probability that $\kappa_9$ chooses its parent among the existing vertices, i.e it will be connected to e.g. $\kappa_8$ with probability $\frac{q}{1+q+q^2+q^3+q^4+q^5+q^6+q^7+q^8}$.</figcaption></figure>

To describe the law of the edges of $B$, we let, for each $i \in \mathbb{N}$, the index $\pi(i)$ be such that $\kappa_{\pi(i)}$ is the parent of $\kappa_i$ in $B$. For any $A \subset \mathbb{N}$ let $G(A)$ denote the induced subgraph of $G$ on the set $A$ (i.e. the graph that contains as vertices the elements of $A$ and edges only those edges with endpoints in $A$).
**Lemma 5.8.** With $\kappa_{\pi(i)}$ denoting the parent of $\kappa_i$ in B we have

$$ \mathbb{P}(\pi(i) = \sigma(r)|G(\mathbb{K}_{i-1})) = \frac{q^{r-1}(1-q)}{1-q^i}, \quad r = 1, \dots, i. \qquad (5.13) $$

*Sketch of proof.* To understand this, first note that $\sigma$ depends only on $G(\mathbb{K}_{i-1})$, where $\mathbb{K}_{i-1} = \{\kappa_0, \dots, \kappa_{i-1}\}$. Second, this formula says that the parent of $\kappa_i$ is the least ranked vertex $\kappa_j$, say, in $\mathbb{K}_{i-1}$ such that $(\kappa_j, \kappa_i)$ is an edge in $G$. The denominator $1-q^i$ expresses the probability that $\kappa_i$ connects to one of the vertices in $\mathbb{K}_{i-1}$. $\square$

Figure 6 shows these probabilities in an example with $i=9$.

*Remark 5.9.* Note that (5.11), (5.12) and (5.13) provide a complete characterization of the law of the special spanning tree B.

## The special tree B in continuous time

Putting B in continuous time means replacing its vertex set $\mathbb{K}$ by a possibly random subset of $(0, \infty)$ in a way allowing its coupling with the PWIT. Let us start by recalling the clockwork lemma: consider a finite set of positive numbers, say $a_1, \dots, a_i$. To simulate a random variable that takes value $j \in \{1, \dots, i\}$ with probability proportional to $a_i$, we can use $\tau_1, \dots, \tau_i$ independent exponential random variables with parameters $a_1, \dots, a_i$. Then the minimum of these random variables equals $\tau_j$ with probability $a_j / \sum_{k=1}^i a_k$.

Fix $i$ and the set $\mathbb{K}_{i-1} = \{0, 1, \dots, i-1\}$. We imagine that this set, along with the edges from B, has been constructed at time $t$. Equip each vertex $\kappa_j \in \mathbb{K}_{i-1}$ with an independent exponential random variable $\tau_j$, corresponding to the elapsed time after time $t$ at which $\kappa_j$ wishes to connect to a new vertex $\kappa_i$. We declare that this takes place at time $t + \tau$, where $\tau = \min(\tau_1, \dots, \tau_i)$ and if $\tau = \tau_j$ then it is vertex $\kappa_j$ that will connect to $\kappa_i$. Let $\rho(j)$ be the rank of $\kappa_j$, i.e. the inverse of $\sigma$ defined in Definition 5.6. We should assign rate $q^{\rho(j)-1}$ to $\tau_j$, as then

$$ \mathbb{P}(\tau_j = \tau) = \frac{q^{\rho(j)-1}}{1+q+\dots+q^{i-1}} = \frac{q^{\rho(j)-1}(1-q)}{1-q^i}, \quad 0 \le j \le i-1, $$

which precisely equal to the probability (5.13). If then we let $T(\kappa_i)$ be the time of appearance of $\kappa_i$ then we must have

$$ T(\kappa_i) - T(\kappa_{i-1}) \stackrel{\text{d}}{=} \tau \sim \text{exponential}(1+q+\dots+q^{i-1}), \qquad (5.14) $$

that is,

$$ T(\kappa_i) - T(\kappa_{i-1}) \sim \text{exponential} \left( \frac{1-q^i}{1-q} \right). $$

Hence we can obtain $T(\kappa_i)$ by an appropriate thinning of a Poisson process.

**Lemma 5.10.** Let $\xi_1 = 0$ and $0 < \xi_2 < \xi_3 < \dots$ be the points of a Poisson(1) point process, independent of the vertex set $\mathbb{K} = \{\kappa_0, \kappa_1, \dots\}$ of C. Then

$$ p\xi_{\kappa_i} \stackrel{\text{d}}{=} T(\kappa_i), \quad i = 0, 1, 2, \dots $$

*Proof.* If $\tau_1, \tau_2, \dots$ are i.i.d. exponential random variables with rate $\lambda$ and if $\nu$ is an independent geometric random variable with parameter $\alpha$ (i.e., $\mathbb{P}(\nu = n) = (1-\alpha)^{n-1}\alpha$, $n \in \mathbb{N}$), then $\tau_1 + \tau_2 + \dots + \tau_\nu$ is exponential with rate $\alpha\lambda$, by the standard Poisson thinning theorem. Recall, from eq. (5.12), that $\kappa_i - \kappa_{i-1}$ is geometric$(1-q^i)$. Applying the above thinning theorem we have that $\xi_{\kappa_i} - \xi_{\kappa_{i-1}}$ is exponential with rate $(1-q^i)$ and so $p\xi_{\kappa_i} - p\xi_{\kappa_{i-1}}$ is exponential with rate $(1-q^i)/p$. Hence, from (5.14),

$$ p\xi_{\kappa_i} - p\xi_{\kappa_{i-1}} \stackrel{\text{d}}{=} T(\kappa_i) - T(\kappa_{i-1}) $$

and the claim follows by independent increments of both sides. $\square$
Remark 5.11. This shows that the correct set of vertices of B, if we are to put it in continuous time and create a Markov process, is the set

$$0 = p\xi_{\kappa_0} < p\xi_{\kappa_1} < p\xi_{\kappa_2} < \dots$$

To spell out the construction explicitly, we identify every integer vertex $\kappa_i$ with the real number $p\xi_{\kappa_i}$ and keep the edges intact. Let now $B_t$ be the induced subgraph of B on the set of new vertices $p\xi_{\kappa_i}$ that do not exceed $t$. Then $B_t$, $t \ge 0$, is Markovian.

## The coupling

The quantities defined above allow us to give a constructive proof of the following theorem.

**Theorem 5.12.** Let B be the special spanning tree of G and $\Pi$ a standard PWIT. Then there is a probability space on which $(\Pi, B)$ is defined in such a way that there is an injection

$$\Phi: \mathbb{K} \to \mathbb{N}^*,$$

preserving edges and having the property that

$$|\Phi(\kappa_i)| = L_{\kappa_i}, \qquad (5.15)$$

for all $\kappa_i \in \mathbb{K}$.

*Informal construction of the coupling.* We simultaneously construct $B_t$ together with $\Pi_t$ at times $t$. Observe that every particle in $\Pi_t$ gives birth to offspring at unit rate, while a particle $p\xi_j$ in $B_t$ are connected to newly discovered vertex at slower rate $1 - q^k$, where $k$ is the rank of $p\xi_j$ for the order $<$. We construct the coupling by strategically selecting the particles in $\Pi$ corresponding to the vertices in B. For sake of illustration, we think of particles in $\Pi$ as being blue, unless they correspond to vertices of B via $\Phi$, in which case they are red. We informally refer to particle $\Phi(\kappa_i)$ as vertex $\kappa_i$.

At time $t=0$ the situation is trivial, there is a single red particle in $\Pi_0$ corresponding to vertex 1 in $B_0$. Fix $t > 0$, let $i$ be the number of red particles in $\Pi_t$, corresponding to vertices $\kappa_0, \dots, \kappa_{i-1}$ in $B_t$. The remaining particles in $\Pi_t$ are blue. We associate to each blue particle an independent blue exponential clock with parameter 1, and to each red particle a pair of independent exponential clocks, such that the rate of the red clock associated to the red particle ranked $r$ is taken to be $q^r$, and the blue clock is $1 - q^r$. These clocks correspond to the times at which each particle creates a child, with the color of the clock corresponding to the color of the newborn particle.

We consider the time $\tau$ corresponding to the smallest of these exponential clocks. At time $t + \tau$, if the clock is blue we add a new blue particle to $\Pi_t$ with position $t + \tau$, which is born from the particle associated to this exponential clock. If the clock at time $t + \tau$ is red, we add a new red particle to $\Pi_t$ with position $t + \tau$, connected to the (red) parent particle $\Phi^{-1}(\kappa_i)$. Simultaneously, we add to $B_{t+\tau}$ the vertex $\kappa_i$, which is connected to the newborn particle in $\Pi_{t+\tau}$ via $\Phi$.

Since red clocks have rate $1, q, \dots, q^{i-1}$, it follows that the particle corresponding to the new vertex will be added after an exponential time of parameter $1 + \dots + q^{i-1}$. Therefore, this time corresponds to $p\xi_{\kappa_i}$ in distribution, so we set $\xi_{\kappa_i} = X(\Phi^{-1}(\kappa_i))/p$. It then should be clear, by construction that $(\Pi_t)$ is the PWIT, B has the law of the special spanning tree, and (5.15) holds, since every edge in B correspond to a parent-child relationship in the PWIT. $\square$

As Barak-Erdős graphs with any connecting constant can be associated to the same branching random walk, this coupling also yields a coupling of Barak-Erdős graphs with different constants. It is worth noting that with this coupling, the set of red “coding” particles is decreasing with $p$. It is also worth observing that typically, the position of the leftmost blue descendant of a red particle tend to be of order $-\log p$, as newborn red particle occur at rate 1, and the rate at which new blue particle occur can be bounded from above by $1 - (1-p)^n$ with $n$ the number of red particles born after that particle.
<figure><img src="image_7.png" /><figcaption>Figure 7: A possible evolution of the PWIT with the vertices of $\mathbb{K}$ embedded correctly. The little triangle at the end of blue particles symbolize the blue descendants produced by each blue particle, which play no role in the coupling, hence do not interact with $\Phi$ or the times at which the red particles appear. However, the blue particles represented here play a role, as they influence the label given to each of the red particle.</figcaption></figure>

**Example 5.13.** We refer to the example drawn in Figure 7. We start with $\kappa_0$ as a root particle of the PWIT. Since $\kappa_0$ is red and has rank 1 its red clock has rate $q^{1-1} = 1$, so its blue clock has rate $1-1=0$. That is, $\kappa_0$, at this stage, produces red offspring. The first offspring, $\kappa_1$, appears at an exponential time with parameter $1+q+\cdots+q^{i-1}$ with $i=1$, hence at an exponential(1) time, that can be taken to be $p\xi_{\kappa_1}$. We set $\Phi(\kappa_1) = 1$. At this time, $\kappa_1$ has rank 1 and $\kappa_0$ has rank 2. Therefore the red and blue clocks of $\kappa_1$ have rates 1, 0, respectively, while the red and blue clocks of $\kappa_0$ have rates $q, 1-q$ respectively. Hence $\kappa_2$ appears at time differing from $p\xi_{\kappa_1}$ by an exponential(1 + q) random variable, that is, at time $p\xi_{\kappa_2}$. Moreover, $\kappa_2$ has parent $\kappa_1$ with probability $1/(1+q) = (1-q)/(1-q^2)$ or $\kappa_0$ with probability $q/(1+q) = q(1-q)/(1-q^2)$. Suppose the latter happens. If $\kappa_0$ had produced 2 blue offspring then $\Phi(\kappa_2) = 4$, as it is its third offspring. Once $\kappa_2$ is added we have that $\kappa_2$ has rank 1 so has no blue clock, $\kappa_1$ has rank 2 so it has a red clock at rate $q$ and a blue at rate $1-q$, while $\kappa_0$ has the least rank, 3, and has a red clock at rare $q^2$ and a blue at rate $1-q^2$. At time $p\xi_{\kappa_3}$ the new particle $\kappa_3$ is added and if it chooses $\kappa_2$ as parent then its label is $\Phi(\kappa_2) = 41$, since $\kappa_2$ produced no offspring, so $\kappa_3$ is its first one.

We may call the times $p\xi_{\kappa_i}$ at which a new vertex of $B$ appears in $\Pi$ as embedded times. We define for $\ell \in \mathbb{Z}_+$

$$ \bar{M}_{\ell} = \inf\{X(u) : u \text{ red particle with } |u| = \ell\} $$

and for $t \ge 0$

$$ \bar{F}_t = \max\{\ell \in \mathbb{Z}_+ : \bar{M}_{\ell} \le t\}, $$

which are the analogue of $(M_\ell)$ and $(F_t)$ defined in (5.10), restricted to the set of red particles from the coupling.

**Corollary 5.14.** The process $(\bar{F}_t, t \ge 0)$ and $(L_k, k \ge 0)$ where $L_k = L_k^{\text{L,R}}$, are related by

$$ F_{p\xi_{\kappa_i}} = \max_{0 \le j \le i} L_{\kappa_j}. $$

## 5.4 Longest chain issued from the initial vertex

The length of the longest path issued from the vertex 1 is studied using the branching random walk coupling described above. This coupling was introduced by Newman [86] for this purpose. In particular, using this coupling, he obtained the following result for the asymptotic behavior of $L_n$ as a function of $p$.

**Theorem 5.15 (Newman [86]).** Let $(p_n)$ be a null sequence.

1. If $\lim_{n \to \infty} np_n = t \in (0, \infty)$, then $\lim_{n \to \infty} L_n^{(1)}(p_n) = F_t$ in distribution.

2. If $\lim_{n \to \infty} np_n = \infty$, then $\lim_{n \to \infty} L_n^{(1)}(p_n)/np_n = e$ in probability.
Proof. We first assume that $np_n \to t \in (0, \infty)$. In this situation, the connected component of the vertex 1 in the Barak-Erdős graph $\tilde{G}(n, p_n)$ converges, as $n \to \infty$ to $(X(u), u \in \mathcal{U}: X(u) \le t)$, using the branching random walk coupling.

Indeed, the number of vertices in this connected component remains tight as $n \to \infty$, the probability of observing one extra edge between two vertices in the component goes to 0. Therefore, $C^{(p_n)} \cap [1, \dots, n]$ is a tree with high probability for $n$ large enough, hence $B^{(p_n)} \cap [0, n] = C^{(p_n)} \cap [0, n]$ with high probability, which completes the proof using Theorem 5.12.

We deduce that the length of the longest path in this connected component is the same as the length of the longest path in the tree. This longest path is given by the largest generation $F_t$ at which there is at least one individual to the left of $t$, completing the proof.

We now assume that $np_n \to \infty$, and we use once again the coupling described in Theorem 5.12. By law of large numbers, the position $\xi_{\kappa_n}$ of the $n$th vertex in the coupling satisfies $p_n\xi_{\kappa_n}/np_n \to 1$ a.s. as $n \to \infty$. Then, using (5.9), for all $\varepsilon > 0$, for $n$ large enough we have $M_{[enp_n(1+\varepsilon)]} \ge np_n(1+\varepsilon/2)$. Therefore, almost surely for $n$ large enough, the longest path issued from 1 will be shorter than $en(1+\varepsilon)$, i.e.

$$ \overline{\lim}_{n \to \infty} \frac{L_n}{np_n} \le e \quad \text{a.s.} $$

For the lower bound, we fix $t > 0$, and we consider in a first time the length of the longest path in the restriction of the Barak-Erdős graph to the set $\{1, \dots, \lfloor t/p_n \rfloor\}$. Thanks to the previous case, we know that the length of this path converges to $F_t$. Moreover, the smallest vertex with index larger than $t/p_n$ connected to this path is positioned at geometric distance with parameter $p_n$ from $\lfloor t/p_n \rfloor$. Therefore, with high probability, there exists a path of length at least $F_t(1 - \varepsilon)$ starting from vertex 1 and ending at a vertex of index between $(t+1/2)/p_n, (t+2)/p_n$.

Chaining this argument, we obtain that with high probability, $L_1^{(n)}(p_n)$ is larger than the sum of $np_n/(t+2)$ independent copies of $F_t$. Letting $n \to \infty$, then $\varepsilon \to 0$, we obtain

$$ \underline{\lim}_{n \to \infty} \frac{L_n}{np_n} \ge \frac{\mathbb{E}(F_t)}{t}. $$

Then using (5.7), we have $\lim_{t \to \infty} \frac{\mathbb{E}(F_t)}{t} = e$, which completes the proof. $\square$

Theorem 5.15 gives the precise asymptotic behavior of $L_n(p_n)$ as long as $\lim_{n \to \infty} np_n < \infty$. However, when $np_n \to \infty$, it only gives the first order of its asymptotic expansion. Using the coupling described in Theorem 5.12, Itoh [61] showed that the asymptotic behavior of the branching random walk applies to the sparse Barak-Erdős settings, and that as long as $np_n \to \infty$ “slowly enough”, we have

$$ \limsup_{n \to \infty} \sup_{k \in \mathbb{N}} |\mathbb{P}(L_n(p_n) = k) - \mathbb{P}(F_{np_n} = k)| = 0, \quad (5.16) $$

showing that the law of $L_n$ has the same asymptotic behavior as $F_{np_n}$ in this regime, described in Lemma 5.4. In particular, this results states that $(L_n(p_n) - np_n e^{-\frac{3}{2e} \log np_n})$ remains tight.

However, this asymptotic behavior fails to hold when $p_n$ decays too slow. The branching random walk associated to the Barak-Erdős graph gives a good description of the connected component of 1 as long as the number of blue balls below position $np_n$ remains small. This is for example true assuming $np_n$ converges to a constant, under which conditions the number of blue balls before $np_n$ go to 0 as $n \to \infty$. On the opposite end of the spectrum, if $p$ remains constant, the asymptotic behavior of $L_n$ differs sharply from the one of $F_{np_n}$. Indeed the leftmost particle will tend to be blue with high probability.

The behavior of red particles in the branching random walk can be compared to a branching random walk with selection. Indeed, when considering dynamically their behavior, we observe that the $k$th largest red ball produces a red offspring at rate $q^k$. In particular, if $k \ll -\log p$, particles branch at a rate close to 1, similarly to the usual branching random walk, while if $k \gg -\log p$, the branching rate of that particle is close to 0. The set of red balls can therefore be closely estimated by the set of surviving particles in the branching random walk with selection of the $N \approx [-\log p]$ rightmost particles.
The branching random walk with selection of the N rightmost particles evolves according to the following procedure. At each generation, all particles reproduce independently, a particle at position x giving birth to a Poisson point process with unit intensity on $[x, \infty)$. Among all children of these particles, only the N leftmost are selected to constitute the new generation of the process.

It is worth observing that this process can be straightforwardly embedded in the branching random walk. We write $\mathcal{D}_N$ for the set of particles in the branching random walk that form the branching random walk with selection of the N rightmost generation, i.e. such that for all $n \in \mathbb{N}$, $\mathcal{D}_N \cap \{|u| = n\}$ is the set of the N leftmost children of the particles in $\mathcal{D}_N \cap \{|u| = n - 1\}$.

Bérard and Gouéré [12] first proved the Brunet-Derrida behavior for a branching random walk with binary branching and selection of the N rightmost individuals. This result was extended by Mallein [77] to more general reproduction laws covering the present case. From Kingman's subadditive theorem, we know the existence of a sequence $(v_N)$ such that for each $N \in \mathbb{N}$,

$$ \lim_{n \to \infty} \frac{1}{n} \max_{u \in \mathcal{D}_N, |u|=n} = v_N \quad \text{a.s.} $$

The Brunet-Derrida behavior of this branching random walk can be stated as follows

$$ v_N = e - \frac{\pi^2 e (1 + o(1))}{2(\log N)^2} \quad \text{as } N \to \infty. \qquad (5.17) $$

Using the coupling between the branching random walk and the Barak-Erdős graph, and the fact that the set of red particles is well-approximated by the set $\mathcal{D}_{[-\log p)^2}$, we obtain the following result.

**Theorem 5.16** (Mallein and Ramassamy [80]). As $p \to 0$, we have

$$ C(p) = pe - \frac{\pi^2 e}{2} p(-\log p)^{-2} + o(p(-\log p)^{-2}). $$

This asymptotic behavior extends to sparse Barak-Erdős graphs, as long as $p_n$ decays to 0 slowly enough, we have

$$ \frac{L_n}{np_n} = e - \frac{\pi^2 e}{2(-\log p_n)^2} (1 + o(1)). \qquad (5.18) $$

The question of distinguishing sequences $p_n$ for which $L_n$ exhibit a behavior similar to (5.16) or (5.18), or do distinguish an intermediate behavior remains open. In order to obtain a proper insight on this question, we begin by giving a proof scheme for Theorem 5.16.

*Scheme of proof of Theorem 5.16.* We first remark that typically, the leftmost blue particle born from a given red particle is produced at a time when the parent is at a distance of order $-\log p$ of the position of the leftmost current red particle in the system. Therefore, for any $\delta > 0$, the set of red particles alive at a large generation $n$ is included in $\mathcal{D}_{(1+\delta)\lfloor -\log p \rfloor}$, and contains all particles alive at generation $n$ in $\mathcal{D}_{(1-\delta)\lfloor -\log p \rfloor}$ for all $p$ large enough.

Using (5.17), we deduce that the leftmost red particle at a large generation $n$ is situated in $[nv_{(1-\delta)\lfloor -\log p \rfloor}, nv_{(1+\delta)\lfloor -\log p \rfloor}]$. Then, using Corollary 5.14, we deduce that with high probability,

$$ \frac{L_n}{p} \in [nv_{(1-\delta)\lfloor -\log p \rfloor}, nv_{(1+\delta)\lfloor -\log p \rfloor}] $$

Letting $n \to \infty$, then $\delta \to 0$ and finally $p \to 0$, Theorem 5.16 will hold. $\square$

We observe that in the proof of Theorem 5.16, we used the coupling with the branching random walk to compare the connected component of the vertex 1 with the set of particles in the branching random walk staying at all time within distance $-\log p$ from the position of the leftmost particle. Note also that we are interested in the position of the minimal displacement at time $np_n$.

Chen [27] proved that in a branching random walk, the trajectory yielding to the minimal position at time $n$ can be scaled in time by a factor $n$ and in space by a factor $\sqrt{n}$ to converge to a
standard Brownian excursion. In particular, we know that typical trajectory yielding to the minimal position at time $n$ remains at all time within distance $\sqrt{t}$ from the leftmost position. As a result, it is expected that as long as $-\log p_n \gg \sqrt{np_n}$, the asymptotic behavior of the position of the minimal displacement at time $n$ is similar in the branching random walk and in the $-\log p_n$-branching random walk. On the opposite, if $-\log p_n \ll (-\log p_n)$, similar techniques as the ones used in [77] show that the minimal displacement becomes more similar to the branching process with selection.

As a result, we formulate the following conjecture for the asymptotic behavior of the length of the longest path starting from 1 in sparse Barak-Erdős graphs.

**Conjecture 5.17.** Let $(p_n)$ be a null sequence with $np_n = \infty$.

1. If $\lim_{n \to \infty} np_n / \log n^2 = 0$, then (5.16) holds.

2. If there exists $\delta > 0$ such that $\lim_{n \to \infty} np_n / (\log n)^{2+\delta} = \infty$, then (5.18) holds.

## 5.5 Extension to stochastic ordered graphs with geometry

In this section, we consider the two following planar extensions of the Barak-Erdős graph. In both cases, the set of vertices of the graph is $\mathbb{N}^2$. In the first model, for all pair of distinct vertices $(i, j)$ and $(k, l)$ a directed edge between $(i, j)$ and $(k, l)$ is present with probability $p$ independently on any other edges if and only if $i \ge k$ and $j \ge l$ (and $(i, j) \ne (k, l)$). This random graph is written $G^{(1)}(p)$. In the second model, a directed edge is present with probability $p$ between $(i, j)$ and $(k, l)$ if and only if $i = k$ and $j > l$, or $j = l$ and $i > k$. We denote by $G^{(2)}(p)$ this random graph. We also write $G^{(1)}(n, m, p)$ (respectively $G^{(2)}(n, m, p)$) the restriction of $G^{(1)}(p)$ (resp. $G^{(2)}(p)$) to the vertex set $\{1, \dots, n\} \times \{1, \dots, m\}$.

Similarly to the Barak-Erdős graph, the connected component of the vertex (1, 1) can be described, in the sparse limit $p \to 0$ as a branching random walk. More precisely, in the graph $G^{(1)}(p)$, rescaling the vertex indices by $p^{1/2}$, the connected component of (1, 1) converges to a branching random walk $X^{(1)}$ on $\mathbb{R}_+^2$, in which a particle at position $(x, y)$ gives birth to a Poisson process of offspring on $[x, \infty) \times [y, \infty)$ with unit intensity. This branching random walk provides an example of stable branching process as defined in [14].

When scaling the vertex indices by $p$, the connected component of the vertex (1, 1) converges, as $p \to \infty$ to a branching random walk $X^{(2)}$ on $\mathbb{R}_+^2$ in which a particle at position $(x, y)$ gives birth to a Poisson process of offspring on $\{x\} \times [y, \infty)$ and an independent Poisson process of offspring on $[x, \infty) \times \{y\}$ with unit intensity.

Using similar methods as the ones used in the Barak-Erdős graph, we can obtain the following results. First, observing that the law of $X^{(1)}$ is stable by the transformation $(x, y) \mapsto (x/a, ay)$, and that

$$ \lim_{n \to \infty} \frac{1}{n} \min \|X^{(1)}(u)\|_{\infty} = \frac{2}{e} \quad \text{a.s.} $$

and applying the same proof as in [86], we obtain the following estimate for the length of the longest path starting from vertex 1.

**Theorem 5.18.** We denote by $L_{n,m}(p)$ the length of the longest path issued from (1, 1) in $G^{(1)}(n, m, p)$.

1. If $p \to 0$ with $mnp \to t$, then $L_{n,m}(p)$ converges in law to $K(t) = \max\{|u| : X^{(1)}(u) \in [0, \sqrt{t}]^2\}$.

2. If $p \to 0$ with $mnp \to t$, then $L_{n,m}(p)/\sqrt{mnp} \to e/2$ in probability.

Similarly, we can obtain the following estimate for the asymptotic behavior of the length of the longest path issued from 1 in the graph $G^{(2)}(n, n, p)$.

**Theorem 5.19.** We denote by $L_n(p)$ the length of the longest path issued from (1, 1) in $G^{(2)}(n, n, p)$.

1. If $p \to 0$ with $np \to t$, then $L_n(p)$ converges in law to $K(t) = \max\{|u| : X^{(1)}(u) \in [0, t]^2\}$.

2. If $p \to 0$ with $np \to t$, then $L_n(p)/np \to e/(1 - \log 2)$ in probability.
## 5.6 Longest path in the Barak-Erdős graph

We now turn to the length of the longest path in the Barak-Erdős graph in the sparse regime. Again, Newman [86, Theorem 2] obtained a completed description of the asymptotic behavior of $L_n(p_n)$ as long as $np_n = O(\log n)$. Moreover, he proved that as long as $np_n \gg \log n$, then the asymptotic behavior of $L_n(p_n)$ and $L_n^{(1)}(p_n)$ are similar.

We decompose the asymptotic behavior of the length of the longest path in the Barak-Erdős graph along the following lines. We first assume that $p_n = o(n^{1-\epsilon})$ for some $\epsilon > 0$. In this situation, the support of the length of the longest path in the Barak-Erdős graph converges to one or two points, depending on the exact asymptotic behavior of $p_n$. Remark that with high probability 1 will not be connected to any other vertex in the graph, so $L_n^{(1)}(p_n)$ converges to 0 in probability.

**Theorem 5.20** (Newman [86], Theorem 2). Let $(p_n)$ be a null sequence such that $\lim_{n \to \infty} n^{1+\epsilon}p_n = 0$ for some $\epsilon > 0$.

1. If $\lim_{n \to \infty} n^2 p_n = 0$, then $\lim_{n \to \infty} L_n(p_n) = 0$ in probability.

2. If there exists $m \in \mathbb{N}$ such that

$$ \lim_{n \to \infty} p_n n^{1+1/m} = \infty \quad \text{and} \quad \lim_{n \to \infty} p_n n^{1+1/(m+1)} = 0, $$

then $L_n(p_n) \to m$ in probability.

3. If there exists $\theta \in (0, \infty)$ and $m \in \mathbb{N}$ such that

$$ \lim_{n \to \infty} p_n n^{1+1/m} = \theta, $$

then $\lim_{n \to \infty} \mathbb{P}(L_n(p_n) = m-1) = 1 - \lim_{n \to \infty} \mathbb{P}(L_n(p_n) = m) = e^{-\frac{\theta m}{(m+1)!}}$.

*Proof.* This result is obtained using first and second moment methods, computing the first and second moment of the number $Z_k(n, p)$ of paths of length $k$. Then, using the Markov inequality from one part and the Cauchy-Schwarz inequality for the second, we have

$$ \mathbb{E}(Z_k(n, p)) \geq \mathbb{P}(Z_k(n, p) \geq 1) \geq \mathbb{E}(Z_k(n, p))^2 / \mathbb{E}(Z_k(n, p)^2). $$

We first note that in the complete graph on the vertex set $\{1, \dots, n\}$, there is $\binom{n}{k+1}$ increasing paths, each of which having probability $p^k$ to be open in the Barak-Erdős graph. Therefore,

$$ \mathbb{E}(Z_k(n, p)) = \binom{n}{k+1} p^k \approx \frac{n^{k+1} p^k}{k!}. $$

With similar computations, we have that

$$ \mathbb{E}(Z_k(n, p)^2) = \sum_{\substack{1 \le i_1 \le \cdots \le i_{k+1} \le n \\ 1 \le j_1 \le \cdots \le j_{k+1} \le n}} \mathbb{P}((i_1, i_2), \dots, (j_k, j_{k+1}) \in E(G)). $$

Observing that if two paths have $r$ vertices in common, they have at most $r-1$ edges in common, we obtain

$$ \begin{aligned} \mathbb{E}(Z_k(n, p)^2) & \le \binom{n}{k+1} \binom{n-k-1}{k+1} p^{2k} + \sum_{r=1}^{k+1} \binom{n}{k+1} \binom{n-k-1}{k-r+1} p^{2k-r-1} \\ & \approx (n^{k+1} p^k)^2 + \sum_{r=1}^{k+1} n^{2k+2-r} p^{2k-r-1}. \end{aligned} $$

If $n^2 p_n \to 0$ as $n \to \infty$, we have

$$ \mathbb{P}(L_n(p_n) \ge 1) = \mathbb{P}(Z_1(n, p_n) \ge 1) \le \frac{n(n-1)}{2} p_n. $$
Therefore $\lim_{n \to \infty} \mathbb{P}(L_n(p_n) = 0) = 1$, showing that $L_n(p_n) \to 0$ in probability.

We now assume that there exists $m \in \mathbb{N}$ such that

$$ \lim_{n \to \infty} p_n n^{1+1/m} = \infty \quad \text{and} \quad \lim_{n \to \infty} p_n n^{1+1/(m+1)} = 0. $$

We observe that

$$ \mathbb{P}(L_n(p_n) \ge m+1) = \mathbb{P}(Z_{m+1}(n, p_n) \ge 1) \le \mathbb{E}(Z_{m+1}(n, p_n)) \le \binom{n}{m+1} p_n^m. $$

Then, as $\lim_{n \to \infty} n^{m+1} p_n^m = 0$, we deduce that $\lim_{n \to \infty} \mathbb{P}(L_n(p_n) \ge m+1) = 0$. Similarly, we have

$$ \begin{aligned} \mathbb{P}(L_n(p_n) \ge m) &= \mathbb{P}(Z_m(n, p_n) \ge 1) \ge \mathbb{E}(Z_m(n, p_n))^2 / \mathbb{E}(Z_m(n, p_n)^2) \\ &\ge \frac{1}{1 + \sum_{r=1}^{m+1} \binom{n-k-1}{k-r+1} p_n^{r-2}}. \end{aligned} $$

But as $\lim_{n \to \infty} n^{-r} p_n^{-r-2} = 0$ for all $r \le m+1$ by assumption, we obtain that $\lim_{n \to \infty} \mathbb{P}(L_n(p_n) \ge m) = 1$, completing the proof that $L_n(p_n) \to m$ in probability in that case.

Next, assuming that $p_n^m n^{m+1} \to \theta^m$, we show that $Z_m(n, p_n)$ converges to a Poisson random variable with parameter $\theta^m/(m+1)!$. Indeed, $Z_m(n, p_n)$ is the sum of $\binom{n}{m+1}$ Bernoulli random variables with parameter $\theta^m/n^{m+1}$. We then observe that the sum of the covariances of these Bernoulli random variables converges to 0 as $n \to \infty$, proving this convergence. As a result, we obtain

$$ \lim_{n \to \infty} \mathbb{P}(L_n(p_n) \ge m) = \lim_{n \to \infty} \mathbb{P}(Z_m(n, p_n) \ge 1) = 1 - e^{-\theta^m/m!}, $$

and as $\mathbb{P}(L_n(p_n) \ge m-1) \to 1$ using the same computations as above, we have obtained the convergence in law of $L_n(p_n)$. $\square$

We then consider the asymptotic behavior of $L_n(p_n)$ assuming that $np_n = o(\log n)$. In this regime, recall that the length of the longest path issued from vertex 1 is of order $enp_n = o(\log n)$. The following result holds.

**Theorem 5.21.** Let $(p_n)$ be a null sequence such that $\lim_{n \to \infty} n^{1+\epsilon} p_n = \infty$ for all $\epsilon > 0$ with $\lim_{n \to \infty} np_n / \log n = 0$. We set

$$ \ell_n = \sup \left\{ k \in \mathbb{N} : \binom{n}{k} p_n^k \le 1 \right\}, $$

then $\lim_{n \to \infty} L_n(p_n) / \ell_n = 1$ in probability.

This result is obtained in the same way as Theorem 5.20, using first and second moment methods to bound the probability of existence of a path of length $\ell_n(1 \pm \epsilon)$. Using similar methods again, one can turn to the case $p_n \sim \gamma \log n/n$. In this situation, $L_n^{(1)}(p_n) \sim \gamma e \log n$, and the longest path also is of order $\log n$, but with a larger constant.

**Theorem 5.22.** Let $(p_n)$ be a sequence such that $p_n \sim \gamma \log n/n$ as $n \to \infty$ for some $\gamma \in (0, 1)$. Then

$$ \lim_{n \to \infty} L_n(p_n) / np_n = eA(\gamma) \quad \text{in probability,} $$

where $A(\gamma)$ is the only solution larger than 1 of $x \log x = (e\gamma)^{-1}$.

Finally, when $np_n \gg \log n$, the length of the longest path and the longest path starting from 1 have similar orders of magnitude.

**Theorem 5.23.** Let $(p_n)$ be a null sequence such that $\lim_{n \to \infty} np_n / \log n = \infty$, then

$$ \lim_{n \to \infty} L_n(p_n) / np_n = e. $$

To prove that $\lim_{n \to \infty} \mathbb{P}(L_n(p_n) > np_n e) = 0$, we use again first moment estimates. Using that $L_n(p_n) \ge L_n^{(1)}(p_n)$ on the other hand and Theorem 5.15, we conclude to Theorem 5.23.
## 5.7 Shortest path

Based on similar computations with the previous section, we are able to compute the asymptotic behavior of the length of the shortest path between 1 and $n$ in the Barak-Erdős graph $\vec{G}(n, p)$. The results in this section are based on [81]. In this section, we write

$$S_n(p) = \min \left\{ k \in \mathbb{N} : \exists i_1 < \dots < i_{k-1} : (1, i_1), \dots, (i_{k-1}, n) \in E(\vec{G}(n, p)) \right\}.$$

the length of the shortest path linking 1 and $n$. By convention, $S_n = \infty$ if there is no path between 1 and $n$.

Observe that for a fixed value of $p$, the edge $(1, n)$ is present with probability $p$, and if this edge is not present, the events

$$((1, k), (k, n) \in E(\vec{G}(n, p))), 2 \le k \le n)$$

are independent of one another, and with same probability $p^2$ of occurrence. As a result, we have

$$\mathbb{P}(S_n(p) = 1) = p, \quad \mathbb{P}(S_n(p) = 2) = (1-p)(1-(1-p)^{n-2}).$$

Therefore, $S_n(p)$ converges in distribution, as $n \to \infty$, to a random variable $S_\infty(p)$ with $\mathbb{P}(S_\infty(p) = 1) = 1 - \mathbb{P}(S_\infty(p) = 2) = p$. With similar computations, it appears that if $p_n \to 0$ with $np_n^2 \to \infty$, then $S_n(p_n) \to 2$ in probability as $n \to \infty$.

The above computation extends to larger paths, and we obtain the following extension of the results of Section 5.6.

**Theorem 5.24.** Let $(p_n)$ be a null sequence.

1. If there exists an integer $m \in \mathbb{N}$ such that

$$\lim_{n \to \infty} p_n n^{1-1/(m+1)} = \infty \quad \text{with} \quad \lim_{n \to \infty} p_n n^{1-1/m} = 0,$$

then $S_n(p_n) \to m + 1$ in probability.

2. If there exists an integer $m \in \mathbb{N}$ such that

$$\lim_{n \to \infty} p_n n^{1-1/m} = \theta \in \mathbb{R}_+,$$

then $\lim_{n \to \infty} \mathbb{P}(S_n(p_n) = m) = 1 - \lim_{n \to \infty} \mathbb{P}(S_n(p_n) = m+1) = e^{-\theta^m/(m-1)!}$

3. If $\lim_{n \to \infty} n^{1-\epsilon} p_n = \infty$ for all $\epsilon > 0$, then $\lim_{n \to \infty} S_n(p_n)/\ell_n = 1$ in probability, where $\ell_n$ is the same quantity as in Theorem 5.21.

For a graph with too small value of $p$, the vertices 1 and $n$ will no longer be connected with high probability. It is well-known for Erdős-Rényi graphs that as long as $p_n > (1 + \epsilon)/n$, vertices 1 and $n$ will be in the same connected component with positive probability. However, this does not implies the existence of a directed path from 1 to $n$ in the graph, and in fact the coupling with the branching random walk shows that as long as $\lim_{n \to \infty} np_n < \infty$, the probability that 1 and $n$ are in the same connected component goes to 0 as $n \to \infty$.

The critical decay rate at which the probability that 1 and $n$ are connected in $\vec{G}(n, p_n)$ with positive probability is currently unknown, as well as the asymptotic behavior of $S_n(p_n)$ for $p_n \sim (\log n)^\alpha/n$ for some $\alpha > 0$.

# 6 Regenerative properties of directed random graphs

We now return to the setup of Section 2.1 and consider the case where we are given a sequence $p_1, p_2, \dots$ of numbers in $[0, 1]$ such that

$$0 < p_1 < 1.$$
The case $p_1 = 1$ is excluded because it uninteresting. We assume that $p_1 > 0$ so that the regenerative methods work: as will be shown in Section 6.1, we can then break the graph into i.i.d. pieces. For the $p_1 = 0$ case see Remark 6.11 below.

We then consider the random graph on $\mathbb{Z}$ such that the pair $(i, j) \in \mathbb{Z} \times \mathbb{Z}$ is a vertex if $i < j$ and with probability $p_{j-i}$, independently from pair to pair. Let us denote this graph by $\vec{G}(\mathbb{Z}, (p_j))$. The reason for introducing probabilities that depend on the physical distance between vertices is twofold: from the point of view of applications, it is more natural; mathematically, the case of constant $p_j$, insofar as regenerative properties are concerned, is not much different from the more general case. Let

$$q_j := 1 - p_j, \quad Q_j := q_1 \cdots q_j, \quad Q_0 := 1.$$

Our goal is to prove a functional central limit theorem for the quantity $L_{0,n}$, the maximum length of all path in $\vec{G}(\mathbb{Z}, (p_j))$ with endpoints between 0 and $n$. This is Theorem 6.9. To do this, we first exhibit some regenerative properties of the graph and then estimate moments of the distances between two typical skeleton points.

## 6.1 Breaking the graph into independent cycles

We showed in Lemma 2.6, that if the sequence $p_j$ does not converge to 0 too fast, in the sense that condition (2.7) of Lemma 2.6,

$$\sum_{n=1}^{\infty} Q_n < \infty,$$

holds, then the skeleton set $\mathcal{S}$ of all vertices $v$ such that $u \rightsquigarrow v \rightsquigarrow w$ for all $u < v < w$ (where $i \rightsquigarrow j$ stands for “there is a path from $i$ to $j$”) is infinite in both directions a.s. and has strictly positive rate

$$\lambda = \prod_{j=1}^{\infty} (1 - Q_j)^2 > 0, \qquad (6.1)$$

as in (2.8). We label the elements of $\mathcal{S}$ by random integers $\Gamma_k$, $k \in \mathbb{Z}$, so that

$$\cdots < \Gamma_{-1} < \Gamma_0 \le 0 < \Gamma_1 < \Gamma_2 < \cdots \qquad (6.2)$$

We therefore know that $\mathbb{P}(0 \in \mathcal{S}) = \lambda > 0$ and

$$\mathbb{E}(\Gamma_{k+1} - \Gamma_k | 0 \in \mathcal{S}) = \mathbb{E}(\Gamma_{k+1} - \Gamma_k | \Gamma_0 = 0) = 1/\lambda < \infty, \quad k \in \mathbb{Z}.$$

Consider now the random sequence

$$\alpha^{(0)} := (\alpha_1^{(0)}, \alpha_2^{(0)}, \dots),$$

consisting of independent entries with

$$\mathbb{P}(\alpha_j^{(0)} = 1) = 1 - \mathbb{P}(\alpha_j^{(0)} = -\infty) = p_j, \quad j \in \mathbb{N},$$

and let $\alpha^{(n)}$, $n \in \mathbb{Z}$, be i.i.d. copies of $\alpha^{(0)}$. Then we can construct $\vec{G}(\mathbb{Z}, (p_j))$ as the graph on $\mathbb{Z}$ with edge set

$$\{(i, j) \in \mathbb{Z} \times \mathbb{Z} : i < j, \alpha_{j-i}^{(i)} = 1\}.$$

(Note that the random variable $\alpha_{j-i}^{(i)}$ was denoted by $\alpha_{i,j}$ in (2.2).) We refer to the random object

$$\mathcal{C}_k := (\alpha^{(n)}, \Gamma_k \le n < \Gamma_{k+1})$$

as the $k$th “cycle”, $k \in \mathbb{Z}$. Let $\vec{G}_k$ be the induced subgraph of $\vec{G}(\mathbb{Z}, (p_j))$ on the set of vertices $\{v \in \mathbb{Z} : \Gamma_k \le v \le \Gamma_{k+1}\}$, that is, keep only those edges with endpoints in this set. The following was proved in [39].
**Lemma 6.1.** Assume that (2.7) holds. Then, conditional on {$0 \in \mathcal{S}$}, the cycles $\mathcal{C}_k$, $k \in \mathbb{Z}$, are i.i.d. and the random graphs $\vec{\mathcal{G}}_k$, $k \in \mathbb{Z}$, are i.i.d.

*Sketch of proof.* It suffices to show that $\mathcal{C}_0$ is independent of $(\mathcal{C}_{-1}, \mathcal{C}_{-2}, \dots)$ conditional on $0 \in \mathcal{S}$. Let $\mathcal{F}^+ := \sigma(\alpha^{(n)}, n > 0)$, $\mathcal{F}^- := \sigma(\alpha^{(n)}, n < 0)$. As in the proof of Lemma 2.6, for each $j \in \mathbb{Z}$, consider the largest of the vertices $u < j$ such that $(u, j)$ is an edge, letting $\ell(j) = j - u$ be its distance from $j$. Similarly, consider the smallest of the vertices $v > j$ such that $(j, v)$ is an edge, setting $r(j) = v - j$. Note that

$$ \{0 \in \mathcal{S}\} = \{\Gamma_0 = 0\} = \{r(-1) \le 1, r(-2) \le 2, \dots; \ell(1) \le 1, \ell(2) \le 2, \dots\} \quad (6.3) $$

Define the random variables

$$ \begin{aligned} \hat{\Gamma}_{-1} &:= \max\{n < 0 : r(n-1) \le 1, r(n-2) \le 2, \dots; \ell(n+1) \le 1, \dots, \ell(0) \le |n|\} \\ \hat{\Gamma}_1 &:= \min\{n > 0 : r(0) \le n, \dots, r(n-1) \le 1; \ell(n+1) \le 1, \ell(n+2) \le 2, \dots\} \end{aligned} $$

and observe that

$$ \text{if } \Gamma_0 = 0 \text{ then } \Gamma_{-1} = \hat{\Gamma}_{-1}, \Gamma_1 = \hat{\Gamma}_1. $$

Whereas $\Gamma_{-1}$ is not $\mathcal{F}^-$-measurable, the random variable $\hat{\Gamma}_{-1}$ is. Also, $\hat{\Gamma}_1$ is $\mathcal{F}^+$ measurable. Similarly, each cycle $\mathcal{C}_k$ with negative index $k$ becomes equal to an $\mathcal{F}^-$-measurable random object. This argument shows that $\mathcal{C}_0$ is independent of $(\mathcal{C}_{-1}, \mathcal{C}_{-2}, \dots)$, conditional on $\{\Gamma_0 = 0\}$. That all the $\mathcal{C}_k$, $k \in \mathbb{Z}$, are identically distributed, under the same conditioning, follows from stationarity. For the last claim observe that $\vec{\mathcal{G}}_k$ is a function of $\mathcal{C}_k$ for all $k \in \mathbb{Z}$. $\square$

**Remark 6.2.** Let $\alpha$ denote the map $n \mapsto \alpha^{(n)}$. For all $k \in \mathbb{Z}$, denote by $\theta^k \alpha$ the map $n \mapsto \alpha^{(n+k)}$. Note that the probability measure $\mathbb{P}$ relates to $\mathbb{P}(\cdot|0 \in \mathcal{S})$ as follows. Let $\Phi(\alpha)$ be a measurable bounded function of $\alpha$. Denote by $\theta^k \Phi$ the function $\alpha \mapsto \Phi(\theta^k \alpha)$. Then

$$ \mathbb{E}(\Phi) = \lambda \mathbb{E} \left\{ \sum_{\Gamma_0 \le k < \Gamma_1} \theta^k \Phi \middle| 0 \in \mathcal{S} \right\}. $$

For a simple proof of this, see [69]. This implies that (without conditioning on $0 \in \mathcal{S}$), the cycles $\mathcal{C}_k$, $k \in \mathbb{Z} \setminus \{0\}$, are i.i.d. each with the same distribution as the conditional distribution of $\mathcal{C}_0$ given $0 \in \mathcal{S}$. Moreover, $\mathcal{C}_0$ is independent of the rest of the cycles, and its law can be found by the last formula. In particular, $\mathbb{E}(\Gamma_{k+1} - \Gamma_k) = \mathbb{E}(\Gamma_{k+1} - \Gamma_k | \Gamma_0 = 0) = 1/\lambda$ for all $k \ne 0$. For $k = 0$, letting $\Phi = \Gamma_1 - \Gamma_0$ in the above formula, we have $\mathbb{E}(\Gamma_1 - \Gamma_0) = \lambda \mathbb{E}(\Gamma_1^2 | \Gamma_0 = 0)$ may be equal to $\infty$ unless a condition stronger that (2.7) is assumed.

## 6.2 Moments of auxiliary stopping times

We aim at studying the moments of the auxiliary random vertices $\mu$ and $\nu$, defined in (6.5) and (6.8), respectively. These random vertices are positive integers and stopping times with respect to the filtration, in the index $n$, generated by the $(\alpha^{(k)}, k \le n)$. The stopping time property is crucial in constructing, in Section 6.3, certain iterates of $\mu$ and $\nu$, used for identifying the least positive skeleton point of the graph.

We need some notation, partially introduced in the proof of Lemma 2.6. Recalling that $i \rightsquigarrow j$ means that there is a path in $\vec{\mathcal{G}}(\mathbb{Z}, \alpha)$ from $i$ to $j$, we let $J \subset \mathbb{Z}$ and write $i \rightsquigarrow J$ if $i \rightsquigarrow j$ for all $j \in J$. Similarly, $J \rightsquigarrow i$ means $j \rightsquigarrow i$ for all $j \in J$. We will need the events

$$ \begin{aligned} A_{u,v}^{+} &= \{u \rightsquigarrow [u+1, v]\}, \\ A_{u,v}^{-} &= \{[u, v-1] \rightsquigarrow v\}, \end{aligned} \quad (6.4) $$

where $u < v$ are integers. By $[a, b]$ when $a, b$ are integers, $a < b$, we mean the set $\{a, a+1, \dots, b\}$. We have $\ell(j) = \max\{k > 0 : \alpha_{j-k,j} = 1\}$ and $r(j) = \min\{k > 0 : \alpha_{j,j+k} = 1\}$ for all $j \in \mathbb{Z}$. Hence
$j - \ell(j)$ is the first predecessor of $j$ in $\vec{G}(\mathbb{Z}, (p_j))$ and $j + r(j)$ its first successor. The $\ell(j)$, $j \in \mathbb{Z}$ are i.i.d. with common distribution determined by

$$ \mathbb{P}(\ell(0) > k) = Q_k = \mathbb{P}(r(0) > k). $$

In particular, $\mathbb{E}\ell(0) = \mathbb{E}r(0) = \sum_{k=0}^{\infty} Q_k$. A few moments of reflection show that, for $d \in \mathbb{N}$,

$$ A_{u,u+d}^{+} = \{\ell(u+1) \le 1, \dots, \ell(u+d) \le d\} $$

$$ A_{u-d,u}^{-} = \{r(u-1) \le 1, \dots, r(u-d) \le d\}. $$

Both events decrease as $d$ increases. Define the random variable

$$ \mu := \inf\{k \in \mathbb{N} : A_{0,k}^{+} \text{ fails}\} \qquad (6.5) $$

(where “A fails” stands for “$A^c$ occurs”, that is, $\mathbf{1}_{A^c} = 1$) Since $A_{0,k}^+$ decreases as $k$ increases, we have

$$ \mathbb{P}(\mu > k) = \mathbb{P}(A_{0,k}^{+}) = \mathbb{P}(\ell(1) \le 1, \dots, \ell(k) \le k) = (1 - Q_1) \cdots (1 - Q_k), $$

and this implies that $\mu$ is defective:

$$ \mathbb{P}(\mu = \infty) = \lim_{k \to \infty} (1 - Q_1) \cdots (1 - Q_k) = \sqrt{\lambda} > 0. $$

We also have

$$
\begin{align}
\mathbb{P}(n < \mu < \infty) &= \mathbb{P} \left( A_{0,n}^{+} \cap \bigcup_{k=1}^{\infty} (A_{0,k}^{+})^{c} \right) = \mathbb{P} \left( A_{0,n}^{+} \cap \bigcup_{k=n+1}^{\infty} (A_{0,k}^{+})^{c} \right) = \mathbb{P} \left( A_{0,n}^{+} \cap \left( \bigcap_{k=n+1}^{\infty} A_{0,k}^{+} \right)^{c} \right) \nonumber \\
&= \mathbb{P}(\ell(1) \le 1, \dots, \ell(n) \le n; \{\ell(1) \le 1, \dots, \ell(n) \le n, \ell(n+1) \le n+1, \dots\}^c) \nonumber \\
&= \mathbb{P}(\ell(1) \le 1, \dots, \ell(n) \le n; \{\ell(n+1) \le n+1, \ell(n+2) \le n+2, \dots\}^c) \nonumber \\
&= \mathbb{P}(\ell(1) \le 1, \dots, \ell(n) \le n) \mathbb{P}(\exists k > n \ell(k) > k) \tag{6.6} \\
&= \mathbb{P}(\ell(1) \le 1, \dots, \ell(n) \le n) [1 - \mathbb{P}(\ell(n+1) \le n+1, \ell(n+2) \le n+2, \dots)] \nonumber \\
&= (1 - Q_1) \cdots (1 - Q_n) [1 - (1 - Q_{n+1})(1 - Q_{n+2}) \cdots] \tag{6.7} \\
&= (1 - Q_1) \cdots (1 - Q_n) - \sqrt{\lambda}. \nonumber
\end{align}
$$

We obtain an upper bound of this easily from (6.6):

$$ \mathbb{P}(n < \mu < \infty) \le \mathbb{P}(\exists k > n \ell(k) > k) \le \sum_{k=n+1}^{\infty} \mathbb{P}(\ell(k) > k) = \sum_{k=n+1}^{\infty} \mathbb{P}(\ell(0) > k) = \sum_{k=n+1}^{\infty} Q_k, $$

and this upper bound converges to 0 as $n \to \infty$ by the assumption that the sequence $(Q_n)$ is summable. We also have an asymptotic lower bound by using (6.7), the inequality $(1 - Q_1) \cdots (1 - Q_n) \ge \sqrt{\lambda}$, for all $n$, and the fact that $(1 - e^{-x})/x$ decreases as $x$ increases:

$$ \mathbb{P}(n < \mu < \infty) \ge \sqrt{\lambda} [1 - e^{-(Q_{n+1}+Q_{n+2}+\cdots})] \ge \sqrt{\lambda} \frac{1 - e^{-\mathbb{E}\ell(0)}}{\mathbb{E}\ell(0)} \sum_{k=n+1}^{\infty} Q_k. $$

We have thus proved

**Lemma 6.3.**

$$ \frac{\sqrt{\lambda}}{1 - \sqrt{\lambda}} \frac{1 - e^{-\mathbb{E}\ell(0)}}{\mathbb{E}\ell(0)} \sum_{k=n+1}^{\infty} Q_k \le \mathbb{P}(\mu > n | \mu < \infty) \le \frac{1}{1 - \sqrt{\lambda}} \sum_{k=n+1}^{\infty} Q_k. $$

Since $Q_k = \mathbb{P}(\ell(0) > k)$, the above inequality says that the tail of the distribution of $\mu$ conditional on it being finite is comparable to the “integrated” tail of the distribution of $\ell(0)$. We say that a positive random variable $Z$ has $p$-moment, for $p \ge 1$, if $\mathbb{E}Z^p < \infty$; we say that it has an exponential moment of $\mathbb{E}e^{\theta Z} < \infty$ for some $\theta > 0$. From the above lemma we conclude the following.
**Corollary 6.4.** Conditional on {$\mu < \infty$}, $\mu$ has a p-moment (respectively, exponential moment) if and only if $\ell(0)$ has a $(p+1)$-moment (respectively, exponential moment).

We similarly wish to examine the moments of the random variable

$$ \nu := \inf\{k \in \mathbb{N} : A_{0,k}^{-} \text{ occurs}\}. \qquad (6.8) $$

Since $A_{0,k}^{-}$ is not monotonic in $k$, we need to use an argument different than before. First observe that

$$ \nu = \inf\{k \in \mathbb{N}[0, k-1] \rightsquigarrow k\} = \inf\{k \in \mathbb{N} : r(k-1) \le 1, \dots, r(0) \le k\}. $$

Define a sequence of nonnegative integer-valued random variables $x_n$, $n = 0, 1, \dots$, by $x_0 = 0$ and

$$ x_n = \max\{r(0) - n, r(1) - (n-1), \dots, r(n-1) - 1\}. $$

Then

$$ \nu = \inf\{n \in \mathbb{N} : x_n = 0\}. $$

But the $x_n$ satisfy

$$ x_{n+1} = \max(x_n, r(n)) - 1, \quad n \ge 0, $$

and since the $r(n)$ are i.i.d., the sequence $(x_n)$ is Markovian. For any integer $K > 0$, if $x_n \ge K$, then

$$ x_{n+1} - x_n = (r(n) - x_n)^+ - 1 \le (r(n) - K)^+ - 1. $$

Since $r(0)$ has finite expectation, we have that $\mathbb{E}(r(0) - K)^+ < 1$, for $K$ large enough. Therefore, after the Markov chain leaves the interval $[0, K]$, it is upper-bounded by a random walk with increments distributed like $(r(0) - K)^+ - 1$ whose mean is negative. By standard properties of random walks this implies that the finiteness of the p-th moment of the return time $T_K$ to the set $[0, K]$ is equivalent to the finiteness of the p-th moment of the positive part of the increments and, in turn, to the finiteness of the p-th moment of $r(0)$ which is the same as the p-th moment of $\ell(0)$. Similar conclusions are made for exponential moments. We have thus proved:

**Lemma 6.5.** $\nu$ has a p-moment (respectively, exponential moment) if and only if $\ell(0)$ has a p-moment (respectively, exponential moment).

**Remark 6.6.** Since $\mathbb{P}(\ell(0) > k) = Q_k$, $k \ge 0$, we see that $\ell(0)$ has p-th moment if and only iff $\sum_{k=1}^{\infty} k^{p-1}Q_k < \infty$. and $\ell(0)$ has an exponential moment if and only if $\sum_{k=1}^{\infty} z^kQ_k < \infty$ for some $z > 1$. In particular, these conditions hold if $p_j = p \in (0, 1)$ for all $j$,

## 6.3 Moments of skeleton points and a central limit theorem

We show that not only skeleton points exist but that they can also be constructed recursively and causally. This will be done by means of iterates of the stopping times $\mu$ and $\nu$. We define two interlaced sequences of stopping times

$$ \nu[1] < \mu[1] < \nu[2] < \mu[2] < \nu[3] < \mu[3] < \dots, $$

as follows.

$$ \begin{aligned} \nu[1] &:= \nu \\ \mu[1] &:= \nu + \theta^{\nu}\mu = \inf\{j > \nu : A_{\nu,j}^{+} \text{ fails}\}, \end{aligned} \qquad (6.9) $$

and, recursively, for $k \ge 2$,

$$ \begin{aligned} \nu[k] &:= \inf\{j > \mu[k-1] : A_{\nu[k-1],j}^{-} \text{ occurs}\} \\ \mu[k] &:= \nu[k] + \theta^{\nu[k]}\mu = \inf\{j > \nu[k] : A_{\nu[k],j}^{+} \text{ fails}\}. \end{aligned} \qquad (6.10) $$
It is understood that if for some $k$ we have $\mu[k] = \infty$ then $\nu[j] = \mu[j] = \infty$ for all $j \ge k + 1$. In fact, since $\mu$ is a defective random variable, with $\mathbb{P}(\mu = \infty) = \sqrt{\lambda}$, it follows that the recursion terminates in finitely many steps. Let

$$ K := \inf\{k \ge 1 : \mu[k] = \infty\}. \qquad (6.11) $$

It is easy to see that $K$ is a geometric($\sqrt{\lambda}$) random variable, that is, $\mathbb{P}(K > k) = (1 - \sqrt{\lambda})^k, k \ge 0$. By construction, we have $\nu[K] < \infty$ a.s.

**Remark 6.7.** It may be instructive to provide intuition regarding the construction above. We wish to find a vertex $K$ that has the property $K \rightsquigarrow j$ for all $j > K$ and $i \rightsquigarrow K$ for all $0 \le i < K$. (This is not quite saying that $K$ is a skeleton point because we don't care whether negative vertices lead to $K$ via a path.) Keep in mind that $\nu$ is a.s. finite but $\mu$ has positive probability that it be infinity. We first have that, $A_{0,\nu}^{-}$ holds. that is, $i \rightsquigarrow \nu$ for all $0 \le i < \nu$. Now define $\mu[1]$ such that $\mu[1] - \nu[1]$ has law of $\mu$. Suppose it so happens that $\mu[1] = \infty$. This means, by definition, that $A_{\nu,j}^{+}$ holds for all $j > \nu$, that is, $\nu \rightsquigarrow j$ for all $j > \nu$. And so, the vertex $K = \nu$ has the required properties. If $\mu[1]$ is not $\infty$, then we repeat the procedure as many times as is required until we obtain one that is infinity.

Using the observation that $\nu[k]$ and $\mu[k]$ are stopping times with respect to the filtration $(\mathcal{F}_n^-)_{n \ge 0}$, where $\mathcal{F}_n^- = \sigma(\alpha^{(k)}, k \le n)$, we easily obtain that

$$ \nu[K] \stackrel{\text{d}}{=} \sum_{i=1}^{\kappa} \nu_i + \sum_{i=1}^{\kappa-1} \mu_i, $$

where $\kappa, \nu_1, \nu_2, \dots, \mu_1, \mu_2, \dots$ are independent, with $\kappa \stackrel{\text{d}}{=} K$, hence geometric($\sqrt{\lambda}$), $\nu_i \stackrel{\text{d}}{=} \nu$, and $\mathbb{P}(\mu_i \in \cdot) = \mathbb{P}(\mu \in \cdot | \mu < \infty)$.

**Lemma 6.8.** $\nu[K]$ has a $p$-moment (respectively, exponential moment) if and only if $\ell(0)$ has a $(p+1)$-moment (respectively, exponential moment).

*Proof.* From Lemma 6.5, we have that $\sum_{i=1}^{\kappa} \nu_i$ has an exponential (respectively, $p$-th) moment if and only if $\ell(0)$ has an exponential (respectively, $p$-th) moment. From Corollary 6.5, we have that $\sum_{i=1}^{\kappa-1} \mu_i$ has an exponential (respectively, $p$-th) moment if and only if $\ell(0)$ has an exponential (respectively, $(p+1)$-th) moment. $\square$

**Theorem 6.9.** Let $p \ge 1$.

(i) $\mathbb{E}((\Gamma_1 - \Gamma_0)^p | \Gamma_0 = 0) < \infty$ if and only if $\sum_{k=1}^{\infty} k^p Q_k < \infty$

(ii) The distribution of $\Gamma_1 - \Gamma_0$ conditional on $\Gamma_0 = 0$ has an exponential moment if and only if $\sum_{k=1}^{\infty} z^k Q_k < \infty$ for some $z > 1$.

*Proof.* By the definition of $\nu$ and $\mu$ we easily see that

$$ [0, \nu[K] - 1] \rightsquigarrow \nu[K] \rightsquigarrow [\nu[K] + 1, \infty) \text{ a.s.} $$

In fact, $\nu[K]$ is the least $j \ge 1$ such that $[0, j - 1] \rightsquigarrow j \rightsquigarrow [j + 1, \infty)$. Note that

$$ (-\infty, -1] \rightsquigarrow 0 \text{ and } [0, \nu[K] - 1] \rightsquigarrow \nu[K] \text{ implies } (-\infty, \nu[K] - 1] \rightsquigarrow \nu[K]. $$

Hence, conditional on 0 being a skeleton point ($\Gamma_0 = 0$), we have that $\nu[K]$ is the next skeleton point:

$$ \mathbb{P}(\nu[K] = \Gamma_1 - \Gamma_0 | \Gamma_0 = 0) = 1. $$

We now use Lemma 6.8 and Remark 6.6 to conclude. $\square$

The results above are used in the proof of the following functional central limit theorem.
**Theorem 6.10.** Consider the random graph $\vec{G}(\mathbb{Z}, (p_j))$, assuming $0 < p_1 < 1$, and

$$ \sum_{k=1}^{\infty} k^2(1-p_1)\cdots(1-p_k) < \infty. $$

For integers $i < j$, let $L_{i,j}$ be the maximum length of all paths with endpoints between $i$ and $j$. Let $\Gamma_k$, $k \in \mathbb{Z}$, be the skeleton points, assuming $\Gamma_0 \le 0 < \Gamma_1$, and $C$ the constant appearing in the law of large numbers for $L_{0,n}$ as in Lemma 2.1. Then

$$ 0 < \sigma^2 := \mathrm{var}(L_{\Gamma_1, \Gamma_2} - C(\Gamma_2 - \Gamma_1)) < \infty \quad (6.12) $$

Define

$$ \ell_n(t) := \frac{L_{0,[nt]} - Cnt}{\sigma\sqrt{\lambda n}}, \quad t \ge 0, \quad n \in \mathbb{N}. $$

Considering the sequence $\ell_n$, $n \in \mathbb{N}$, as a sequence of random elements of the Skorokhod space $D[0, \infty)$ (see [16]), equipped with the topology of local uniform convergence, converges in distribution to a standard Brownian motion.

*Sketch of proof.* We have $\lambda > 0$ because $p_1 > 0$. It is clear that $\sigma^2 > 0$. The reason that $\sigma^2$ is finite follows $L_{\Gamma_1, \Gamma_2} \le \Gamma_2 - \Gamma_1$ and Theorem 6.9 which guarantees that $\mathbb{E}[(\Gamma_1 - \Gamma_2)^2] = \mathbb{E}[(\Gamma_1 - \Gamma_0)^2]\Gamma_0 = 0] < \infty$. From Remark 6.2 we also have that $\mathbb{E}\Gamma_1 < \infty$. Let $N_n = \max\{j \ge 1 : \Gamma_j \le n\}$. By the definition of $\mathcal{S}$, if $v \in \mathcal{S}$ then the maximal path from some $u < v$ to some $w > v$ must necessarily include $v$. Hence

$$ L_{0,n} = L_{0,\Gamma_1} + L_{\Gamma_1,\Gamma_2} + \cdots + L_{\Gamma_{N_n,n}}. $$

We can then write

$$ \ell_n(t) = \frac{L_{0,\Gamma_1} - C\Gamma_1}{\sigma\sqrt{\lambda n}} + \frac{1}{\sigma\sqrt{\lambda n}} \sum_{i=2}^{N_{nt}} [L_{\Gamma_{i-1},\Gamma_i} - C(\Gamma_i - \Gamma_{i-1})] + \frac{L_{\Gamma_{nt},nt} - C(nt - \Gamma_{N_{nt}})}{\sigma\sqrt{\lambda n}} \quad (6.13) $$

Define also

$$ \hat{\ell}_n(t) := \frac{1}{\sigma\sqrt{\lambda n}} \sum_{i=2}^{nt} [L_{\Gamma_{i-1}, \Gamma_i} - C(\Gamma_i - \Gamma_{i-1})], \quad \varphi_n(t) := \frac{N_{nt}}{n}. $$

The first and third terms of (6.13) converge to 0 in distribution, as random elements of $D[0, \infty)$. The middle term is simply equal to $\hat{\ell}_{n\circ\varphi_n}$. Hence the limit of $\ell_n$ exists if and only if the limit of $\hat{\ell}_{n\circ\varphi_n}$ exists, in which case the limits are equal. But $\hat{\ell}_n$ converges in distribution to $\frac{1}{\sqrt{\lambda}}B$, where $B$ is a standard Brownian motion, and $\varphi_n$ converges in distribution to the function $\varphi$, where $\varphi(t) = \lambda t$. Therefore, by the continuity in $D[0, \infty)$, of the composition operator, we have $\hat{\ell}_{n\circ\varphi_n}$ converges in distribution to the process $\frac{1}{\sqrt{\lambda}}B(\lambda t)$, $t \ge 0$, which is equal in distribution to $B$. Hence $\ell_n$ converges in distribution to $B$. $\square$

*Remark 6.11.* We made the assumption that $p_1 > 0$ in order that the set $\mathcal{S}$ serve as a skeleton set over which the graph regenerates, that is, we have independent pieces. If $p_1 = 0$ then $\mathcal{S}$ is useless; for example, $\lambda = 0$ in this case. However, if $p_1 = \cdots = p_j = 0$ but $p_{j+1} > 0$ then we can establish a 1-dependent structure.<fnref n="11" /> One can still deal with this case, but one needs a somewhat different technique based on weakly regenerative processes.

*Remark 6.12.* At this stage, we have no estimate for the variance (6.12). Estimating this is probably a complex problem even for the case when all the $p_j$ are equal.

*Remark 6.13.* Observe that in $\vec{G}(\mathbb{Z}, p)$, with positive probability, there are many maximal length paths between successive skeleton points. Since $\lambda > 0$, this implies that the number of linear extensions of the random partial order induced by the edges on $n$ vertices increases exponentially fast, and this allows one to obtain directly the CLT for the logarithm number of linear extensions [6].

*Remark 6.14.* Note that the events appearing in the definition of $\mathcal{S}$ depend on the entire random sequence of edges but, nevertheless, produce a regenerative structure. This phenomenon, in a more general context, has been studied in [50].

<footnote n="11">¹¹We say that a random sequence $X_i$, $i \in \mathbb{Z}$, is 1-dependent if, for each $i \in \mathbb{Z}$, the sequences $(X_j, j < i)$ and $(X_j, j > i)$ are independent.</footnote>
# 7 Directed random graphs on partially ordered sets

A direction towards generalizations of the Barak-Erdős graph on the set of integers, is to consider a set of vertices $V$ equipped with a partial order. The directed random graph must respect the partial order of $V$. We will consider two cases below, that of $V = \mathbb{Z} \times I$ where $I$ is a finite set and that of $V = \mathbb{Z} \times \mathbb{Z}$. We shall deal with law of large numbers and functional central limit theorems and see that asymptotic normality fails. There is an interesting connection with Brownian last passage percolation [56, 11]. The Brownian last passage percolation process is the one defined by (7.1) below. The results of this section are taken from [39] and [72].

## 7.1 Brownian last passage percolation

Consider $V = \mathbb{Z} \times I$ where, for simplicity, let $I = \{0, 1, \dots, M\}$ for a positive integer $M$. Elements of $V$ are denoted by $(u, i)$, $(v, j)$, etc. Define the standard partial order on $V$, denoted by $\ll$ by

$$ (u, i) \ll (v, j) \text{ if } (u, i) \neq (v, j) \text{ and } u \le v, i \le j. $$

Consider the random graph $\vec{G}(V, p)$, with $0 < p < 1$ with edges defined as follows. A pair of vertices $(u, i)$, $(v, j)$, with $(u, i) \ll (v, j)$, form an edge directed from $(u, i)$ to $(v, j)$ with probability $p$, independently from pair to pair. We consider all directed paths from $(u, i)$ to $(v, j)$ and denote by $L_{(u,i),(v,j)}$ the maximum length of all such paths. We also let

$$ L_{u,v}^* = \text{maximum length of all paths with endpoints in the } [u, v] \times I, \quad L_n^* := L_n^*. $$

We are interested in the LLN and CLT for $L_{0,n}^*$ as $n \to \infty$.

Regarding the LLN the ergodic arguments of Section 2.1 go through, provided we consider the shift $\theta$ that acts in the horizontal direction only. We can then easily obtain that, for the same constant $C = C(p)$ corresponding to the Barak-Erdős graph $\vec{G}(\mathbb{Z}, p)$, we have

$$ L_n^*/n \to C, \text{ as } n \to \infty, \text{ a.s. and in } L^1, $$

where $C$ is the constant for the Barak-Erdős graph $\vec{G}(\mathbb{Z}, p)$.

The CLT is more interesting. It involves a process that appears e.g. in [88].

**Theorem 7.1.** Consider the random graph $\vec{G}(\mathbb{Z} \times I, p)$, $I = \{1, \dots, M\}$ and let $L_n^*$ be the maximum length of all paths in $\{0, 1, \dots, n\} \times I$. Then, with $C, \sigma$ as in Theorem 6.10,

$$ \ell_n(t) := \frac{L_{[nt]}^* - Cnt}{\sigma\sqrt{\lambda n}}, \quad t \ge 0, \quad n \in \mathbb{N}, $$

as a sequence of random elements of $D[0, \infty)$ with the local uniform topology, converges in distribution to the process

$$ Z_M(t) := \max_{0=t_0 \le t_1 \le \dots \le t_M = t} \sum_{i=1}^{M} (B^{(i)}(t_i) - B^{(i)}(t_{i-1})), \quad (7.1) $$

where $B^{(1)}, \dots, B^{(M)}$ are independent standard Brownian motions.

*Sketch of proof.* If $\mathcal{S}^{(i)}$ denotes the set of skeleton points of the restriction of $\vec{G}(\mathbb{Z} \times I, p)$ on the line $\mathbb{Z} \times \{i\}$, we have that the $\mathcal{S}^{(i)}$ are independent and all equal in distribution to the set of skeleton points of the Barak-Erdős graph $\vec{G}(\mathbb{Z}, p)$. Hence all the $\mathcal{S}^{(i)}$ are stationary renewal processes on $\mathbb{Z}$ and also aperiodic (in the sense that the greatest common divisor of the positive integers in the support of the distance between successive skeleton points is 1). Therefore the set $\cap_{i \in I} \mathcal{S}^{(i)}$ is also a renewal process with positive rate [74] and the even smaller set

$$ \mathcal{S}^I = \{ x \in \bigcap_{i \in I} \mathcal{S}^{(i)} : \text{ for all } i, j \in I, i < j, \text{ there is an edge between } (x, i) \text{ and } (x, j) \} $$