1. Introduction
In this work, we study the scaling limit of the genealogical structure of a slightly supercritical Galton–Watson forest by showing convergence of its height process under rescaling. The height process is defined using a depth-first exploration of the forest. Consequently, it encodes only a part of a supercritical Galton–Watson forest: a walker that executes a depth-first exploration will never cross the first path to infinity that it encounters. We show that our convergence result can nevertheless be applied, by using it to establish metric space convergence of the configuration model in the critical window. Moreover, our result shows that the height process for supercritical continuous-state branching processes (CSBPs) that was defined by Lambert in [Reference Lambert41] is in fact the limit under rescaling of its discrete counterpart.
We will briefly introduce the encoding of a (random) forest by a Łukasiewicz path and a height process in the discrete setting. Furthermore, we will introduce the Łukasiewicz path and height process in the continuous setting. We then state our results and methods, after which we provide an overview of related work.
1.1. Encoding forests by processes
The encoding of random trees and forests in the discrete setting and the continuum by (excursions of) random processes has been around for a long time; see e.g. [Reference Aldous5, Reference Duquesne and Le Gall24, Reference Duquesne and Winkel25, Reference Dwass28, Reference Le Gall and Le Jan43, Reference Neveu, Pitman, Azéma, Yor, Meyer and Springer48, Reference Rogers, Azéma, Yor and Springer50].
Let T be an ordered rooted finite tree, say $|T|=n$ . Let $v_0,\dots,v_{n-1}$ denote the vertices of the tree visited in depth-first order, so that $v_0$ is the root of the tree. We will define the height function and Łukasiewicz path of T. Both of these functions uniquely characterize T. The height process of T, referred to as h, is defined as
i.e. for all i, h(i) equals the distance from $v_i$ to the root. Moreover, for all $i\in\{1,\dots,n\}$ , let $y_i$ be the number of children of $v_{i-1}$ , and set $y_0=1$ . Then the Łukasiewicz path of T is defined by
for $i=0,\dots,n$ . Thus, x(i) is the total number of younger siblings of $v_i$ and its ancestors, where younger means that they are explored later in the depth-first search. Note that
which is proved by Le Gall in [Reference Le Gall42]. These encodings of trees by walks can easily be extended to ordered forests by concatenating the Łukasiewicz paths and height processes.
We can use the correspondence between forests and their Łukasiewicz paths to construct Galton–Watson forests from random walks. Suppose $(D_1,D_2,\dots)$ are independent and identically distributed (i.i.d.) random variables with law $\pi$ on ${\mathbb N}=\{0,1,2\dots\}$ . Then
is the Łukasiewicz path of a random forest in which all vertices have independent offspring with law $\pi$ . We refer to such a forest as a $\pi$ -Galton–Watson forest ( $\operatorname{GW}(\pi)$ ). We will write $(H(k),k\geq 0)$ to denote the height process corresponding to $(S(k),k\geq 0)$ .
The continuous counterpart of the Galton–Watson process is a continuous-state branching process (CSBP) (see e.g. [Reference Grey30]). The rôle of the Łukasiewicz path is played by a Lévy process $(L_t,t\geq 0)$ without negative jumps (i.e. a spectrally positive Lévy process). The law of L is completely characterized by its Laplace exponent $\phi$ , defined via
Then, for $\zeta_L=\inf\{t> 0\,{:}\, L_t\leq 0\}$ ,
and $\varphi^{-1}\,{:}\,(0,\varphi(\zeta_L))\to {\mathbb R}$ , the inverse of $\varphi$ , the CSBP with branching mechanism $\phi$ , which we refer to as $\operatorname{CSBP}(\phi)$ , can be defined as
We wish to define the height process corresponding to $(L_t,t\geq 0)$ (which encodes the genealogy of the CSBP corresponding to the consecutive excursions of $(L_t,t\geq 0)$ above its infimum) analogously to (1), so we should define a functional $H(L)=(H_t,t\geq 0)$ of L such that $H_t$ in some sense measures the ‘size’ of the set $\{s\leq t\,{:}\,L_{s-}=\inf\{L_r\,{:}\,r\in[s,t]\}\}$ . In [Reference Le Gall and Le Jan43], it was established that if L almost surely does not drift to $\infty$ and satisfies
then there exists a continuous process $(H_t,t\geq 0)$ such that
with the limit in probability for all $t\in[0,\infty)$ . Further results were proved in [Reference Duquesne and Le Gall24]. The excursions of $(H_t,t\geq 0)$ above 0 encode metric spaces called Lévy trees, which are defined in [Reference Duquesne and Le Gall23]. In [Reference Lambert41], the definition of H(L) was extended to spectrally positive Lévy processes L that drift to $\infty$ almost surely.
1.2. Results and methods
For each n, let $D_1^n,D_1^2,\dots$ be an i.i.d. sequence of random variables with law $\pi_n$ , and set
Let $(H^n(k),k\geq 0)$ be the corresponding height process as defined in Section 1.1. We impose the following conditions:
-
(C1) There exist a nondecreasing sequence of positive integers $(\gamma_n,n\geq 1)$ that converges to $\infty$ and a Lévy process $(L_t,t\geq 0)$ on ${\mathbb R}$ that does not have downward jumps and is of infinite variation, such that
(2) \begin{equation}\left(n^{-1}S^n_{\lfloor n \gamma_n t \rfloor}, t\geq 0\right) \overset{d}{\to}(L_t,t\geq 0)\end{equation}in ${\mathbb D}({\mathbb R}_+,{\mathbb R})$ as $n\to\infty$ . -
(C2) For $Y^n_m$ , the number of vertices at height m in the first n trees of the forest encoded by $(S^n(k),k\geq 0)$ , for every $\delta>0$ , we have
(3) \begin{equation}\liminf\limits_{n\to\infty}{\mathbb P}\left[Y^n_{\lfloor \delta \gamma_n\rfloor}=0\right]>0.\end{equation}
The following result is proved in [Reference Duquesne and Le Gall24].
Theorem 1. ([Theorem 1.4.3 and Theorem 2.2.1].) Suppose Conditions (C1) and (C2) hold, and in addition the following hold:
-
(C3*) The Laplace exponent $\phi(\theta)$ of $(L_t, t\geq 0)$ satisfies
\begin{equation*}\int_1^\infty \frac{du}{\phi(u)}<\infty.\end{equation*} -
(C4*) Almost surely, $L_t$ does not drift to $\infty$ as $t\to\infty$ .
-
(C5*) We have ${\mathbb E}[D^n_1]\leq 1$ for all n.
Then there exists a continuous modification of the height process of $(L_t,t\geq 0)$ , say (Ht, t ≥ 0) such that
as $n\to \infty$ , jointly with (2).
Our main result is the analogue of Theorem 1 for supercritical Galton–Watson processes.
Theorem 2. Suppose Conditions (C1) and (C2) hold, and in addition the following hold:
-
(C3) For $\phi(\theta)$ the Laplace exponent of $(L_t, t\geq 0)$ and $\xi>0$ the unique value such that $\phi(\xi)=0$ , we have
\begin{equation*}\int_1^\infty \frac{du}{\phi(u+\xi)}<\infty.\end{equation*} -
(C4) We have $L_t\to \infty$ almost surely as $t\to\infty$ .
-
(C5) We have ${\mathbb E}[D^n_1]>1$ for all n.
Then there exists a continuous modification of the height process of $(L_t,t\geq 0)$ , say (Ht, t ≥ 0), such that
as $n\to \infty$ , jointly with (2).
Roughly speaking, Condition (C2) ensures that the maximal height in a forest of a number n of $\operatorname{GW}(\pi_n)$ trees, rescaled by $\gamma_n^{-1}$ , may not exceed $\delta$ . An analogous fact holds for $\operatorname{CSBP}(\phi)$ . Informally, Condition (C3) ensures that a Lévy tree encoded by an excursion of $L_t$ above its infimum, conditional on the excursion being finite, has finite height almost surely. This is a necessary condition for a continuous modification of the height process to exist. Finally, Conditions (C4) and (C5) ensure that $\operatorname{GW}(\pi_n)$ and $\operatorname{CSBP}(\phi)$ respectively are supercritical.
Our method is based on the following pathwise construction of $(S^n(k),H^n(k), k\geq 0)$ :
-
1. Up to the first time that it hits its overall infimum, $(S^n(k),k\geq 0)$ encodes a random number of finite trees, which are independent and each have the law of a tree in $\operatorname{GW}(\pi_n)$ conditioned to be finite. This yields a pathwise construction of $(S^n(k),H^n(k), k\geq 0)$ up to the first time that $(S^n(k),k\geq 0)$ hits its overall infimum.
-
2. After the first time that it hits its overall infimum, $(S^n(k),k\geq 0)$ encodes an infinite spine with trees attached to the left of the infinite spine, and vertices attached to the right of the infinite spine. To be precise, for every vertex v on the infinite spine, a random number of independent copies of a tree in $\operatorname{GW}(\pi_n)$ conditioned to be finite are attached to v left of the infinite spine, and a random number of vertices (that will never be visited) are attached to the right of the infinite spine. This yields a pathwise construction of $(S^n(k),H^n(k), k\geq 0)$ after the first time that $(S^n(k),k\geq 0)$ hits its overall infimum. This construction is similar to the pathwise construction for Galton–Watson processes with immigration defined in [Reference Duquesne and Winkel25].
(See e.g. [Reference Janson36], [Reference Lyons and Peres44, Section 5.7], and [Reference Athreya and Ney6, Chapter I.12] for the laws of the trees encoded by $(S^n(k), k\geq 0)$ before and after it hits its overall infimum, although height processes are not considered in these works.)
We define a similar pathwise construction of $(L_t,H_t,t\geq 0)$ , which is standard for the pre-infimum process (see e.g. [Reference Bertoin10, Chapter VII]), and based on [Reference Lambert41, Section 5] for the post-infimum process. We then show convergence in distribution under rescaling of the pathwise construction of $(S^n(k),H^n(k), k\geq 0)$ to the pathwise construction of $(L_t,H_t,t\geq 0)$ .
Finally, in Section 4 we use Theorem 2 to show metric space convergence of the largest components of a uniform graph with an i.i.d. heavy-tailed degree sequence in the critical window, which extends the main result of [Reference Conchon-Kerjan and Goldschmidt17]. For a precise statement of this result, and an overview of earlier work on related graph models, we refer the reader to Section 4.
1.3. Related work
While there is an extensive literature concerning the convergence of height processes for critical branching processes, we are only aware of two works that consider the supercritical case: [Reference Broutin, Duquesne and Wang14, Reference Duquesne22]. In [Reference Broutin, Duquesne and Wang14, Theorem B2], Broutin, Duquesne, and Wang discuss convergence of the height process of a model similar to the model we consider here. However, in that work, the authors only consider the forest before the first infinite line of descent. In [Reference Duquesne22], Duquesne studies a class of supercritical branching processes with a single infinite line of descent (sin-trees). The author encodes the resulting trees with two processes, one that encodes the genealogical structure on the left, and one that encodes the genealogical structure on the right side of the infinite line of descent. For this model, convergence under rescaling of the discrete contour processes to the continuum height process is proved. The pathwise construction that we use resembles the pathwise construction used in [Reference Duquesne22].
In [Reference Duquesne and Winkel26], convergence of supercritical Galton–Watson trees under rescaling is studied through a different lens. In Theorem 4.15 of that work, Duquesne and Winkel show the convergence of a class of supercritical Galton–Watson forests to a Lévy forest in the sense of Gromov–Hausdorff convergence on locally compact rooted real trees. Although their theorem applies to the entire forest, and not just to the trees and pendant subtrees to the left of the first infinite line of descent, convergence in the Gromov–Hausdorff topology on locally compact rooted real trees does not imply convergence of ‘depth-first ordering’ of the vertices in the tree, as convergence of the height process does.
An alternative approach to viewing the height process of a supercritical branching process is introduced in [Reference Delmas18] for branching processes with a quadratic branching mechanism, and extended to general CSBPs in [Reference Abraham and Delmas1]. The approach is to build the super-critical tree up to a given level a, such that the tree can be encoded by a height process. Then, the law of the resulting tree is absolutely continuous with respect to the law of a (sub-)critical Lévy tree whose branches above level a are removed, which is referred to as pruning. Furthermore, this family of processes indexed by a satisfies a consistency property, and hence there exists a projective limit. It is established in [Reference Abraham, Delmas and He2] that the limit object has the same law as the supercritical Lévy tree defined in [Reference Duquesne and Winkel25]. In [Reference He and Luan32], He and Luan define an analogous pruning operation for supercritical Galton–Watson trees and prove that the contour functions of these truncated Galton–Watson trees converge weakly to the processes constructed by Abraham and Delmas in [Reference Abraham and Delmas1].
2. The construction of the height process
In this section, we will combine results from the literature in order to give a construction of the height process of a supercritical Galton–Watson process in the discrete case, and of a supercritical CSBP in the continuum.
2.1. The height process in the discrete case
In this section, we describe a pathwise construction of the height process corresponding to $S^n$ . We do this by considering separately the process before and after it hits its overall infimum. This corresponds to considering the laws of finite and infinite trees in a supercritical branching process separately; this idea can be traced back to Harris [Reference Harris31]. In the descriptions of the two parts, we will make use of a process that is locally absolutely continuous to $S^n$ , which we will denote by $\hat{S}^n$ . We will refer to to $\hat{S}^n$ as ‘ $S^n$ conditioned to die out’. This formalizes, in the random walk framework, the well-known fact that a supercritical Galton–Watson process conditioned to die out is a subcritical Galton–Watson process.
For $t\geq 0$ , define
and set $\phi_n(\theta)=\log {\mathcal L}_{S^n(1)}(\theta)$ . Since ${\mathbb E}[S^n(1)]>0$ , we have ${\mathcal L}_{S^n(1)}'(0)<0$ , so by the convexity of ${\mathcal L}_{S^n(1)}(\theta)$ and the fact that ${\mathcal L}_{S^n(1)}(0)=1$ , there is a unique $\xi_n>0$ such that ${\mathcal L}_{S^n(1)}(\xi_n)=1$ and $\phi_n(\xi_n)=0$ . Let ${\mathbb P}_n$ be the law of $S^n$ , and let
be the natural filtration of $S^n$ . Let ${\mathbb P}_n^\#$ be locally absolutely continuous with respect to ${\mathbb P}_n$ , with
and let $\hat{S}^n$ be a process which under ${\mathbb P}_n$ has the law of $S^n$ under ${\mathbb P}_n^\#$ . Let
so that $\{\tau^n(m)<\infty\}$ may be interpreted as the event that at least m trees in the Galton–Watson forest are finite. The following properties of $\xi_n$ and $\hat{S}^n$ are standard (see e.g. [Reference Athreya and Ney6, Chapter I.12]).
Theorem 3. The following hold:
-
1. For any $m\geq 0$ ,
\begin{align*} \exp\!({-}\,\xi_n m)&={\mathbb P}_n\left[\tau^n(m)<\infty \right]. \end{align*} -
2. If $\Lambda\in {\mathcal F}_{\tau^n(m)}^n$ for some $m>0$ , then
\begin{align*} {\mathbb P}^\#_n[\Lambda]={\mathbb P}_n\left[\Lambda|\tau^n(m)<\infty\right]. \end{align*} -
3. The process $\hat{S}^n$ is a downward skip-free random walk on the integers.
The following lemma is a first reason why $\hat{S}^n$ plays an important rôle in the pathwise construction of $S^n$ .
Lemma 1. Let $G^n$ be a geometric random variable with success probability equal to $1-\exp\!({-}\,\xi_n)$ , i.e. ${\mathbb P}_n(G^n=k)=\exp\!({-}\,k\xi_n)(1-\exp\!({-}\,\xi_n))$ , independent of $\hat{S}^n$ . Then the pre-infimum process of $S^n$ has the law of $\hat{S}^n$ , stopped at the first time it reaches level $G^n$ .
Proof. Note that the negative of the overall infimum of $S^n$ , which we denote by $-I^{n}_{\infty}$ , equals the number of finite trees in the forest defined by $S^n$ viewed as a Łukasiewicz path. Hence, it is distributed as a geometric random variable with parameter $\exp\!({-}\,\xi_{n})$ . Let $\rho^n$ denote the time when $S^n$ first reaches $I^{n}_{\infty}$ . We have that
has the same distribution as
which, by Theorem 3, is equal in distribution to
Combining this with the distribution of $I^{n}_{\infty}$ , we find that for $G_n$ a random variable with the geometric distribution with success probability $\exp\!({-}\,\xi_n)$ independent of $S^n$ , $(S^n(j)\,{:}\,0\leq j \leq \rho^{n})$ under ${\mathbb P}_{n}$ has the same distribution as $(\hat{S}^{n}(j)\,{:}\,0\leq j \leq \tau^n(G^n))$ under ${\mathbb P}_{n}^\#$ .
By Theorem 3, $\hat{S}^n$ is the Łukasiewicz path of a subcritical Galton–Watson forest. We let $\hat{H}^n$ be its height process as defined in (1), i.e.
Then Lemma 1 has the following corollary.
Corollary 1. We have that
We will now characterize the post-infimum process and its height process. Let ${\mathbb P}_n^\uparrow$ be the law of $(S^n(k),k\geq 0)$ conditioned to be non-negative for all k. Note that we are conditioning on an event of non-zero probability because $S^n$ is supercritical, so this is well-defined.
The following lemma suggests an adaptation of $S^n$ that has the same height process, and that turns out to be easier to work with.
Lemma 2. For a discrete Łukasiewicz path $(X_k,k\geq 0)$ , set $\underline{\underline{X}}_n=\min\{X_m, m\geq n\}$ . We will refer to $\underline{\underline{X}}_n$ as the future infimum process. Then, the height processes of X and $X-\underline{\underline{X}}$ are the same.
Proof. Let $H^*$ denote the height process of $X-\underline{\underline{X}}$ . Then, by definition,
Set $\underline{\underline{g}}(n)=\max\{ m < n \,{:}\,X_m=\underline{\underline{X}}_m\}$ . Then, for $m\leq \underline{\underline{g}}(n)$ , we have that $\underline{\underline{X}}_m=\min\{ X_j\,{:}\,m\leq j \leq n\}$ and $\min\{X_j-\underline{\underline{X}}_j , m\leq j \leq n \}=0$ . Also, for $m>\underline{\underline{g}}(n)$ , we have $\underline{\underline{X}}_m=\underline{\underline{X}}_n.$ Hence, indeed,
where $H_n$ is the height process of $X_n$ .
Note that since $S^n$ drifts to $+\infty$ almost surely, $S^n-\underline{\underline{S}}^{n}$ under ${\mathbb P}^\uparrow_{n}$ is recurrent in zero. Indeed, if $S^n$ drifts to $+\infty$ , we have $\underline{\underline{S}}^{n}(k)>-\infty$ for all $k>0$ . Then, by the definition of $\underline{\underline{S}}^{n}$ , there is a finite $l>k$ such that $S^n(l)=\underline{\underline{S}}^{n}(l)$ . Moreover, $S^n-\underline{\underline{S}}^{n}$ is non-negative. Combining these facts implies that $S^n-\underline{\underline{S}}^{n}$ is the Łukasiewicz path of an infinite spine with finite trees attached to it only on the left-hand side. $S^n$ describes the same infinite spine with trees on its left-hand side, but also contains information on the total number of children (including children to the right of the spine) of vertices on the spine. See Figure 1. We will use this description to study the distributions of these paths.
Using terminology introduced by Janson in [Reference Janson36], we will call a vertex immortal if it is the root of an infinite tree. Otherwise we will call it mortal. Note that since $S^n$ drifts to $+\infty$ almost surely, every vertex has a positive probability of being immortal. Hence there are almost surely countably infinitely many infinite spines. Note that in every generation, we only visit the vertices to the left of the leftmost immortal vertex. This means that, under ${\mathbb P}^\uparrow_{n}$ , an excursion of $S^n-\underline{\underline{S}}^{n}$ above 0 consists of an increment (of size, say, $B^{(n)}$ ) corresponding to the mortal older brothers of the first immortal vertex, and then an excursion with the law of $S^n$ starting at $B^{(n)}$ conditioned to hit 0 in finite time. This corresponds to sampling first the number of trees to the left of the infinite spine and then the shapes of those trees.
The sample paths of $S^n$ can be constructed from the sample paths of $S^n-\underline{\underline{S}}^{n}$ , by adding the randomness that encodes the number of younger brothers of vertices on the leftmost path to infinity. This corresponds to replacing the jumps of size $B^{(n)}$ by jumps of size $N^{(n)}-1$ , with $N^{(n)}$ being distributed as the total generation size given $B^{(n)}$ . This is illustrated in Figure 1. (A similar decomposition of Galton–Watson trees conditioned on non-extinction is discussed by Lyons and Peres in Section 5.7 of [Reference Lyons and Peres44], where they do not introduce the encoding by a Łukasiewicz path and height process.)
Note that the height at time k in the tree encoded by $S^n$ under ${\mathbb P}^\uparrow_n$ is given by the height of the position along the infinite spine where the finite subtree containing the vertex visited at time k is attached plus the height of the vertex in the finite subtree.
We will now investigate the joint distribution of $N^{(n)}$ and $B^{(n)}$ .
Lemma 3. Let $N^{(n)}$ be the number of children in a set of offspring conditioned to contain at least one immortal vertex, let $B^{(n)}$ be the number of older brothers of the oldest immortal vertex in such a set of offspring, and let $\exp\!({-}\,\xi_n)$ be the probability that, under ${\mathbb P}_{n}$ , a tree dies out. Then for $l>k$ we have
Proof. Let $\psi_n$ denote the probability generating function of the offspring distribution under ${\mathbb P}_{n}$ (i.e. the law of $Z^n_1$ under ${\mathbb P}_{n}$ ). Let $M_n$ be the random variable representing the number of mortal children of an immortal parent, and let $J_n$ be the random variable representing the number of immortal children of an immortal parent. Then, in [Reference Janson36], Janson gives the generating function of the joint law of $M_n$ and $J_n$ as
Also, given the number of mortal and immortal children, they appear in a uniformly random order. It is then straightforward that the generating function of the total number of children of an immortal parent is given by
so we obtain that for $k=1,2,\dots$ ,
Using (5) to analyze the generating function of the joint law of $N^{(n)}$ and $J_n$ , we see that, conditional on the value of $N^{(n)}$ , $J_n$ is distributed as a binomial random variable with parameters $N^{(n)}$ and $1-\exp\!({-}\,\xi_n)$ conditioned to be at least 1. Since the mortal and immortal children appear in a uniform order, conditional on the generation size $N^{(n)}$ , the number of mortal older brothers of the first immortal vertex, $B^{(n)}$ , is distributed as a geometric random variable with success parameter $\exp\!({-}\,\xi_n)$ conditioned to be at most $N^{(n)}-1$ . We obtain that
which proves the statement.
These findings on the post-infimum process can be summarized as follows.
Proposition 1. The sample paths of $S^n$ and $S^n-\underline{\underline{S}}^n$ under ${\mathbb P}^\uparrow_n$ can be constructed by concatenating excursions above the future infimum as follows. Sample a countably infinite number of independent copies of $B^{(n)}$ and $N^{(n)}$ according to
Start an excursion with an increment of size $N^{(n)}-1$ above the previous future infimum, and continue from there as a process with law ${\mathbb P}^\#_n$ . Kill the excursion at $N^{(n)}-B^{(n)}-1$ above the previous future infimum, which will be the new future infimum.
By replacing the jumps of size $N^{(n)}-1$ by jumps of size $B^{(n)}$ we obtain $S^n-\underline{\underline{S}}^{n}$ .
2.1.1. A pathwise construction.
The characterization of the pre- and post-infimum processes justifies the following pathwise construction of $(S^n,S^n-\underline{\underline{S}}^n, H^n)$ under ${\mathbb P}_n$ . This is similar to the pathwise construction of the encoding processes of a Galton–Watson process with immigration given in Section 2.2 of [Reference Duquesne22].
See Figure 2 for a graphical representation of the construction.
-
Let $\hat{S}^n(k)$ be a random walk with law ${\mathbb P}^\#_n$ , and let $\hat{H}^n(k)$ be the corresponding height process. Set $\hat{I}^n(k)=\min_{m\leq k} \hat{S}^n(k)$ . The trees encoded by $\hat{S}^n(k)$ will be used as the finite trees that are explored before the first infinite tree is encountered, and as the finite subtrees to the left of the leftmost infinite spine which are rooted at the vertices on the infinite spine.
-
Let $G^n$ be distributed as a geometric random variable with mean $\exp\!({-}\,\xi_n)$ , which gives the number of finite trees explored by the process. We then let $(B^{(n)}_1,N^{(n)}_1)$ , $(B_2^{(n)},N^{(n)}_2),\dots$ be i.i.d. pairs of random variables, independent of $\hat{S}^n$ , distributed as $(B^{(n)},N^{(n)})$ . Set $Q^n(0)=G_n$ , $Q^n(k)=G_n+\sum\limits_{i=1}^k N_i^{(n)}$ for $k\geq 1$ . Then $N^{(n)}_m$ will be the number of children attached to the mth vertex on the infinite spine. Also, set $R^n(0)=G_n$ and $R^n(k)=G_n+\sum\limits_{i=1}^k B_i^{(n)}$ for $k\geq 1$ . Then $B^{(n)}_m$ will be the number of finite subtrees to the left of the infinite spine rooted at the mth vertex on the infinite spine.
-
Define $F^{n}(k)=\inf\{l\leq k-1:-\hat{I}^n(k-1-l)<R^n(l)\}.$ Then $F^{n}(k)$ will be the number of vertices located on the leftmost infinite spine among the first k vertices that we visit in our depth-first exploration.
-
Then define
$$S^n(k)=-G^{(n)}+\hat{S}^n\left(k-{F}^{(n)}(k)\right)+{Q}^n\left({F}^{(n)}(k)\right)-F^{n}(k),$$so that$$(S^n-\underline{\underline{S}}^{n})(k)= \hat{S}^n(k-{F}^{(n)}(k))+{R}^n\left({F}^{(n)}(k)\right)$$and(6)
By Corollary 1, Proposition 1, and Lemma 2, the constructed process has the desired distribution.
In the next section, we will introduce the continuous counterpart of this construction. In Section 3, we will use Equation (6) to show the joint convergence under rescaling of the discrete processes to the continuous processes.
2.2. The height process of a supercritical Lévy process
Just as in the discrete case, we will obtain a pathwise construction of a supercritical spectrally positive Lévy process and its height process by considering its pre- and post-infimum processes separately. As before, let L be such a Lévy process with Laplace exponent $\phi$ . Define $I_\infty=\inf\{L_t,t\geq 0\}$ , and set $\rho=\sup\{t>0\,{:}\,L_{t}=I_\infty\}$ . The process on $[0,\rho]$ will be referred to as the pre-infimum process, and the process on $[\rho,\infty)$ (shifted up by $-I_\infty$ so that it starts at 0) will be referred to as the post-infimum process. Informally, as in the discrete case, the pre-infimum process encodes the ${\mathbb R}$ -trees without a path of infinite length, and the post-infimum process encodes the metric structure to the left of the leftmost path of infinite length in the first ${\mathbb R}$ -tree that contains such a path.
(In [Reference Bertoin9], Bertoin uses a different strategy, and splits the process at the infimum attained on a compact time interval. We will not use this approach, and so we will not discuss his results here.)
On an infinite time horizon, the following results on spectrally positive Lévy processes are available:
-
1. By Théorème 2 in Bertoin [Reference Bertoin8], the pre-infimum process of a spectrally positive Lévy process that drifts to $+\infty$ has the same law as the process ‘conditioned to drift to $-\infty$ ’ stopped at an independent exponential level. Informally, this result says that the pre-infimum process encodes ${\mathbb R}$ -trees conditioned to die out.
-
2. By Lemma 4.1 in Millar [Reference Millar45] (which is rephrased as ‘Théorème (Millar)’ in [Reference Bertoin8]; we will use the latter version of the result), the post-infimum process of a spectrally positive Lévy process that drifts to $+\infty$ has the same law as the process conditioned to stay positive, and is independent of the pre-infimum process. Informally, this result says that the post-infimum process encodes (part of) a single ${\mathbb R}$ -tree conditioned to be infinite.
-
3. In [Reference Lambert41], Lambert describes the height process corresponding to a class of spectrally positive Lévy processes conditioned to stay positive.
We start with an overview of the results by Bertoin [Reference Bertoin8] that we use. Firstly, since L is supercritical, there is a unique $\xi>0$ such that $\phi(\xi)=0$ . Let ${\mathbb P}$ be the law of L, and set
Then $(\!\exp\!({-}\,\xi L_t),t\geq 0)$ is a ${\mathbb P}$ -martingale. Let ${\mathbb P}^\#$ be locally absolutely continuous with respect to ${\mathbb P}$ , with
Let $\hat{L}$ be a process which under ${\mathbb P}$ has the law of L under ${\mathbb P}^\#$ . The following analogue of Theorem 3 is a straightforward consequence of the fact that $\exp\!({-}\,\xi L_t)$ is a martingale. See [Reference Bertoin10, Chapter VII].
Theorem 4. The following hold:
-
1. For $\tau(x)=\inf\{t>0 \,{:}\, L_t=-x\}$ ,
$${\mathbb P}[\tau(x)<\infty]=\exp\!({-}\,\xi x).$$ -
2. If $\Lambda\in {\mathcal F}_{\tau(x)}$ for some $x>0$ , then
$${\mathbb P}^\#[\Lambda]={\mathbb P}[\Lambda|\tau(x)<\infty].$$ -
3. We have that ${\mathbb P}^\#$ is the law of a spectrally positive subcritical Lévy process with Laplace exponent $\phi^\#(\cdot)=\phi(\cdot+\xi)$ .
The following theorem is then proved in [Reference Bertoin8] as Théorème 2.
Theorem 5. ([Reference Bertoin8, Thàreme 2].) Let E be an exponential random variable with rate $\xi$ . The pre-infimum process of L has the law of $\hat{L}$ , independent of E, stopped at the first time it reaches level E.
These observations, together with Proposition 1.4.3 of Duquesne and Le Gall [Reference Duquesne and Le Gall24], imply the following proposition.
Proposition 2. There exists a continuous modification of the height process corresponding to $\hat{L}$ , which we will denote by $\hat{H}$ . Moreover, for
we have $\rho<\infty$ almost surely; furthermore, there exists a continuous modification of the height process of L up to $\rho$ , which we will refer to as H, and for E an exponential random variable with rate $\xi$ ,
Proof. Since L is supercritical, $\rho$ is finite almost surely. Theorem 4.3 and Condition (C3) ensure that the conditions of Theorem 1.4.3 in [Reference Duquesne and Le Gall24] are satisfied, which implies that the height process corresponding to $\hat{L}$ exists and has a continuous modification. Theorem 5 then yields the proposition.
We will now focus on the post-infimum process. We will use two important results from the literature. Firstly, by Lemma 4.1 in Millar [Reference Millar45], the post-infimum process $(L_{\rho+t}-I_{\infty}, t\geq 0)$ has the same law as L conditioned to stay positive and is independent of the pre-infimum process. Call the law of L conditioned to stay positive ${\mathbb P}^\uparrow$ . For the definition of this process, see [Reference Bertoin8, Reference Chaumont15, Reference Chaumont16]. The height process of L under ${\mathbb P}^\uparrow$ is characterized by Lambert in [Reference Lambert41], and is obtained via the continuous counterpart of the construction in Section 2.1. Indeed, in [Reference Lambert41], Lambert defines
and in [Reference Lambert41, Lemma 8ii] he shows that the height processes of $L-\underline{\underline{L}}$ and L are equal. Then, in [Reference Lambert41, Theorem 3], he gives a pathwise construction of $L-\underline{\underline{L}}$ and its local time at 0 under ${\mathbb P}^\uparrow$ , by viewing $L-\underline{\underline{L}}$ as a continuous-time branching process with immigration, an object introduced in [Reference Kawazu and Watanabe40]. Lemma 8ii of [Reference Lambert41] also illustrates how to construct the height process corresponding to $L-\underline{\underline{L}}$ . Translating these results to our setting yields the following proposition, which is the continuous counterpart of the pathwise construction of $S^n-\underline{\underline{S}}^n$ under ${\mathbb P}_n^\uparrow$ described in Proposition 1.
Theorem 6. ([Reference Lambert41, Theorem 3, Lemma 8ii].) Recall the definition of ${\mathbb P}^\#$ from (7). Let $\hat{L}$ be a process which under ${\mathbb P}$ has the law of L under ${\mathbb P}^\#$ , and let $\phi^\#$ be its Laplace exponent. Let $\widetilde{R}$ be a subordinator with Laplace exponent $\frac{\phi(\cdot)}{\cdot+\xi}$ independent of $\hat{L}$ . Then $\widetilde{R}$ is a subordinator. For $t\geq 0$ , define the right inverse of $\widetilde{R}$ by
and set
Then, for $L^*$ defined by
$L-\underline{\underline{L}}$ under ${\mathbb P}^\uparrow$ has the same law as $L^*$ . Moreover, the local time of $L^*$ at 0 may be defined by
Finally, suppose that $\hat{H}$ is a continuous modification of the height process corresponding to $\hat{L}$ . Then
is a continuous modification of the height process corresponding to $L^*_t$ .
Combining the above proposition with the characterization of the pre-infimum process in Proposition 2, we obtain the following result.
Proposition 3. Let $\hat{L}$ be a process which under ${\mathbb P}$ has the law of L under ${\mathbb P}^\#$ , satisfying Condition (C3), so that its height process is well-defined and has a continuous modification $\hat{H}$ . Define $\hat{I}_t=\inf\{\hat{L}_s\,{:}\,s\leq t\}$ . Let E be an exponential random variable with rate $\xi$ . Let $\widetilde{D}$ be distributed as in the statement of Theorem 6, independent of $\hat{L}$ and E, and set
and
Then the height process of L is well-defined and has a continuous modification H. Moreover, H is also the height process of $L-\underline{\underline{L}}$ , and
Proof. The existence of $\hat{H}$ follows from Proposition 2. The construction of $L-\underline{\underline{L}}$ follows from Proposition 2 for the pre-infimum process, and from [Reference Millar45, Lemma 4.1] and Theorem 6 for the post-infimum process.
We claim that $(\hat{H}_t+{R}^{-1}({-}\,\hat{I}_t),t\geq 0)$ is the height process corresponding to the process
Firstly, note that for $\rho^*=\sup\{t\,{:}\,\hat{I}_t=-E\}$ ,
The height process is, by definition, not affected by translating the Łukasiewicz path by a constant, so on $[0,\rho^*]$ , the claim follows. On $[\rho^*,\infty)$ , the claim follows from Theorem 6.
Finally, we claim that the height processes of L and $L-\underline{\underline{L}}$ agree. Set $I_\infty=\inf\{L_t,t\geq 0\}$ and $\rho=\sup\{t>0\,{:}\,L_{t}=I_\infty\}$ , and observe that
Again because the height process is not affected by adding a constant to the Łukasiewicz path, the claim follows on $[0,\rho]$ . On $[\rho,\infty)$ , the claim follows from Lemma 8ii in [Reference Lambert41].
3. Joint convergence of the height process and Łukasiewicz path
In this section, we will show the convergence of the discrete Łukasiewicz path $S^n$ and height process $H^n$ to their continuous counterparts L and H under rescaling. The convergence result relies on the construction of the discrete and continuous processes introduced in (6) and Proposition 3 respectively.
We will start by proving the joint convergence of $\hat{S}^n$ and its height process $\hat{H}^n$ under rescaling. Recall that by Condition (C1) there exists a nondecreasing sequence of positive integers $(\gamma_n,n\geq 1)$ that converges to $\infty$ such that
in ${\mathbb D}({\mathbb R}_+,{\mathbb R})$ as $n\to\infty$ .
Theorem 7. We have that
in ${\mathbb D}({\mathbb R}_+,{\mathbb R})^2$ as $n\to \infty$ .
Proof. We will first show convergence under rescaling of the Łukasiewicz path, i.e.
in the Skorokhod topology as $n\to \infty$ , after which we will use Theorem 2.3.1 of Duquesne and Le Gall [Reference Duquesne and Le Gall24] to show the joint convergence with the height process. Since $\hat{S}^n$ is a downward skip-free random walk on the integers, it will be sufficient to show that for all $\theta>0$ ,
(See e.g. [Reference Broutin, Duquesne and Wang14, Lemma A3].) Note that by definition,
For sake of brevity, we will denote $n\gamma_n\phi_n(n^{-1}\cdot)$ by $\bar{\phi}_n(\cdot)$ . By the convergence under rescaling of $S^n$ to L, we know that $\bar{\phi}_n$ converges to $\phi$ pointwise. We will first show that
as $n\to \infty$ ; then we will show that there is a $b<\xi$ such that for any $B>b$ ,
uniformly on [b,B]. Together, (9) and (10) imply (8).
Note that by definition, $n\xi_n$ is the unique non-trivial zero of $\bar{\phi}_n$ . By convexity of $\phi$ and by $\phi(0)=\phi(\xi)=0$ , we see that for all $\epsilon>0$ ,
So by the pointwise convergence of $\bar{\phi}_n$ to $\phi$ , we have that, for all n large enough,
But then $n\xi_n\in (\xi-\epsilon,\xi+\epsilon)$ , which implies (9). To prove (10), given the pointwise convergence of $\bar{\phi}_n$ to $\phi$ , it will be sufficient to find a $y<\xi$ such that, for all n large enough, $\bar{\phi}_n$ is monotone on $[y,\infty)$ . By convexity of $\bar{\phi}_n$ for all n, it is enough to show that there is an $x<y<\xi$ such that
for all n large enough. However, by convexity of $\phi$ and by $\phi(0)=\phi(\xi)$ , there exist $x<y<0$ such that
The pointwise convergence of $\bar{\phi}_n$ to $\phi$ then implies (11), and hence (10) and (8).
We now wish to apply [Reference Duquesne and Le Gall24, Theorem 2.3.1] to obtain joint convergence under rescaling of the Łukasiewicz path and height process. Considering Theorem 3.3, Condition (C3), and (8), the only condition that is left to check is that, for ${Y}^n_m$ the number of individuals in generation m in the Galton–Watson branching process given by the first n trees in the forest encoded by $S^n$ , we have for all $\delta>0$
We claim that this is equivalent to the statement above under ${\mathbb P}$ . Indeed,
so the equivalence follows from the fact that
The statement then follows from
which is the assumption (3).
We will now show joint convergence under rescaling of $Q^n$ and $R^n$ , which is the content of the next theorem. Suppose, without loss of generality, that the Laplace exponent of L is given by
for $a>0$ , $b\geq 0$ , and $\nu$ a measure on $[0,\infty)$ that satisfies $\int_0^\infty (1\wedge x)\nu(x)<\infty$ , so that $(a,b,\nu)$ is the characteristic triple of L.
Define
and let $(R_t,Q_t)_{t\geq 0}$ be a Lévy process with Lévy measure $\tilde{\nu}$ , drift vector (b,2b), and no Gaussian component, so that $(R_t)_{t\geq 0}$ and $(Q_t)_{t\geq 0}$ are both subordinators. Let E be an exponential random variable with rate $\xi$ .
Theorem 8. It holds that
in ${\mathbb D}({\mathbb R}_+,{\mathbb R}_+^2)$ as $n\to \infty$ .
Proof. First we recall that $R^n_0=Q^n_0\sim \operatorname{Geom}(\!\exp\!({-}\,\xi_n))$ . Recalling that $n\xi_n\to \xi$ , we get that for any $x>0$ ,
so we can conclude that
We aim to use [Reference Jacod and Shiryaev33, Theorem VII.2.9] to prove the convergence under rescaling of
We will approximate this random walk by a Poissonized version. To that end, define
Let $(\bar{S}^n_t,t\geq 0)$ denote the compound Poisson process defined by
We claim that
Indeed, $\bar{S}^n_1$ is a Poissonized version of $n^{-1}S^n_{\lfloor n\gamma_n \rfloor}$ , so (13) is implied by (2). Now, let $h\,{:}\,{\mathbb R}\to {\mathbb R}$ be a bounded function such that $h(x)=-x$ on a neighborhood of 0. Then Theorem VII.2.9 in [Reference Jacod and Shiryaev33] implies the following facts:
-
1. We have $\int_{-1/n}^\infty\nu_n(dx)h(x)\to a_h$ for some $a_h$ as $n\to\infty$ .
-
2. As $n\to \infty$ ,
(14) \begin{equation}\int_{-1/n}^\infty\nu_n(dx)(h(x))^2 \to b+\int_{0}^\infty\nu(dx)(h(x))^2.\end{equation} -
3. For bounded continuous $f\,{:}\,{\mathbb R}^+\to {\mathbb R}$ such that $f(x)=o(x^2)$ when $x\downarrow 0$ , it holds that
(15) \begin{equation}\int_{-1/n}^\infty\nu_n(dx)f(x) \to \int_{0}^\infty\nu(dx)f(x).\end{equation}
Recalling that
we now define
Then, by an argument similar to the one used before, for $(\bar{R}^n_t, \bar{Q}^n_t,t\geq 0)$ denoting the process with stationary increments defined by
we get that for all t, $(\bar{R}^n_t, \bar{Q}^n_t)$ is a Poissonized version of
We will show that for all t,
which implies the functional convergence by a result in Kallenberg’s book [Reference Kallenberg39, Theorem 16.14]. By Theorem VII.2.9 in [Reference Jacod and Shiryaev33], using the truncation function $H(x,y)=(x\wedge 1,y\wedge 1)$ , the following properties imply (16):
-
1. We have
-
(a) $\int_0^\infty\int_0^\infty \tilde{\nu}_n(dx,dy)(x\wedge 1)\to \int_0^\infty\int_0^\infty \tilde{\nu}(dx,dy)(x\wedge 1)+b$ , and
-
(b) $\int_0^\infty\int_0^\infty \tilde{\nu}_n(dx,dy)(y\wedge 1)\to \int_0^\infty\int_0^\infty \tilde{\nu}(dx,dy)(y\wedge 1)+2b$ .
-
-
2. We have
-
(a) $\int_0^\infty\int_0^\infty \tilde{\nu}_n(dx,dy)(x\wedge 1)^2\to \int_0^\infty\int_0^\infty \tilde{\nu}(dx,dy)(x\wedge 1)^2$ ,
-
(b) $\int_0^\infty\int_0^\infty \tilde{\nu}_n(dx,dy)(y\wedge 1)^2\to \int_0^\infty\int_0^\infty \tilde{\nu}(dx,dy)(y\wedge 1)^2$ , and
-
(c) $\int_0^\infty\int_0^\infty \tilde{\nu}_n(dx,dy)(x\wedge 1)(y\wedge 1)\to \int_0^\infty\int_0^\infty \tilde{\nu}(dx,dy)(y\wedge 1)^2$ .
-
-
3. For all continuous, bounded $F\,{:}\,{\mathbb R}^2\to {\mathbb R}$ that are 0 on a neighborhood of 0,
$$\int_0^\infty\int_0^\infty \tilde{\nu}_n(dx,dy)F(x,y)\to \int_0^\infty\int_0^\infty \tilde{\nu}(dx,dy)F(x,y).$$
We will prove the conditions one by one, starting with 1a. We note that
We will first argue that
uniformly in all $x>0$ as $n\to \infty$ . Recall that $n\xi_n=\xi+o(1)$ , which, together with the Riemann integrability of $\exp\!({-}\,\xi y)(y\wedge 1)$ on compact intervals, implies pointwise convergence in (17). The facts that $\int_0^\infty dy\exp\!({-}\,\xi y)(y\wedge 1)<\infty$ and that $\int_0^x dy\exp\!({-}\,\xi y)(y\wedge 1)=O(x^2)$ as $x\to 0$ , together with the uniform continuity of $f(x,y)\,{:\!=}\,\frac{1}{x\wedge 1}\exp\!({-}\,\xi y)(y\wedge 1)$ on $(\delta,\infty)\times (0,R)$ for any $\delta>0$ and $R>0$ , then imply that convergence in (17) is in fact uniform, as claimed.
Since $\int_{-1/n}^\infty\nu_n(dx)(x\wedge 1)$ is convergent as $n\to \infty$ , and in particular bounded, we have that
converges to 0 as $n\to \infty$ . So in order to prove 1a, it is sufficient to show that
To see this, consider a truncation function h, and define
Then, note that $\int_0^x dy\exp\!({-}\,\xi y)(y\wedge 1)=\frac{x^2}{2}+o(x^2)$ as $x\to 0$ , so $g_u(x)=o(x^2)$ as $x\to 0$ . Furthermore, $g_u$ is bounded, because $\int_0^x dy\exp\!({-}\,\xi y)(y\wedge 1)$ is bounded. Then, by (15),
Moreover, since
and $\int_{-1/n}^\infty \nu_n(dx)h(x)\to a_h$ , we find that
which, combined with (19), implies that
proving 1a.
A similar proof shows that also 1b holds.
To prove 2a, note that
The first fact we need is that
converges to 0 as $n\to \infty$ , which is proved in a similar manner to (18). Then, since $\int_0^x dy\exp\!({-}\,\xi y)(y\wedge 1)^2=o(x^2)$ as $x\to 0$ , and it is a bounded function of x, we can use (15) to obtain 2a. The proofs of 2b, 2c, and 3 are similar.
By Theorem VII.2.9 in [Reference Jacod and Shiryaev33], for all $t>0$ ,
which proves the statement.
The final steps in the proof of Theorem 2 are similar to the proof of Theorem 1.5 in [Reference Duquesne22].
Recall that $F^{n}(k)=\inf\{l\,{:}\,-\hat{I}^n(k-1-l)<R^n(l)\}$ . We also define its continuous counterpart
We will now use the convergence of $(R^n,Q^n)$ under rescaling to prove the convergence under rescaling of $F^{n}$ to F. For this we need the following technical lemma, whose proof can be found in the appendix.
Lemma 4. Suppose $f_n\to f$ in ${\mathbb D}({\mathbb R}_+,{\mathbb R})$ as $n\to\infty$ , with $f_n$ increasing for all n, and f increasing and continuous. Furthermore, suppose $g_n\to g$ in ${\mathbb D}({\mathbb R}_+,{\mathbb R})$ as $n\to\infty$ , with $g_n$ increasing for all n, g strictly increasing, and $g_n(t) \to \infty$ and $g(t)\to \infty$ as $t\to \infty$ . Then
is continuous, and
in ${\mathbb D}({\mathbb R}_+,{\mathbb R})$ as $n\to\infty$ .
Moreover, for $(\epsilon_n)_{n\geq 0}$ such that $\epsilon_n\downarrow 0$ ,
in ${\mathbb D}({\mathbb R}_+,{\mathbb R})$ as $n\to\infty$ .
Lemma 5. We have that
in ${\mathbb D}({\mathbb R}_+,{\mathbb R})$ as $n\to\infty$ , jointly with the joint convergence of $R^n$ and $Q^n$ under rescaling (Theorem 8) and the joint convergence of $\hat{S}^n$ and $\hat{H}^n$ under rescaling (Theorem 7), where $(R^n,Q^n)$ is independent of $(\hat{S}^n,\hat{H}^n)$ . Moreover, $(F_t,t\geq 0)$ is continuous almost surely.
Proof. We need to show that
in ${\mathbb D}({\mathbb R}_+,{\mathbb R})$ as $n\to\infty$ and that $\left(\inf\{s\,{:}\,-\hat{I}_t<R_s\},t\geq 0\right)$ is continuous, for which we will use Lemma 4. Firstly, recall that L is of infinite variation, so that $b>0$ , or $\nu((0,\infty))=\infty$ . In the first case, it is obvious that R is strictly increasing. In the second case, note that since R has Lévy measure
the intensity of jumps of size $\epsilon$ goes to $\infty$ as $\epsilon$ goes to 0, which implies that the jumps of R are dense, and its sample paths are strictly increasing with probability 1. By Skorokhod’s representation theorem, we may work on a probability space where the joint convergence of $R^n$ and $Q^n$ under rescaling (Theorem 8) and the joint convergence of $\hat{S}^n$ (and $\hat{I}^n$ ) and $\hat{H}^n$ under rescaling (Theorem 7) all hold almost surely. Then, by Lemma 4, since $\hat{I}$ is continuous ( $\hat{L}$ is spectrally positive), we have that
in ${\mathbb D}({\mathbb R}_+,{\mathbb R})$ as $n\to\infty$ and $F_t$ is continuous almost surely. The result follows.
From Theorem 7, Theorem 8, and Lemma 5 we know that, as $n\to \infty$ ,
jointly, in ${\mathbb D}({\mathbb R}_+,{\mathbb R})^2$ , ${\mathbb D}({\mathbb R}_+,{\mathbb R}^2)$ , and ${\mathbb D}({\mathbb R}_+,{\mathbb R})$ respectively. We would like to show the convergence under rescaling of $Q^n(F^{n}(k))$ and of $R^n(F^{n}(k))$ jointly with the convergence in (20), since these quantities appear in the pathwise construction of $S^n$ and $S^n-\underline{\underline{S}}^n$ in Equation (6). For this we need a technical lemma, which follows immediately from the characterization of convergence in the Skorokhod topology given in the book of Ethier and Kurtz [Reference Ethier and Kurtz29, Proposition 3.6.5].
Lemma 6. Let E be a metric space, and suppose $h_n\to h$ in ${\mathbb D}({\mathbb R}_+,E)$ and $f_n\to f$ in ${\mathbb D}({\mathbb R}_+,{\mathbb R}_+)$ as $n\to \infty$ . If $f_n$ and f are non-decreasing and f is continuous, then
in ${\mathbb D}({\mathbb R}_+,{\mathbb R}^2)$ as $n\to\infty$ .
Lemma 7. We have
in ${\mathbb D}({\mathbb R}_+,{\mathbb R}^2)$ as $n\to\infty$ , jointly with the convergence in (20).
Proof. By Skorokhod’s representation theorem we may work on a space where the convergence of (20) holds almost surely. The result then follows from Lemma 6.
Lemma 8. We have
in ${\mathbb D}({\mathbb R}_+,{\mathbb R})^2$ as $n\to\infty$ , jointly with the convergence in (20).
Proof. Firstly, note that $k-F^{n}(k)$ equals the number of steps not spent on the spine up to time k and so is a non-decreasing function of k. Then, note that
and
in ${\mathbb D}({\mathbb R}_+,{\mathbb R})$ almost surely as $n\to\infty$ . We may use Skorokhod’s representation theorem to work on a space where the convergence in (20) holds almost surely, and then Lemma 6 gives the result.
We will now prove Theorem 2.
Proof of Theorem 2. Let $(\hat{L}, \hat{H})$ , $\hat{I}$ , (R,Q), and $F_t=\inf\{s\,{:}\,-\hat{I}_t<R_s\}$ be as defined in Section 2.2. Then, for $\underline{\underline{S}}^n$ the future infimum of $S^n$ , we know by the pathwise construction of $S^n$ , $S^n-\underline{\underline{S}}^n$ , and $H^n$ given in (6), and by Lemmas 8, 7, and 5, that
in ${\mathbb D}({\mathbb R}_+,{\mathbb R}^3)$ as $n\to\infty$ . By assumption, we have that
so
and by construction, $\hat{L}_t+R_{F_t}$ equals $\hat{L}_t+Q_{F_t}$ minus its future infimum. Then, by Proposition 3, we know that $\hat{H}_t+F_t$ is the height process corresponding to $\hat{L}_t+R_{F_t}$ and hence to $\hat{L}_t+Q_{F_t}.$ The result follows.
4. Application to the configuration model in the critical window
This section contains new results on the scaling limit of the configuration model with i.i.d. power-law degrees in the critical window. We use Theorem 2 to extend the methods in Conchon-Kerjan and Goldschmidt [Reference Conchon-Kerjan and Goldschmidt17] from the critical point to the critical window.
The configuration model is a method of constructing a multigraph with a given degree sequence that was introduced by Bollobás in [Reference Bollobás13]:
Consider n vertices labeled by [n] and a sequence $\textbf{d}=(d_i)_{i\in[n]}\in {\mathbb N}^n$ such that $\sum_{i\in [n]}d_i$ is even. We will sample a multigraph such that the degree of vertex i is equal to $d_i$ for every $i\in [n]$ . The configuration model on n vertices having degree sequence $\textbf{d}$ is constructed as follows. Equip vertex j with $d_j$ half-edges. Two half-edges create an edge once they are paired. Pick any half-edge and pair it with a uniformly chosen half-edge from the remaining unpaired half-edges and keep repeating the above procedure until all half-edges are paired.
Note that the graph constructed by the above procedure may contain self-loops or multiple edges. It can be shown that, conditionally on the constructed multigraph being simple, the law of such graphs is uniform over all possible simple graphs with degree sequence $\textbf{d}$ . Furthermore, as shown in [Reference Janson35], under very general assumptions, the asymptotic probability of the graph being simple is positive. For a discussion of the configuration model and standard results, see [Reference Van der Hofstad51, Chapter 7].
4.1. Model and result
We use the configuration model to construct a uniform graph with a random degree sequence. The model we consider is as follows.
Fix $\lambda\in{\mathbb R}$ . Most quantities that will be defined depend on $\lambda$ . To avoid overcomplicating the notation, this will not be made explicit unless necessary to avoid confusion. For each $n \in {\mathbb N}$ , let $D_1^{n}, D_2^{n}, \dots, D_n^{n} \geq 1 $ be an i.i.d. degree sequence satisfying the following properties (which are labeled by ‘CM’ for ‘configuration model’):
-
(CM1) For $\mu_n \,{:\!=}\, {\mathbb E}[D_1^{n}] $ , we have $\mu_n\rightarrow \mu$ as $n \rightarrow \infty$ , with $\mu$ not depending on $\lambda$ .
-
(CM2) We have ${\mathbb E} \left[\left(D_1^{n}\right)^2\right]=\left(2+\lambda n ^{-\tfrac{\alpha-1}{\alpha+1}}\right) {\mathbb E}[D_1^{n}]$ for some $\alpha \in (1,2)$ .
-
(CM3) We have ${\mathbb P} (D_1^{n}=k)\sim c_n k^{-(\alpha+2)}$ as $k\rightarrow \infty$ , with $c_n>0$ for all n and $c_n\to c$ as $n\to \infty$ .
-
(CM4) For $Z^n$ a random variable such that ${\mathbb P}(Z^n=k)=k{\mathbb P}(D_1^{n}=k)/\mu_n$ , and $(S^n(k),k\geq 0)$ a random walk with steps distributed as $Z^n-2$ , let $Y^n_m$ be the number of vertices at height m in the first $\lfloor n^{1/(\alpha+1)}\rfloor$ trees of the forest encoded by $(S^n(k),k\geq 0)$ . Then, for every $\delta>0$ ,
\begin{equation*}\liminf\limits_{n\to\infty}{\mathbb P}\left[Y^n_{\lfloor \delta n^{\tfrac{\alpha-1}{\alpha+1}}\rfloor}=0\right]>0.\end{equation*}
Let $G_1^n, G_2^n,\dots$ be the components of a uniformly random graph with i.i.d. degrees that are distributed as $D_1^n$ , with the components listed in decreasing order of size. View each $G_i^n$ as a compact measured metric spaces by equipping it with the graph distance $d_i^n$ , and the counting measure on its vertices, $\mu_i^n$ . More generally, a compact measured metric space will be denoted by a triple $(G,d,\mu)$ , for (G, d) a compact metric space and $\mu$ a finite Borel measure on (G, d). Formally, each $G_i^n$ is an element of the Polish space of isometry-equivalence classes of measured metric spaces, endowed with the Gromov–Hausdorff–Prokhorov distance. For a discussion of the topology, we refer the reader to [Reference Addario-Berry, Broutin, Goldschmidt and Miermont3, Section 2]. We will prove the following theorem.
Theorem 9. There exists a sequence of random compact measured metric spaces
such that, as $n\to \infty$ ,
in the sense of the product Gromov–Hausdorff–Prokhorov topology.
In the case where $\lambda=0$ , and the degree distribution does not depend on n, this result was already known from [Reference Conchon-Kerjan and Goldschmidt17, Theorem 1.1]; this is known as the critical case. Intuitively, criticality entails that for large n, and for $(V_n,W_n)$ an edge chosen uniformly at random from the graph, the expected degree of $V_n$ is roughly 2. Our contribution is then to prove the theorem for all $\lambda\in{\mathbb R}$ and for degree distributions depending on n. This is known as the critical window, in which, for large n, and for $(V_n,W_n)$ an edge chosen uniformly at random from the graph, the expected degree of $V_n$ is roughly $2+ \lambda n ^{-\tfrac{\alpha-1}{\alpha+1}}$ .
4.2. Related work
Most results on the configuration model have been obtained for models with a deterministic degree sequence. The phase transition for the undirected setting was shown in [Reference Janson and Łuczak37, Reference Molloy and Reed46, Reference Molloy and Reed47]. The limiting law of the rescaled component sizes at criticality and in the critical window were obtained by Riordan [Reference Riordan49] under the assumption that the degrees are bounded. Dhara, van der Hofstad, van Leeuwaarden, and Sen showed convergence under rescaling of the component sizes and surpluses in the critical window in the finite-third-moment setting [Reference Dhara, van der Hofstad, van Leeuwaarden and Sen19] and in the heavy-tailed regime [Reference Dhara, van der Hofstad, van Leeuwaarden and Sen20]. Bhamidi, Dhara, van der Hofstad, and Sen obtained metric space convergence in the critical window in [Reference Bhamidi, Dhara, van der Hofstad and Sen11], a result that the authors later improved to a stronger topology in [Reference Bhamidi, Dhara, van der Hofstad and Sen12]; both of these results also hold conditional on the constructed multigraph being simple. We will discuss the results of Bhamidi, Dhara, van der Hofstad, and Sen further at the end of this section.
Configuration models with a random degree sequence are considered in [Reference Conchon-Kerjan and Goldschmidt17, Reference Joseph38]. Joseph [Reference Joseph38] showed convergence of the component sizes and surpluses of the large components under rescaling at criticality, both for degree distributions with finite third moments and for the heavy-tailed regime. Conchon-Kerjan and Goldschmidt [Reference Conchon-Kerjan and Goldschmidt17] showed product Gromov–Hausdorff–Prokhorov convergence of the large components at criticality in these two regimes, and showed that the results also hold conditioned on the resulting graph being simple.
In recent work [Reference Donderwinkel and Xie21], the author and Xie showed metric space convergence under rescaling of the strongly connected components of the directed configuration model at criticality.
4.2.1. Results in [Reference Bhamidi, Dhara, van der Hofstad and Sen11, Reference Bhamidi, Dhara, van der Hofstad and Sen12].
We now describe the model that is considered in [Reference Bhamidi, Dhara, van der Hofstad and Sen11, Reference Bhamidi, Dhara, van der Hofstad and Sen12] to provide a comparison with our result. Our description of the results in [Reference Bhamidi, Dhara, van der Hofstad and Sen11] closely follows the presentation in [Reference Conchon-Kerjan and Goldschmidt17].
Let $\mathfrak{d}_1^n\geq \cdots\geq \mathfrak{d}_n^n$ be a family of deterministic degree sequences, such that $\sum_{i=1}^n\mathfrak{d}_i^n$ is even, and if $\mathfrak{D}_n$ denotes the degree of a vertex chosen uniformly at random, the following conditions hold (they are labeled by ‘DD’ for ‘deterministic degrees’):
-
(DD1) We have $n^{-1/(\alpha+1)}\mathfrak{d}_i^n\to \mathfrak{\vartheta}_i$ as $n\to\infty$ for each $i\geq 1$ , where $\vartheta_1\geq \vartheta_2\geq \cdots \geq 0 $ is such that $\sum_{i\geq 1} \vartheta^3<\infty$ , but $\sum_{i\geq 1}\vartheta_i^2=\infty$ .
-
(DD2) We have $\mathfrak{D}_n\overset{d}{\to}\mathfrak{D}$ , along with the convergence of its first two moments, for some random variable $\mathfrak{D}$ with ${\mathbb P}(\mathfrak{D}=1)>0$ , ${\mathbb E}[\mathfrak{D}]=\mu$ , and ${\mathbb E}[\mathfrak{D}(\mathfrak{D}-1)]/{\mathbb E}[\mathfrak{D}]=\theta>1$ , and
$$\lim_{K\to\infty}\limsup_{n\to\infty}n^{-3/(\alpha+1)} \sum_{i\geq K+1}\left(\mathfrak{d}_i^n\right)^3=0.$$
Let $\theta_n={\mathbb E}\left[\mathfrak{D}_n(\mathfrak{D}_n-1)\right]/{\mathbb E}\left[\mathfrak{D}_n\right]$ . The authors of [Reference Bhamidi, Dhara, van der Hofstad and Sen11, Reference Bhamidi, Dhara, van der Hofstad and Sen12] sample a uniform graph with this degree sequence and perform percolation at parameter
for some $\tilde{\lambda}\in {\mathbb R}$ , which yields a graph in the critical window. Call the resulting degree sequence $(\mathfrak{D}_1^{n,\tilde{\lambda}}, \dots ,\mathfrak{D}_n^{n,\tilde{\lambda}})$ . In this setting, [Reference Bhamidi, Dhara, van der Hofstad and Sen11, Theorem 2.2] is the precise analogue of our Theorem 9 in the Gromov-weak topology. In [Reference Bhamidi, Dhara, van der Hofstad and Sen12], this result is strengthened to convergence in the Gromov–Hausdorff–Prokhorov topology, under the following additional assumptions:
-
(DD3) For $\mathfrak{D}^*_n$ the degree of a size-biased pick from $\mathfrak{d}_1^n,\dots,\mathfrak{d}_n^n$ , there exists $c_0>0$ such that for all $1\leq l\leq \mathfrak{d}^n_1$ and $n\geq 1$ ,
$${\mathbb P}\left(\mathfrak{D}^*_n\geq l\right)\geq \frac{c_0}{l^\alpha}.$$ -
(DD4) For $\beta_i^n=n^{-2/(\alpha+1)}\sum_{j=1}^{i-1}\left(\mathfrak{d}^n_j\right)^2$ , there exists a sequence $(k_n)_{n\geq 1}$ with $k_n\to \infty$ and $k_n=o\left(n^{1/(\alpha+1)}\right)$ such that $\beta_{k_n}^n/\log n\to \infty$ as $n\to\infty$ .
-
(DD5) For all $\epsilon>0$ ,
$$\lim_{k\to \infty}\limsup_{n\to\infty} n^{-1/(\alpha+1)}\sum_{i\in (k,kn)}e^{-\epsilon \beta_i^n}\mathfrak{d}^n_i=0.$$
These extra assumptions allow the authors of [Reference Bhamidi, Dhara, van der Hofstad and Sen12] to show that the components in their graph model satisfy the global lower mass-bound property [Reference Bhamidi, Dhara, van der Hofstad and Sen12, Theorems 1.2 and 1.3], which allows them to extend the results in [Reference Bhamidi, Dhara, van der Hofstad and Sen11] to convergence in the Gromov–Hausdorff–Prokhorov topology using results from [Reference Athreya, Löhr and Winter7].
The limit object in [Reference Bhamidi, Dhara, van der Hofstad and Sen11, Reference Bhamidi, Dhara, van der Hofstad and Sen12] is constructed by making vertex identifications in tilted inhomogeneous continuum random trees. The scaling limit of the depth-first walk that Bhamidi, Dhara, van der Hofstad, and Sen consider is a thinned Lévy process, whereas we show convergence to a measure-changed Lévy process. The connection between our results and theirs will become clear in the following section.
4.2.2. Relationship to percolation.
We will illustrate that the law of a degree sequence that is obtained by bond percolation on the half-edges of a sequence of vertices with i.i.d. degrees in the supercritical regime satisfies the conditions of Theorem 9. This is approximately the degree distribution after bond percolation on the edges of a uniform random graph with such a supercritical random degree sequence, although we ignore dependence between the degrees of different vertices. Using results of Janson [Reference Janson34], such mild dependence can be shown to have a negligible effect on the properties of the graph, but we omit the straightforward details. We also show how our results are related to the results in [Reference Bhamidi, Dhara, van der Hofstad and Sen11, Reference Bhamidi, Dhara, van der Hofstad and Sen12].
Let D be a random variable in ${\mathbb N}$ that satisfies ${\mathbb E} [D]=\mu$ , ${\mathbb E} [D^2]=\rho>2\mu$ and ${\mathbb P} (D=k)\sim ck^{-(\alpha+2)}$ for $\alpha \in (1,2)$ as $k\rightarrow \infty$ . Define $C_{\alpha}=\frac{c\Gamma(2-\alpha)}{\alpha(\alpha-1)}$ , so that the Laplace transform ${\mathcal L}_D$ of D satisfies
for $\theta \rightarrow 0$ . View D as the degree distribution. Then, keep every half-edge with probability
and call the resulting degree distribution $B^{(\lambda,n)}$ .
In the next paragraph, we will show that the conditions of Theorem 9 are satisfied for $B^{(\lambda,n)}$ . Then, for $\mathfrak{d}_1^n,\dots,\mathfrak{d}_n^n$ denoting a sample of i.i.d. random variables $\mathfrak{D}_1,\dots, \mathfrak{D}_n$ with the same distribution as D, Conditions (DD1) and (DD2) are satisfied almost surely for some sequence of random variables $\mathfrak{\vartheta}_i$ [Reference Dhara, van der Hofstad, van Leeuwaarden and Sen20, Section 2.2]. Moreover, the order statistics of the percolated degree sequence with $\tilde{\lambda}=\lambda/(\rho/\mu-1)$ closely resemble an ordered sample of i.i.d. random variables distributed as $B^{(\lambda,n)}$ . Therefore, it should be the case that, in this particular set-up, the limit of Bhamidi, Dhara, van der Hofstad, and Sen corresponds to the limit in Theorem 9.
We will now verify the conditions of Theorem 9 for $B^{(\lambda,n)}$ . Note that the Laplace transform ${\mathcal L}_{B^{(\lambda,n)}}$ of $B^{(\lambda,n)}$ satisfies
so that
as $\theta\to 0$ . This implies that Conditions (CM1), (CM2), and (CM3) are satisfied with $\mu_n=p(\lambda,n)\mu\to\mu/(\frac{\rho}{\mu}-1)$ and $c_n=cp(\lambda,n)^{\alpha+1}\to c/(\frac{\rho}{\mu}-1)^\alpha$ as $n\to \infty$ .
We now check Condition (CM4). We will drop the dependency on $\lambda$ from the notation, unless it is necessary to avoid confusion. Let $\tilde{D}$ be a random variable with the size-biased distribution of D, i.e. for all $k\in {\mathbb N}$ ,
and similarly, let $\tilde{B}_n$ be a random variable with the size-biased distribution of ${B}^{(n,\lambda)}$ , i.e.
Let $g_{\tilde{D}-1}(x)$ and $g_{{\tilde{B}}_n-1}(x)$ be the probability generating functions of $\tilde{D}-1$ and $\tilde{B}_n-1$ respectively. Then (22) implies that
Letting $g_{{\tilde{B}}_n-1}^{\circ k }$ denote the kth iterate of $g_{{\tilde{B}}_n-1}$ , note that Condition (CM4) is equivalent to
(See for instance the discussion below Theorem 2.3.1 in [Reference Duquesne and Le Gall24].) As in the proof of [Reference Broutin, Duquesne and Wang14, Proposition 5.25], it is sufficient to show that, for $t\in (0,\infty)$ and $r_n(t)$ the value such that
we have
Note that
where we change variable to $s=p(\lambda,n)r$ . An elementary calculation yields that
as $s\to 0$ , which implies that
as $s\to 0$ . Then, setting $v=n^{1/(\alpha+1)}s$ implies that
so that, since $p(n,\lambda)=\Theta(1)$ as $n\to \infty$ , we obtain
as required. This implies that Condition (CM4) is satisfied and so, indeed, performing bond percolation on the half-edges of a sequence of vertices with i.i.d. degrees in the supercritical regime yields a degree distribution that satisfies the conditions of Theorem 9.
4.2.3. The methods in [Reference Conchon-Kerjan and Goldschmidt17].
In this section, we will further discuss the results and methods of Conchon-Kerjan and Goldschmidt [Reference Conchon-Kerjan and Goldschmidt17]. As mentioned previously, Conchon-Kerjan and Goldschmidt study a specific case of the model defined in Section 4.1, namely the case where the degree sequence does not depend on n and $\lambda=0$ . They prove Theorem 9 for that family of models, which is the content of [Reference Conchon-Kerjan and Goldschmidt17, Theorem 1.1]. (Their result includes the case $\alpha=2$ , which we do not consider here.)
The limit object is referred to as the $\alpha$ -stable graph for $\alpha\in (1,2)$ (and the Brownian graph for $\alpha=2$ ). They obtain an additional result that identifies the components of the limit object as ${\mathbb R}$ -trees encoded by tilted excursions of an $\alpha$ -stable spectrally positive Lévy process for $\alpha\in (1,2)$ (and tilted excursions of a Brownian motion for $\alpha=2$ ) with additional vertex identifications. We cannot obtain such a description of the limit components in Theorem 9 because of their lack of self-similarity.
We now give an informal overview of the proof of [Reference Conchon-Kerjan and Goldschmidt17, Theorem 1.1]. Much of the proof transfers over to our setting without change, so after this overview we will focus on the parts of the proof that are different in our setting. The method in [Reference Conchon-Kerjan and Goldschmidt17] relies on using the configuration model in a depth-first manner, which we describe below.
From the description of the configuration model, it is clear that we can pick an order of connecting half-edges to our convenience. Hence we will choose an order that makes it similar to a depth-first exploration process. First, sample an i.i.d. degree sequence $D_1,\dots, D_n$ with $D_1\geq 1$ almost surely. Start from a vertex v chosen with probability proportional to $D_v$ and label its half-edges in an arbitrary way. We maintain a stack, which is an ordered list of the half-edges that we have seen but have not yet explored. Add all the half-edges of v to the stack, ordered according to their labels, with the lowest label being on top of the stack. From now on, at each step, if the stack is non-empty, take the half-edge from the top of the stack, and sample its pair uniformly among the unpaired half-edges, i.e. the remaining half-edges on the stack, and the unexplored half-edges not on the stack. If the paired half-edge was not on the stack, say it was linked to vertex w, then remove the paired half-edges from the system and place the remaining $D_w-1$ half-edges of w on the top of the stack, arbitrarily labeled and in decreasing order of label, so that the lowest label of a half-edge of w is now on top of the stack (unless the degree of w is 1). If the paired half-edge was on the stack, remove both paired half-edges from the system. If the stack is empty, we start a new connected component by selecting an unexplored vertex with probability proportional to its degree, and putting its half-edges on top of the stack.
The argument then proceeds as follows:
-
1. Conditionally on $D_1,\dots,D_n$ , if we order the vertices by the time their first half-edge is paired in the configuration model, the ordered degree sequence $\hat{D}^n_1,\dots, \hat{D}^n_n$ is a size-biased random ordering of $D_1,\dots,D_n$ , and the forest encoded by the Łukasiewicz path $\tilde{S}^n_m=\sum_{i=1}^m\left(\hat{D}^n_i-2\right)$ is closely related to the components of the multigraph given by the configuration model.
-
2. For $i\neq j$ , in general, $\hat{D}^n_i$ is not equal to $\hat{D}^n_j$ in distribution, and $\hat{D}^n_i$ and $\hat{D}^n_j$ are dependent. These facts make $\tilde{S}^n$ hard to study. However, for $Z_1,\dots, Z_n$ i.i.d. with ${\mathbb P}(Z_1=k)=\frac{k{\mathbb P}(D_1=k)}{{\mathbb E}[D_1]},$ for $m\leq n$ there exists a function $\phi^n_m$ such that for $g\,{:}\,{\mathbb N}^m\to{\mathbb R}$ ,
$${\mathbb E}[g(\hat{D}_1^n,\hat{D}_2^n,\dots,\hat{D}_m^n)]={\mathbb E}[\phi_m^n(Z_1,Z_2,\dots,Z_m)g(Z_1,Z_2,\dots,Z_m)].$$Moreover, $\phi^n_m$ behaves well under rescaling, which allows the authors of [Reference Conchon-Kerjan and Goldschmidt17] to study $S_m\,{:\!=}\,\sum_{i=1}^m\left(Z_i-2\right)$ , and then use the measure change to translate results on this simpler process to results on $\tilde{S}^n$ . -
3. Indeed, under rescaling, S converges to an $\alpha$ -stable spectrally positive Lévy process L, jointly with its height process, and this result is used to show that $\tilde{S}$ (up to time $O(n^{\alpha/(\alpha+1)})$ ) converges to a process that is locally absolutely continuous to L, jointly with its height process.
-
4. The excursions of $\tilde{S}^n$ above its running infimum and the corresponding excursions above 0 of its height process encode individual trees in the forest. It is shown that the longest excursions explored up to time $\Theta(n^{\alpha/(\alpha+1)})$ converge under rescaling. The theory of size-biased point processes, developed by Aldous in [Reference Aldous, Barlow and Bingham4], is then used to show that, in fact, with high probability, all large excursions are observed in the first $\Theta(n^{\alpha/(\alpha+1)})$ steps, and that the excursions listed in decreasing order of length converge as well.
-
5. By adding extra randomness and making some vertex identifications, one can modify the forest encoded by $\tilde{S}^n$ to yield a multigraph that is equal in law to the graph created by the configuration model, and these modifications behave well under rescaling the graph and taking limits.
-
6. Finally, the authors show that conditioning on the graph not containing multiple edges and loops does not affect the distribution of the largest components. This follows from an argument adapted from Joseph [Reference Joseph38], which shows that the first loops and multiple edges are sampled far beyond the time scale $\Theta(n^{\alpha/(\alpha+1)})$ , and so their presence or absence cannot affect the scaling limit.
4.3. Adapting the methods in [Reference Conchon-Kerjan and Goldschmidt17] to the critical window
The largest barrier to generalizing the methods in [Reference Conchon-Kerjan and Goldschmidt17] is showing the convergence under rescaling of S, jointly with its height process. The results proved in Section 3 allow us to do this. After that, it is trivial to extend most of the arguments in [Reference Conchon-Kerjan and Goldschmidt17] to the critical window.
The convergence under rescaling of S is the content of Proposition 4. We then discuss the results in [Reference Conchon-Kerjan and Goldschmidt17] that are not trivially extended to the critical window and need some further justification.
Let $D_1^n,\dots, D_n^n$ be i.i.d. with a degree distribution as specified in 4.1. Recall that the degree distribution depends on both $\lambda$ and n, but that we have dropped the dependency on $\lambda$ in the notation.
We consider the configuration model executed in depth-first order on vertices with degrees $D_1^n,\dots, D_n^n$ . Let $(\hat{D}_1^n,\dots,\hat{D}_n^n)$ denote the degrees in order of discovery, so that $(\hat{D}_1^n,\dots,\hat{D}_n^n)$ is distributed as a size-biased random ordering of $D_1^n,\dots,D_n^n$ . This is defined as follows.
Let $\Sigma$ be a random permutation of $\{1,\dots,n\}$ such that
Then, by Proposition 3.2 of [Reference Conchon-Kerjan and Goldschmidt17],
Now let $0\leq m\leq n$ and $k_1,k_2,\dots,k_m\geq 1$ , and define $\Xi^n_{n-m}$ to be a random variable having the same law as $D^n_{m+1}+\cdots+D^n_{n}$ . Then, for
Proposition 3.2 in [Reference Conchon-Kerjan and Goldschmidt17] yields that for $Z^n_1,\dots,Z^n_n$ i.i.d. random variables with the size-biased degree of $D_1^n$ , i.e.
for any test-function $g\,{:}\,{\mathbb N}^m\rightarrow {\mathbb R},$ we have
that is, $\phi_m^n$ defines a measure change to get from a vector of size-biased distributed random variables to a vector of size-biased ordered random variables. We note that
is the Łukasiewicz path of a forest that is closely related to the depth-first spanning forest of our graph of interest, because it encodes the degrees in order of discovery. Therefore, the existence of the measure change motivates the study of the limit under rescaling of
and its corresponding height process. This is the content of the following proposition.
Proposition 4. Let L be a spectrally positive $\alpha$ -stable Lévy process with Lévy measure $\pi(dx)=\frac{c}{\mu}x^{-(\alpha+1)}dx$ . Then, for any $\lambda\in {\mathbb R}$ , there exists a continuous modification of the height process of $(L_t+\lambda t, t\geq 0)$ , which we will denote by $H^\lambda$ . Moreover, for $H^n$ the height process corresponding to $S^n$ , we have that, as $n\rightarrow \infty$ ,
in ${\mathbb D}({\mathbb R}_+,{\mathbb R})^2$ .
We will use Theorem 2 to prove Proposition 4. We will first study the Laplace transform of $Z_1^n$ , which is the content of the following lemma.
Lemma 9. Define ${\mathcal L}_{Z_1^{n}}(s)={\mathbb E}[\,\!\exp\!({-}\,s Z_1^{n})] $ . Then
as $s\to 0$ .
Proof. Note that
for $s\rightarrow 0$ , where the last equality follows from the Euler–Maclaurin formula, using that ${\mathbb P}( Z_1^{n}= k)\sim \frac{c_n}{\mu_n}k^{-(\alpha+1)}$ as $k\rightarrow \infty$ . Then, because ${\mathbb E}[Z_1^{n} ]=2+\lambda n ^{-\tfrac{\alpha-1}{\alpha+1}}$ , integrating twice gives the result.
Proof of Proposition 4. We will first prove that $S^n$ converges in distribution under rescaling. Set
and
so that
is the Doob–Meyer decomposition of $S^n$ . Observe that
in ${\mathbb D}({\mathbb R}_+,{\mathbb R})$ as $n\to\infty$ .
We claim that for every $t\geq 0$ ,
Firstly, observe that for all $\theta>0$ ,
Recall that $C_{\alpha}=\frac{c\Gamma(2-\alpha)}{\alpha(\alpha-1)}$ , and set $C^{(n)}=\frac{c_n\Gamma(2-\alpha)}{\alpha(\alpha-1)}$ , so that $C^{(n)}\to C_\alpha$ as $n\to\infty$ . We will show that for every $\theta>0$ ,
as $n\rightarrow \infty$ , which will prove the claim.
Note that
Then, Lemma 9 implies that
as $s\rightarrow 0$ . Plugging this into (26), we find that as $n\rightarrow \infty$ ,
which proves (25).
Now, using [Reference Kallenberg39, Theorem 16.14], we may deduce that as $n\rightarrow \infty$ ,
in ${\mathbb D}({\mathbb R}_+,{\mathbb R})$ .
In order to also obtain the convergence of the height process under rescaling, we note that for $\lambda\leq 0$ , we can directly apply [Reference Duquesne and Le Gall24, Theorems 1.4.3 and 2.2.1], stated in this work as Theorem 1. In the case of $\lambda>0$ , we apply Theorem 2. In both results, we use the scaling parameters $p=n^{1/\alpha+1}$ and $\gamma_p=n^{\tfrac{\alpha-1}{\alpha+1}}$ . The conditions of the theorems then follow directly from our assumptions on the degree distributions and (27). This implies the existence of a continuous modification of the height process and the claimed convergence.
We will now prove that in the cases we consider, $\phi^n_m$ behaves well under rescaling. This is the content of the following proposition, which is a generalization of the proof of [Reference Conchon-Kerjan and Goldschmidt17, Proposition 4.3].
Proposition 5. Set
Then
as $n\rightarrow \infty$ , and the sequence $\{\phi(n,t), n\in{\mathbb N}\}$ is uniformly integrable.
The proof will follow the structure of the proof of [Reference Conchon-Kerjan and Goldschmidt17, Proposition 4.3], but we will need to adapt the technical lemmas presented there to our more general setting.
Proof. The following technical lemmas need justification in the more general setting:
-
For $\lambda=0$ and a degree distribution that does not depend on n, for any $t\geq 0$ , by [Reference Conchon-Kerjan and Goldschmidt17, Lemma 4.4] it holds that, as $n\to\infty$ ,
$$\frac{1}{n}\sum\limits_{k=0}^{\lfloor tn^{{\alpha/(\alpha+1)}}\rfloor -1} S^n(k) \xrightarrow{d} \int_0^tL_sds.$$Using the continuous mapping theorem (see e.g. [Reference Durrett27, Theorem 3.2.4]), we find that for general $\lambda$ and for the degree distribution depending on n, for any $t\geq 0$ ,(28) \begin{equation}\frac{1}{n}\sum\limits_{k=0}^{\lfloor tn^{{\alpha/(\alpha+1)}}\rfloor -1} S^n(k) \xrightarrow{d} \int_0^tL_sds+\frac{\lambda t^2}{2}.\end{equation} -
Define ${\mathcal L}_{D_1^n}(s)\,{:\!=}\,{\mathbb E}[\,\!\exp\!({-}\,sD_1^{n})]$ . Then [Reference Conchon-Kerjan and Goldschmidt17, Lemma 4.5a] and the argument thereafter state that for $\lambda=0$ and a degree distribution that does not depend on n,
\begin{align*}{\mathcal L}_{D_1^n}(s)&=1-\mu_ns+\mu_ns^2-\frac{C_{\alpha}}{\alpha+1}s^{\alpha+1}+o(s^{\alpha+1})\\&=\exp\!\left({-}\,\mu_n s + \frac{\mu_n(2-\mu_n)}{2}s^2-\frac{C_{\alpha}}{\alpha+1}s^{\alpha+1}+o(s^{\alpha+1})\right).\end{align*}In our set-up, we find, similarly to how we obtained ${\mathcal K}_{n}^{\prime\prime}(s)$ , that$${\mathcal L}_{D_1^n}^{\prime\prime\prime}(s)=-c\Gamma(2-\alpha)s^{\alpha-2}+o(s^{\alpha-2})$$as $s\rightarrow 0$ , and using ${\mathbb E}[D_1^{n}]=\mu_n$ and ${\mathbb E} \left[(D_1^{n})^2\right]=\left(2+\lambda n ^{-\tfrac{\alpha-1}{\alpha+1}}\right) \mu_n$ , we get, by integrating three times, that(29) \begin{align}\begin{split}{\mathcal L}_{D_1^n}(s)&=1-\mu_ns+\left(1+\frac{\lambda}{2} n^{-\tfrac{\alpha-1}{\alpha+1}}\right)\mu_ns^2-\frac{C^{(n)}}{\alpha+1}s^{\alpha+1}+o(s^{\alpha+1})\\&=\exp\!\left({-}\,\mu_n s + \frac{\mu_n(2+\lambda n ^{-\tfrac{\alpha-1}{\alpha+1}}-\mu_n)}{2}s^2-\frac{C^{(n)}}{\alpha+1}s^{\alpha+1}+o(s^{\alpha+1})\right)\end{split}\end{align}as $s\rightarrow 0$ . -
For $\lambda=0$ and a degree distribution that does not depend on n, for $m=\lfloor tn^{\alpha/(\alpha+1)}\rfloor$ , by [Reference Conchon-Kerjan and Goldschmidt17, Lemma 4.6] it holds that, as $n\to\infty$ ,
\begin{equation*}\exp \left(m- \frac{ 2+\mu_n}{2\mu_n}\frac{m^2}{n}\right)\left[{\mathcal L}\left(\frac{m}{n\mu_n}\right)\right] ^{n-m} \rightarrow \exp\!\left({-}\, \frac{C_{\alpha}}{(\alpha+1 )\mu^{\alpha+1}}t^{\alpha+1}\right).\end{equation*}By (29) we straightforwardly obtain that, in our set-up, as $n\rightarrow \infty$ ,(30) \begin{equation}\exp \left(m- \frac{ 2+\mu_n}{2\mu_n}\frac{m^2}{n}\right)\left[{\mathcal L}\left(\frac{m}{n\mu_n}\right)\right] ^{n-m} \rightarrow \exp\!\left({-}\, \frac{C_{\alpha}}{(\alpha+1 )\mu^{\alpha+1}}t^{\alpha+1}+\frac{\lambda t^2}{2\mu}\right).\end{equation} -
For $\lambda=0$ and a degree distribution that does not depend on n, for $s(0)=0$ and $s(i)=\sum_{j=1}^i (k_j-2)$ , for $i\geq 1$ , by [Reference Conchon-Kerjan and Goldschmidt17, Lemma 4.7] it holds that
$$\phi_m^{n}(k_1,\dots,k_m)\geq \exp\!\left(\frac{1}{n\mu_n}\sum\limits_{i=0}^{m}(s(i)-s(m))-\frac{C_\alpha}{(\alpha+1 )\mu^{\alpha+1}}t^{\alpha+1} \right)(1+o(1)) .$$Adapting the proof to our set-up, using (30), we find that for $s(0)=0$ and $s(i)=\sum_{j=1}^i (k_j-2)$ , for $i\geq 1$ ,$$\phi_m^{n}(k_1,\dots,k_m)\geq (1+o(1))\exp\!\left(\frac{1}{n\mu_n}\sum\limits_{i=0}^{m}(s(i)-s(m))-\frac{C_\alpha t^{\alpha+1}}{(\alpha+1 )\mu^{\alpha+1}}+\frac{\lambda t^2}{2\mu}\right) .$$The proof of this can be found in the appendix.
Now we have that
But then, by (27) and (28), since
we get that
We then finish the proof in the same way as the proof of [Reference Conchon-Kerjan and Goldschmidt17, Proposition 3.3] to conclude that
as $n\rightarrow \infty$ , and that the sequence $\{\phi(n,t), n\in{\mathbb N}\}$ is uniformly integrable. The details can be found in the appendix.
Remember that $n^{-1/(\alpha+1)}\left( S^n\left(\lfloor tn^{{\alpha/(\alpha+1)}}\rfloor\right)\!, t\geq 0\right)$ converges in law to $(L_t+\lambda t, t\geq 0)$ as $n\to \infty$ . We can get from the process $\left(S^n\left(\lfloor sn^{{\alpha/(\alpha+1)}}\rfloor\right)\!,0\leq s \leq t\right)$ to the process $\left(\tilde{S}^{n}\left(\lfloor sn^{{\alpha/(\alpha+1)}}\rfloor\right)\!,0\leq s \leq t \right)$ via the measure change $\phi(n,t)$ . The random variable $\phi(n,t)$ converges in law to $\phi(t)$ as $n\to\infty$ . Therefore, we will define the process $(\tilde{K}^{\lambda},\tilde{H}^\lambda)$ via the following measure change. For $t\geq 0$ , for every non-negative integrable functional $F\,{:}\,{\mathbb D}([0,t],{\mathbb R}^2)\to{\mathbb R}$ ,
Proposition 6. We have
in ${\mathbb D}({\mathbb R}_+,{\mathbb R}^2)$ as $n\to\infty$ .
Proof. We want to show that for any $t\geq 0$ and any bounded continuous test function $f\,{:}\,{\mathbb D}([0,t],{\mathbb R}^2) \rightarrow {\mathbb R}$ , for $\tilde{H}^n$ the height process corresponding to $\tilde{S}^n$ ,
as $n\rightarrow \infty$ . Using our measure change, this is equivalent to showing that for any $t\geq 0$ and any bounded continuous test function $f\,{:}\,{\mathbb D}([0,t],{\mathbb R}^2)\rightarrow {\mathbb R}$ ,
We now finish as in the proof of [Reference Conchon-Kerjan and Goldschmidt17, Theorem 4.1] to obtain the result.
The following proposition characterizes the law of $\tilde{K}^\lambda$ .
Proposition 7. For $\tilde{K}^\lambda(t)$ as defined in (31), for $\theta>0$ ,
The proof can be found in the appendix.
Proof of Theorem 9. Given Proposition 6, the rest of the proof is completely analogous to the proof of Theorem 1.1 in [Reference Conchon-Kerjan and Goldschmidt17]. Proposition 7 characterizes the law of the encoding process of the components of the limit object.
Appendix A. Proofs of technical results
Proof of Lemma 4. First note that since f and g are increasing, the function given by $\left(\inf \{s\geq 0\,{:}\,f(t)<g(s)\},t \geq 0 \right)$ is also increasing, and so in particular it has limits from the left and from the right at every point of its domain. Fix $t\geq 0$ . Suppose that
Then we must have that
-
(1) there is an $\tilde{s}$ such that $f(t)=g(\tilde{s})$ , and
-
(2) $f(q)<f(t)$ for all $q<t$ .
It follows that
But then, since g is strictly increasing,
so we must have
We also need to show that
Fix $\epsilon>0$ . Suppose $\inf\{s\geq 0\,{:}\,f(t)<g(s)\}=\tilde{s}$ , which implies that $f(t)<g(\tilde{s}+\epsilon)$ . Then, as $q\downarrow t$ , we have $f(q)\downarrow f(t)$ , so for $q>t$ small enough, $f(q)<g(\tilde{s}+\epsilon)$ . Hence,
which proves that
Therefore, $\left(\inf \{s\geq 0\,{:}\,f(t)<g(s)\},t \geq 0 \right)$ is continuous.
By Proposition 3.6.5 in Ethier and Kurtz [Reference Ethier and Kurtz29], proving
in ${\mathbb D}({\mathbb R}_+,{\mathbb R})$ as $n\to\infty$ is then equivalent to showing that for all $t\in {\mathbb R}_+$ , and for all $(t_n)_{n\geq 0}$ in ${\mathbb R}_+$ such that $t_n\to t$ , we have
Suppose $\inf\{s\geq 0\,{:}\,f(t)<g(s)\}=\tilde{s}$ . Fix $\epsilon>0$ and $(t_n)_{n\geq 0}$ in ${\mathbb R}_+$ such that $t_n\to t$ . We will first show that for n large enough,
By the definition of $\tilde{s}$ and monotonicity, we have that $f(t)<g(\tilde{s}+\epsilon/2)$ . Since g is strictly increasing, we have that there is a $\delta>0$ such that $g(\tilde{s}+\epsilon/2)=f(t)+\delta$ . Moreover, since $f_n\to f$ in ${\mathbb D}({\mathbb R}_+,{\mathbb R})$ as $n\to\infty$ and f is continuous, $f_n(t_n)\to f(t)$ , so we may pick n large enough so that
Since $g_n\to g$ in ${\mathbb D}({\mathbb R}_+,{\mathbb R})$ , for n large enough there exists a monotone bijection $\lambda_n\,{:}\,[0,\tilde{s}+2\epsilon]\to [0,\tilde{s}+2\epsilon]$ such that
and
Hence,
and
for $s=\tilde{s}+3\epsilon/4$ . Hence, for n large enough,
We now want to show that for n large enough,
Fix $s<\tilde{s}-\epsilon$ . We will be done if we can show that $f_n(t_n)\geq g_n(s)$ . Since g is strictly increasing, we know that there exists a $\delta>0$ such that $g(\tilde{s}-\epsilon/2)+\delta =g(\tilde{s}-\epsilon/4)$ . Also, by the definition of $\tilde{s}$ , we have $f(t)\geq g(\tilde{s}-\epsilon/4)$ . Pick n large enough that there exists a monotone bijection $\lambda_n\,{:}\,[0,\tilde{s}+2\epsilon]\to [0,\tilde{s}+2\epsilon]$ such that
and
and such that
Then
which proves the statement.
Finally we show that for $(\epsilon_n)_{n\geq 0}$ such that $\epsilon_n\downarrow 0$ ,
in ${\mathbb D}({\mathbb R}_+,{\mathbb R})$ as $n\to\infty$ . Fix $t\in {\mathbb R}_+$ , $t_n\to t$ , and $\epsilon>0$ . We need to show that
First, note that
which is smaller than $\tilde{s}+\epsilon$ for n large enough by previous results. Moreover, note that for $s\leq \tilde{s}-\epsilon$ ,
which is larger than $g_n(s)$ for n large enough by previous results, since $t_n-\epsilon_n(\tilde{s}-\epsilon)\to t $ . Hence,
for n large enough, which concludes the proof.
We will now prove two technical lemmas needed for the proof of Proposition 5.
Lemma 10. For $m=\lfloor t n^{\alpha/(\alpha+1)}\rfloor$ , for
$s(0)=0$ and $s(i)=\sum_{j=1}^i (k_j-2)$ , for $i\geq 1$ , we have that
The arguments presented are an adaption of the proof of [Reference Conchon-Kerjan and Goldschmidt17, Lemma 4.7].
Proof. We can write
Then, since $\log(1+x)\leq x$ for all $x\in ({-}\,1,\infty)$ , and there is a $C>0$ such that for all $1\leq i \leq m-1$ , $\log(1-i/n)\geq -i/n-Cm^2/n^2$ , we have that
Note that by the definition of m, $m^3/n^2=\Theta\left(n^{(\alpha-2)/(\alpha+1)}\right)=o(1)$ , so the final exponent tends to 1 as $n\to \infty$ . Then by (30), which states that as $n\rightarrow \infty$ ,
the desired result follows.
Furthermore, recall that
and
Lemma 11. As $n\to \infty$ ,
and $\{\phi(n,t),n\in{\mathbb N}\}$ is uniformly integrable.
The arguments presented are an adaptation of the proof of [Reference Conchon-Kerjan and Goldschmidt17, Proposition 4.3].
Proof. Recall that $S^n(k)=\sum_{i=1}^k(Z^n_i-2).$ By the statement proved above, we have that
Then, by Theorem 4 and (28), we get that
Hence, we get that
and the right-hand side equals $\phi(t)$ , which has mean 1 by [Reference Conchon-Kerjan and Goldschmidt17, Proposition 3.2]. Also, ${\mathbb E}[\phi(n,t)]=1$ . Then, by [Reference Conchon-Kerjan and Goldschmidt17, Lemma 4.8], we must have that
and $\{\phi(n,t),n\in{\mathbb N}\}$ is uniformly integrable.
Proof of Proposition 7. Let $\tilde{K}^\lambda_t$ be defined as in (31): for $t\geq 0$ , for every non-negative integrable functional $F\,{:}\,{\mathbb D}([0,t],{\mathbb R}^2)\to{\mathbb R}$ ,
We want to show that
The proof will be an adaptation of the proof of [Reference Conchon-Kerjan and Goldschmidt17, Proposition 6.2]. As before, let L be the spectrally positive $\alpha$ -stable Lévy process having Lévy measure $\pi(dx)=\frac{c}{\mu}x^{-(\alpha+1)}dx$ and Laplace transform
Let $X_t$ be the process with Laplace transform
and let
Set
We claim that
As in [Reference Conchon-Kerjan and Goldschmidt17], decomposing $\pi$ gives that
so that
Let $0=t_0<t_1<\cdots<t_m=t$ and let $\theta_1,\dots,\theta_m\in {\mathbb R}_+$ . Then, since X has independent increments, by the argument as presented above,
where we use the fact that L also has independent increments and perform integration by parts. This proves the statement.
Acknowledgements
The author would like to thank Christina Goldschmidt for many productive meetings. She would also like to thank Matthias Winkel for helpful input in the early stages of this project, Thomas Duquesne for pointing out interesting literature, and Thomas Hughes for careful proofreading. Finally, she would like to thank an anonymous referee for their diligent reading of the paper and for their useful comments and suggestions.
Funding information
The author was funded by a Clarendon Scholarship and a CRM–ISM Postdoctoral fellowship.
Competing interests
There were no competing interests to declare which arose during the preparation or publication process of this article.