UKvardate []

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

Sergey Foss, Takis Konstantopoulos, Bastien Mallein, Sanjay Ramassamy

###### Abstract

We consider directed random graphs, the prototype of which being the Barak-
Erdős graph $\overrightarrow{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
$\overrightarrow{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. 1 Introduction
  2. 2 From the Barak-Erdős graph to the infinite bin model
    1. 2.1 Ergodic arguments
    2. 2.2 The infinite bin model corresponding to the Barak-Erdős graph.
  3. 3 The general infinite bin model
    1. 3.1 Definition and first properties of the infinite bin model
    2. 3.2 The speed of the general infinite bin model
    3. 3.3 Coupling words
    4. 3.4 Construction of a stationary version and coupling
    5. 3.5 New expressions for the speed
  4. 4 Analytic properties of the asymptotic length of the longest path
    1. 4.1 First formulas for $C$
    2. 4.2 Analyticity of $C$
    3. 4.3 Power series expansion of $C(p)$ around $p=1$
  5. 5 Longest path of the Barak-Erdős graph in the sparse regime
    1. 5.1 Heuristics on the sparse limit
    2. 5.2 The PWIT and some of its properties
    3. 5.3 Coupling of the PWIT and the Barak-Erdős graph
    4. 5.4 Longest chain issued from the initial vertex
    5. 5.5 Extension to stochastic ordered graphs with geometry
    6. 5.6 Longest path in the Barak-Erdős graph
    7. 5.7 Shortest path
  6. 6 Regenerative properties of directed random graphs
    1. 6.1 Breaking the graph into independent cycles
    2. 6.2 Moments of auxiliary stopping times
    3. 6.3 Moments of skeleton points and a central limit theorem
  7. 7 Directed random graphs on partially ordered sets
    1. 7.1 Brownian last passage percolation
    2. 7.2 Generalization to partially ordered vertex sets and distance-dependent probabilities
    3. 7.3 Convergence to the Tracy-Widom distribution
  8. 8 Weighted Barak-Erdős graphs
    1. 8.1 Finite variance weights
    2. 8.2 Infinite variance weights
  9. 9 Analytic properties of charged graphs
    1. 9.1 The two-weights model
    2. 9.2 Further structure of inter-skeleton pieces
    3. 9.3 Criticality and nondifferentiability
    4. 9.4 $\mathbb{Y}\subset\mathbb{X}_{\text{\rm crit}}$
    5. 9.5 $\mathbb{X}_{\text{\rm crit}}\subset\mathbb{Y}$
  10. 10 Perfect simulation aspects of charged graphs
    1. 10.1 The Max Growth System (MGS)
    2. 10.2 The MGS of a random charged graph, coupling and stationarity
    3. 10.3 Perfect simulation
  11. 11 Additional remarks and open problems

##  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. We
call this a Barak-Erdős graph due to the 1984 paper [10] by Anton 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 [50, 57], from
biology [84, 29, 28] and from physics [58, 59].

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 [41]) 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 [59] 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 $\overrightarrow{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
$\overrightarrow{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 $\overrightarrow{G}(\mathbb{Z},p)$, the rate
$\lambda(p)$ of the skeleton (plotted in Figure 1) equals $\varphi(1-p)^{2}$,
where $\varphi(x)=(1-x)(1-x^{2})\cdots$, 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
$\overrightarrow{G}(\mathbb{Z},p)$ little by little. If we let
$\overrightarrow{G}_{n}$ be $\overrightarrow{G}(\\{1,\ldots,n\\},p)$ then the
sequence $(\overrightarrow{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 [41] 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 [41] was mostly concerned with
an extension of Borovkov’s theory of renovating events [19, 20, 22, 40]. This
approach enabled facilitate good explicit bounds for $C=C(p)$, the LPP
constant for $\overrightarrow{G}(\mathbb{Z},p)$.

Rather than repeating the arguments of [41] we use the IBM derived from
$\overrightarrow{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
[76, 77]. 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\leq p\leq 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^{\prime}(0)=e$. On the
other hand, $C^{\prime\prime}(0)$ does not exist. In fact, the convergence of
$C(p)/p$ to $e$ is very slow. It was shown in [76] 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 [39, 64] 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 [75] 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
$\overrightarrow{G}(\\{1,\ldots,n\\},p_{n})$. We also note that [83] proved
among other results, using branching processes, that if $L_{n}$ is the maximum
length of all paths in $\overrightarrow{G}(\\{1,\ldots,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 $\overrightarrow{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 $\mathscr{S}$ and the
regeneration properties, exhibiting a construction of elements of
$\mathscr{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 [36].

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 $\overrightarrow{G}(\mathbb{Z}\times I,p)$,
where $I$ is a partially ordered set, say a finite set $I=\\{1,\ldots,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 [36]. 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\geq_{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
$\overrightarrow{G}(\mathbb{Z}\times\mathbb{Z},p)$. It was shown in [69] 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 [69] 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 [46] and [42]. 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 [42]). If $u$ is a random
variable representing an edge weight, then we show that $\mathbb{E}u^{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 $\mathbb{E}u^{3}<\infty$. When $\mathbb{E}u^{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 [90].
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 [44] 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\geq
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 $\overrightarrow{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{split}L^{\mathsf{L},\mathsf{R}}_{i,j}&:=\text{ the maximal length of
all paths from $i$ to $j$ ;}\\\ L^{\mathsf{L}}_{i,j}&:=\text{ the maximal
length of all paths from $i$ to some $j^{\prime}\leq j$;}\\\
L^{\mathsf{R}}_{i,j}&:=\text{ the maximal length of all paths from some
$i^{\prime}\geq i$ to $j$;}\\\ L_{i,j}&:=\text{ the maximal length of all
paths from some $i^{\prime}\geq i$ to some $j^{\prime}\leq j$.}\end{split}$
(2.1)

(Superscripts $\mathsf{L}$, $\mathsf{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 $\overrightarrow{G}$ is the Barak-Erdős graph
$\overrightarrow{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 [62]. 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
$\overrightarrow{G}(\mathbb{Z},\alpha)$ with whose set edges is

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

Choosing $-\infty$ rather than $0$ is convenient because if we take any
sequence $i_{0}<i_{1}<\cdots<i_{\ell}$ of integers, for some
$\ell\in\mathbb{N}$, then the quantity
$(\alpha_{i_{0},i_{1}}+\alpha_{i_{1},i_{2}}+\cdots+\alpha_{i_{\ell-1},i_{\ell}})^{+}$
takes values $0$ or $\ell$; it takes value $\ell$ if and only if
$(i_{0},i_{1},\ldots,i_{\ell})$ forms a path in
$\overrightarrow{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^{\mathsf{L},\mathsf{R}}_{1,3}=\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 111Note 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$.

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

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

$L_{i,j}:=\max_{\begin{subarray}{c}i\leq i_{0}<i_{1}<\cdots<i_{\ell}\leq j\\\
\ell\in\mathbb{N}\end{subarray}}(\alpha_{i_{0},i_{1}}+\alpha_{i_{1},i_{2}}+\cdots+\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$ $\mathbb{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
$\overrightarrow{G}(\mathbb{Z},\alpha)$ with endpoints between $i$ and $j$
(consistent with the last of (2.1)) we have

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

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 [62] 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$. ∎

######  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^{\mathsf{L},\mathsf{R}}_{0,n}/n$ exists a.s., one might be
tempted to use the obvious superadditivity

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

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

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

$i\leadsto j\iff\text{ there is a path in
$\overrightarrow{G}(\mathbb{Z},\alpha)$ from $i$ 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}$ there is a path in
$\overrightarrow{G}(\mathbb{Z},\alpha)$ from $\min(i,j)$ to $\max(i,j)$}\\}.$
(2.4)

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

$\mathscr{S}=\mathscr{S}(\alpha)=\\{j\in\mathbb{Z}:\,\alpha\in A_{j}\\}.$
(2.5)

The elements of $\mathscr{S}$ are called skeleton points or skeleton vertices
of the graph $\overrightarrow{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
$\mathscr{S}\raisebox{0.43057pt}{\scriptsize$\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})$ (2.6)

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

######  Lemma 2.4.

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

###### Sketch of proof..

The first claim is due to the Poincaré recurrence lemma [DUR]. The second
claim is from basic properties of stationary point processes. ∎

######  Remark 2.5.

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

The following is taken from [36].

######  Lemma 2.6.

Consider $\overrightarrow{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.$ (2.7)

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

$\lambda=\prod_{j>0}(1-(1-p_{1})\cdots(1-p_{j}))^{2}.$ (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

$\mathscr{S}^{-}$ is an infinite set.

Consider the random variables

$\displaystyle\ell(j)$ $\displaystyle:=\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\leadsto j,\text{ for all }j=1,\ldots,m\\},$

noticing that

$A^{+}_{0,m}=\bigcap_{j=1}^{m}\bigcup_{i=0}^{j-1}\\{i\leadsto
j\\}=\bigcap_{j=1}^{m}\\{\ell(j)\leq j\\}.$

Therefore,

$A^{+}_{0}:=\\{0\leadsto 1,0\leadsto
2,\ldots\\}=\bigcap_{j=1}^{\infty}\\{\ell(j)\leq j\\},$

and so

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

Similarly,

$A_{0}^{-}:=\\{-1\leadsto 0,-2\leadsto 0,-3\leadsto 0,\ldots\\}$

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_{1})\cdots(1-p_{j}))^{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 [83].

######  Corollary 2.8.

Consider the four quantities defined by (2.1) for a Barak-Erdős graph
$\overrightarrow{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^{\mathsf{L}}_{0,n}}{n}=\lim_{n\to\infty}\frac{L^{\mathsf{R}}_{0,n}}{n}=\lim_{n\to\infty}\frac{L^{\mathsf{L},\mathsf{R}}_{0,n}}{n}=C(p)\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

$\mathscr{S}^{+}$, $\mathscr{S}^{-}$ are a.s. infinite with positive rate
$\lambda$. We can easily see that
$L_{0,n}=L^{\mathsf{L},\mathsf{R}}_{0,n}+o(n)$, as $n\to\infty$, a.s.

The conclusion now follows from Lemma 2.1. ∎

######  Remark 2.9.

For a $\overrightarrow{G}(\mathbb{Z},p)$ with $0\leq p\leq 1$, we have that
the rate of its skeleton is given by

$\lambda=\prod_{j=1}^{\infty}(1-(1-p)^{j})^{2}$ (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}+\cdots$, 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},\ldots}{\text{\Large$\mathfrak{1}$}}_{n=\ell_{1}+2\ell_{2}+\cdots}=\sum_{\ell_{1}}q^{\ell_{1}}\sum_{\ell_{2}}q^{2\ell_{2}}\cdots=(1-q)^{-1}(1-q^{2})^{-2}\cdots=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) [48]; see
Andrews [8] for a more modern account. Other algebraic proofs are due to
Jacobi, Euler, and others; see Pólya and Szegő [86, $\mathsection$4, 50-54]
for these proofs.

######  Remark 2.10.

It is interesting to see that for a sparse $\overrightarrow{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 $12$th point is a skeleton point.

Table 1: Average distance between two successive skeleton points in the infinite Barak-Erdős graph with parameter $p$. $p$ | $0.01$ | $0.1$ | $0.3$ | $0.5$ | $0.6$ | $0.8$ | $0.9$
---|---|---|---|---|---|---|---
$1/\lambda$ | $10^{139}$ | $6\times 10^{11}$ | $558.46$ | $11.99$ | $4.9$ | $1.73$ | $1.26$
Figure 1: Plot of the rate $\lambda(p)$ of skeleton points against the
connectivity probability $p$

We used the formula
$\lambda(p)=\left(\sum_{n=-\infty}^{\infty}(-1)^{n}(1-p)^{\frac{3n^{2}-n}{2}}\right)^{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
$\overrightarrow{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
$\overrightarrow{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

$\overrightarrow{G}_{n}=\overrightarrow{G}(\\{1,\ldots,n\\},p).$

To construct $\overrightarrow{G}_{n+1}$ we need to add all edges $(i,n+1)$ for
which $\alpha_{i,n+1}=1$. Conditional on $\overrightarrow{G}_{n}$, the
distribution of $\overrightarrow{G}_{n+1}$ will not change if we permute the
variables $\alpha_{1,n+1},\ldots,\alpha_{n,n+1}$.

We choose to order the variables $\alpha_{1,n+1}$, $i=1,\ldots,n$ by ordering
the vertices $i=1,\ldots,n$, according to decreasing values of
$(L^{\mathsf{R}}_{1,i})_{1\leq i\leq n}$:

$j\preceq i\iff L^{\mathsf{R}}_{1,j}\geq L^{\mathsf{R}}_{1,i},$

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

$X_{n}(\ell):=|\\{1\leq i\leq n:\,L^{\mathsf{R}}_{1,i}=\ell\\}|.$

In particular, $X_{n}(0)$ is the number of vertices $j$ for each none of the
edges $(i,j)$ exist, for any $1\leq 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\leq j\leq n}L^{\mathsf{R}}_{1,j},$

for notational convenience. Hence $X_{n}(L_{n})$ is the number of vertices
$1\leq i\leq n$ such that $L^{\mathsf{R}}_{1,i}$ 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}=[\ldots,\infty,\infty,X_{n}(0),X_{n}(1),\ldots,X_{n}(L_{n}),0,0,\ldots].$
(2.10)

Note that $X_{1}=[\ldots,\infty,\infty,1,0,0,\ldots]$, 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 $\overrightarrow{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 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)+\cdots+X_{n}(L_{n})\leq
I<X_{n}(B_{n})+X_{n}(B_{n}+1)+\cdots+X_{n}(L_{n}),$ (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)={\text{\Large$\mathfrak{1}$}_{\left\\{k=\ell\right\\}}}$.

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}\geq 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(X_{n},\xi_{n+1})+1},$ (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)\leq
z\right\\},$

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 [41] 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 [83]. 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 [41], 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\leq 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

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

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

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

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\left\\{k\in\mathbb{Z}:X(k)>0\right\\},$

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. 222This 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..

##### 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$.

$\cdots$$8$$9$$7$$3$$4$$5$$6$$1$$2$ Figure 2: Representation of the state
$X=[\ldots,2,1,4,2,0,0,\ldots]$ in terms of balls in bins. Balls are
enumerated from right to left.

######  Example 3.1.

Let $X=[\ldots,2,1,4,2,0,0,\ldots]$ be the configuration pictured in Figure 2.
If $\xi=1$ then the next state is $X=[\ldots,2,1,4,2,1,0,\ldots]$. 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=[\ldots,2,1,4,3,0,0,\ldots]$. 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\bigg{\\{}k\in\mathbb{Z}:\,\sum\limits_{j>k}X(j)<\xi\bigg{\\}},$
(3.1)

writing $B(X,\infty)=-\infty$ by convention. 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},$ (3.2)

similarly to (2.12), where $\delta_{k}$ is the element of
$\mathbb{Z}_{+}^{\mathbb{Z}}$ 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)+\cdots+X(F)<\xi\leq X(B)+X(B+1)+\cdots+X(F),\text{ where $F=F(X)$.}$

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

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

######  Definition 3.2 (infinite bin model).

Given a probability measure $\mu$ on
$\overline{\mathbb{Z}}_{+}=\\{0,1,2,\ldots,\infty\\}$, and an i.i.d. random
sequence $(\xi_{n})_{n\geq 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 $\overline{\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),\text{
}\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\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\geq 0)$ be a sequence of i.i.d. random variables with law
$\mu$, we set

$A_{n}=\sum_{k=1}^{n}{\text{\Large$\mathfrak{1}$}_{\left\\{\xi_{k}=0\right\\}}}\quad\text{and}\quad
B_{n}=\sum_{k=1}^{n}{\text{\Large$\mathfrak{1}$}_{\left\\{\xi_{k}=\infty\right\\}}},$

and observe that $(A_{n},B_{n})$ is the same random walk as defined in the
lemma. Moreover, if 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\cdots\circ\Phi_{\xi_{1}}(X_{0})\quad\text{and}\quad
Y_{n+1}=\Phi_{\zeta_{n+1}}(Y_{n})=\Phi_{\zeta_{n+1}}\circ\cdots\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\cdots\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},\ldots,\xi_{n})$
equal to $0$ and $B_{n}$ equal to $-\infty$, the rest being given, in the same
order, by $(\zeta_{1},\ldots,\zeta_{n-A_{n}-B_{n}})$, which completes the
proof. ∎

######  Theorem 3.5 (Speed of the IBM [[41, 76]).

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\leq v_{\mu}\leq 1$, not dependent of $X_{0}$, such that

$\lim_{n\rightarrow\infty}\frac{F(X_{n})}{n}=v_{\mu}\quad a.s.$

The quantity $v_{\mu}$ is called the speed of the IBM($\mu$). This theorem is
proved in Section 3.2 by bounding the IBM($\mu$) 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 $\mu$ is a probability distribution on
$\bar{\mathbb{Z}}_{+}$ with $\mu(\mathbb{N})>0$, then setting
$\nu=\mu(\cdot|\mathbb{N})$, we have (by law of large numbers)

$v_{\mu}=\mu(0)+\mu(\mathbb{N})v_{\nu}.$

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($\mu$) where $\mu$ 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 $\mu$ 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
$\xi\in\mathbb{N}$, $B(X,\xi)\leq B(Y,\xi)$, that is, if for every $\xi$ the
$\xi$-th ball of $X$ is to the left of the $\xi$-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^{\prime}\leq\infty\text{ and }X\preceq Y\text{
then }\Phi_{\xi^{\prime}}(X)\preceq\Phi_{\xi}(Y).$ (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^{\prime}\preceq Y^{\prime}$ implies
$X+X^{\prime}\preceq Y+Y^{\prime}$.

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

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

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 $\mu$ and $\nu$ be two probability measures on $\overline{\mathbb{Z}}_{+}$
such that for every $i\geq 0$ we have $\mu([0,i])\leq\nu([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}(\mu)$ and $(Y_{n})\sim\text{IBM}(\nu)$ such
that $X_{n}\preceq Y_{n}$ for every $n\geq 0$ a.s.

###### Proof.

The assumption that $\mu([0,i])\leq\nu([0,i])$ for all $i$ allows us to define
random $\xi,\xi^{\prime}$, with laws $\mu,\nu$, respectively, such that
$\xi^{\prime}\leq\xi$ a.s. Hence we can build an i.i.d. sequence of pairs
$(\xi_{n},\xi^{\prime}_{n})_{n\geq 1}$ such that $\xi_{n}$ has law $\mu$,
$\xi^{\prime}_{n}$ has law $\nu$ and $\xi^{\prime}_{n}\leq\xi_{n}$ for all
$n\geq 1$. Defining the IBM($\mu$) $(X_{n})$ using $(\xi_{n})$ and the
IBM($\nu$) $(Y_{n})$ using $(\xi^{\prime}_{n})$, we obtain that $X_{n}\preceq
Y_{n}$ for every $n\geq 0$ a.s. by applying (3.3) inductively. ∎

###  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_{\mu}$ for IBM$(\mu)$. We first examine the case where $\mu$ 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 $\bar{\mathbb{Z}}_{+}$, distributed according
to the law $\mu$. Assume there is an integer $k$ such that

$\xi\in\\{0,1,\ldots,k\\}\cup\\{\infty\\}\text{ a.s.}$ (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}{\text{\Large$\mathfrak{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

$\text{there exists }k\geq 2\text{ such that }\mu(k)>0.$

Given a configuration $X$ define

$\widetilde{\Pi}_{k}(X):=\big{[}X(B(X,k)+1),\ldots,X(F(X))\big{]},$ (3.5)

which is interpreted as a _finite word_ 333A 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}=\\{\varnothing\\}$. 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, $\varnothing$ is the only word with length
$0$. in $\mathbb{N}$. Let $|\widetilde{\Pi}_{k}(X)|$ be its

length and $\|\widetilde{\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\leq|\widetilde{\Pi}_{k}(X)|=F(X)-B(X,k)\leq k-1,\quad
0\leq\|\widetilde{\Pi}_{k}(X)\|=\sum_{j=X(B,k)+1}^{F(X)}X(j)\leq k-1,$

and $|\widetilde{\Pi}_{k}(X)|=0$ if and only if
$\|\widetilde{\Pi}_{k}(X)\|=0$.

The set

$\displaystyle\widetilde{\Pi}_{k}(\mathbb{S})$
$\displaystyle=\\{\widetilde{\Pi}_{k}(X):X\in\mathbb{S}\\}$
$\displaystyle=\\{\varnothing\\}\cup\\{[a_{1},\ldots,a_{\ell}]:\,1\leq\ell\leq
k-1,\,a_{1},\ldots,a_{\ell}\geq 1,\,a_{1}+\cdots+a_{\ell}\leq k-1\\}$

is finite444More precisely $|\widetilde{\Pi}_{k}(\mathbb{S})|=2^{k-1}$.
Indeed, recall that the set of $\ell$-tuples $(a_{1},\ldots,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 $\widetilde{\Pi}_{k}(\mathbb{S})$ has
cardinality $\sum_{\ell=0}^{k-1}\binom{k-1}{\ell}=2^{k-1}$..

We think of $\Pi_{k}$ as a projection of $\mathbb{S}$ on $\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
$\Pi_{k}(X)$ remains a Markov chain.

######  Lemma 3.10.

Let $k\geq 2$ be an integer, and assume that the law $\mu$ is supported in
$\\{0\\}\cup\\{1,\ldots,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}=\widetilde{\Pi}_{k}(X_{n})$, $n\geq 0$, is an irreducible Markov chain
with values in the set $\widetilde{\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 $\widetilde{\Pi}_{k}$ preserves the Markov
property is because each of the states $a\in\widetilde{\Pi}_{k}(\mathbb{S})$
conveys just enough information about the state $X\in\mathbb{S}$ with
$a=\widetilde{\Pi}_{k}(X)$ that is enough to decouple the past from the
future.

For example, if $a=\varnothing$ then we know that any $X\in\mathbb{S}$ with
$a=\widetilde{\Pi}_{k}(X)$ must satify $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\leq\xi\leq 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
$\widetilde{\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 [76, Lemma 3.1], it is perhaps best to work out two examples and
leave the formal details to the reader.

[$\emptyset$]$[1]$$1,2$$1$$2$

[$\emptyset$]$[1]$$[2]$$[1,1]$$1,2,3$$2,3$$1$$3$$1,2$$2$$3$$1$

Figure 3: 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$.

It is easy to see that the Markov chain $\widetilde{\Pi}_{k}(X_{n})$ has an
irreducible class connected to the state $\varnothing$ (by producing a
sequence of moves that takes the chain from any state to $\varnothing$; the
assumption that $\mathbb{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. ∎

Given $a=[a_{1},\ldots,a_{\ell}]\in\widetilde{\Pi}_{k}(\mathbb{S})$ let
$L(a)=a_{\ell}$ with the convention that $L(a)=k$ if $a=\varnothing$. So if
$Z_{n}=\widetilde{\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,\ldots,k\\}\cup\\{\infty\\}$ where $k\geq 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\rightarrow\infty}\frac{F(X_{n})}{n}=v_{\mu}\quad\text{a.s.}$

###### Proof.

Let $Z_{n}=\widetilde{\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})\geq\xi_{j},$
(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 3.
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. ∎

######  Remark 3.12.

Observe that $v_{\mu}$ can be computed from the knowledge of the invariant
distribution $\pi$ of the Markov chain $\widetilde{\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)\geq\xi).$

For example, if $k=2$, we have
$v_{\mu}=\pi(\varnothing)\mu(\\{0,1,2\\})+\pi([1])\mu(\\{0,1\\})=(\mu(1)+\mu(2))^{2}/(\mu(1)+2\mu(2))$;
see Figure 3. 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 $\overline{\mathbb{Z}}_{+}$ with distribution $\mu$. Fix $k\geq 1$
and define

$\xi^{j}_{k}:=\xi{\text{\Large$\mathfrak{1}$}}_{\xi\leq
k}+j{\text{\Large$\mathfrak{1}$}}_{\xi>k},$

and let $\mu^{j}_{k}$ be the distribution of $\xi^{j}_{k}$. We are only
interested in the cases where $j=0,k$ or $\infty$ (noticing that
$\xi^{\infty}_{k}=\xi$ when $\xi\leq k$ or $\infty$ when $\xi>k$).

Clearly,

$\xi^{0}_{k}\leq\xi^{k}_{k}\leq\xi\leq\xi^{\infty}_{k}.$

Let $(\xi^{0}_{k,n},\xi^{k}_{k,n},\xi_{n},\xi^{\infty}_{k,n})$,
$n\in\mathbb{N}$, be i.i.d. copies of
$(\xi^{0}_{k},\xi^{k}_{k},\xi,\xi^{\infty}_{k})$.

Define 4 coupled IBMs, $(X^{0}_{k,n})$, $(X^{k}_{k,n})$, $(X_{n})$ and
$(X^{\infty}_{k,n})$, as in Definition 3.2, using the 4 coupled sequences
$(\xi^{0}_{k,n})$, $(\xi^{k}_{k,n})$, $(\xi_{n})$ and $(\xi^{\infty}_{k,n})$
of selection numbers, respectively. By (3.3) and Proposition (3.9) we have

$\forall n\geq 0~{}~{}X^{\infty}_{k,n}\preceq X_{n}\preceq X^{k}_{k,n}\preceq
X^{0}_{k,n}~{}\text{ a.s.}$ (3.7)

We next observe that

$\widetilde{\Pi}_{k}(X^{\infty}_{k,n})=\widetilde{\Pi}_{k}(X^{0}_{k,n})\quad\text{for
all }n\geq 0,$ (3.8)

where $\widetilde{\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^{\infty}_{k,n}\neq\xi^{0}_{k,n}$ 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

$\displaystyle
X^{0}_{k,n}=\Phi_{\xi^{0}_{k,n}}\circ\cdots\circ\Phi_{\xi^{0}_{1,n}}(X_{0})=\Phi_{0}^{I_{n}}\circ\Phi_{\xi^{\infty}_{k,n}}\circ\cdots\circ\Phi_{\xi^{\infty}_{1,n}}(X_{0})=\Phi_{0}^{I_{n}}\left(X^{\infty}_{k,n}\right),$

where
$I_{n}=\sum_{j=0}^{n-1}{\text{\Large$\mathfrak{1}$}_{\left\\{\xi_{k}\in(k,\infty)\right\\}}}$.
Consequently, $X^{0}_{k,n}(\ell)=X^{\infty}_{k,n}(\ell-I_{n})$ for all
$\ell\in\mathbb{Z}$, from which we deduce that
$\widetilde{\Pi}_{k}(X^{\infty}_{k,n})=\widetilde{\Pi}_{k}(X^{0}_{k,n})$,
completing the proof.

∎

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

###### Proof of Theorem 3.5.

Let $k\geq 1$ be an integer. By Proposition 3.11, there exist
$v_{\mu^{\infty}_{k}}$ and $v_{\mu^{0}_{k}}$ in $[0,1]$ such that

$\displaystyle\lim_{n\rightarrow\infty}\frac{F(X^{\infty}_{k,n})}{n}$
$\displaystyle=v_{\mu^{\infty}_{k}},\quad\lim_{n\rightarrow\infty}\frac{F(X^{0}_{k,n})}{n}=v_{\mu^{0}_{k}}\qquad\text{a.s.}$

Using that $F(X^{0}_{k,n})=F(X^{\infty}_{k,n})+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)).$ (3.9)

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

$F(X^{\infty}_{k,n})\leq F(X_{n})\leq F(X^{0}_{k,n})\quad\text{a.s.}$ (3.10)

Combining (3.9) and (3.10) we deduce that

$v_{\mu^{\infty}_{k}}\leq\varliminf_{n\rightarrow\infty}\frac{F(X_{n})}{n}\leq\varlimsup_{n\rightarrow\infty}\frac{F(X_{n})}{n}\leq
v_{\mu^{\infty}_{k}}+\mu([k+1,\infty))\quad\text{a.s.}$ (3.11)

Since for every $i\geq 0$ and $k\geq 1$, we have
$\mu^{\infty,k}([0,i])\leq\mu^{\infty,k+1}([0,i])$, we have by Proposition 3.9
that $X^{\infty,k}_{n}\preceq X^{\infty,k+1}_{n}$ thus the sequence
$(v_{\mu^{\infty,k}})_{k\geq 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\rightarrow\infty}\frac{F(X_{n})}{n}=v_{\mu}\quad\text{a.s.}$

∎

######  Remark 3.13.

If $\nu$ is another probability distribution on $\bar{\mathbb{Z}}_{+}$ such
that $\nu([0,i])\leq\mu([0,i])$ for all $i\geq 0$, then it follows from
Proposition 3.9 that $v_{\nu}\leq 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
process555Observe 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.. Since $F(X_{n+1})-F(X_{n})\geq
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.

Recalling 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\geq
1}\mathbb{N}^{n}=\mathbb{N}^{*}\backslash\\{\varnothing\\}$

If $\alpha\in\cal U$ then we write it, rather uncoventionally, _from right to
left_

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

(or $(\alpha_{\ell},\ldots,\alpha_{1})$ when confusion arises) as we made the
identification

$\Phi_{\alpha_{\ell}}\raisebox{0.43057pt}{\scriptsize$\circ$}\cdots\raisebox{0.43057pt}{\scriptsize$\circ$}\Phi_{\alpha_{1}}\equiv\alpha_{\ell}\cdots\alpha_{1}.$
(3.12)

######  Example 3.14.

Take $X=[\ldots,5,3,2,1,2,0,0,\ldots]$, 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}=[\ldots,5,3,2,1,2,1,0,\ldots]$,
$5(1X)=\Phi_{5}\raisebox{0.43057pt}{\scriptsize$\circ$}\Phi_{1}(X)=X+\delta_{1}+\delta_{-1}$,
$4(5(1X))=\Phi_{4}\raisebox{0.43057pt}{\scriptsize$\circ$}\Phi_{5}\raisebox{0.43057pt}{\scriptsize$\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
$\varnothing$, which is not considered as a selection word. However, we can
formally define $\Phi_{\varnothing}$ as the identity on $\mathbb{S}$.

If $\alpha=\alpha_{\ell}\cdots\alpha_{1}$ is a selection word and $k\leq\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\leq k\leq|\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,
$\varnothing\alpha=\alpha\varnothing=\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}[]{rcl}\mathbb{S}&\longrightarrow&\mathbb{N}^{k}\\\
X&\longmapsto&\left(X\left(F(X)-k+1\right),\ldots,X\left(F(X)\right)\right)\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}~{}~{}\Pi_{k}(\alpha X)=\Pi_{k}(\alpha Y).$

Let $\mathcal{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$.

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 $\mathcal{C}_{1}\supset\mathcal{C}_{2}\supset\cdots$. Hence
$\mathcal{C}_{1}$ is the set of all coupling words. Note that
$\mathcal{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
$\mathcal{U}\setminus\mathcal{C}_{1}$ are non-coupling.

######  Definition 3.16 (Coupling number).

The coupling number of $\alpha$ is defined by

$K(\alpha)=\sup\\{k\geq 0:\,\forall X,Y\in\mathbb{~{}}\Pi_{k}(\alpha
X)=\Pi_{k}(\alpha Y)\\}.$

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

$K(\alpha)=k\iff\alpha\in\mathcal{C}_{k}\setminus\mathcal{C}_{k+1}.$

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

######  Example 3.17.

We have that $K(1)=1$, $K(1,1)=2$, and more generally, if
$1^{\ell}=(1,\ldots,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}\not\in\mathcal{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\mathcal{C}_{2}\setminus\mathcal{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},\ldots,\alpha_{1})\in\mathcal{U}$ is called
_triangular_ if for every $1\leq i\leq\ell$ we have $\alpha_{i}\leq i$. We
denote by $\mathcal{T}$ the set of triangular words. An infinite sequence
$(\ldots,\alpha_{3},\alpha_{2},\alpha_{1})$ of positive integers is called an
infinite triangular word if $\alpha_{i}\leq 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\geq 1$ and let $\alpha$ be a triangular word with
$\vartheta_{1}(\alpha)=k$. Then $\alpha$ is $k$-coupling.

###### Proof.

Write $\alpha=(\alpha_{\ell},\ldots,\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\leq i\leq 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\leq i\leq\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\geq 1$, $X_{i}(k)=Y_{i}(k)$ and $\sum_{j\geq
1}X_{i}(j)=\sum_{j\geq 1}Y_{i}(j)=i$. This is trivially true when $i=0$.

If $1\leq i\leq\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})\geq 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\geq 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)\geq f$. Since
each transition $\Phi_{1}$ adds a balls to a previously empty bin, we have
that $f\geq\vartheta_{1}(\alpha)=k$, which shows that
$\alpha\in\mathcal{C}_{k}$. ∎

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\geq 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\geq 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 $\mathbb{S}_{0}$ the set of all $X\in\mathbb{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}=\left(\Phi_{0}\right)^{u}$.

Next, let

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

be the projection $\mathbb{S}\to\mathbb{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\geq 1}$ of i.i.d. random variables with law $\mu$, we define the
pinned IBM$(\mu)$ to be the Markov process $(\widehat{X}_{n})$ with values in
$\mathbb{S}_{0}$ given by

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

We leave the initial configuration $\widehat{X}_{0}\in\mathbb{S}_{0}$
unspecified.

Let $(\widehat{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\geq 1$. We observe that for any selection word $\alpha$ and
$X\in\mathbb{S}$, we have $\Theta(\alpha X)=\Theta(\alpha(\Theta X))$.
Therefore, for each $n\in\mathbb{N}$, we have

$\widehat{X}_{n}=\Theta X_{n}.$

As a result, $\widehat{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}.$ (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\text{ and
}\sup_{k\in\mathbb{N}}\mu(k)<1.$ (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\leq n)$. Then a.s.
there exists a unique process $(Y_{n})_{n\in\mathbb{Z}}$ on $\mathbb{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\geq 1$. In that case, there would be $k$ processes
$(Y^{j}_{n})_{n\in\mathbb{Z},1\leq j\leq k}$ on $\mathbb{S}_{0}$ satisfying
(3.13), given by

$Y^{k}_{n}(\ell)=\begin{cases}k&\text{ if }\ell\leq-1\\\ 0&\text{ if }\ell\geq
1\\\ \left((j+n)\text{ mod }k\right)+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, 41].

######  Remark 3.24.

To extend Theorem 3.23 to measure $\mu$ such that $\mu(0)=1$, one can use [27]
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 [77].

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

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

is invariant under translations and $\mathscr{R}\cap[0,\infty)$ and
$\mathscr{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}\leq
1,\xi_{k+1}\leq 2,\xi_{k+2}\leq
3,\ldots)=\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 $\mathscr{R}$
contains infinitely many positive and infinitely many negative integers a.s. ∎

We write $\mathscr{R}=\\{T_{0},T_{\pm 1},T_{\pm 2},\ldots\\}$ and arrange the
indexing so that

$\cdots<T_{-1}<T_{0}\leq 0<T_{1}<\cdots$

For each $n$ in $\mathbb{Z}$, let $s(n)$ be the unique (random) integer such
that $T_{s(n)}\leq 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\geq 1$.
Consider the selection word

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

Since $T_{s(n)-k+1}\in\mathscr{R}$, the word $\xi_{n}\cdots\xi_{T_{s(n)-k+1}}$
is triangular. Note that the number of elements of $\mathscr{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 $\mathscr{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-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. ∎

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 $\widehat{X}_{0}\in\mathbb{S}_{0}$ and let
$(\widehat{X}_{n})_{n\geq 0}$ be a pinned IBM($\mu$) constructed using the
variables $\xi_{n},n\geq 1$. Let $(Y_{n})$ be the stationary version of the
pinned IBM. Then for every $k\geq 1$, there exists $n_{k}\geq 1$ such that for
every $n\geq n_{k}$, we have

$\Pi_{k}(\widehat{X}_{n})=\Pi_{k}(Y_{n}).$ (3.16)

###### Proof.

Let $k\geq 1$ and set $n_{k}=T_{k}$ which is finite a.s. If $n\geq n_{k}$, we
have $\vartheta_{1}(\xi_{n}\cdots\xi_{1})\geq k$ and (3.16) follows from Lemma
3.19. ∎

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}\leq Y_{0}(0)).$ (3.17)

###### Proof.

Let $(X_{n})$ be an IBM constructed using the random variables $(\xi_{n},n\geq
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}\left(F(X_{j})-F(X_{j-1})\right)=\lim_{n\to\infty}\frac{1}{n}\sum_{j=1}^{n}\mathbb{P}(\xi_{j}\leq
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}\leq L(X_{j-1}))=\mathbb{P}(\xi_{j}\leq
Y_{j-1}(0))=\mathbb{P}(\xi\leq Y_{0}(0)),$

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

###  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,\ldots$ 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:

$\displaystyle\mathcal{G}$
$\displaystyle:=\\{\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\\},$
$\displaystyle\mathcal{B}$
$\displaystyle:=\\{\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)\\},$
$\displaystyle\text{and }\mathcal{A}$
$\displaystyle:=\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)\geq 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\mathcal{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 $\mathcal{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 Definition 3.15 infra. Let $b$ be this number of balls.
Then $F(\xi\alpha X)=F(\alpha X)+1$ if and only if $\xi\leq b$. Since neither
$\xi$ nor $b$ depend on $X$, it follows that the word is good if $\xi\leq b$,
or bad otherwise.

By Lemma 3.19 every triangular word is in $\mathcal{C}_{1}$. Hence the
previous argument applies. ∎

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\leq 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 ($\cal 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}\not\in\mathcal{V},i=2,\ldots,\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)\not\in\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}.$
(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},\ldots,\alpha_{1})\in\mathcal{U}$ under
the probability measure $\mu$ is defined to be

$w_{\mu}(\alpha):=\prod\limits_{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
$\varnothing$ is not a selection word) and define

$T^{*}_{\mathcal{V}}:=\sup\\{-\infty<\ell\leq
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\limits_{\alpha\in\mathcal{V}_{\min}\cap\mathcal{G}}w_{\mu}(\alpha)=1-\sum\limits_{\alpha\in\mathcal{V}_{\min}\cap\mathcal{B}}w_{\mu}(\alpha).$
(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}\leq Y_{0}(0))$. Observe
that

$\\{\xi_{1}\leq
Y_{0}(0)\\}=\\{F(\xi_{1}\xi_{0}\cdots\xi_{T}Y_{T-1})-F(\xi_{0}\cdots\xi_{T}Y_{T-1})=1\\}.$
(3.20)

Since $\xi_{1}\xi_{0}\cdots\xi_{T}\not\in\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}\not\in\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).$
(3.21)

The length of the word $\xi_{1}\xi_{0}\cdots\xi_{T}$ is $2-T$, so

$\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),$

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}$.
∎

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, [77]).

Let $\mu$ be a probability measure on $\mathbb{N}$ satisfying assumptions
(3.14). Then

$\displaystyle v_{\mu}$
$\displaystyle=\sum\limits_{\alpha\in\mathcal{T}_{\min}\cap\mathcal{G}}w_{\mu}(\alpha)$
(3.22) $\displaystyle v_{\mu}$
$\displaystyle=\sum\limits_{\alpha\in\mathcal{G}_{\min}}w_{\mu}(\alpha).$
(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\leq
1:\,(\xi_{1}\,\xi_{0}\,\xi_{-1}\cdots\xi_{\ell+1}\xi_{\ell})\in\mathcal{T}\\}$.
By Lemma 3.25 all the points of $\mathscr{R}$ are finite in absolute value
a.s. Hence there are points $-\infty<\ell\leq 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\leq
1:\,\xi_{1}\cdots\xi_{\ell}\in\mathcal{G}\cup\mathcal{B}\\}\geq
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\varnothing=\mathcal{G}_{\min},$

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

######  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 [77], 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, [77, 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 $\overrightarrow{G}(\mathbb{Z},p)$. Then $(X_{n})$ is an
IBM$(\mu_{p})$. Looking at (2.10) we see that

$F(X_{n})=L_{n},$ (4.1)

where $L_{n}$ is the maximum of all paths in
$\overrightarrow{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}}.$ (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\leq 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}\left((1-p)^{R_{p}}\right).$ (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\leq 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). ∎

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\limits_{i=1}^{\ell}(\alpha_{i}-1)=\sum\limits_{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\leq 1$. Then

$\displaystyle C(p)$
$\displaystyle=\sum\limits_{\alpha\in\mathcal{T}_{\min}\cap\mathcal{G}}p^{|\alpha|}(1-p)^{H(\alpha)}$
(4.4) $\displaystyle C(p)$
$\displaystyle=\sum\limits_{\alpha\in\mathcal{G}_{\min}}p^{|\alpha|}(1-p)^{H(\alpha)}.$
(4.5)

##### Precise bounds.

We use Theorem 3.35 to obtain precise bounds on $C(p)$. Let $k\geq 1$ and let
$0<p\leq 1$. Recalling the notation
$\xi^{j}_{k}=\xi{\text{\Large$\mathfrak{1}$}}_{\xi\leq
k}+j{\text{\Large$\mathfrak{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^{j}_{k}$.

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

$\forall p\in[0,1],\quad\underline{C}_{k}(p)\leq C(p)\leq\overline{C}_{k}(p).$
(4.6)

As the IBM($\mu^{\infty}_{p,k}$) and the IBM($\mu^{k}_{p,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 $\overline{C}_{k}(p)$ are rational functions in $p$
that can be computed explicitly. For example, with $k=3$, performing such
computations yields

$\displaystyle\underline{C}_{3}(p)$
$\displaystyle=\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}$
$\displaystyle\overline{C}_{3}(p)$
$\displaystyle=\frac{p^{3}-2p^{2}+p-1}{p^{5}-4p^{4}+8p^{3}-9p^{2}+6p-3}.$

It is worth noting that (3.9) implies that

$0\leq\overline{C}_{k}(p)-\underline{C}_{k}(p)\leq(1-p)^{k},$

therefore the sequences of functions $(\overline{C}_{k}(p))_{k\geq 1}$ and
$(\underline{C}_{k}(p))_{k\geq 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})\text{ as $p\to
1$}.$

$p$011 (a) $k=3$

$p$011 (b) $k=6$

$p$011 (c) $k=12$

Figure 4: Successive bounds on the function $C$ (in red) by $\overline{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$.

######  Remark 4.4.

Writing the balance equations for the stationary version $Y$ of the
IBM($\mu_{p}$), Foss and Konstantopoulos [41] 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\geq 0$ define

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

By formula (4.4), we have that $C(p)=D(p,1-p)$ for every $0<p\leq 1$. Let
$0<p_{0}\leq 1$. The rest of the proof consists in the construction of
$(p^{\prime},q^{\prime})$ such that $p^{\prime}>p_{0}$, $q^{\prime}>1-p_{0}$
and the series (4.7) for $D(p^{\prime},q^{\prime})$ converges. This will imply
the normal convergence 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\leq 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)\leq\mathbb{E}(r^{2-T_{0}}),$

where $T_{0}$ is the largest nonpositive point of the set $\mathscr{R}$
defined in (3.15). To see this, recall the time
$T^{*}_{\mathcal{T}}=\sup\\{-\infty\leq t\leq
1:\,\xi_{1}\xi_{0}\cdots\xi_{t}\in\mathcal{T}\\}$ and recall that
$\mathbb{P}(T^{*}_{\mathcal{T}}>-\infty)=1$ (as in the proof of Theorem 3.35)
and that $\mathbb{P}(T^{*}_{\mathcal{T}}\geq T_{0})=1$. For brevity, set
$T=T^{*}_{\mathcal{T}}$. Arguing as in (3.21) we have

$\mathbb{E}(r^{2-T_{0}})\geq\mathbb{E}(r^{2-T})\geq\mathbb{E}\left(r^{2-T};\,{\xi_{1}\xi_{0}\cdots\xi_{T}\in\mathcal{T}_{\min}\cap\mathcal{G}}\right)=\sum_{\alpha\in\mathcal{T}_{\min}\cap\mathcal{G}}\mathbb{E}\left(r^{2-T};\,{\xi_{1}\xi_{0}\cdots\xi_{T}=\alpha}\right)\\\
=\sum_{\alpha\in\mathcal{T}_{\min}\cap\mathcal{G}}\mathbb{E}\left(r^{|\alpha|};\,{\xi_{1}\xi_{0}\cdots\xi_{2-|\alpha|}=\alpha,2-T=|\alpha|}\right)=\sum_{\alpha\in\mathcal{T}_{\min}\cap\mathcal{G}}r^{|\alpha|}\mathbb{P}\left({\xi_{1}\xi_{0}\cdots\xi_{2-|\alpha|}=\alpha}\right)\\\
=\sum_{\alpha\in\mathcal{T}_{\min}\cap\mathcal{G}}r^{|\alpha|}p^{\alpha_{1}}(1-p)^{\alpha_{1}-1}\cdots
p^{\alpha_{\ell}}(1-p)^{\alpha_{\ell}-1}=D(rp,1-p).$

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 [77, 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\left(\frac{p_{0}}{2},\frac{p_{0}}{r}\right)<p<p_{0}$. Then setting
$p^{\prime}=rp$ and $q^{\prime}=1-p$ we have that $p^{\prime}>p_{0}$,
$q^{\prime}>1-p_{0}$ and the series (4.7) for $D(p^{\prime},q^{\prime})$
converges.

∎

######  Remark 4.6.

We observe that $C^{\prime}(0)=e$ and $C^{\prime\prime}(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|\leq 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\leq k\leq|\alpha|$, we remark
that $S(|\alpha|)=H(\alpha)-|\alpha|<-1$. We denote by $n=\max\\{1\leq
k\leq|\alpha|:S(k)<-1\\}$, and remark that $S(k)\leq-2$ for all $n\leq
k\leq|\alpha|$. In particular, as $S(1)=\alpha_{1}-2\geq-1$, we have $n\geq
2$.

As $\alpha_{k}\geq 1$, we have $S(k)-S(k-1)\geq-1$ for all $2\leq
k\leq|\alpha|$. Therefore, $S(n)=-2$ and for all $k\leq n-|\alpha|$, we have
$S(n+k)\geq-k-2$. As a result, $\alpha_{n+k}=2+S_{n+k}-S_{n+k-1}\leq
2-2-(-(k-1)-2)\leq 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.
∎

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 ([76]).

For every $n\geq 0$, define

$a_{n}:=\sum\limits_{\alpha\in\mathcal{G}_{\min}}\binom{|\alpha|}{n-H(\alpha)}(-1)^{H(\alpha)}.$
(4.8)

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

$C(1-q)=\sum\limits_{n\geq 0}(-1)^{n}a_{n}q^{n}.$ (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\geq
0$ and $\ell\geq 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}.$ (4.10)

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

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

which is in particular clearly finite.

###### Proof of Theorem 4.8.

Let $n\geq 0$ and let $0\leq q<1$. Rewrite formula (4.5) as

$\displaystyle C(1-q)=\sum\limits_{h\geq
0}\sum\limits_{\ell=1}^{h+1}\sum\limits_{\alpha\in\mathcal{G}_{\min}\cap\mathcal{U}_{\ell}^{h}}q^{h}(1-q)^{\ell}$
$\displaystyle=\sum\limits_{h\geq
0}\sum\limits_{\ell=1}^{h+1}|\mathcal{G}_{\min}\cap\mathcal{U}_{\ell}^{h}|\sum\limits_{i=0}^{\ell}\binom{\ell}{i}(-1)^{i}q^{i+h}$
$\displaystyle=\sum\limits_{h\geq 0}\sum\limits_{n\geq
0}\sum\limits_{\ell=1}^{h+1}|\mathcal{G}_{\min}\cap\mathcal{U}_{\ell}^{h}|\binom{\ell}{n-h}(-1)^{n-h}q^{n},$
(4.12)

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\limits_{h\geq 0}\sum\limits_{n\geq
0}\sum\limits_{\ell=1}^{h+1}|\mathcal{G}_{\min}\cap\mathcal{U}_{\ell}^{h}|\binom{\ell}{n-h}q^{n}=\sum\limits_{h\geq
0}\sum\limits_{\ell=1}^{h+1}|\mathcal{G}_{\min}\cap\mathcal{U}_{\ell}^{h}|q^{h}(1+q)^{\ell}.$
(4.13)

By (4.10), we have

$I_{q}\leq(1+q)\sum\limits_{h\geq
0}\sum\limits_{\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\geq 0}$ be a random walk on $\mathbb{Z}$ starting
at $0$ and taking a step $+1$ (resp. $-1$) with probability $\tfrac{q}{1+2q}$
(resp. $\tfrac{1+q}{1+2q}$). Performing the change of variables $N=h+\ell$, we
have

$\sum\limits_{h\geq
0}\sum\limits_{\ell=0}^{h}\binom{h+\ell}{\ell}q^{h}(1+q)^{\ell}=\sum\limits_{N\geq
0}(1+2q)^{N}\mathbb{P}(S_{N}\leq 0).$ (4.14)

Applying Chernoff’s bound, we get

$\mathbb{P}(S_{N}\leq 0)\leq\inf\limits_{t\geq
0}\left(\mathbb{E}(e^{-tS_{1}})\right)^{N}\leq\inf\limits_{t\geq
0}\left(\frac{qe^{t}+(1+q)e^{-t}}{1+2q}\right)^{N}\leq\left(\frac{2\sqrt{q(1+q)}}{1+2q}\right)^{N}.$

Thus, when $0\leq q<\tfrac{\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\geq 0$ we also have the formula

$a_{n}=\sum\limits_{\alpha\in\mathcal{T}_{\min}\cap\mathcal{G}}\binom{|\alpha|}{n-H(\alpha)}(-1)^{H(\alpha)}.$
(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}^{h}_{\ell}|\leq|\mathcal{U}^{h}_{\ell}|$.
Based on the numerical computation of the first few terms of
$\tfrac{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})$, two 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 [76]. 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
[90] to obtain the first $24$ values of $a_{n}$. See Table 2 for the first few
values of $a_{n}$.

Table 2: The values of $a_{n}$ for $0\leq n\leq 12$. $n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
---|---|---|---|---|---|---|---|---|---|---|---|---|---
$a_{n}$ | 1 | 1 | 1 | 3 | 7 | 15 | 29 | 54 | 102 | 197 | 375 | 687 | 1226

This sequence is referenced as A321309 in the On-Line Encyclopedia of Integer
Sequences [88].

From the observation of the first terms of the sequence arises the following
conjecture:

######  Conjecture 4.11.

Removing the first two terms, the sequence $(a_{n})_{n\geq 2}$ is strictly
increasing.

##  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 $\overrightarrow{G}(\mathbb{N},p)$ in the sparse
graph limit, that is, when $p\to 0$. It can be seen that, in this limit,
$\overrightarrow{G}(\mathbb{N},p)$ is well-approximated by a branching random
walk, a discrete-time particle system on the positive half-line
$\mathbb{R}_{+}$. Throught this section, we will let $G$ denote the
$\overrightarrow{G}(\mathbb{N},p)$.

Let $L_{n}(p)$ be the maximum length of all paths in
$\overrightarrow{G}(\mathbb{N},p)$ from $1$ to $n$. Using branching random
walk approximation, Newman [83] 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,}$
(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 [77] 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, [77] states that

$\frac{C(p)}{p}=e-\frac{\pi^{2}e}{2}(\log
p)^{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}-}2}(1+o(1)),\quad\text{as
$p\to 0$},$ (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. 666The
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 at its currently
occupied position. This model was notably studied in [73] in which the speed
and fluctuation of the cloud if particles as $N\to\infty$ is obtained.

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}}.$ (5.3)

######  Remark 5.1.

Belief in this conjecture was increased by the study of an exactly solvable
model [25, 32]. 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 777Equations
of this type are partial differential equations of the form
$v_{t}=v_{xx}+F(v)$ were introduced by Kolmogorov, Petrovsky and Piscounov
[64] 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
[39], a paper cited in [64] 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 [80]. Connections between the noisy F-KPP equation and
the branching Brownian motion with selection were obtained in [37, 35].
equations modeling e.g. directed polymers [82] among many other examples.

We present in the current paper an alternative, possibly simpler, construction
of the coupling used by Mallein and Ramassamy [77] 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 [83] and [77] 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.

###  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 [93] and references therein. For example, let
${G}(n,\lambda/n)$ be an Erdős-Rényi random graph. That is, on the set
$\\{1,\ldots,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. [33].

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:=\overrightarrow{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
$\overrightarrow{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}}{\text{\Large$\mathfrak{1}$}}_{(1,k)\in
E(G)}\,\delta_{pk}\xrightarrow{\rm d}N,\quad\text{ as }p\to 0.$

where $\xrightarrow{\rm 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 [49, 42] 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

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

where $\mathbb{N}^{0}=\\{\varnothing\\}$ 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 $\varnothing$ 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(\varnothing)=0,$

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

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

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 $3$d offspring of the $5$th offspring of
the $2$nd offspring of $\varnothing$ 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.
888 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 [59]: Let $N_{t}$, $t\geq 0$, be a
collection of i.i.d. standard Poisson processes. Interpreting $N$ as a set of
points, we let $V=\bigcup_{t\geq 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},\ldots,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})$.  999The 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.

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)\leq t\\},\quad X_{t}:=\\{X(u):\,X(u)\leq
t\\},\quad\Pi_{t}=(V_{t},X_{t}),$

be the induced subgraph of $\Pi$ on the set of vertices $u$ with $X(u)\leq t$.
Hence $\Pi_{t}$ describes the immortal particles process up to time $t$. Note
that $\Pi_{t}$, $t\geq 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)\leq t,\,|u|=\ell\\}|,$ (5.4)

then

$Z_{t}=(Z_{t}(0),Z_{t}(1),\ldots),\quad t\geq 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\geq 0$, is also Markovian. This process is an
Uchiyama-type continuous-time branching random walk [92] 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)\leq t\\}|=\sum_{\ell\geq
0}Z_{t}(\ell),\quad t\geq 0,$

is also Markovian with state space $\\{1,2,\ldots\\}$ 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)\leq
t\\}=\max\\{\ell\in\mathbb{Z}_{+}:\,Z_{t}(\ell)>0\\},$ (5.5)

