(5.6), respectively, are generalized inverses of one another. Indeed, it is
clear that, for all $t\geq 0$ and all $\ell\in\mathbb{Z}_{+}$,

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

which implies that the front bin $F_{t}$ in the PWIT-IBM, as defined by (5.5),
satisfies

$F_{t}=\max\\{\ell\in\mathbb{Z}_{+}:\,M_{\ell}\leq t\\}.$ (5.10)

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

######  Lemma 5.4 (Corre [31]).

For all $t\geq 1$, we set

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

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

$\lim_{t\to\infty}\mathbb{P}(F_{t}\leq
n_{t}+k)-\mathbb{E}\left(\exp\left(-c_{\star}D_{\infty}e^{y_{t}-k-1}\right)\right)=0.$

######  Remark 5.5.

Lemma 5.4 shows that as $t\to\infty$, $F_{t}$ remains tight around its median
but does not converge in distribution, due to the fluctuations of $\log
t-{\left\lfloor\log t\right\rfloor}$.

###### Proof of Lemma 5.4.

By definition of $F_{t}$, and the fact that $M_{\ell}$ is atomless and
increases as $\ell$ increases, we have

$.\mathbb{P}(F_{t}\leq
n_{t}+k)=\mathbb{P}\left(M_{n_{t}+k+1}>t\right)=\mathbb{P}\left(M_{n_{t}+k+1}\geq
t\right),\quad k\in\mathbb{N}.$

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

$\lim_{n\to\infty}\mathbb{P}(M_{n}\geq n/e+\tfrac{3}{2e}\log
n+x_{n})-\mathbb{E}\left(\exp\left(-c_{\star}D_{\infty}e^{ex_{n}}\right)\right)=0.$

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

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

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

$\lim_{t\to\infty}\mathbb{P}(M_{n_{t}+k+1}\geq
t)-\mathbb{E}\left(\exp\left(-c_{\star}D_{\infty}e^{y_{t}-k-1}\right)\right)=0,$

which completes the proof. ∎

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

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

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

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

$\kappa_{0}=1,\qquad\kappa_{i}=\min\\{k>\kappa_{i-1}:\,1\leadsto k\\},\quad
i\in\mathbb{N}.$

Clearly,

$\kappa_{1}-\kappa_{0},\,\kappa_{2}-\kappa_{1},\ldots\text{ are independent},$
(5.11)

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

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

This describes the law of the random set

$\mathbb{K}=\\{\kappa_{0},\kappa_{1},\kappa_{2},\ldots\\}=V(C)$

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

#### The spanning tree $B$ and its law

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

$\mathbb{K}_{i-1}:=\\{\kappa_{0},\ldots,\kappa_{i-1}\\}$

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

######  Definition 5.6 (Vertex ranking).

Fix $i\in\mathbb{N}$ and let $a,b$ be distinct elements of
$\\{0,1,\ldots,i-1\\}$.

We say that $\kappa_{a}\lhd\kappa_{b}$ (or $\kappa_{b}\rhd\kappa_{a}$), if
either $L_{\kappa_{a}}>L_{\kappa_{b}}$ or $L_{\kappa_{a}}=L_{\kappa_{b}}$ and
$a>b$. Note that $(\mathbb{K}_{i-1},\lhd)$ is a totally ordered set and that
$\lhd$ depends on $i$ (that is, the order on $\mathbb{K}_{i}$ is different
from the order on $\mathbb{K}_{i-1}$). Let now

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

be the unique bijection so that

$\kappa_{\sigma(1)}\lhd\kappa_{\sigma(2)}\lhd\cdots\lhd\kappa_{\sigma(i)}.$

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

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

denote the inverse function.

######  Definition 5.7 (Special spanning tree $B$).

The special spanning tree $B$ of $C$ is defined as being the maximal-length
spanning tree with the property that, for all $i$, the unique parent of
$\kappa_{i}$ in $B$ is the minimal element $\kappa_{j}$ for the order $\lhd$
among the elements such that $(\kappa_{j},\kappa_{i})$ is an edge in $G$.

Figure 5 gives an example of the definitions.

$\kappa_{0}$$\kappa_{1}$$\kappa_{2}$$\kappa_{3}$$\kappa_{4}$$\kappa_{5}$$\kappa_{6}$$\kappa_{7}$$\kappa_{8}$$\kappa_{9}$$0$$1$$1$$1$$2$$2$$3$$1$$2$$9$$8$$7$$6$$4$$3$$1$$5$$2$$q^{8}$$q^{7}$$q^{6}$$q^{5}$$q^{3}$$q^{2}$$1$$q^{4}$$q$
Figure 5: The first $9$ vertices of $C$ are shown, together with the edges
between them. Vertices of $G$ not connected to $1$ via a path are not shown.
The number above each vertex $\kappa_{j}$ is the maximal path length
$L_{\kappa_{i}}$. The number below each vertex is its rank. The thick edges
are the edges of the special spanning tree $B$. To explain this, consider,
e.g., vertex $\kappa_{6}$ and observe that is connected to $\kappa_{4}$ with
$L_{\kappa_{4}}=2$ and to $\kappa_{3}$ with $L_{\kappa_{3}}=1$; so we choose
$\kappa_{4}$ as the parent of $\kappa_{6}$ in $B_{5}$. Consider vertex
$\kappa_{8}$. It is connected to vertices $\kappa_{2}$ and $\kappa_{1}$ with
$L_{\kappa_{2}}=L_{\kappa_{1}}=2$. Since $\kappa_{2}$ has lower rank than
$\kappa_{1}$ we declare that $\kappa_{2}$ is the parent of $\kappa_{8}$ in
$B$. Finally, the quantities on the lower line are proportional to the
probability that $\kappa_{9}$ chooses its parent among the existing vertices.

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

######  Lemma 5.8.

With $\kappa_{\pi(i)}$ denoting the parent of $\kappa_{i}$ in $B$ we have

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

###### Sketch of proof.

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

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

######  Remark 5.9.

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

#### The special tree $B$ in continuous time

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

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

$\mathbb{P}(\tau_{j}=\tau)=\frac{q^{\rho(j)-1}}{1+q+\cdots+q^{i-1}}=\frac{q^{\rho(j)-1}(1-q)}{1-q^{i}},\quad
0\leq j\leq i-1,$

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

$T(\kappa_{i})-T(\kappa_{i-1})\overset{\mathrm{d}}{=}\tau\sim\operatorname{exponential}(1+q+\cdots+q^{i-1}),$
(5.14)

that is,

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

Hence we can obtain $T(\kappa_{i})$ by an appropriate thinning of a Poisson
process.

######  Lemma 5.10.

Let $\xi_{1}=0$ and $0<\xi_{2}<\xi_{3}<\cdots$ be the points of a Poisson$(1)$
point process, independent of the vertex set
$\mathbb{K}=\\{\kappa_{0},\kappa_{1},\ldots\\}$ of $C$. Then

$p\xi_{\kappa_{i}}\overset{\mathrm{d}}{=}T(\kappa_{i}),\quad i=0,1,2,\ldots$

###### Proof.

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

$p\xi_{\kappa_{i}}-p\xi_{\kappa_{i-1}}\overset{\mathrm{d}}{=}T(\kappa_{i})-T(\kappa_{i-1})$

and the claim follows by independent increments of both sides. ∎

######  Remark 5.11.

This shows that the correct set of vertices of $B$, if we are to put it in
continuous time and create a Markov process, is the set

$0=p\xi_{\kappa_{0}}<p\xi_{\kappa_{1}}<p\xi_{\kappa_{2}}<\cdots$

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

#### The coupling

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

######  Theorem 5.12.

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

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

preserving edges and having the property that

$|\Phi(\kappa_{i})|=L_{\kappa_{i}},$ (5.15)

for all $\kappa_{i}\in\mathbb{K}$.

###### Informal construction of the coupling..

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

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

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

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

As Barak-Erdős graphs with any connecting constant can be associated to the
same branching random walk, this coupling also yields a coupling of Barak-
Erdős graphs with different constants. It is worth noting that with this
coupling, the set of red “coding” particles is decreasing with $p$. It is also
worth observing that typically, the position of the leftmost blue descendant
of a red particle tend to be of order $-\log p$, as newborn red particle occur
at rate $1$, and the rate at which new blue particle occur can be bounded from
above by $1-(1-p)^{n}$ with $n$ the number of red particles born after that
particle.

$\kappa_{0}$$\emptyset$$\kappa_{1}$$1$$\kappa_{2}$$4$$\kappa_{3}$$41$ Figure
6: A possible evolution of the PWIT with the vertices of $\mathbb{K}$ embedded
correctly. The little triangle at the end of blue particles symbolize the blue
descendants produced by each blue particle, which play no role in the
coupling, hence do not interact with $\Phi$ or the times at which the red
particles appear. However, the blue particles represented here play a role, as
they influence the label given to each of the red particle.

######  Example 5.13.

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

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

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

and for $t\geq 0$

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

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

######  Corollary 5.14.

The process $(\bar{F}_{t},t\geq 0)$ and $(L_{k},k\geq 0)$ where
$L_{k}=L^{\mathsf{L},\mathsf{R}}_{k}$, are related by

$F_{p\xi_{\kappa_{i}}}=\max_{0\leq j\leq i}L_{\kappa_{j}}.$

###  5.4 Longest chain issued from the initial vertex

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

######  Theorem 5.15 (Newman [83]).

Let $(p_{n})$ be a null sequence.

  1. 1.

If $\lim_{n\to\infty}np_{n}=t\in(0,\infty)$, then
$\lim_{n\to\infty}L^{(1)}_{n}(p_{n})=F_{t}$ in distribution.

  2. 2.

If $\lim_{n\to\infty}np_{n}=\infty$, then
$\lim_{n\to\infty}L^{(1)}_{n}(p_{n})/np_{n}=e$ in probability.

###### Proof.

We first assume that $np_{n}\to t\in(0,\infty)$. In this situation, the
connected component of the vertex $1$ in the Barak-Erdős graph
$\overline{\mathcal{G}}(n,p_{n})$ converges, as $n\to\infty$ to
$(X(u),u\in\mathcal{U}:X(u)\leq t)$, using the branching random walk coupling.

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

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

We now assume that $np_{n}\to\infty$, and we use once again the coupling
describe in Theorem 5.12. By law of large numbers, the position
$\xi_{\kappa_{n}}$ of the $n$th vertex in the coupling satisfies
$p_{n}\xi_{\kappa_{n}}/np_{n}\to 1$ a.s. as $n\to\infty$. Then, using (5.9),
for all $\varepsilon>0$, for $n$ large enough we have $M_{{\left\lfloor
enp_{n}(1+\varepsilon)\right\rfloor}}\geq np_{n}(1+\varepsilon/2)$. Therefore,
almost surely for $n$ large enough, the longest path issued from $1$ will be
shorter than $en(1+\varepsilon)$, i.e.

$\varlimsup_{n\to\infty}\frac{L_{n}}{np_{n}}\leq e\quad\text{a.s.}$

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

Chaining this argument, we obtain that with high probability,
$L^{(n)}_{1}(p_{n})$ is larger than the sum of $np_{n}/(t+2)$ independent
copies of $F_{t}$. Letting $n\to\infty$, then $\varepsilon\to 0$, we obtain

$\varliminf_{n\to\infty}\frac{L_{n}}{np_{n}}\geq\frac{\mathbb{E}(F_{t})}{t}.$

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

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

$\lim_{n\to\infty}\sup_{k\in\mathbb{N}}\left|\mathbb{P}(L_{n}(p_{n})=k)-\mathbb{P}(F_{np_{n}}=k)\right|=0,$
(5.16)

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

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

The behavior of red particles in the branching random walk can be compared to
a _branching random walk with selection_. Indeed, when considering dynamically
their behavior, we observe that the $k$th largest red ball produces a red
offspring at rate $q^{k}$. In particular, if $k\ll-\log p$, particles branch
at a rate close to $1$, similarly to the usual branching random walk, while if
$k\gg-\log p$, the branching rate of that particle is close to $0$. The set of
red balls can therefore be closely estimated by the set of surviving particles
in the branching random walk with selection of the $N\approx{\left\lfloor-\log
p\right\rfloor}$ rightmost particles.

The branching random walk with selection of the $N$ rightmost particles
evolves according to the following procedure. At each generation, all
particles reproduce independently, a particle at position $x$ giving birth to
a Poisson point process with unit intensity on $[x,\infty)$. Among all
children of these particles, only the $N$ leftmost are selected to constitute
the new generation of the process.

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

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

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

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

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

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

######  Theorem 5.16 (Mallein and Ramassamy [77]).

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

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

$\frac{L_{n}}{np_{n}}=e-\frac{\pi^{2}e}{2(-\log p_{n})^{2}}(1+o(1)).$ (5.18)

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

###### Scheme of proof of Theorem 5.16.

Observing that typically, the leftmost blue particle born from a given red
particle is produced at a time when the particle at a distance of order $-\log
p$ of the position of the leftmost current red particle in the system, we
observe that for any $\delta>0$, the set of red particles alive at a large
generation $n$ is included in $\mathcal{D}_{(1+\delta){\left\lfloor-\log
p\right\rfloor}}$, and contains all particles alive at generation $n$ in
$\mathcal{D}_{(1-\delta){\left\lfloor-\log p\right\rfloor}}$ for all $p$ large
enough.

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