which is the largest generation particle present in $\Pi_{t}$. 101010The 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|$. So $Z_{t}(\ell)=0$ for all
$\ell>K_{t}$. We use the abbreviation PWIT-IBM for $Z_{t}$, $t\geq 0$ and note
that it differs from $\Pi_{t}$, $t\geq 0$, only by the absence of the
connections information.

The total number of particles in every bin $\ell$, with $\ell\geq 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.$

###### 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

$\displaystyle\mathbb{E}\sum_{|u|=\ell}f(X(u))$
$\displaystyle=\mathbb{E}\sum_{|v|=\ell-1}\mathbb{E}[f(X(v)+X(vk)-X(v))|X(v)]$
$\displaystyle=\mathbb{E}\sum_{|v|=\ell-1}\mathbb{E}\left[\int_{0}^{\infty}f(X(v)+t)N(dt)\bigg{|}X(v)\right]=\mathbb{E}\sum_{|v|=\ell-1}\int_{0}^{\infty}f(X(v)+t)dt,$

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. ∎

######  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)={\text{\Large$\mathfrak{1}$}}_{x\leq 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\geq
0$, is the Yule-Furry process. ∎

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),$ (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 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 [55], Kingman [63] and Biggins [15] proved under increasing
generality that

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

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

$\kappa(\theta)=\log\int_{0}^{\infty}e^{-\theta
x}\mathrm{d}x=-\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 [56] 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,}$ (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_{\star}>0$
such that for all $x\geq 0$,

$\mathbb{P}(M_{n}\geq n/e+\tfrac{3}{2e}\log
n+x)=\mathbb{E}\left(\exp\left(-c_{\star}D_{\infty}e^{ex}\right)\right)$ (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\geq 0$, we note that the
functions $t\mapsto K_{t}$ and $\ell\mapsto M_{\ell}$, defined in (5.5) and