$\frac{L_{n}}{p}\in[nv_{(1-\delta){\left\lfloor-\log
p\right\rfloor}},nv_{(1+\delta){\left\lfloor-\log p\right\rfloor}}$

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

∎

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

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

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

######  Conjecture 5.17.

Let $(p_{n})$ be a null sequence with $np_{n}=\infty$.

  1. 1.

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

  2. 2.

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

###  5.5 Extension to stochastic ordered graphs with geometry

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

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

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

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

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

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

######  Theorem 5.18.

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

  1. 1.

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

  2. 2.

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

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

######  Theorem 5.19.

We denote by $L_{n}(p)$ the length of the longest path issued from $(1,1)$ in
$\mathcal{G}^{(2)}(n,n,p)$.

  1. 1.

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

  2. 2.

If $p\to 0$ with $np\to t$, then $L_{n}(p)/np\to e/(1-\log 2)$ in probability.

###  5.6 Longest path in the Barak-Erdős graph

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

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

######  Theorem 5.20 (Newman [83], Theorem 2).

Let $(p_{n})$ be a null sequence such that
$\lim_{n\to\infty}n^{1+\varepsilon}p_{n}=0$ for some $\varepsilon>0$.

  1. 1.

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

  2. 2.

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

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

then $L_{n}(p_{n})\to m$ in probability.

  3. 3.

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

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

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

###### Proof.

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

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

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

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

With similar computations, we have that

$\mathbb{E}(Z_{k}(n,p)^{2})=\sum_{\begin{subarray}{c}\\{i_{1},\ldots,i_{k+1}\\}\subset\\{1,\ldots,n\\}\\\
\\{j_{1},\ldots,j_{k+1}\\}\subset\\{1,\ldots,n\\}\end{subarray}}\mathbb{P}((i_{1},i_{2}),\ldots(j_{k},j_{k+1})\in
E(G)).$

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

$\displaystyle\mathbb{E}(Z_{k}(n,p)^{2})$
$\displaystyle\leq\binom{n}{k+1}\binom{n-k-1}{k+1}p^{2k}+\sum_{r=1}^{k+1}\binom{n}{k+1}\binom{n-k-1}{k-r+1}p^{2k-r-1}$
$\displaystyle\approx(n^{k+1}p^{k})^{2}+\sum_{r=1}^{k+1}n^{2k+2-r}p^{2k-r-1}.$

If $n^{2}p_{n}\to 0$ as $n\to\infty$, we have

$\mathbb{P}(L_{n}(p_{n})\geq 1)=\mathbb{P}(Z_{1}(n,p_{n})\geq
1)\leq\frac{n(n-1)}{2}p_{n}.$

Therefore $\lim_{n\to\infty}\mathbb{P}(L_{n}(p_{n})=0)=1$, showing that
$L_{n}(p_{n})\to 0$ in probability.

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

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

We observe that

$\mathbb{P}(L_{n}(p_{n})\geq m+1)=\mathbb{P}(Z_{m+1}(n,p_{n})\geq
1)\leq\mathbb{E}(Z_{m+1}(n,p_{n}))\binom{n}{m+1}p_{n}^{m}.$

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

$\displaystyle\mathbb{P}(L_{n}(p_{n})\geq m)$
$\displaystyle=\mathbb{P}(Z_{m}(n,p_{n})\geq
1)\geq\mathbb{E}(Z_{m}(n,p_{n}))^{2}/\mathbb{E}(Z_{m}(n,p_{n})^{2})$
$\displaystyle\geq\frac{1}{1+\sum_{r=1}^{m+1}\frac{\binom{n-k-1}{k-r+1}}{\binom{n-k-1}{k+1}}p_{n}^{-r-2}}.$

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

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

$\lim_{n\to\infty}\mathbb{P}(L_{n}(p_{n})\geq
m)=\lim_{n\to\infty}\mathbb{P}(Z_{m}(n,p_{n})\geq 1)=1-e^{-\theta^{m}/m!},$

and as $\mathbb{P}(L_{n}(p_{n})\geq m-1)\to 1$ using the same computations as
above, we have obtained the convergence in law of $L_{n}(p_{n})$. ∎

We then consider the asymptotic behavior of $L_{n}(p_{n})$ assuming that
$np_{n}=o(\log n)$. In this regime, recall that the length of the longest path
issued from vertex $1$ is of order $enp_{n}=o(\log n)$. The following result
holds.

######  Theorem 5.21.

Let $(p_{n})$ be a null sequence such that
$\lim_{n\to\infty}n^{1+\varepsilon}p_{n}=\infty$ for all $\varepsilon>0$ with
$\lim_{n\to\infty}np_{n}/\log n=0$. We set

$\ell_{n}=\sup\left\\{k\in\mathbb{N}:\binom{n}{k}p_{n}^{k}\leq 1\right\\},$

then $\lim_{n\to\infty}L_{n}(p_{n})/\ell_{n}=1$ in probability.

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

######  Theorem 5.22.

Let $(p_{n})$ be a sequence such that $p_{n}\sim\gamma\log n/n$ as
$n\to\infty$ for some $\gamma\in(0,1)$. Then

$\lim_{n\to\infty}L_{n}(p_{n})/np_{n}=eA(\gamma)\quad\text{in probability},$

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

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

######  Theorem 5.23.

Let $(p_{n})$ be a null sequence such that $\lim_{n\to\infty}np_{n}/\log
n=\infty$, then $\lim_{n\to\infty}L_{n}(p_{n})/np_{n}=e$.

To bound $L_{n}(p_{n})$ from above, we use again first moment estimates,
showing that $\lim_{n\to\infty}\mathbb{P}(L_{n}(p_{n})>np_{n}e)=0$. Using that
$L_{n}(p_{n})\geq L_{n}^{(1)}(p_{n})$ on the other hand and Theorem 5.15, we
conclude to Theorem 5.23.

###  5.7 Shortest path

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

$S_{n}(p)=\min\left\\{k\in\mathbb{N}:\exists
i_{1}<\cdots<i_{k-1}:(1,i_{1}),\ldots,(i_{k-1},n)\in
E(\overrightarrow{\mathcal{G}}(n,p))\right\\}.$

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

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

$(\\{(1,k),(k,n)\in E(\overrightarrow{\mathcal{G}}(n,p))\\},2\leq k\leq n)$

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

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

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

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

######  Theorem 5.24.

Let $(p_{n})$ be a null sequence.

  1. 1.

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

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

then $S_{n}(p_{n})\to m+1$ in probability.

  2. 2.

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

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

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

  3. 3.

If $\lim_{n\to\infty}n^{1-\varepsilon}p_{n}=\infty$ for all $\varepsilon>0$,
then $\lim_{n\to\infty}S_{n}(p_{n})/\ell_{n}=1$ in probability, where
$\ell_{n}$ is the same quantity as in Theorem 5.20.

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

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

##  6 Regenerative properties of directed random graphs

We now return to the setup of Section 2.1 and consider the case where we are
given a sequence $p_{1},p_{2},\ldots$ of numbers in $[0,1]$ such that

$0<p_{1}<1.$

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

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

$q_{j}:=1-p_{j},\quad Q_{j}:=q_{1}\cdots q_{j},\quad Q_{0}:=1.$

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

###  6.1 Breaking the graph into independent cycles

We showed in Lemma 2.6, that if the sequence $p_{j}$ does not convergence to
$0$ too fast, in the sense that condition (2.7) of Lemma 2.6,

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

holds, then the skeleton set $\mathscr{S}$ of all vertices $v$ such that
$u\leadsto v\leadsto w$ for all $u<v<w$ (where $i\leadsto j$ stands for “there
is a path from $i$ to $j$”)

is infinite in both directions a.s. and has strictly positive rate

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

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

$\cdots<\Gamma_{-1}<\Gamma_{0}\leq 0<\Gamma_{1}<\Gamma_{2}<\cdots$ (6.2)

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

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

Consider now the random sequence

$\alpha^{(0)}:=(\alpha^{(0)}_{1},\alpha^{(0)}_{2},\ldots),$

consisting of independent entries with

$\mathbb{P}(\alpha^{(0)}_{j}=1)=1-\mathbb{P}(\alpha^{(0)}_{j}=-\infty)=p_{j},\quad
j\in\mathbb{N},$

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

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

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

$\mathscr{C}_{k}:=(\alpha^{(n)},\,\Gamma_{k}\leq n<\Gamma_{k+1})$

as the $k$th “cycle”, $k\in\mathbb{Z}$. Let $\overrightarrow{G}_{k}$ be the
induced subgraph of $\overrightarrow{G}(\mathbb{Z},(p_{j}))$ on the set of
vertices $\\{v\in\mathbb{Z}:\,\Gamma_{k}\leq v\leq\Gamma_{k+1}\\}$, that is,
keep only those edges with endpoints in this set. The following was proved in
[36].

######  Lemma 6.1.

Assume that (2.7) holds. Then, conditional on $\\{0\in\mathscr{S}\\}$, the
cycles $\mathscr{C}_{k}$, $k\in\mathbb{Z}$, are i.i.d. and the random graphs
$\overrightarrow{G}_{k}$, $k\in\mathbb{Z}$, are i.i.d.

###### Sketch of proof.

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

$\\{0\in\mathscr{S}\\}=\\{\Gamma_{0}=0\\}=\\{r(-1)\leq 1,r(-2)\leq
2,\ldots;\ell(1)\leq 1,\ell(2)\leq 2,\ldots\\}$ (6.3)

Define the random variables

$\displaystyle\widehat{\Gamma}_{-1}$ $\displaystyle:=\max\\{n<0:r(n-1)\leq
1,r(n-2)\leq 2,\ldots;\ell(n+1)\leq 1,\ldots,\ell(0)\leq|n|\\}$
$\displaystyle\widehat{\Gamma}_{1}$ $\displaystyle:=\min\\{n>0:~{}r(0)\leq
n,\ldots,r(n-1)\leq 1;\ell(n+1)\leq 1,\ell(n+2)\leq 2,\ldots\\}$

and observe that

$\text{ if }\Gamma_{0}=0\text{ then
}\Gamma_{-1}=\widehat{\Gamma}_{-1},\,\Gamma_{1}=\widehat{\Gamma}_{1}.$

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

######  Remark 6.2.

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

$\mathbb{E}(\Phi)=\lambda\mathbb{E}\bigg{\\{}\sum_{\Gamma_{0}\leq
k<\Gamma_{1}}\theta^{k}\Phi\bigg{|}0\in\mathscr{S}\bigg{\\}}.$

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

###  6.2 Moments of auxiliary stopping times

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

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

$\displaystyle\begin{split}A^{+}_{u,v}&=\\{u\leadsto[u+1,v]\\},\\\
A^{-}_{u,v}&=\\{[u,v-1]\leadsto v\\},\end{split}$ (6.4)

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

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

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

$\displaystyle A^{+}_{u,u+d}$ $\displaystyle=\\{\ell(u+1)\leq
1,\ldots,\ell(u+d)\leq d\\}$ $\displaystyle A^{-}_{u-d,u}$
$\displaystyle=\\{r(u-1)\leq 1,\ldots,r(u-d)\leq d\\}.$

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

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

(where “$A$ fails” stands for “$A^{c}$ occurs”, that is,
${\text{\Large$\mathfrak{1}$}}_{A^{c}}=1$ a.s.) Since $A^{+}_{0,k}$ decreases
as $k$ increases, we have

$\mathbb{P}(\mu>k)=\mathbb{P}(A_{0,k}^{+})=\mathbb{P}(\ell(1)\leq
1,\ldots,\ell(k)\leq k)=(1-Q_{1})\cdots(1-Q_{k}),$

and this implies that $\mu$ is defective:

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

We also have

$\displaystyle\mathbb{P}(n<\mu<\infty)$
$\displaystyle=\mathbb{P}\left(A_{0,n}^{+}\cap\bigcup_{k=1}^{\infty}(A_{0,k}^{+})^{c}\right)=\mathbb{P}\left(A_{0,n}^{+}\cap\bigcup_{k=n+1}^{\infty}(A_{0,k}^{+})^{c}\right)=\mathbb{P}\left(A_{0,n}^{+}\cap\bigg{(}\bigcap_{k=n+1}^{\infty}A_{0,k}^{+}\bigg{)}^{c}\right)$
$\displaystyle=\mathbb{P}(\ell(1)\leq 1,\ldots,\ell(n)\leq n;\\{\ell(1)\leq
1,\ldots,\ell(n)\leq n,\ell(n+1)\leq n+1,\ldots\\}^{c})$
$\displaystyle=\mathbb{P}(\ell(1)\leq 1,\ldots,\ell(n)\leq n;\\{\ell(n+1)\leq
n+1,\ell(n+2)\leq n+2,\ldots\\}^{c})$ $\displaystyle=\mathbb{P}(\ell(1)\leq
1,\ldots,\ell(n)\leq n)\,\mathbb{P}(\exists k>n~{}\ell(k)>k)$ (6.6)
$\displaystyle=\mathbb{P}(\ell(1)\leq 1,\ldots,\ell(n)\leq
n)\,\left[1-\mathbb{P}(\ell(n+1)\leq n+1,\ell(n+2)\leq n+2,\ldots)\right]$
$\displaystyle=(1-Q_{1})\cdots(1-Q_{n})\,\left[1-(1-Q_{n+1})(1-Q_{n+2})\cdots\right]$
(6.7) $\displaystyle=(1-Q_{1})\cdots(1-Q_{n})-\sqrt{\lambda}.$

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

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

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

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

We have thus proved

######  Lemma 6.3.

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

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

######  Corollary 6.4.

Conditional on $\\{\mu<\infty\\}$, $\mu$ has a $p$-moment (respectively,
exponential moment) if and only if $\ell(0)$ has a $(p+1)$-moment
(respectively, exponential moment).

We similarly wish to examine the moments of the random variable

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

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

$\nu=\inf\\{k\in\mathbb{N}\,[0,k-1]\leadsto
k\\}=\inf\\{k\in\mathbb{N}:\,r(k-1)\leq 1,\ldots,r(0)\leq k\\}.$

Define a sequence of nonnegative integer-valued random variables $x_{n}$,
$n=0,1,\ldots$, by $x_{0}=0$ and

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

Then

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

But the $x_{n}$ satisfy

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

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

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

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

######  Lemma 6.5.

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

######  Remark 6.6.

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

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

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

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

as follows.

$\displaystyle\nu[1]$ $\displaystyle:=\nu$ $\displaystyle\mu[1]$
$\displaystyle:=\nu+\theta^{\nu}\mu=\inf\\{j>\nu:~{}A^{+}_{\nu,j}\text{
fails}\\},$ (6.9)

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

$\displaystyle\nu[k]$
$\displaystyle:=\inf\\{j>\mu[k-1]:A_{\nu[k-1],j}^{-}\text{ occurs}\\}$
$\displaystyle\mu[k]$
$\displaystyle:=\nu[k]+\theta^{\nu[k]}\mu=\inf\\{j>\nu[k]:A_{\nu[k],j}^{+}\text{
fails}\\}.$ (6.10)

It is understood that if for some $k$ we have $\mu[k]=\infty$ then
$\nu[j]=\mu[j]=\infty$ for all $j\geq k+1$. In fact, since $\mu$ is a
defective random variable, with $\mathbb{P}(\mu=\infty)=\sqrt{\lambda}$, it
follow that the recursion terminates in finitely many steps. Let

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

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

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

$\nu[K]\overset{\mathrm{d}}{=}\sum_{i=1}^{\kappa}\nu_{i}+\sum_{i=1}^{\kappa-1}\mu_{i},$

where $\kappa,\nu_{1},\nu_{2},\ldots,\mu_{1},\mu_{2},\ldots$ are independent,
with $\kappa\overset{\mathrm{d}}{=}K$, hence geometric$(\sqrt{\lambda})$,
$\nu_{i}\overset{\mathrm{d}}{=}\nu$, and
$\mathbb{P}(\mu_{i}\in\cdot)=\mathbb{P}(\mu\in\cdot|\mu<\infty)$.

######  Lemma 6.7.

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

###### Proof.

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

######  Theorem 6.8.

Let $p\geq 1$.
(i) $\mathbb{E}((\Gamma_{1}-\Gamma_{0})^{p}|\Gamma_{0}=0)<\infty$ if and only
if $\sum_{k=1}^{\infty}k^{p}Q_{k}<\infty$
(ii) The distribution of $\Gamma_{1}-\Gamma_{0}$ conditional on $\Gamma_{0}=0$
has an exponential moment if and only if
$\sum_{k=1}^{\infty}z^{k}Q_{k}<\infty$ for some $z>1$.

###### Proof.

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

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

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

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

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

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

We now use Lemma 6.7 and Remark 6.6 to conclude. ∎

The results above are used in the proof of the following functional central
limit theorem.

######  Theorem 6.9.

Consider the random graph $\overrightarrow{G}(\mathbb{Z},(p_{j}))$, assuming
$0<p_{1}<1$, and

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

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

$0<\sigma^{2}:=\operatorname{var}(L_{\Gamma_{1},\Gamma_{2}}-C(\Gamma_{2}-\Gamma_{1}))<\infty$
(6.12)

Define

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

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

###### Sketch of proof.

We have $\lambda>0$ because $p_{1}>0$. It is clear that $\sigma^{2}>0$. The
reason that $\sigma^{2}$ is finite follows
$L_{\Gamma_{1},\Gamma_{2}}\leq\Gamma_{2}-\Gamma_{1}$ and Theorem 6.8 which
guarantees that
$\mathbb{E}[(\Gamma_{1}-\Gamma_{2})^{2}]=\mathbb{E}[(\Gamma_{1}-\Gamma_{0})^{2}|\Gamma_{0}=0]<\infty$.
From Remark 6.2 we also have that $\mathbb{E}\Gamma_{1}<\infty$. Let
$N_{n}=\max\\{j\geq 1:\,\Gamma_{j}\leq n\\}$. By the definition of
$\mathscr{S}$, if $v\in\mathscr{S}$ then the maximal path from some $u<v$ to
some $w>v$ must necessarily include $v$. Hence

$L_{0,n}=L_{0,\Gamma_{1}}+L_{\Gamma_{1},\Gamma_{2}}+\cdots+L_{\Gamma_{N_{n},n}}.$

We can then write

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

Define also

$\widehat{\ell}_{n}(t):=\frac{1}{\sigma\sqrt{\lambda
n}}\sum_{i=2}^{nt}\left[L_{\Gamma_{i-1},\Gamma_{i}}-C(\Gamma_{i}-\Gamma_{i-1})\right],\quad\varphi_{n}(t):=\frac{N_{nt}}{n}.$

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

######  Remark 6.10.

We made the assumption that $p_{1}>0$ in order that the set $\mathscr{S}$
serve as a skeleton set over which the graph regenerates, that is, we have
independent pieces. If $p_{1}=0$ then $\mathscr{S}$ is useless; for example,
$\lambda=0$ in this case. However, if $p_{1}=\cdots=p_{j}=0$ but $p_{j+1}>0$
then we can establish a 1-dependent structure.111111We say that a random
sequence $X_{i}$, $i\in\mathbb{Z}$, is 1-dependent if, for each
$i\in\mathbb{Z}$, the sequences $(X_{j},j<i)$ and $(X_{j},j>i)$ are
independent. One can still deal with this case, but one needs a somewhat
different technique based on weakly regenerative processes.

######  Remark 6.11.

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

######  Remark 6.12.

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

######  Remark 6.13.

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

##  7 Directed random graphs on partially ordered sets

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

###  7.1 Brownian last passage percolation

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

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

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

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

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

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

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

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

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

######  Theorem 7.1.

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

$\ell_{n}(t):=\frac{L^{*}_{[nt]}-Cnt}{\sigma\sqrt{\lambda n}},\quad t\geq
0,\quad n\in\mathbb{N},$

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

$Z_{M}(t):=\max_{0=t_{0}\leq t_{1}\leq\ldots\leq
t_{M}=t}\,\sum_{i=1}^{M}\big{(}B^{(i)}(t_{i})-B^{(i)}(t_{i-1})\big{)},$ (7.1)

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

###### Sketch of proof.

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

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

is still a renewal process as it is obtained by thinning. Moreover,
$\mathscr{S}^{I}$ is stationary and ergodic (with respect to $\theta)$ and has
positive rate. Hence $\mathscr{S}^{I}$ is an random subset of $\mathbb{Z}$
that is infinite in both directions. Let $\Gamma_{k}^{I}$, $k\in\mathbb{Z}$,
be an enumeration of the elements of $\mathscr{S}^{I}$ with
$\Gamma_{k}^{I}<\Gamma_{k+1}^{I}$ for all $k\in\mathbb{Z}$, and
$\Gamma^{I}_{0}\leq 0<\Gamma_{1}^{I}$. Then, as in the Barak-Erdős case (see
Lemma 6.1) is we let $\overrightarrow{G}_{k}$ be the induced subgraph of
$\overrightarrow{G}(\mathbb{Z}\times I,p)$ on $\\{(u,i)\in\mathbb{Z}\times
I:\,\Gamma_{k}^{I}\leq u\leq\Gamma_{k+1}\\}$, we have that, conditional on
$\\{0\in\mathscr{S}^{I}\\}$, the $\overrightarrow{G}_{k}$, $k\in\mathbb{Z}$,
are i.i.d. Therefore, a maximal-length path on $\\{0,\ldots,n\\}\times I$ is
necessarily a path from $(0,1)$ to $(n,M)$ such that if
$0\leq\Gamma_{k}^{I}\leq n$ then such a path passes via a vertex whose
horizontal coordinate is $\Gamma_{k}^{I}$; see Figure 7.

Figure 7: A maximal length path on $[0,n]\times I$ passes through all
intermediate skeleton points and switches line at some of them.

Using this and breaking $\ell_{n}(t)$ as in (6.13), we arrive at the result by
using Donsker’s theorem. Details can be found in [36]. ∎

###  7.2 Generalization to partially ordered vertex sets and distance-
dependent probabilities

In the above, we can take $I$ to be a finite partially ordered set
$(I,\preceq)$ with a bottom element called $1$ and a top element called $M$.
We then equip $\mathbb{Z}\times I$ with a strict partial order $\ll$ defined
by

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

A pair of vertices $(u,i)$, $(v,j)$, with $(u,i)\ll(v,j)$, form an edge
directed from $(u,i)$ to $(v,j)$ with probability $r_{v-u,i,j}$, independently
from pair to pair. As before, we let $L_{(u,i),(v,j)}$ the maximum length of
paths from $(u,i)$ to $(v,j)$. A convenient set of assumptions for the
probabilities $r_{n,i,j}$ is:

$\forall i\in I~{}r_{n,i,i}=:p_{n},\quad
0<p_{1}<1,\quad\sum_{n=1}^{\infty}n\prod_{m=1}^{n}(1-p_{m})<\infty.$ (7.2)

Let as denote by $\overrightarrow{G}(\mathbb{Z}\times I,(r_{n,i,j}))$ the
resulting random graph on $\mathbb{Z}\times I$ and let $L^{*}_{0,n}$ be the
maximum length of all paths with endpoints in $[0,n]\times I$.

Then Theorem 7.1 remains the same in form, that is, we normalize
$L^{*}_{0,[nt]}$ in the same way and obtain that the normalized sequence of
processes converge in distribution to a process akin to (7.1) but with an
additional maximization since the presence of partial order allows for more
flexibility.

To express the limiting process we need the Hasse diagram $\mathbb{H}(I)$ of
the partially ordered set $(I,\preceq)$, which is the directed graph on $I$
obtained by declaring there is an edge from $i$ to $j$ if

$\text{$i\preceq j$ and there is no $k$, distinct from $i$ and $j$, such that
$i\preceq k\preceq j$}.$

See [34]. Let $B^{(i)}$, $i\in I$, be independent standard Brownian motions.
For any path $\iota=(\iota_{0},\ldots,\iota_{r})$ in $\mathbb{H}(I)$ we write

$Z^{(\iota)}(t):=\max_{0=t_{0}\leq t_{1}\leq\cdots\leq
t_{r}=t}\big{\\{}B^{(\iota_{0})}(t_{1})+[B^{(\iota_{1})}(t_{2})-B^{(\iota_{1})}(t_{1})]+\cdots+[B^{(\iota_{r})}(t_{r})-B^{(\iota_{r})}(t_{r-1})]\big{\\}},$

and then let

$Z_{I}(t):=\max_{\iota}Z^{(\iota)}(t),$ (7.3)

where the maximum is taken over all paths $\iota$ in $\mathbb{H}(I)$ from $0$
to $M$. Then $Z_{I}$ is the limit of the sequence of normalized processes.

###  7.3 Convergence to the Tracy-Widom distribution

##### Self-similarity.

It is clear that the process $Z_{I}$ of (7.3) is not Gaussian, but is is
continuous and self-similar:

$(Z_{I}(ct))_{t\geq 0}\overset{\mathrm{d}}{=}c^{1/2}(Z_{I}(t))_{t\geq 0},$

for any $c>0$. In particular, the process $Z_{M}$ of (7.1) is a special case
of (7.3), when $I=\\{1,\ldots,M\\}$, has well-known connection with random
matrix theory; see below.

##### Queueing theory.

Glynn and Whitt [52] considered an infinite number single-server FCFS
infinite-buffer queues connected in series. At time $0$ there are $M$
customers in the first one and none in the others. Denote by $\sigma_{m,n}$
the service time of customer $m$ in queue $n$. It is assumed that the
$\sigma_{m,n}$, are i.i.d. random variables with finite variance. One quantity
of interest in queueing theory is the time $L_{m,n}$ that customer $m$ departs
from queue $n$. For this, we have an obvious recursion, namely,

$L_{m,n}=\max(L_{m-1,n},L_{m,n-1})+\sigma_{m,n},$

because if customer $m$ finds, upon arrival, queue $n$ occupied, it has to
wait until the previous customer departs from queue $n$ at time $L_{m,n-1}$,
so $L_{m,n}=L_{m,n-1}+\sigma_{m,n}$; and if it finds the queue empty then
$L_{m,n}=L_{m,n-1}+\sigma_{m,n}$. We can easily solve the recursion and
express it as follows. Consider $\mathbb{N}\times\mathbb{N}$ as a directed
graph where each vertex $(i,j)$ has two outgoing edges, one to $(i,j+1)$ and
one to $(i+1,j)$. Equip each $(i,j)\in\mathbb{N}\times\mathbb{N}$ with weight
$\sigma_{i,j}$. Let $\pi$ be a path in this graph. Then $w(\pi)$ is the sum of
the weights of the vertices of this path. We obtain

$L_{m,n}=\max\\{w(\pi):\,\pi\text{ is path from $(1,1)$ to
$(m,n)$}\\},\quad(m,n)\in\mathbb{N}\times\mathbb{N}.$

Consider now the normalized departure times,

$\ell_{m}^{(n)}:=\frac{L_{m,n}-n\mathbb{E}\sigma}{\sqrt{n\operatorname{var}\sigma}},$

where $\sigma$ has the same law as (any of) the $\sigma_{m,n}$. Then [52] show
that

$\ell_{M}^{(n)}\to Z_{M}(1),\text{ as }n\to\infty,\text{ in distribution},$

where $Z_{M}$ is as in (7.1). For subsequent work on the symmetry, duality,
and other quantities of interest, see [9].

##### The GUE.

Let $H$ be an $M\times M$ GUE (Gaussian Unitary Ensemble) random matrix [81].
This is a random element of the set of complex Hermitian $M\times M$ matrices
such that each diagonal element has standard complex Gaussian distribution and
each off-diagonal element has standard real Gaussian distribution. (A standard
complex Gaussian distribution is the law of $Z=X+\sqrt{-1}Y$ where $X,Y$ are
i.i.d. Gaussian random variables with $\mathbb{E}X=\mathbb{E}Y=0$,
$\mathbb{E}X^{2}=\mathbb{E}Y^{2}=1$.) Moreover, all elements $H_{k,\ell}$,
$k\leq\ell$, are independent (and $H_{\ell,k}=\overline{H}_{k,\ell}$ for
$k\leq\ell$). The eigenvalues of $H$ are real random variables and the largest
of them is denoted by $\lambda_{M}$. It is clear that $H$ satisfies
$H\overset{\mathrm{d}}{=}UHU^{-1}$ for any unitary ($U^{-1}=U^{*}$) complex
matrix $U$. It was shown by Baryshnikov [11], thus answering an open question
by Glynn and Whitt [52], that $Z_{M}(1)$ satisfies

$Z_{M}(1)\overset{\mathrm{d}}{=}\lambda_{M},$ (7.4)

thus establishing a connection between Brownian last passage percolation and
random matrix theory.

##### CLT for the largest GUE eigenvalue.

The law of $\lambda_{m}$ (as well as the joint law of all eigenvalues of an
$m\times m$ GUE random matrix) satisfies $\lambda_{m}/\sqrt{m}\to 2$. The CLT
for $\lambda_{m}$ is

$m^{1/6}(\lambda_{m}-2\sqrt{m})\xrightarrow{\text{d}}F_{2},$ (7.5)

where the distribution function $F_{2}$ a determinantal form:

$F_{2}(x)=\det(I-A_{K})_{L^{2}[0,x]},$

where $A_{K}$ is the operator on $L^{2}[0,x]$ with kernel $K$ defined

$K(x,y)=\frac{\operatorname{Ai}(x)\operatorname{Ai}^{\prime}(y)-\operatorname{Ai}^{\prime}(x)\operatorname{Ai}(y)}{x-y},$

and where $\operatorname{Ai}(x)$ is the principal Airy function, defined as
the solution $y=Ai(x)$ to the linear ODE $y^{\prime\prime}-xy=0$ with boundary
condtion $y\to 0$ as $x\to\infty$. Fourier-transforming the ODE, at least
formally, easily yields that
$\operatorname{Ai}(x):=\pi^{-1}\int_{0}^{\infty}\cos(\tfrac{1}{3}\omega^{3}+\omega
x)d\omega=\pi^{-1}\lim_{\Omega\to\infty}\int_{0}^{\Omega}\cos(\tfrac{1}{3}\omega^{3}+\omega
x)d\omega$. Note that $K(x,x)$ is defined as a limit when $y\to x$. The
determinant above is to be understood as the Fredholm determinant of the
operator $A_{K}$ acting on $L^{2}[0,x]$. This was established by Tracy and
Widom [91] and the distribution $F_{2}$ is known as the Tracy-Widom law. See
also Anderson, Guionnet and Zeitouni [7]. The determinant can be computed
explicitly and a semi-explicit formula for $F_{2}$ can be found.

##### Barak-Erdős graph on $\mathbb{N}\times\mathbb{N}$.

Consider the graph $\overrightarrow{G}(\mathbb{N}\times\mathbb{N},p)$, with
$0<p<1$. We equip $\mathbb{N}\times\mathbb{N}$ with the natural partial order;
$(i,j)$ is before $(i^{\prime},j^{\prime})$ if $i\leq i^{\prime}$, $j\leq
j^{\prime}$ and $(i.j)\neq(i^{\prime},j^{\prime})$. If $(i,j)$ is before
$(i,j^{\prime})$ we put and edge between them with probability $p$,
independently from pair to pair of comparable vertices. Paths in this graph
move in a “northeast” direction (including the north and the east). We let
$L_{n,m}$ be the maximum length of all paths from $(1,1)$ to $(n,m)$. The
induced subgraph of $\overrightarrow{G}(\mathbb{N}\times\mathbb{N},p)$ on any
horizontal line is a $\overrightarrow{G}(\mathbb{N},p)$. Consider the $m$-th
line and apply Theorem 6.9. We obtain

$\left(\frac{L_{[nt].m}-Cnt}{\sigma\sqrt{\lambda n}}\right)_{t\geq
0}\xrightarrow{\text{d}}Z_{m},\text{ as }n\to\infty.$

On the other hand, by self-similarity and (7.4), we have

$Z_{m}(t)\overset{\mathrm{d}}{=}\sqrt{t}\lambda_{m},$

and $m^{1/6}(\lambda_{m}-2\sqrt{m})\xrightarrow{\text{d}}F_{2}$. It is then
natural to if we can obtain a limit for a normalized $L_{n,m}$ when $n$ and
$m$ tend to infinity simultaneously. To see what kind of scaling we can
expect, write (7.5) as

$m^{1/6}\left(\frac{Z_{m}(t)}{\sqrt{t}}-2\sqrt{m}\right)\xrightarrow{\text{d}}F_{2},\text{
as }n\to\infty.$

A statement of the form $X(t,m)\xrightarrow[m\to\infty]{\text{(d)}}X$, where
the distribution of $X(t,m)$ does not depend on the choice of $t>0$, implies
the statement $X(t,m(t))\xrightarrow[t\to\infty]{\text{d}}X$, for any function
$m(t)$ such that $m(t)\xrightarrow[t\to\infty]{}\infty$. Hence, upon setting
$m=[t^{a}]$, we have

$t^{a/6}\bigg{(}\frac{Z_{[t^{a}]}(t)}{\sqrt{t}}-2\sqrt{t^{a}}\bigg{)}\xrightarrow[t\to\infty]{\text{d}}F_{2}.$

Therefore, it is reasonable to guess that an analogous limit theorem holds for
a centered scaled version of the largest length $L_{n,[n^{a}]}$, namely that

$n^{a/6}\bigg{(}\frac{L_{n,[n^{a}]}-c_{1}n}{c_{2}\sqrt{n}}-2\sqrt{n^{a}}\bigg{)}\xrightarrow[t\to\infty]{\text{d}}F_{2},$
(7.6)

where $c_{1},c_{2}$ are appropriate constants. Indeed, (7.6) holds, with
$c_{1}=C=C(p)$ and $c_{2}=\lambda\sigma^{2}$. This was proved in [69].

That paper used the idea of strong coupling with Brownian motions (Komlós-
Major-Tusnády [67, 68, Theorem 4]), as in [17], a paper dealing with last
passage percolation on $\mathbb{N}\times\mathbb{N}$ with random weights on the
vertices. The difficulty in the proof of the main theorem in [69] is that if
we consider the intersection of the sets of skeleton points corresponding to
each line then their intersection is empty.

We also refer the reader to the seminal paper of Johansson [60] for last
passage percolation on a lattice (with i.i.d. exponential weights on
vertices).

##  8 Weighted Barak-Erdős graphs

We now sketch results on last passage percolation on the Barak-Erdős graph
with random weights on its edges; we refer to [46] and [42] for details.
Recall that existence of an edge $(i,j)$ is encoded by a random variable
$\alpha_{i,j}$ that takes value $1$ with probability $p$ or $-\infty$ with
probability $1-p$. Let $u$ be a positive random variable with distribution
function $F(x)=\mathbb{P}(u\leq x)$, and let $u_{i,j}$, $i<j$, be a collection
of i.i.d. copies of $u$. If $\alpha_{i,j}=1$ then edge $(i,j)$ exists and has
weight $u_{i,j}$. We now have a weighted random graph that we will denote as
$\overrightarrow{G}(\mathbb{Z},p,u)$. A path from $i$ to $j$ of length $\ell$
and weight $w$ is a sequence $(i=i_{0}<i_{1}<\cdots<i_{\ell-1}<i_{\ell}=j)$
such that $\alpha_{i_{0},i_{1}}=\cdots=\alpha_{i_{\ell-1},i_{\ell}}=1$ and
$u_{i_{0},i_{1}}+\cdots+u_{i_{\ell-1},i_{\ell}}=w$. A geodesic from $i$ to $j$
is a maximum weight path from $i$ to $j$.

Different phenomena appear depending on whether $\mathbb{E}u^{2}$ is finite or
not.

###  8.1 Finite variance weights

Assume that $\mathbb{E}u^{2}<\infty$. We study

$W_{i,j}:=\max_{\begin{subarray}{c}i=i_{0}<i_{1}<\cdots<i_{\ell}=j\\\
\ell\in\mathbb{N}\end{subarray}}\left(\sum_{k=1}^{\ell}\alpha_{i_{k-1},i_{k}}u_{i_{k-1},i_{k}}\right)^{+},$

the maximum weight of all paths from $i$ and $j$. If we further define the
larger quantity $\widetilde{W}_{i,j}:=\max_{\begin{subarray}{c}i\leq
i_{0}<i_{1}<\cdots<i_{\ell}\leq j\\\
\ell\in\mathbb{N}\end{subarray}}\left(\sum_{k=1}^{\ell}\alpha_{i_{k-1},i_{k}}u_{i_{k-1},i_{k}}\right)^{+}$,
the maximum weight of all paths with endpoints between $i$ and $j$ we obtain
the subadditive inequality

$\widetilde{W}_{i,k}\leq\widetilde{W}_{i,j}+\widetilde{W}_{j,k}+\max_{i\leq
x\leq j\leq y\leq k}u_{x,y}.$

We can then see that $\lim_{n\to\infty}\widetilde{W}_{0,n}/n$ exists iff the
expectation of the latter maximum is finite which requires that the second
moment of $u$ be finite. Hence $\mathbb{E}u^{2}<\infty$ is necessary and
sufficient for the above limit to exist.

To understand this, and to prepare the ground for the central limit theorem,
we consider two random subsets of the integers. The first is the usual
skeleton set $\mathscr{S}$ and the second is the set $\mathscr{R}_{c}$ of
$c$-renewal points where $c$ is a positive constant. To define this, we first
define the events

$\displaystyle A_{i}^{+}$ $\displaystyle=\\{W_{i,i+n}>cn\text{ for all }n\geq
1\\},$ $\displaystyle A_{i}^{-}$ $\displaystyle=\\{W_{i-n,i}>cn\text{ for all
}n\geq 1\\},$ $\displaystyle A_{i}^{-+}$
$\displaystyle=\\{\alpha_{i-m,i+n}u_{i-m,i+n}<c(m+n)\text{ for all }m,n\geq
1\\},$

and then let

$\mathscr{R}_{c}=\\{i\in\mathbb{Z}:\,A_{i}^{+}\cap A_{i}^{-}\cap
A_{i}^{-+}\text{ occurs}\\}.$

Clearly, $\mathscr{R}_{c}$ is a stationary and ergodic random set with density

$\mu(c,p)=\mathbb{P}(A_{0}^{+}\cap A_{0}^{-}\cap A_{0}^{-+}).$

Since

$\mathscr{R}_{c}\subset\mathscr{S}.$

we have $\mu(c,p)\leq\lambda(p)$, where $\lambda(p)$ is the density of
$\mathscr{S}$; see (2.9) and Remark 2.9.

######  Lemma 8.1.

Assume that $\mathbb{E}u^{2}<\infty$ and
$0<c<(\mathbb{E}u)(\mathbb{E}W_{\Gamma_{1},\Gamma_{2}})$. Then $\mu(c,p)>0$.
Moreover, $\overrightarrow{G}(\mathbb{Z},p,u)$ regenerates over
$\mathscr{R}_{c}$.

###### Sketch of proof.

We first observe that $\mathbb{P}(A_{0}^{+})=\mathbb{P}(A_{0}^{-})$. If we
choose $0<c<(\mathbb{E}u)(\mathbb{E}W_{\Gamma_{1},\Gamma_{2}})$ then
$\mathbb{P}(A_{0}^{+})>0$. The finiteness of $\mathbb{E}u^{2}$ implies the
positivity of $\mathbb{P}(A_{0}^{-+})$. It can be shown that
$A_{0}^{+},A_{0}^{-},A_{0}^{-+}$ are independent and so
$\mu(c,p)=\mathbb{P}(A_{0}^{+})\mathbb{P}(A_{0}^{-})\mathbb{P}(A_{0}^{-+})>0$.
For details see [42, Lemma 2 supra]. For the last assertion see [42, Lemma 3].
∎

This lemma is responsible for the law of large numbers:

######  Theorem 8.2.

Assume that $\mathbb{E}u^{2}<\infty$ and $0<p\leq 1$. Then there is a constant
$C$ depending on $p$ and the law of $u$ such that

$\lim_{n\to\infty}\frac{W_{0,n}}{n}=\lim_{n\to\infty}\frac{\widetilde{W}_{0,n}}{n}=C\text{
a.s. and in $L^{1}$}.$

We remark that the equality of the two limits is because of the existence of
the $c$-renewal points that have positive density. The CLT holds provided that
the third moment of $u$ is finite:

######  Theorem 8.3.

Assume that $\mathbb{E}u^{3}<\infty$ and $0<p\leq 1$.

Then the sequence of processes

$\left\\{\frac{W_{0,[nt]}-Cnt}{\sqrt{\lambda n}},\,t\geq 0\right\\}$

converges in distribution, as $n\to\infty$, to a zero mean Brownian motion.

Theorems 8.2 and 8.3 may be complemented by a result describing the behavior
of the weight of the heaviest edge on a geodesic path. Assuming that $F$ is
continuous ensures that there is a unique geodesic path from $0$ to $n$. Then
we can define

$h_{n}:=\text{ maximum weight of all edges on the geodesic path from $0$ to
$n$.}$

We also assume that the edge weight $u$ is regularly varying with index $s$,
in the sense that

$\frac{1-F(tx)}{1-F(x)}\to t^{-s},\text{ as }x\to\infty,\text{ for every
}t>0.$ (8.1)

Of course, $s>2$ is needed in order that $\mathbb{E}u^{2}$ be finite. When
$2<s<3$, one can deduce that the fluctuations of $W_{0,n}$ are of order larger
than $\sqrt{n}$, and so the central limit theorem cannot be extended to this
case.

######  Theorem 8.4.

Let the edge weight $u$ be a continuous random variable that is also regularly
varying with index $s>2$ in the sense of (8.1). Then we have

$\frac{\log h_{n}}{\log n}\rightarrow\frac{1}{s-1}\text{ in probability as
}n\rightarrow\infty.$ (8.2)

In particular, if $2<s<3$ then

$\frac{\operatorname{var}W_{0,n}}{n}\rightarrow\infty,$

and a central limit theorem such as that in Theorem 8.3 cannot hold.

The proof of this can be found in [46].

###  8.2 Infinite variance weights

Assume now that $\mathbb{E}u^{2}=\infty$. Under this condition, $W_{0,n}$
grows faster than linearly. This can be seen by considering the contribution
of the single heaviest edge in $[0,n]$, and noting that the expectation of the
maximum of $n^{2}$ i.i.d. random variables with infinite variance has
expectation that grows faster than $n$. Since $W_{0,n}$ is at least as large
as the weight of this single edge, we have that $\mathbb{E}W_{0,n}/n\to\infty$
as $n\to\infty$, and from Kingman’s subadditive ergodic theorem we can
conclude that in fact $W_{0,n}/n\to\infty$ a.s.

As before, we assume that $u$ is a continuous random variable such that the
regular variation condition (8.1) holds. We need $s<2$ in order that
$\mathbb{E}u^{2}$ be infinite.

New phenomena occur in the infinite variance case. In order to describe them
succinctly and avoid technicalities, we shall further assume that $p=1$. That
is, we only present results for the $\overrightarrow{G}(\mathbb{Z},1,u)$ case.

##### Finite model

Let $\overrightarrow{G}_{n}$ be a graph on
$V_{n}=\left\\{0,\frac{1}{n},\ldots,\frac{n-1}{n},1\right\\}$, edges
$E_{n}=\\{(i/n,j/n):\,0\leq i<j\leq n\\}$, and weights $u^{(n)}_{e}$, $e\in
E_{n}$, that are i.i.d. copies of $u$. We can think of a path $\pi$ of
$\overrightarrow{G}_{n}$ as a collection of edges $e_{1},\ldots,e_{\ell}$
where the ending point of $e_{i}$ is the starting point of $e_{i+1}$ for all
$1\leq i<\ell$. Let $\Pi_{n}$ be the set of all paths in
$\overrightarrow{G}_{n}$ from $0$ to $n$ (a set of size $2^{n-1}$). The
maximum weight of all paths in $\Pi_{n}$ can be written as

$W_{0,n}=\max_{\pi\in\Pi_{n}}\sum_{e\in\pi}u^{(n)}_{e}.$

The latter maximum will not increase if we throw in all admissible subsets of
the set of edges $E_{n}$, where we say that a set $A\subset E_{n}$ is
admissible if every pair of elements of $A$ are non-overlapping edges in the
sense that the endpoints of one are $\leq$ the endpoints of the other. If we
let $\mathcal{C}_{n}$ be the set of all admissible sets of edges then

$W_{0,n}=\max_{\pi\in\mathcal{C}_{n}}\sum_{e\in A}u^{(n)}_{e}.$ (8.3)

We next introduce another way to construct $\overrightarrow{G}_{n}$. This
second construction can be used to define a corresponding model on a
continuous set of vertices with an appropriately defined maximum path weight
$W$ in such a way that a scaled version of $W_{0,n}$ converges to $W$ in
distribution. Note that $E_{n}$ has size

$N=N_{n}=\binom{n+1}{n}.$

Let $E_{n}=\\{e_{1},\ldots,e_{N}\\}$ be an enumeration of the edges. Let
$M_{e_{1}}^{(n)},M_{e_{2}}^{(n)},\ldots,M_{e_{N}}^{(n)}$ be the order
statistics of the $u^{(n)}_{e_{1}},u^{(n)}_{e_{2}},\ldots,u^{(n)}_{e_{N}}$
That is,
$\\{M_{e_{1}}^{(n)},M_{e_{2}}^{(n)},\ldots,M_{e_{N}}^{(n)}\\}=\\{u^{(n)}_{e_{1}},u^{(n)}_{e_{2}},\ldots,u^{(n)}_{e_{N}}\\}$
(as sets) and $M_{e_{1}}^{(n)}>M_{e_{2}}^{(n)}>\cdots>M_{e_{N}}^{(n)}$.

Let $Y_{1}^{(n)},Y_{2}^{(n)},\ldots,Y_{N}^{(n)}$ be a random ordering of
$\\{e_{1},\ldots,e_{N}\\}$ chosen uniformly from all the $N!$ possibilities.
Assign weight $M_{e_{i}}^{(n)}$ to $Y_{i}^{(n)}$.

We then have

$\mathcal{C}_{n}=\left\\{A\subset\left\\{e_{1},\ldots,e_{N}\right\\}:\text{
for every pair $\\{e_{i},e_{j}\\}\subset A$ the $Y_{e_{i}}^{(n)}$,
$Y_{e_{j}}^{(n)}$ are non-overlapping}\right\\}$ (8.4)

and

$W_{0,n}=\max_{A\in\mathcal{C}_{n}}\sum_{e_{i}\in A}M_{e_{i}}^{(n)}$ (8.5)

which is equivalent (the same in distribution) to the previous definition of
$W_{0,n}$ in (8.3).

##### Infinite model

We next define a random weighted graph $\overrightarrow{G}$ on countably
infinite random set of vertices. Let $W_{1},W_{2},\ldots$ be a sequence of
i.i.d. exponential random variables with mean 1 each. Set

$M_{k}=(W_{1}+\cdots+W_{k})^{-1/s},\quad k=1,2,\ldots.$

Let $U_{1},U_{2},\ldots$ and $V_{1},V_{2},\ldots$ be two sequences of i.i.d.
uniform random variables in $[0,1]$. We further assume that $\\{U_{i}\\}$,
$\\{V_{i}\\}$, $\\{W_{i}\\}$ are independent. The edges of
$\overrightarrow{G}$ are taken to be

$Y_{i}=(\min(U_{i},V_{i}),\,\max(U_{i},V_{i})),\quad i=1,2,\ldots.$

The $i$-th largest weight $M_{i}$ will be attached to the $i$-th edge $Y_{i}$.
In analogy to (8.4) we define

$\mathcal{C}=\left\\{A\subset\left\\{1,2,\ldots\right\\}:Y_{i}\cap
Y_{j}=\varnothing\text{ for all pairs }\\{i,j\\}\subset A\right\\}.$

In analogy to to (8.5) we let

$W=\sup_{A\in\mathcal{C}}\sum_{i\in A}M_{i}.$ (8.6)

A priori the random variable $W$ could be infinite, but Theorem 8.5 below
guarantees that it is almost surely finite.

##### Convergence results

The intuition behind the approximation of the finite model by the infinite one
is the following pair of convergence results. First, for any $k\in\mathbb{N}$
we have

$\left(Y_{1}^{(n)},Y_{2}^{(n)},\ldots,Y_{k}^{(n)}\right)\xrightarrow{\text{\rm
d}}(Y_{1},Y_{2},\ldots,Y_{k})$ (8.7)

as $n\rightarrow\infty$, where we use the product topology on
$([0,1]^{2})^{k}$.

Following [79, 54], let
$b_{n}=a_{N_{n}}=F^{(-1)}\left(1-\frac{1}{N_{n}}\right)$ and put

$\widetilde{M}_{i}^{(n)}=\frac{M_{i}^{(n)}}{b_{n}}.$

(As an example, if $F(x)=1-x^{-s}$ for $x\geq 1$, then $b_{n}$ grows like
$n^{2/s}$. More generally, under assumption (8.1),
$\lim_{n\to\infty}\frac{\log b_{n}}{\log n}=2/s$). Then from classical results
in extreme value theory we have for any $k\in\mathbb{N}$ that

$\left(\widetilde{M}_{1}^{(n)},\widetilde{M}_{2}^{(n)},\ldots,\widetilde{M}_{k}^{(n)}\right)\xrightarrow{\text{\rm
d}}\left(M_{1},M_{2},\ldots,M_{k}\right)\text{ as }n\rightarrow\infty.$ (8.8)

In this way both the locations and weights of the heaviest edges (i.e. edges
with heaviest weights) in the discrete model above are approximated by their
equivalents in the continuous model. It is shown in [46] the heaviest edges,
dominant contribution to the maximum weight. The precise convergence result is
as follows.

######  Theorem 8.5.

The random variable $W$ in (8.6) is almost surely finite. If (8.1) holds with
$s\in(0,2)$, then $\frac{W_{0,n}}{b_{n}}\rightarrow W$ in distribution as
$n\rightarrow\infty$.

For $n$ large, the heaviest edge in the geodesic has length on the order of
$n$. This is in contrast to the behavior in the case $\mathbb{E}u^{2}<\infty$,
where the important contribution to the maximal weight is given by edges of a
lighter order, see e.g. Theorem 8.3 above.

##  9 Analytic properties of charged graphs

We now turn to some results concerning the behavior of the last passage
percolation constant $C$ of the Barak-Erdős graph as a function of edge
weights. The problem is, in general, hard, so we consider here the simple
model introduced in [44]. The next section will deal with a more general
model.

A charged graph is a graph with possibly negative weights on its edges. We are
interested in last passage percolation on random directed charged graphs. The
charge of a path is the sum of the charges of its edges. We are interested in
the maximum charge of all paths. If all charges are negative then the maximum
of negative quantities is the negative of a minimum of positive quantities, so
the problem becomes that of first passage percolation, In view of this, we
shall assume that some charges are nonnegative.

For the models of this and the next section we assume that the support of the
charge distribution is not a subset of $(-\infty,0)$. It will then turn out
that the last passage percolation constant is positive, so it matters little
if we take positive part of the charge of a path before maximization.

###  9.1 The two-weights model

Let $x$ be a real number, possibly negative (which can be thought of as a
penalty). To each pair $(i,j)$ of positive integers with $i<j$ we assign
weight or, rather, charge (since $x$ is allowed to be negative)

$w^{x}_{i,j}=\begin{cases}1,&\text{ with probability }p\\\ x,&\text{ with
probability }1-p\end{cases}.$

Let $\Pi_{i,j}$ be the set of strictly increasing finite sequences of
integers, $i_{0}<i_{1}<\cdots<i_{\ell}$ such that $i_{0}=i$ and $i_{\ell}=j$.
An element $\pi\in\Pi_{i,j}$ is a finite path in the complete directed graph
on $\mathbb{Z}$ (that is, a graph such that every $(i,j)$ with $i<j$ is an
edge directed from $i$ to $j$). So $\Pi_{i,j}$ is a deterministic set of size
$2^{j-i}-1$. Define

$w^{x}(\pi)=\sum_{k=1}^{\ell}w^{x}_{i_{k-1},i_{k}},\quad\text{ if
}\pi=(i_{0},\ldots,i_{\ell})\in\Pi_{i,j},$

and call $w^{x}(\pi)$ the charge or weight of $\pi$. We are interested in

$W^{x}_{i,j}=\max_{\pi=(i_{0},\ldots,i_{\ell})\in\Pi_{i,j}}~{}\sum_{k=1}^{\ell}w^{x}_{i_{k-1},i_{k}}.$
(9.1)

We will use the notation $\overrightarrow{G}(\mathbb{Z},p,x)$ to denote the
directed charged random graph on $\mathbb{Z}$ that contains as edges all
$(i,j)\in\mathbb{Z}\times\mathbb{Z}$ with $i<j$ and which has with i.i.d. edge
charges distributed as $w^{x}_{i,j}$. We study the asymptotic growth rate
$C(p,x)$ of $W^{x}_{i,j}$; see (9.2) below. The Barak-Erdős graph is still
denoted by $\overrightarrow{G}(\mathbb{Z},p)$ and, as usual, $C(p)$ is the
maximal path growth rate. The parameter $p$ is fixed throughout this section.
We shall be interested in the behavior of the model when $x$ varies.

We may extend the model by letting $x$ range in
$\mathbb{R}\cup\\{-\infty,+\infty\\}$. The case $x=+\infty$ is uninteresting
as being trivial. The case $x=-\infty$ formally corresponds to the Barak-Erdős
graph, the reason being as follows. The charge of
$i_{0},i_{1},\ldots,i_{\ell}$ equals $-\infty$ iff
$w^{x}_{i_{k},i_{k+1}}=-\infty$ for some $k$, and this is equivalent to
$i_{0},i_{1},\ldots,i_{\ell}$ not being a path in
$\overrightarrow{G}(\mathbb{Z},p)$. Hence
$(W^{-\infty}_{i,j})^{+}=L^{\mathsf{L},\mathsf{R}}_{i,j}$ and
$\overrightarrow{G}(\mathbb{Z},p,-\infty)=\overrightarrow{G}(\mathbb{Z},p)$.

An alternative way to think of $\overrightarrow{G}(\mathbb{Z},p,x)$ is by
letting all edges of $\overrightarrow{G}(\mathbb{Z},p)$ be blue and all non-
edges be red. Blue edges have charge 1; red edges have charge $x$.

######  Theorem 9.1.

For $-\infty<x<\infty$ we have

$\lim_{n\to\infty}\frac{W^{x}_{0,n}}{n}=\lim_{n\to\infty}\frac{(W^{x}_{0,n})^{+}}{n}=\inf_{n\in\mathbb{N}}\frac{\mathbb{E}(W^{x}_{0,n})^{+}}{n}=:C(p,x),$
(9.2)

a.s. and in $L^{1}$.

The constant $C(p,x)$ is defined through this theorem. The theorem is proved
by using ergodic arguments and Kingman’s theorem, thanks to the superadditive
inequality

$W^{x}_{i,k}\geq W^{x}_{i,j}+W^{x}_{j,k},\quad i<j<k.$

Further properties of $C(p,x)$ are in Theorem 9.2 below. We shall use the
following notations.

$\displaystyle\mathbb{X}_{C}$
$\displaystyle:=\\{x\in\mathbb{R}:\,C(p,\cdot)\text{ is not differentiable at
}x\\}$ $\displaystyle\mathbb{Q}^{*}$
$\displaystyle:=\mathbb{Q}\setminus\mathbb{Z}$ $\displaystyle\mathbb{Y}$
$\displaystyle:=\\{q\in\mathbb{Q}^{*}:\,q<0\\}\cup\\{0\\}\cup\\{\tfrac{1}{2},\tfrac{1}{3},\ldots\\}\cup\\{2,3,\ldots\\}$

######  Theorem 9.2.

  1. (i)

Scaling. $C(p,x)=xC(1-p,x)$, for all $x>0$.

  2. (ii)

Continuity at $-\infty$. $\lim_{x\to-\infty}C(p,x)=C(p)$.

  3. (iii)

Convexity. $C(p,x)$ is increasing convex over $x\in\mathbb{R}$ and strictly
positive.

  4. (iv)

Asymptotic growth.
$\lim_{x\to\infty}C(p,x)/x=C(1-p,0)=\left(\sum_{n=1}^{\infty}p^{\frac{1}{2}n(n-1)}\right)^{-1}$.

  5. (v)

Nondifferentiability. $\mathbb{X}_{C}=\mathbb{Y}$.

The proof of (v) is the most complex and shall only be sketched below.
Property (i) follows from by comparing $\overrightarrow{G}(\mathbb{Z},p,x)$
with $\overrightarrow{G}(\mathbb{Z},1-p,1/x)$. Property (iii) follows from the
fact that $W^{x}_{i,j}$ is an increasing convex function of $x$. Strict
positivity is due to $C(p,x)>C(p)>0$ for all $x$. The first part of Property
(iv) is a consequence of continuity of the convex function and the scaling
property (i). The last formula of (iv) is due to Dutta [38].

To deal with (v), we start by further elaborating on skeleton points.

###  9.2 Further structure of inter-skeleton pieces

As usual, $[m,n]$ stands for the set of all integers $k$ with $m\leq k\leq n$.
That the set $\mathscr{S}$ of skeleton points of
$\overrightarrow{G}(\mathbb{Z},p)$ splits $\overrightarrow{G}(\mathbb{Z},p,x)$
into independent parts is not a surprise; see Lemma 6.1. Hence, if
$(i_{0},\ldots,i_{\ell})$ achieves the maximum in the right-hand side of the
definition (9.1) for $W^{x}_{i,j}$, then $\\{i_{0},\ldots,i_{\ell}\\}$
contains all elements of $\mathscr{S}\cap[i,j]$.

Enumerate the elements $\Gamma_{k}$ of $\mathscr{S}$ as in (6.2). Let
$\overrightarrow{G}(I,p)$ be the Barak-Erdős graph on the (possibly random)
set of vertices $I\subset\mathbb{Z}$.

Fix a positive integer $n$. Consider the event $A^{+}_{0,n}$ that there is a
path in $\overrightarrow{G}(\mathbb{Z},p)$ from $0$ to every vertex in $(1,n]$
and the event $A^{-}_{0,n}$ that there is a path from any vertex in $[0,n-1)$
to $n$; see (6.4). In addition, let

$F_{0,n}:=\big{\\{}\text{for all $0<j<n$ there is $0<i<n$ such that there is
no path from $\min(i,j)$ to $\max(i,j)$}\big{\\}},$

and then set

$H_{0,n}:=A^{+}_{0,n}\cap A^{-}_{0,n}\cap F_{0,n}.$

The following is an expression for the distribution of
$\overrightarrow{G}([\Gamma_{0},\Gamma_{1}],p)$ conditional on
$\\{\Gamma_{0}=0\\}$.

######  Proposition 9.3.

For any nonnegative deterministic functional
$\varphi\big{(}\overrightarrow{G}([\Gamma_{0},\Gamma_{1}],p\big{)}$ of
$\overrightarrow{G}([\Gamma_{0},\Gamma_{1}],p)$ we have

$\mathbb{E}\left\\{\varphi\big{(}\overrightarrow{G}([\Gamma_{0},\Gamma_{1}],p\big{)}\big{|}\Gamma_{0}=0\right\\}=\sum_{n=1}^{\infty}\mathbb{E}\left\\{\varphi\big{(}\overrightarrow{G}([0,n],p\big{)};H_{0,n}\right\\},$
(9.3)

In particular,

$\mathbb{P}(\Gamma_{1}-\Gamma_{0}=n|\Gamma_{0}=0)=\mathbb{P}(\Gamma_{2}-\Gamma_{1}=n)=\mathbb{P}(H_{0,n}).$
(9.4)

Furthermore,

$C(p,x)=\lambda\mathbb{E}W^{x}_{\Gamma_{1},\Gamma_{2}}=\lambda\sum_{n=1}^{\infty}\mathbb{E}(W^{x}_{0,n};H_{0,n}),$
(9.5)

where $\lambda=\lambda(p)$ is as in (2.9).

For a proof see [44]. The intuition should be clear because, if, say,
$A^{+}_{0,n}\cap A^{-}_{0,n}$ holds (in which case both $0$ and $n$ are in
$\mathscr{S}$) but $F_{0,n}$ fails, then there is an element of $\mathscr{S}$
strictly between $0$ and $n$. The first equality of (9.5) is by standard
renewal theory. The second follows from (9.3).

######  Remark 9.4.

From (9.4) we can obtain some values of the distribution of
$\Gamma_{2}-\Gamma_{1}$:

$\mathbb{P}(\Gamma_{2}-\Gamma_{1}=n)=\begin{cases}p,&\text{ if }n=1\\\
0,&\text{ if }n=2\\\ p^{4}(1-p),&\text{ if }n=3\\\
p^{7}(1-p)^{3}+3p^{5}(1-p)^{2},&\text{ if }n=4\end{cases}$

The smallest value of $\Gamma_{2}-\Gamma_{1}$ is $1$. Suppose that
$\Gamma_{2}-\Gamma_{1}\geq 2$. Note that
$\overrightarrow{G}([\Gamma_{1},\Gamma_{2}],p)$ must necessarily have the
edges $(\Gamma_{1},\Gamma_{1}+1)$ and $(\Gamma_{2}-1,\Gamma_{2})$. If
$\Gamma_{2}-\Gamma_{1}$ were allowed to take value $2$ then
$\Gamma_{1}+1=\Gamma_{2}-1$ would have been a skeleton point strictly between
$\Gamma_{1}$ and $\Gamma_{2}$, which is impossible. This explains why
$\mathbb{P}(\Gamma_{2}-\Gamma_{1}=2)=0$.

###  9.3 Criticality and nondifferentiability

Let $\pi=(i_{0},\ldots,i_{\ell})$ be a finite strictly increasing sequence of
integers. Let $N(\pi)$ be the number of $(i_{k-1},i_{k})$, $k=1,\ldots,\ell$
that are also edges of $\overrightarrow{G}(\mathbb{Z},p)$. Thus, $N(\pi)$ is
the number of blue edges of $\pi$. Similarly, $\overline{N}(\pi)$ is the
number of red edges. Then

$w^{x}(\pi)=\sum_{k=1}^{\ell}w^{x}_{i_{k-1},i_{k}}=N(\pi)+x\overline{N}(\pi).$

Define

$\Pi^{x}_{i,j}:=\\{\pi\in\Pi_{i,j}:\,w^{x}(\pi)=W^{x}_{i,j}\\},$

a random set of paths with maximal charge. Let $D^{+}$ denote right derivative
with respect to $x$; similarly $D^{-}$ for left derivative. Using (9.5) and
the dominated convergence theorem we obtain

$\displaystyle D^{+}C(p,x)$
$\displaystyle=\lambda\mathbb{E}D^{+}W^{x}_{\Gamma_{1},\Gamma_{2}}=\lambda\mathbb{E}\max_{\pi\in\Pi^{x}_{\Gamma_{1},\Gamma_{2}}}\overline{N}(\pi),$
$\displaystyle D^{-}C(p,x)$
$\displaystyle=\lambda\mathbb{E}D^{-}W^{x}_{\Gamma_{1},\Gamma_{2}}=\lambda\mathbb{E}\min_{\pi\in\Pi^{x}_{\Gamma_{1},\Gamma_{2}}}\overline{N}(\pi).$

######  Definition 9.5 (the sets $\mathfrak{G}_{n}$ and $\mathfrak{H}_{n}$).

Let $\mathfrak{G}_{n}$ be the set of all directed graphs on $[0,n]$, that is,
graphs whose edge directions compatible with the natural ordering of integers.

Let $\mathfrak{H}_{n}\subset\mathfrak{G}_{n}$ contain all
$G\in\mathfrak{G}_{n}$ such that, for all $0<j<n$,

  1. (a)

there is a path in $G$ from $0$ to $n$ containing $j$;

  2. (b)

for some $i\neq j$ there is no path in $G$ from $\min(i,j)$ to $\max(i,j)$

For any path $\pi$ in a graph $G$ we let $N_{G}(\pi)$ be the number of edges
of $\pi$ that are also edges of $G$ and we let $\overline{N}_{G}(\pi)$ the
number of edges of $\pi$ that are not edges of $G$.

######  Definition 9.6 (criticality).

We say that $x\in\mathbb{R}$ is critical if there is a positive integer $n$
and and a graph $G\in\mathfrak{H}_{n}$ possessing two paths $\pi_{1},\pi_{2}$
such that

  1. (a)

$N_{G}(\pi_{1})+x\overline{N}_{G}(\pi_{1})=N_{G}(\pi_{2})+x\overline{N}_{G}(\pi_{2})=\max_{\pi\in\Pi_{0,n}}(N_{G}(\pi)+x\overline{N}_{G}(\pi))$

  2. (b)

$\overline{N}_{G}(\pi_{1})\neq\overline{N}_{G}(\pi_{2})$.

Criticality is a property of real numbers. We let

$\mathbb{X}_{\text{\rm crit}}=\\{x\in\mathbb{R}:x\text{ is critical}\\}.$

Using Proposition 9.3 we can prove

######  Theorem 9.7.

$\mathbb{X}_{C}=\mathbb{X}_{\text{\rm crit}}.$

In view of this, Theorem 9.2(v) is equivalent to

$\mathbb{X}_{\text{\rm crit}}=\mathbb{Y},$ (9.6)

which is a deterministic problem of graph-theoretic/combinatorial nature.
Proving this is rather complicated. We shall sketch some aspects of it below.

###  9.4 $\mathbb{Y}\subset\mathbb{X}_{\text{\rm crit}}$

Let $x\in\mathbb{R}$, $G\in\mathfrak{G}_{n}$ and $\pi\in\Pi_{0,n}$. Think of
the common edges of $\pi$ and $G$ as blue and the remaining edges of $\pi$ as
red. There are $N_{G}(\pi)$ blue and $\overline{N}_{G}(\pi)$ red edges. The
path $\pi$ is called $(x,G)$-maximal if it achieves the maximum in
$\max_{\pi\in\Pi_{0,n}}(N_{G}(\pi)+x\overline{N}_{G}(\pi))$.

Showing that $x\in X_{\text{\rm crit}}$ one proceeds by constructing a
$G\in\mathfrak{H}_{n}$ possessing at least two $(x,G)$-maximal paths with
different number of red edges. Figure 8 summarizes how this is done for each
element $x$ of $\mathbb{Y}$, except $x=2,3,\ldots$, since if we know that
$1/k\in\mathbb{X}_{\text{\rm crit}}$ ($k=2,3,\ldots$) then we also know that
$k\in\mathbb{X}_{\text{\rm crit}}$ by the scaling property. For example,
Figure 8(a) shows that $0\in\mathbb{X}_{\text{\rm crit}}$. Indeed, consider
the paths $\pi_{1}=(0,1,3)$ and $\pi_{2}=(0,1,2,3)$. They both have weight $2$
(which is maximal), however, the first has no red edges but the second has one
red edge. This means that $0$ satisfies the definition of criticality.

$\bullet$0$\bullet$1$\bullet$2$\bullet$3 (a) Each red edge (i.e. each non-
edge) has charge $0$. This graph shows that $0\in\mathbb{X}_{\text{\rm
crit}}$.

$\bullet$0$\bullet$1$\bullet$$k$$\bullet$$k+1$$\bullet$$\bullet$$\bullet$ (b)
Let $k\in\\{2,3,\ldots\\}$. Each non-edge has charge $1/k$. This graph shows
that $1/k\in\mathbb{X}_{\text{\rm crit}}$.

$\bullet$0$\bullet$1$\bullet$$\ell+1$$\bullet$$\ell+1$$\bullet$$k+1$$\bullet$$k+2$$\bullet$$\bullet$$\bullet$$\bullet$
(c) Let $-\ell\in\\{-1,-2,\ldots\\}$. Each non-edge has charge $-1/\ell$. This
graph shows that $-\ell\in\mathbb{X}_{\text{\rm crit}}$.

0$a_{0}$$a_{1}$$a_{t-1}$$a_{t}$$n$0$n$0$n$0$n$ (d) Let $x<0$, rational, but
not an integer. Each non-edge has charge $x$. Write $x=-\ell+(s/t)$,
$\ell,s,t\in\mathbb{N}$, $t>1$, $\gcd(s,t)=1$, $s<t$.

Figure 8: Graphs exhibiting that $\mathbb{Y}\subset\mathbb{X}_{\text{\rm
crit}}$.

The most complex case is that of the last line of Figure 8. We explain the
construction of the graph.

We first need the following number-theoretic lemma that can be thought of as
placing $n$ balls in $N$ bins “as uniformly as possible”. Let $\lfloor
x\rfloor$, $\lceil x\rceil$ be the upper, lower, respectively, parts of $x$.

######  Lemma 9.8 (Corollary to Sturm’s lemma [72]).

Let $N,n$ be positive integers, $N\geq n$. Then there exists a unique finite
sequence $v=(v_{1},\ldots,v_{N})$ of elements of $\\{0,1\\}$ such that, for
all $0\leq i<j\leq N$, the following hold:

$\displaystyle\sum_{i<k\leq
j}v_{k}\in\bigg{\\{}\bigg{\lfloor}(j-i)\frac{n}{N}\bigg{\rfloor},\,\bigg{\lceil}(j-i)\frac{n}{N}\bigg{\rceil}\bigg{\\}},\quad\sum_{i<k\leq
N}v_{k}=\bigg{\lfloor}(N-i)\frac{n}{N}\bigg{\rfloor},\quad v_{1}=1.$

We say that the sequence $(v_{1},\ldots,v_{N})$ defined through this lemma is
the $(N,n)$–balanced sequence. For example, with $N=7$ $n=4$ we find
$(v_{1},\ldots,v_{7})=(1,1,0,1,0,1,0)$

Next, given $x<0$, $x\in\mathbb{Q}^{*}$, write

$x=-\ell+\frac{s}{t},$

uniquely, where $\ell,s,t$ are positive integers, $t>1$, $\gcd(s,t)=1$, $s<t$,
and let $(v_{1},\ldots,v_{t})$ be the $(t,t-s)$–balanced sequence. Construct a
graph $G$ on $[0,n=3m]$ where

$\displaystyle m$ $\displaystyle:=t(\ell+3)-(s+1),$

by letting the first and last parts consist of edges joining consecutive
integers and making the middle part as shown in the figure. The vetices
$a_{0},\ldots,a_{t}$ are defined by

$\displaystyle a_{0}$ $\displaystyle:=m,$ $\displaystyle a_{1}$
$\displaystyle:=a_{0}+(\ell+1)+v_{1},$ $\displaystyle a_{j}$
$\displaystyle:=a_{j-1}+(\ell+2)+v_{j},\quad j=2,\ldots,t.$

Finally, $0$ is connected by an edge to some vertices as show in the figure
and some vertices are connected to $n$ directly. For example, with $x=-11/7$
we have $x=-2+(3/7)$, that is, $\ell=2$, $s=3$, $t=7$, $m=31$, $n=93$. The
$(7,4)$ balanced sequence is $(v_{1},\ldots,v_{7})=(1,1,0,1,0,1,0)$. We also
have $a_{0}=31$, $a_{1}-a_{0}=\ell+1+v_{1}=4$, $a_{2}-a_{1}=\ell+2+v_{2}=5$,
$a_{3}-a_{2}=4$, $a_{4}-a_{3}=5$, $a_{5}-a_{4}=4$, $a_{6}-a_{5}=5$,
$a_{7}-a_{6}=4$. That this graph belongs to $\mathfrak{H}_{n}$ is not obvious,
neither it is obvious that $x\in\mathbb{X}_{\text{\rm crit}}$. The details are
omitted.

###  9.5 $\mathbb{X}_{\text{\rm crit}}\subset\mathbb{Y}$

We will show that $\mathbb{Y}^{c}\subset\mathbb{X}_{\text{\rm crit}}^{c}$.
Note that all irrationals are elements of $\mathbb{Y}^{c}$.

First assume that $x\in\mathbb{Y}^{c}$ is irrational. Since, by Proposition
9.7, $\mathbb{X}_{\text{\rm crit}}=\mathbb{X}_{C}$, we show that
$x\in\mathbb{X}_{C}^{c}$.

The set of points at which $x\mapsto W^{x}_{\Gamma_{1},\Gamma_{2}}$ fails to
be differentiable is included in the set of points $x$ for which there are two
paths $\pi_{1},\pi_{2}$ from $\Gamma_{1}$ to $\Gamma_{2}$ such that
$w^{x}(\pi_{1})=w^{x}(\pi_{2})$ with
$\overline{N}(\pi_{1})\neq\overline{N}(\pi_{2})$. This implies that
$(\overline{N}(\pi_{2})-\overline{N}(\pi_{1}))x=N(\pi_{1})-N(\pi_{2})$, which
means that $x$ is rational. Hence $W^{x}_{\Gamma_{1},\Gamma_{2}}$ is
differentiable at rational points $x$ and, by the dominated convergence
theorem, the same is true for $C(p.x)$. We thus proved that if $x$ is
irrational then $x\in\mathbb{X}_{C}^{c}$.

Next let $x\in\mathbb{Y}^{c}$ but not irrational. Showing that
$x\in\mathbb{X}_{\text{\rm crit}}^{c}$ one proceeds by showing that for every
$n\geq 3$ and every $G\in\mathfrak{H}_{n}$ there is a unique $(x,G)$-maximal
path or that every $(x,G)$-maximal path has the same $\overline{N}_{G}(\pi)$
(=number of red edges).

If $x=1$ then every edge and every non-edge of a graph $G\in\mathfrak{G}_{n}$
has charge $1$. Hence the maximum length of all paths is $n$ and this is
achieved exactly one path, the path $(0,1,2,\ldots,n)$. So
$1\in\mathbb{X}_{\text{\rm crit}}^{c}$.

We know that negative rationals and the number $0$ are critical. So assume
that $x>0$. We know that $1$ is not critical. So assume that
$x\in(0,1)\cup(1,\infty)$. By the scaling property, we only need to consider
$x\in(0,1)$. Since $1/2,1/3,\ldots$ are critical, we assume that
$x\in(0,1)\setminus\\{1/2,1/3,\ldots\\}$.

######  Proposition 9.9.

Every $0<x<1$ that is not the reciprocal of an integer is not critical.

The proof of this is rather lengthy and relies on special properties of
maximal paths that can be found in Lemmas 4.5, 4.6, 4.7, 4.8, 4.9 and 4.10 of
[44].

To state them, we adopt some terminology. Call an edge short if its endpoints
are successive integers; otherwise, call it long. Say that edge $e=(i,j)$ is
nested in $e^{\prime}=(i^{\prime},j^{\prime})$ if $i^{\prime}\leq i<j\leq
j^{\prime}$ and $e\neq e^{\prime}$. Let $\pi,\pi^{\prime}\in\Pi_{0,n}$. We say
that the interval $[i,j]\subset[0,n]$ is $(\pi,\pi^{\prime})$-special if the
set of vertices $k\in[i,j]$ that belong to both $\pi$ and $\pi^{\prime}$
consists of $i$ and $j$ only.

######  Lemma 9.10.

If $0<x<2$ then every maximal path contains all short blue edges.

######  Lemma 9.11.

If $0<x<2$ then every long edge of a maximal path $\pi$ is blue ( in other
words, every red edge of $\pi$ must be short).

######  Lemma 9.12.

If $x>0$ then no blue edge of a maximal path can be nested in a different blue
edge of another maximal path.

######  Lemma 9.13.

Let $0<x<2$. Then for every pair $\pi,\pi^{\prime}\in\Pi_{0,n}$ of maximal
paths such that $\overline{N}_{G}(\pi)\neq\overline{N}_{G}(\pi^{\prime})$
there is a $(\pi,\pi^{\prime})$-special interval $I$ such that

$\overline{N}_{G}(\pi|_{I})\neq\overline{N}_{G}(\pi^{\prime}|_{I})$

and

$N_{G}(\pi|_{I})-N_{G}(\pi^{\prime}|_{I})\in\\{-1,1\\}.$

The proof of the lemmas are omitted, but we give the proof of Proposition 9.9:

###### Proof of Proposition 9.9.

We prove the contrapositive: if $0<x<1$ is critical then $x=1/m$ for some
integer $m$. So suppose that $x$ is critical and $0<x<1$. Then there is $n\geq
3$ and $G\in\mathfrak{H}_{n}$ (edges of $G$ are called blue and non-edges red)
and two maximal paths $\pi_{1}$, $\pi_{2}$ with different number of red edges:
$\overline{N}_{G}(\pi_{1})\neq\overline{N}_{G}(\pi_{2})$. By the Lemma 9.13,
there is a $(\pi_{1},\pi_{2})$-special interval $[i,j]$ such that
$N_{G}(\pi_{1}|_{I})-N_{G}(\pi_{2}|_{I})\in\\{1,-1\\}$. Since

$0=w^{x}_{G}(\pi_{1}|_{I})-w^{x}_{G}(\pi_{2}|_{I})=(\overline{N}_{G}(\pi_{1}|_{I})-\overline{N}_{G}(\pi_{2}|_{I}))x+(N_{G}(\pi_{1}|_{I})-N_{G}(\pi_{2}|_{I})),$

it follows that

$x=\frac{1}{|\overline{N}_{G}(\pi_{1}|{[i,j]})-\overline{N}_{G}(\pi_{2}|{[i,j]})|},$

and hence the reciprocal of a positive integer. ∎

######  Remark 9.14.

We considered here differentiability properties for a last passage percolation
problem. Differentiability properties of a first passage percolation model
were studied in [89].

##  10 Perfect simulation aspects of charged graphs

We now turn our attention to charged graphs with edge charge distribution $F$:
to every pair of $(i,j)$ of integers, with $i<j$, assign a charge $w_{i,j}$
with distribution $F$, independently. For a path
$\pi=(i_{0},\ldots,i_{\ell})$, that is, a finite increasing sequence of
integers, assign charge
$w(\pi)=w_{i_{0},i_{1}}+\cdots+w_{i_{\ell-1},i_{\ell}}$, and let

$W_{i,j}=\sup\\{w(\pi):\text{ $\pi$ is a path from $i$ to $j$}\\}.$ (10.1)

We use the notation $\overrightarrow{G}(\mathbb{Z},F)$ for this random charged
graph. Thus, $\overrightarrow{G}(\mathbb{Z},p\delta_{1}+(1-p)\delta_{x})$ is
another notation the graph dealt with in Section 9, while
$\overrightarrow{G}(\mathbb{Z},p\delta_{1}+(1-p)\delta_{-\infty})$ is another
notation for the Barak-Erdős graph $\overrightarrow{G}(\mathbb{Z},p)$.
Superadditivity inequality implies that there is a deterministic $C(F)$ such
that

$\frac{W_{0,n}}{n}\to C(F),\quad\text{ a.s. as }n\to\infty.$

In Section 9 we studied $C(p,x)\equiv C(p\delta_{1}+(1-p)\delta_{x})$ as a
function of $x$. To deal with $C(F)$ as a function of $F$ analytically is
beyond the scope of this survey. We will, however, explain how to approach
this problem from an algorithmic view point, one that allows to draw
conjectures by simulating the graph as accurately as possible.

As explained at the start of Section 9, we will assume that
$\operatorname{esssup}w_{i,j}>0$, else we are dealing with a first passage
percolation problem. We will also assume, for convenience, that this essential
supremum is finite so, without loss of generality, let

$\operatorname{esssup}w_{i,j}=\inf\\{z:F((z,\infty))=0\\}=1.$ (10.2)

See Remark 10.8 below that explains that the finiteness of
$\operatorname{esssup}w_{i,j}$ is not a problem insofar as the perfect
simulation is concerned. Comparing $F$ with the distribution
$p\delta_{1/2}+(1-p)\delta_{-\infty}$ with $p=F([1/2,1])$ we obtain that

$C(F)>0.$

The goal of this section is the construction of a random variable whose
expectation is $C(F)$ and such that this random variable can be perfectly
simulated. A survey of perfect simulation can be found in [61]. Its relation
to the so-called backwards-coupling was studied in [45]. It belongs to the
broader area of coupling methods for stochastic recursions that may entirely
lack the Markovian property [22, 30, 41].

To do this we discuss an auxiliary Markovian particle system, called Max
Growth System (MGS), that is an analog of the Infinite Bin Model. Our
reference throughout this section is [65].

###  10.1 The Max Growth System (MGS)

The content of this subsection is purely deterministic. Consider point
measures on the set $\mathbb{R}\cup\\{-\infty\\}$ that will be referred to as
“space”:

$\mathcal{N}:=\\{\text{all locally finite point measures on
}\mathbb{R}\cup\\{-\infty\\}\\}.$

For example,
$\nu=2\delta_{1}+\delta_{-1.5}+3\delta_{-4}+\delta_{-\infty}\in\mathcal{N}$.

We think of $\nu$ as consisting of $7$ particles, such that two of them are at
$1$, one at $-1.5$, three at $-4$ and one at $-\infty$; so we can equivalently
represent $\nu$ by the locations of its particles
$(1,1,-1.5,-4,-4,-4,-\infty)$ arranged in decreasing order. In general, we let
$\nu_{1}\geq\nu_{2}\geq\cdots$ be the locations of the particles of $\nu$. So
the function

$\mathcal{N}\ni\nu\mapsto\nu_{k}:=\text{ location of $k$th largest particle of
$\nu$}$

is well-defined for each $k$ and $\nu=\sum_{k\geq 1}\delta_{\nu_{k}}$.

We also let

$\|\nu\|:=\nu(\mathbb{R}\cup\\{-\infty\\}),\quad\inf\nu:=\nu_{\|\nu\|},$

with $\inf\nu=-\infty$ if $\|\nu\|=\infty$. Next let

$\mathcal{W}:=\big{\\{}w=(w_{1},w_{2},\ldots):\,\sup_{k\geq 1}w_{k}\leq
1,\;w_{k}\in\mathbb{R}\cup\\{-\infty\\}\text{ for all }k\big{\\}},$

and define

$\mathfrak{m}(\nu,w):=\sup_{k\geq 1}(\nu_{k}+w_{k}),\quad\nu\neq 0,\quad
w\in\mathcal{W}.$

The map responsible for the dynamics of the MGS is defined by

$\Psi_{w}\nu:=\nu+\delta_{\mathfrak{m}(\nu,w)}.$

Composing these maps, for possibly different $w$ each time, gives a trajectory
in $\mathcal{N}$. More precisely, the MGS starting at “time” $T$ from state
$\nu(T)\in\mathbb{N}$ and driving sequence $w(t)$, $t>T$, is the sequence
defined by

$\nu(t)=\Psi_{w(t)}\nu(t-1),\quad t>T,$

that is,

$\nu(t)=\Psi_{w(t)}\raisebox{0.43057pt}{\scriptsize$\circ$}\Psi_{w(t-1)}\raisebox{0.43057pt}{\scriptsize$\circ$}\cdots\raisebox{0.43057pt}{\scriptsize$\circ$}\Psi_{w(T+1)}\nu(T).$

Let $\mathcal{N}_{0}$ consist of those $\nu\in\mathcal{N}$ with $\nu_{1}=0$.
Define the map

$\sigma:\mathcal{N}\to\mathcal{N}_{0},\quad\sigma\nu=\sum_{k\geq
1}\delta_{\nu_{k}-\nu_{1}}$

that places the origin of space at $\nu_{1}$. We will need the following
easily verified properties.

$\displaystyle\sigma\Psi_{w}=\sigma\Psi_{w}\sigma,$
$\displaystyle\mathfrak{m}(\sigma\nu,w)=\mathfrak{m}(\nu,w)-\nu_{1}.$

We next consider an MGS $\nu(t)$, $t\geq 0$, and show that under certain
conditions on the driving sequence the quantity

$\mathfrak{M}(t)\equiv\mathfrak{m}(\nu(t-1),w(t))$

will eventually not depend on the choice of the initial state $\nu(0)$.

######  Lemma 10.1 (Decoupling property).

Fix $\ell\in[0,1)$. Consider two MGSs, $\nu$, $\tilde{\nu}$, starting at time
$0$ with $\nu(0)\in\mathcal{N}_{0}$ and $\tilde{\nu}(0)=\delta_{0}$. Assume
that the driving sequence $w(t)$, $t>0$, is the same for both. Let
$\mathfrak{M}(t)=\mathfrak{m}(\nu(t-1),w(t))$,
$\tilde{\mathfrak{M}}(t)=\mathfrak{m}(\nu(t-1),w(t))$. If

$\displaystyle\nu_{2}(0)$ $\displaystyle\leq-\ell,$ (10.3)
$\displaystyle\bar{w}(t)$
$\displaystyle:=\max\\{w_{1}(t),\ldots,w_{t}(t)\\}\geq 1-\ell\quad\text{ for
all $1\leq t\leq n$,}$ (10.4)

then

$\mathfrak{M}(t)=\tilde{\mathfrak{M}}(t)\quad\text{ for all $1\leq t\leq n$.}$
(10.5)

###### Proof.

We have $\nu_{1}(0)=0\geq-\ell\geq\nu_{2}(0)$, by assumption. We will show by
induction that, for all $n\in\mathbb{N}$,

$\text{if $\bar{w}(1),\ldots,\bar{w}(n)\geq 1-\ell$ }\text{ then
}\begin{cases}\mathfrak{M}(n)=\tilde{\mathfrak{M}}(n)\\\
\nu(n)|_{\mathbb{R}_{+}}=\tilde{\nu}(n)|_{\mathbb{R}_{+}}\\\
\nu(n)(\mathbb{R}_{+})=n+1\\\ \nu_{n+2}(n)\leq-\ell\end{cases}$ (10.6)

Let $n=1$ and assume that $\bar{w}(1)=w_{1}(1)\geq 1-\ell$. We have
$\mathfrak{M}(1)=\max\\{\nu_{1}(0)+w_{1}(1),\nu_{2}(0)+w_{2}(1),\ldots\\}=w_{1}(1)$
because $\nu_{1}(0)+w_{1}(1)=w_{1}(1)\geq 1-\ell$ and since $1\geq w_{j}(1)$,
$-\ell\geq\nu_{j}(0)$ for all $j\geq 2$, we have $w_{1}(1)\geq
w_{j}(1)+\nu_{j}(0)$ for all $j\geq 2$ and so only the first term survives in
the maximum. But then $\mathfrak{M}(1)=w_{1}(1)=\tilde{\mathfrak{M}}(1)$.
Since $\nu(1)=\nu(0)+\delta_{\mathfrak{M}(1)}$ we have that its restriction on
$\mathbb{R}_{+}$ equals $\delta_{0}+\delta_{w_{1}(1)}$ and
$\nu_{3}(1)=\nu_{2}(0)\leq-\ell$. So (10.6) holds when $n=1$.

Assume next (10.6) holds for some $n$. We show its veracity for $n+1$. Assume
that $\bar{w}(1),\ldots,\bar{w}(n),\bar{w}(n+1)\geq 1-\ell$. By (10.6) we have
$\nu(n)|_{\mathbb{R}_{+}}=\tilde{\nu}(n)|_{\mathbb{R}_{+}}$ (containing $n+1$
particles on $\mathbb{R}_{+}$) and $\nu_{n+1}(n-1)\leq-\ell$. So

$\displaystyle\mathfrak{M}(n+1)$ $\displaystyle=\max_{j\geq
1}\\{\nu_{j}(n)+w_{j}(n+1)\\}$ $\displaystyle=\max_{j\leq
n+1}\\{\nu_{j}(n)+w_{j}(n+1)\\}\vee\max_{j>n+1}\\{\nu_{j}(n)+w_{j}(n+1)\\}$
$\displaystyle=\max_{j\leq
n+1}\\{\tilde{\nu}_{j}(n)+w_{j}(n+1)\\}\vee\max_{j>n+1}\\{\nu_{j}(n)+w_{j}(n+1)\\}$
$\displaystyle=\max_{j\leq
n+1}\\{\tilde{\nu}_{j}(n)+w_{j}(n+1)\\}=\tilde{\mathfrak{M}}(n+1).$

The reason that we dropped the second maximum is that $\max_{j\leq
n+1}\\{\tilde{\nu}_{j}(n-1)+w_{j}(n)\\}\geq\max_{j\leq n+1}w_{j}(n)\geq
1-\ell$ while
$\max_{j>n+1}\\{\nu_{j}(n-1)+w_{j}(n)\\}\leq\nu_{n+1}(n-1)+\max_{j>n+1}w_{j}(n)\leq-\ell+1$.
We also have
$\nu(n+1)=\nu(n)+\delta_{\mathfrak{M}(n+1)}=\nu(n)+\delta_{\tilde{\mathfrak{M}}(n+1)}$
so $\nu(n+1)|_{\mathbb{R}_{+}}=\tilde{\nu}(n+1)|_{\mathbb{R}_{+}}$ and they
have $n+2$ particles on $\mathbb{R}_{+}$, while
$\nu_{n+3}(n+1)=\nu_{n+2}(n)\leq-\ell$.

∎

######  Remark 10.2.

Lemma 10.1 and the conclusion (10.5) can easily be modified if we need to
start the MGS from an arbitrary time $T$ rather than $T=0$. The quantity that
replaces $\overline{w}(t)$ will be

$\bar{w}(T;t):=\max\\{w_{1}(T+t),\ldots,w_{t}(T+t)\\}.$ (10.7)

This is needed in Theorem 10.6 below.

######  Remark 10.3.

The decoupling property is essentially responsible for producing, in a
stochastic version of the MGS, the so-called renovating events that constitute
a nice way for exhibiting stability. The original theory can be found in [19,
20, 21, 22, 23] and its extension for functional of stochastic dynamical
systems in [42].

###  10.2 The MGS of a random charged graph, coupling and stationarity

######  Definition 10.4.

Given a probability measure $Q$ on $\mathcal{W}$ define the random process
MGS$(Q)$ by $\nu(t)=\Psi_{w(t)}\nu(t-1)$, $t\geq 1$, with $w(1),w(2),\ldots$
being independent with common law $Q$, with $\nu(0)\in\mathcal{N}$ arbitrary.
Clearly, MGS$(Q)$ is Markovian. In the particular case where the components of
$w(1)$ are i.i.d. with common distribution $F$ we shall be using the notation
MGS$(Q_{F})$.

Let $\overrightarrow{G}(\mathbb{Z},F)$ be a random charged graph with charge
distribution $F$ satisfying (10.2). Let

$W_{n}:=W_{0,n},$

in the notation of (10.1). In particular, $W_{0}=0$, $W_{1}=w_{0,1}$,
$W_{2}=(w_{0,1}+w_{1,2})\vee w_{1,2}$. Let

$\nu^{G}(n):=\sum_{k=0}^{n}\delta_{W_{k}},\quad n\geq 0.$ (10.8)

Then $\nu^{G}(n)\in\mathcal{N}$ and has $n+1$ particles. Clearly,
$\nu^{G}(n)=\nu^{G}(n-1)+\delta_{W_{n}}$, with $W_{n}=\max_{0\leq k\leq
n-1}(W_{k}+w_{k,n})=\max_{k}(\nu^{G}_{k}(n-1)+w_{\pi(k),n})$ where $\pi$ is a
permutation on $\\{0,\ldots,n-1\\}$ that puts $W_{0},\ldots,W_{n-1}$ in
decreasing order.

Hence $W_{n}\overset{\mathrm{d}}{=}\max_{k}(\nu^{G}_{k}(n-1)+w_{k,n})$ and so
if we consider the MGS$(Q_{F})$ defined by

$\nu(n)=\nu(n-1)+\delta_{\mathfrak{m}(\nu(n-1),w(n))},$

starting with $\nu(0)=\delta_{0}$, we see that

$\nu^{G}\overset{\mathrm{d}}{=}\nu,$ (10.9)

not only component-wise, but also as processes.

Therefore, letting

$M_{n}=\max_{0\leq k\leq n}W_{k}$ (10.10)

we have

$(M_{n}-M_{n-1},n\geq
1)\overset{\mathrm{d}}{=}(\mathfrak{m}(\sigma\nu(n-1),w(n))^{+},n\geq 1),$

which implies that $M_{n}/n$ is a sample mean:

$\frac{M_{n}}{n}=\frac{1}{n}\sum_{j=1}^{n}(M_{j}-M_{j-1})\overset{\mathrm{d}}{=}\frac{1}{n}\sum_{j=1}^{n}\mathfrak{m}(\sigma\nu(j-1),w(j))^{+},$

where the last equality in distribution is at the level of sequences. Since

$C(F)=\lim_{n\to\infty}\frac{W_{n}}{n}=\lim_{n\to\infty}\frac{M_{n}}{n}\text{
a.s.},$

and since $\int_{0}^{\infty}xF(dx)<\infty$, we have

$C(F)=\lim_{n\to\infty}\frac{\mathbb{E}M_{n}}{n}=\lim_{n\to\infty}\frac{1}{n}\sum_{j=1}^{n}\mathbb{E}\mathfrak{m}(\sigma\nu(j-1),w(j))^{+}.$

######  Remark 10.5.

Let us make the reasonable ansatz that the quantity inside the last
expectation converges in distribution to some random variable:

$\mathfrak{m}(\sigma\nu(n-1),w(n))^{+}\xrightarrow{\text{\rm
d}}\bar{\mathfrak{m}}^{+}\text{ as }n\to\infty.$ (10.11)

Then a poor man’s estimate of $C(F)$ would be to simply to compute sample
means $n^{-1}\sum_{j=1}^{n}\mathbb{E}\mathfrak{m}(\sigma\nu(j-1),w(j))^{+}$
for large $n$. But the sample means are not from i.i.d. copies of the limiting
variable and thus the sampling is “not perfect”. To achieve perfect sampling,
we must first show that the non-Markovian process
$\mathfrak{m}(\sigma\nu(n-1),w(n))$, $n=1,2,\ldots$, has a stationary version
(we say that a process has a stationary version if it is eventually equal to a
stationary process; the “eventually” means that there is a finite random time
after which the two processes are equal a.s.) from which we can sample i.i.d.
copies constructively.

######  Theorem 10.6.

Suppose that $F$ satisfies (10.2). Let $\nu$ be an MGS$(Q_{F})$ with driving
sequence $w(t)$, $t\in\mathbb{Z}$, starting from an arbitrary state at an
arbitrary, possibly random, time. Then there exists a stationary process
$(\bar{\mathfrak{m}}(t),t\in\mathbb{Z})$ such that

$\mathfrak{m}(\sigma\nu(t-1),w(t))=\bar{\mathfrak{m}}(t)\text{ for $t$ large
enough, a.s.}$

In particular $\mathbb{E}(\bar{\mathfrak{m}}(0)^{+})=C(F)$.

###### Proof.

Let $\ell\in[0,1)$ be such that $p:=F([1-\ell,1])>0$, which is possible due to
(10.2). For $k\in\mathbb{Z}$, consider the event

$R_{k}:=\\{w_{1}(k)\geq\ell\\}\cap\bigcap\limits_{j=1}^{\infty}\big{\\{}\max(w_{1}(k+j),\ldots,w_{j}(k+j))\geq
1-\ell\big{\\}}.$

It is clear from its definition that $(R_{k},k\in\mathbb{Z})$ is a stationary
sequence of events with

$\mathbb{P}(R_{k})=\mathbb{P}(R_{0})=F([\ell,1])\prod_{j=1}^{\infty}(1-(1-p)^{j})>0.$

Consider the stationary random set $J:=\\{k\in\mathbb{Z}:R_{k}\text{
holds}\\}$. Since $\mathbb{P}(R_{k})>0$, we have, by ergodicity (more
specifically by the Poincaré recurrence theorem), $\inf J=-\infty$ and $\sup
J=\infty$ a.s. We enumerate the elements of $J$ by

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

Hence the $R_{T_{i}}$ are all events of probability $1$. We define
$\tilde{\nu}(t)$, $t\in\mathbb{R}$, by letting, for all $j$,

$\tilde{\nu}(T_{j})=\delta_{0},\qquad\tilde{\nu}(t)=\sigma\sum_{i\in\mathbb{Z}}\mathbbm{1}_{\\{T_{i}<t<T_{i+1}\\}}\Psi^{t}_{w(t)}\raisebox{0.43057pt}{\scriptsize$\circ$}\cdots\raisebox{0.43057pt}{\scriptsize$\circ$}\Psi^{T_{i}+1}_{w(T_{i}+1)}\delta_{0},\quad
t\not=T_{j}.$

On the other hand, thanks to Lemma 10.1, the process
$\mathfrak{m}(\sigma\nu(t-1),w(t))$, $t>T_{i}$, is algebraically independent
of $\nu(T_{i})$. This shows, see [41], that the stationary process $\bar{m}$
defined by

$\bar{\mathfrak{m}}(t)=\mathfrak{m}(\sigma\tilde{\nu}(t-1),w(t)),\quad
t\in\mathbb{Z},$

satisfies $\bar{\mathfrak{m}}(t)=\mathfrak{m}(\sigma\nu(t-1),w(t))$ for all
$t$ large enough, a.s.

Next, using that

$C(F)=\lim_{n\to\infty}\frac{\mathbb{E}(M_{n})}{n}=\lim_{n\to\infty}\frac{1}{n}\sum_{j=1}^{n}\mathbb{E}(\mathfrak{m}(\sigma\nu(j-1),w(j))^{+})\quad\text{a.s.},$

and using the eventual equality between $\mathfrak{m}(\sigma\nu(t-1),w(t))$
and $\bar{\mathfrak{m}}(t)$, we have

$C(F)=\lim_{n\to\infty}\frac{1}{n}\sum_{j=1}^{n}\mathbb{E}(\bar{\mathfrak{m}}(j)^{+})=\mathbb{E}(\bar{\mathfrak{m}}(0)^{+}),$

by stationarity and ergodicity of the sequence. ∎

###  10.3 Perfect simulation

Recall the quantity $\overline{w}$ defined by (10.7).

######  Theorem 10.7 (Perfect simulation).

Define

$T^{*}:=\sup\\{t\leq-1:\,{w}_{1}(t)\geq\ell,\min_{1\leq
j\leq|t|}\overline{w}(t;j)\geq 1-\ell\\}.$

Then $|T^{*}|<\infty$ a.s., and

$\bar{\mathfrak{m}}(0)=\mathfrak{m}\left(\sigma\Psi^{T^{*}+1}_{w(T^{*}+1})\raisebox{0.43057pt}{\scriptsize$\circ$}\cdots\raisebox{0.43057pt}{\scriptsize$\circ$}\Psi^{0}_{w(0)}\delta_{0};w(0)\right)\text{
a.s.}$

###### Proof.

We recall that $(T_{-j},j\in\mathbb{N})$ are the negative elements of the
random set $J$, with $T_{-1}>-\infty$. We remark that

$w_{1}(T_{-1})\geq\ell,\quad\bar{w}(T_{-1};j)\geq 1-\ell\text{ for all
$j>0$},$

therefore $T_{*}\geq T_{-1}$, proving its finiteness.

Moreover, since

$w_{1}(T^{*})\geq\ell,\min_{1\leq j\leq|t|}\bar{w}(T^{*};j)\geq 1-\ell,$

by Corollary 10.1, the quantity
$\mathfrak{m}\left(\sigma\Psi^{T^{*}+1}_{w(T^{*}+1})\raisebox{0.43057pt}{\scriptsize$\circ$}\cdots\raisebox{0.43057pt}{\scriptsize$\circ$}\Psi^{0}_{w(0)}\nu;w(0)\right)$
does not algebraically depend on the value of $\nu\in\mathcal{N}_{0}$. As a
result, it is equal to $\bar{\mathfrak{m}}(0)$.

∎

Fix $t=0$ and $J=1$;

Generate the variable $w_{1}(0)$;

Fix Stopping = False;

while  _Stopping = False_ do