# On the structure of genealogical trees associated with explosive Crump-Mode-
Jagers branching processes

T. Iyer111Weierstrass Institute for Applied Analysis and Stochastics,
Mohrenstrasse 39, 10117 Berlin, Germany. & B. Lodewijks222University of
Augsburg, Universitätsstraße 14, 86159 Augsburg, Germany.

(November 27, 2023)

###### Abstract

We study the structure of genealogical trees associated with explosive Crump-
Mode-Jagers branching processes (stopped at the explosion time), proving
criteria for the associated tree to contain a node of infinite degree (a
_star_) or an infinite path. Next, we provide uniqueness criteria under which
with probability $1$ there exists exactly one of a unique star or a unique
infinite path. Under the latter uniqueness criteria we also provide an example
where, with strictly positive probability less than $1$, there exists a unique
star in the model. We thus illustrate that this probability is not restricted
to being $0$ or $1$. Moreover, we provide structure theorems when there is a
star, where we prove that certain trees appear as sub-trees in the tree
infinitely often. We apply our results to a general discrete evolving tree
model, named _explosive recursive trees with fitness_. As a particular case,
we study a family of _super-linear preferential attachment models with
fitness_. For these models, we derive phase transitions in the model
parameters in three different examples, leading to either exactly one star
with probability $1$ or one infinite path with probability $1$, with every
node having finite degree. Furthermore, we highlight examples where sub-trees
$T$ of _arbitrary_ size can appear infinitely often; behaviour that is
markedly distinct from super-linear preferential attachment models studied in
the literature so far.

Keywords: Explosive Crump-Mode-Jagers branching processes, super-linear
preferential attachment, preferential attachment with fitness, random
recursive trees, condensation.

AMS Subject Classification 2010: 60J80, 90B15, 05C80.

###### Contents

  1. 1 Introduction
    1. 1.1 Random recursive trees with fitness
    2. 1.2 Overview of our contribution and structure
      1. 1.2.1 Structure of the paper
    3. 1.3 Notation and preliminaries
  2. 2 Statements of main results
    1. 2.1 Global assumptions
    2. 2.2 Sufficient criteria for a star
    3. 2.3 Sufficient criteria for an infinite path and structural results in the star regime
    4. 2.4 Uniqueness conditions related to the existence of a star or an infinite path
    5. 2.5 Proof techniques and relation to existing literature
  3. 3 Examples of applications and an open problem
    1. 3.1 The structure of explosive recursive trees with fitness
      1. 3.1.1 The star/path transition in explosive recursive trees with fitness
      2. 3.1.2 Sub-trees in explosive recursive trees with fitness when there is a star
    2. 3.2 Phase transitions in specific models of explosive recursive trees with fitness
      1. 3.2.1 Connection to existing literature: super-linear preferential attachment
      2. 3.2.2 Assumptions for the fitness function and vertex-weight distribution
      3. 3.2.3 Phase transitions for super-linear preferential attachment models with fitness
      4. 3.2.4 Discussion related to Theorem 3.21: the super-linear case
    3. 3.3 Proof techniques
    4. 3.4 Open problem
  4. 4 Proofs of main results
    1. 4.1 Sufficient criteria for a star
      1. 4.1.1 Proof of Theorem 2.5
    2. 4.2 Sufficient criteria for an infinite path and structural results in the star regime
      1. 4.2.1 Proof of Theorem 2.8
      2. 4.2.2 Proof of Theorem 2.10
    3. 4.3 Uniqueness conditions related to the existence of a star or an infinite path
      1. 4.3.1 Proof of Theorem 2.12
  5. 5 Proofs for applications of main results
    1. 5.1 Preliminary results and tools
    2. 5.2 Structure theorems related to explosive recursive trees
      1. 5.2.1 Proof of Theorem 3.4
      2. 5.2.2 Proof of Theorem 3.7
    3. 5.3 Possibility for both a star and infinite path to occur with positive probability
      1. 5.3.1 Proof of Theorem 2.15
  6. 6 Examples of phase transitions in specific models of recursive trees with fitness
    1. 6.1 Phase transitions for the emergence of an infinite star or path: proof of Theorem 3.16
      1. 6.1.1 Conditions for an infinite star: Item 1 of Theorem 3.4.
      2. 6.1.2 Conditions for an infinite path, Assumption 2.6.
      3. 6.1.3 Proofs of Lemmas 6.3 and 6.4
    2. 6.2 Sub-tree counts in specific models of recursive trees with fitness
      1. 6.2.1 Proof of Corollary 3.8
      2. 6.2.2 Proof of Theorem 3.21
  7. A Additional results for other fitness functions
  8. B Verifying conditions for other inter-birth time distributions
    1. B.1 Conditions for an infinite star, Assumption 2.2.
    2. B.2 Conditions for an infinite path, Assumption 2.6.
  9. C Proof of Lemma 6.6

##  1 Introduction

Given a population of an entity moving towards explosion, that is, the
emergence of infinitely many individuals in finite time, what can be said
about the genealogical tree associated with the population at the time of
explosion? On the one hand, an infinite path in the tree may be interpreted as
an infinite line of evolution, with infinitely many ‘variants’ contributing to
the explosion; on the other, a node of infinite degree (which we often call a
_star_) may be interpreted, informally, as the emergence of a ‘dominant
variant’. This is the goal of the present investigation, where as a simplified
model of an evolving population, we use _Crump–Mode–Jagers_ branching
processes.

In a CMJ branching process (named after [17, 35]), an ancestral _root_
individual produces offspring according to a collection of points on the non-
negative real line. Each individual ‘born’ produces offspring according to an
identically distributed collection of points, translated by their birth time
(see Section 1.3 for a more formal description). One is generally interested
in properties of the population as a function of time. Classical work from the
1970s and ’80s related to this model generally deals with the _Malthusian
case_ , which, informally, refers to the fact that the population grows
exponentially in time. These include strong laws of large numbers for
_characteristics_ associated with the process [56], properties of birth times
in the $k$th generation [43], an $x\log{x}$ theorem [59], and numerous other
results, for example [10, 57, 39, 37, 38]; see also the classical books [5,
36]. A number of more recent results are concerned with _asymptotic
fluctuations_ associated with the process in the Malthusian case, see, for
example, [31, 41, 32, 44]. Other results are motivated by applications of
these processes, including M/G/1 queues [28], vaccination and epidemic
modelling [6, 7, 49], and numerous applications to random graphs, see Section
1.1 below.

Far fewer results exist for CMJ branching processes when a Malthusian
parameter does not exist. In a particular case of reinforced branching
process, a _condensation_ phase transition can occur, where non-exponential
growth occurs due to individuals having random weights that influence their
offspring distribution. In this case, a ‘small’ numbers of individuals with
large weight produce larger and larger families, which in turn lead a rate of
growth faster than exponential [19]. In more extreme circumstances,
individuals produce larger and larger families so quickly that the process
explodes in finite time. General criteria for explosion have been provided in
terms of the solution of a functional fixed point equation by Komjáthy [45],
who also extended the necessary and sufficient criteria for explosion in
branching random walks in [1]. We refer the reader to [45] for a more
comprehensive overview of the literature related to explosion in branching
processes. In [11], the authors provide sufficient criteria for _local
explosion_ in closely related growth-fragmentation processes. Meanwhile, more,
sufficient criteria for explosion in CMJ processes are in preparation in [33].

###  1.1 Random recursive trees with fitness

Aside from the applications outlined above, CMJ branching processes are often
involved in the analysis of random graph models, more often, random trees. As
far as the authors are aware, direct applications date back to Pittel [61], in
providing a new proof for the limiting behaviour of the heights of _random
recursive trees_ and _affine preferential attachment trees_ , but the
technique of using continuous-time embeddings to analyse discrete
combinatorial processes is more classical, going back to works of Arthreya and
Karlin [3, 4].

Later, works by, for example [62, 12, 30, 58, 25] showed that CMJ branching
processes can be applied to a large number of growing tree models. A natural
framework of evolving trees, which corresponds to genealogical trees of CMJ
branching processes and encompasses many existing models of recursive trees
(which we refer to as random recursive trees with fitness [34]), posits that
nodes $v$ arrive one at a time, and are assigned a random i.i.d.  _weight_
$W_{v}$ sampled from a measure $\mu$ on an arbitrary measure space
$(S,\mathcal{S})$ (see Definition 3.1). Newly arriving nodes then connect,
with edges directed outwards from the target nodes, with probability
proportional to a general, measurable fitness function $f:\mathbb{N}_{0}\times
S\rightarrow[0,\infty)$ that incorporates information about the current out-
degree of the target, and its weight. A natural quantity of interest in this
model is the proportion of nodes $\widetilde{N}_{k}$ (at the $n$th time-step)
having out-degree $k$. This model may be roughly classified according to the
following conjectured phases [34]:

  1. 1.

The _non-condensation phase:_ There exists $\lambda>0$ such that
$\sum_{j=1}^{\infty}\mathbb{E}\left[\prod_{i=0}^{j-1}\frac{f(i,W)}{f(i,W)+\lambda}\right]=1.$
In this case, if $p_{k}$ denotes the limit of $\widetilde{N}_{k}$, we have
$\sum_{k=0}^{\infty}p_{k}=1$. In other words, all of the mass of edges is
distributed around nodes of _microscopic_ degrees.

  2. 2.

The _condensation phase_ (see [15, 19, 21, 18]): We have
$\sum_{j=1}^{\infty}\mathbb{E}\left[\prod_{i=0}^{j-1}\frac{f(i,W)}{f(i,W)+\lambda}\right]<1$,
for any $\lambda>0$ such that the sum converges. In this case,
$0<\sum_{k=0}^{\infty}p_{k}<1$, so that a positive fraction of ‘mass’ is lost
from the empirical measure to a sub-linear number of nodes of ‘large degrees’.

  3. 3.

The _extreme-condensation phase:_ For any $\lambda>0$ we have
$\sum_{j=1}^{\infty}\mathbb{E}\left[\prod_{i=0}^{j-1}\frac{f(i,W)}{f(i,W)+\lambda}\right]=\infty.$
In this case, $\sum_{k=0}^{\infty}p_{k}=0$, so that all of the ‘mass’ of edges
is concentrated in nodes of ‘large’ degrees.

Part of the goal of this article is to investigate the behaviour of the third
phase above, in the _explosive_ case that

$\sum_{i=0}^{\infty}\frac{1}{f(i,w)}<\infty,\qquad\text{for $\mu$-almost all
$w\in S$.}$ (1.1)

Note that this implies that
$\prod_{i=0}^{\infty}\frac{f(i,W)}{f(i,W)+\lambda}>0$ almost surely, so that
the condition in Phase 3 is satisfied.

In [58], Oliveira and Spencer showed that, in the case $f(i,w)=i^{p}$, with
$1+\frac{1}{k}<p\leq 1+\frac{1}{k-1}$ for some $k\in\mathbb{N}$ (equality only
for $k\geq 2$), the infinite tree associated with this process is somehow
extreme: it contains a single node of infinite degree, connected to infinitely
many children with an associated sub-tree of size at most $k$, and only
finitely many with an associated sub-tree of size $k+1$ or larger. This paper
uses the fact that the associated CMJ branching process is _explosive_ , a
technique also exploited in similar works related to ‘balls-in-bins’ processes
[55]. Related work by Arthreya [2, Theorem 2.1] attempts to prove that,
according to a certain summability condition, either every node in the
infinite tree has finite degree, or with positive probability there exists a
single node such that all but finitely many new nodes connect to this node.
However, there is a mistake here, in that [2, Theorem 2.1b] should really
state: the probability that there exists a single node such that all but
finitely many new-coming nodes connect to this node is zero (indeed, note that
[2, Corollary 2.2] directly contradicts [58]). Nevertheless, the associated
summability condition and result in this paper is interesting, and motivates
the question of whether there is a critical condition that guarantees the
existence of a node of infinite degree in the infinite tree, or every node
having finite degree, cf. Theorem 3.4, below.

A related question is whether or not, in the associated _recursive tree with
fitness_ model, the index associated with the node of maximal degree is fixed
after some finite time, or changes infinitely often, that is, whether or not
there is a _persistent hub_. A unique node of infinite degree in the infinite
tree associated with the model thus implies the existence of such a hub. In a
slightly different model of evolving graphs, when $f(i,w)=g(i)$ with $g$ being
a _concave_ sub-linear function, one of the results of Dereich and Mörters
[20] shows that a persistent hub emerges if and only if
$\sum_{i=1}^{\infty}g(i)^{-2}<\infty$. In the recursive tree model described
above, Galashin [23] proved that, if $f(i,w)=g(i)$, with $g$ _convex_ and
unbounded, a persistent hub always appears. This has been extended to a much
wider range of functions $g$, independent of the weight $w$, by Banerjee and
Bhamidi in [8].

When weights are added, however, in the sense that $f(i,w)$ may depend on $w$,
a different picture emerges. Suppose that $w$ takes values in $[0,\infty)$. In
the case $f(i,w)=w(i+1)$, under a particular set of conditions leading to the
_condensation phase_ (Item 2 above), in [19] the authors show that there is no
persistent hub, and the size of the node of maximal degree grows sub-linearly
in the size of the tree. In the case $f(i,w)=i+w$ or $f(i,w)=w$, when the
weights $w$ are sampled according to certain classes of distributions, in [53,
63] and [52, 51], respectively, the authors provide critical criteria
depending on the parameters of the weight distribution, for the existence, or
non-existence, of a persistent hub. A number of other particular models of so
called _preferential attachment with fitness_ have been studied, see, for
example, [26, 42, 22], and related works regarding local weak limits of
preferential attachment type models [9, 50, 24].

###  1.2 Overview of our contribution and structure

In this paper we provide general sufficient conditions for the genealogical
tree associated with an explosive CMJ branching process to contain a node of
infinite degree or an infinite path at the explosion time (in Theorems 2.5 and
2.8, respectively). When there is a node of infinite degree, we provide
criteria for one to see a fixed tree as a sub-tree of a child of that node
either infinitely often, or finitely often, in Theorem 2.10. We also prove
uniqueness criteria in Theorem 2.12, under which there almost surely exists a
unique node of infinite degree or a unique infinite path. Under the conditions
of the uniqueness theorem, we provide a counter-example in Theorem 2.15, where
the events that there is a node of infinite degree, or an infinite path, both
have positive probability, less than $1$. Finally, in Theorems 3.4, 3.7, and
Corollary 3.8 we apply our results to the recursive tree with fitness model
and prove phase transitions in three particular models in Theorems 3.16 and
3.21. We encourage the reader more interested in this discrete model to refer
to these results first.

The question of whether the genealogical tree of an explosive CMJ branching
process contains an infinite path or a node of infinite degree has not been
investigated in this level of generality previously. Our techniques involve
significant improvements of those of [58] (see also Sections 2.5 and 3.3), and
thus allow us to greatly extend the picture associated with the general
recursive tree with fitness model. Intriguingly, our results show that when
there is a unique node of infinite degree in the infinite tree associated with
the model, in many particular cases there exist children of the node of
infinite degree that have arbitrarily large, but finite, degree (or even an
arbitrarily large, but finite, number of descendants). Previous comments in
the literature seem to indicate that it was believed that when there is an
infinite degree node, the degrees of all other nodes are bounded, see [8,
Section 3]. Finally, we remark that the phase transitions related to the
emergence of a node of infinite degree are reminiscent of a different notion
of _condensation_ in conditioned Bienaymé-Galton-Watson trees [40].

####  1.2.1 Structure of the paper

The paper is structured in the following way. Below, in Section 1.3, we
introduce a formal description of the model and the notation we use in this
paper. Section 2 states the main results, which are most general and require
certain assumptions on the inter-birth time distribution. Section 3 then
discusses the particular example of exponentially distributed inter-birth
times and how this relates to a family of discrete tree models coined
_recursive trees with fitness_. Here, we derive sufficient conditions such
that the assumptions used for the main results are satisfied. Moreover, when
considering certain sub-families of recursive trees with fitness, we prove
more precise results in terms of phase diagrams for the existence of either
unique infinite-degree nodes or unique infinite paths. As mentioned above, we
encourage the reader more interested in results related to the discrete
recursive tree model (which is also less abstract), to refer to the results of
Section 3.1 first, before reading the section below.

Aside for a few exceptions, Section 4 proves the main results of Section 2,
Section 5 proves the most general results of Section 3, and Section 6 proves
the particular examples of Section 3. Finally, we consider a number of other
models in Appendix A and B, showing that the assumptions subject to which the
main results hold are valid more broadly.

###  1.3 Notation and preliminaries

In this paper, we consider properties of the genealogical trees associated
with Crump-Mode-Jagers branching processes; a tree-valued stochastic process
$(\mathscr{T}_{t})_{t\geq 0}$ which one may regard as the genealogical tree
representing a population evolving over time. The goal then, is to define a
state space of individuals, in this setting, the infinite _Ulam-Harris_ tree
of potential individuals associated with a common ancestor, _birth times_
$\mathcal{B}(u)$ associated with individuals, which themselves are encoded by
a random function $(X,W)$, and then define $\mathscr{T}_{t}$ as the set of
individuals born up to time $t$. Note that the notation we use is slightly
different to the common notation regarding CMJ branching processes, see Remark
1.1 further below.

First, we generally use $\mathbb{N}:=\\{1,2,\ldots\\}$,
$\mathbb{N}_{0}:=\mathbb{N}\cup\\{0\\}$ and for $n\in\mathbb{N}$ we let
$[n]:=\\{1,\ldots,n\\}$. We consider _individuals_ in the process as being
labelled by elements of the infinite _Ulam-Harris_ tree
$\mathcal{U}_{\infty}:=\bigcup_{n\geq 0}\mathbb{N}^{n}$; where
$\mathbb{N}^{0}:=\\{\varnothing\\}$ contains a single element $\varnothing$
which we call the _root_. We denote elements $u\in\mathcal{U}_{\infty}$ as a
tuple, so that, if $u=(u_{1},\ldots,u_{k})\in\mathbb{N}^{k},k\geq 1$, we write
$u=u_{1}\cdots u_{k}$. An individual $u=u_{1}u_{2}\cdots u_{k}$ is to be
interpreted recursively as the $u_{k}$th child of the individual $u_{1}\cdots
u_{k-1}$; for example, $1,2,\ldots$ represent the offspring of $\varnothing$.
Suppose that $(\Omega,\Sigma,\mathbb{P})$ is a complete probability space and
$(S,\mathcal{S})$ is a measure space. We also equip $\mathcal{U}_{\infty}$
with the sigma algebra generated by singleton sets. Then, we fix a random
mappings $X:\Omega\times\mathcal{U}_{\infty}\rightarrow[0,\infty]$,
$W:\Omega\times\mathcal{U}_{\infty}\rightarrow S$, and define
$(X,W):\Omega\times\mathcal{U}_{\infty}\rightarrow[0,\infty]\times S$, so that
$u\mapsto(X(u),W_{u})$. In general, for $u\in\mathcal{U}_{\infty}$ and
$j\in\mathbb{N}$, one interprets $W_{u}$ as a ‘weight’ associated with $u$,
and $X(uj)$ the waiting time between the birth of the $(j-1)$th and $j$th
_child_ of $u$.

We introduce some notation related to elements $u\in\mathcal{U}_{\infty}$: we
use $|\cdot|$ to measure the _length_ of a tuple $u$, so that, if
$u=\varnothing$ we set $|u|=0$, whilst if $u=u_{1}\cdots u_{k}$ then $|u|=k$.
If, for some $x\in\mathcal{U}_{\infty}$, we have $x=uv$, we say $u$ is a
_ancestor_ of $x$. We introduce a notation to refer to ancestors: given
$\ell\leq|u|$, we set $u_{|_{\ell}}:=u_{1}\cdots u_{\ell}$. It will be helpful
to equip $\mathcal{U}_{\infty}$ with the lexicographic total order $\leq_{L}$:
given elements $u,v$ we say $u\leq_{L}v$ if either $u$ is a ancestor of $v$,
or $u_{\ell}<v_{\ell}$ where $\ell=\min\left\\{i\in\mathbb{N}:u_{i}\neq
v_{i}\right\\}$. We say a subset $T\subset\mathcal{U}_{\infty}$ is a _tree_
if, given that $u\in T$, we also have $u_{|_{\ell}}\in T$, for each
$\ell\leq|u|$. Note that any such trees can be viewed as graphs in the natural
way, connecting nodes to their children.

Now, we use the values of $X$ to associate _birth times_ $\mathcal{B}(u)$ to
individuals $u\in\mathcal{U}_{\infty}$. In particular, we define
$\mathcal{B}:\Omega\times\mathcal{U}_{\infty}\rightarrow[0,\infty]$
recursively as follows:

$\mathcal{B}(\varnothing):=0\quad\text{and for
$u\in\mathcal{U}_{\infty},i\in\mathbb{N}$,}\quad\mathcal{B}(ui):=\mathcal{B}(u)+\sum_{j=1}^{i}X(uj).$

Consequentially, a value of $X(ui)=\infty$ indicates that the individual $u$
has stopped producing offspring, and does not produce $i$ children or more.

Finally, we set
$\mathscr{T}_{t}=\\{x\in\mathcal{U}_{\infty}:\mathcal{B}(x)\leq t\\}$ and
identify for each $t\geq 0$, $\mathscr{T}_{t}$ as the _genealogical tree_ of
individuals with birth time at most $t$. Again we emphasise that one may think
of this, intuitively, as the set of all individuals, originating from a common
ancestor, that have been born by time $t$. More formally, we identify the
process with $(\widetilde{\mathscr{T}}_{t})_{t\geq 0}$; a measurable mapping
$\Omega\times[0,\infty)\times\mathcal{U}_{\infty}\rightarrow[0,\infty]$. Then,
if $u\in\mathscr{T}_{t}$, we set
$\widetilde{\mathscr{T}}_{t}(u)=\mathcal{B}(u)$, and otherwise, set
$\widetilde{\mathscr{T}}_{t}(u)=\infty$. In addition, we set
$\mathcal{W}_{t}=\\{(x,\mathcal{B}(x),W_{x}):x\in\mathscr{T}_{t}\\}$, so that
$(\mathcal{W}_{t})_{t\geq 0}$ also incorporates information about the random
‘weights’ of individuals in the tree $\mathscr{T}_{t}$. We let
$(\mathcal{F}_{t})_{t\geq 0}$ and $(\mathscr{W}_{t})_{t\geq 0}$ denote the
filtrations generated by $(\widetilde{\mathscr{T}}_{t})_{t\geq 0}$ and
$(\mathcal{W}_{t})_{t\geq 0}$, respectively; and by taking their completions
if necessary, assume that both $\mathcal{F}_{t}$ and $\mathscr{W}_{t}$ are
complete. By abuse of notation, we use the symbol $\mathscr{T}_{t}$ to refer
to $\widetilde{\mathscr{T}}_{t}$, the set $\mathscr{T}_{t}$, and the graph
associated with $\mathscr{T}_{t}$ where the vertex set is $\mathscr{T}_{t}$
and edges connect elements to their children. For a given choice of $X,W$, we
say $(\mathscr{T}_{t})_{t\geq 0}$ is the genealogical tree process associated
with an $(X,W)$-_Crump-Mode-Jagers_ branching process; often, we refer to
$(\mathscr{T}_{t})_{t\geq 0}$ directly as an $(X,W)$-_Crump-Mode-Jagers_
branching process, viewed as a stochastic process in $t$, adapted to its
natural filtration $(\mathscr{F}_{t})_{t\geq 0}$.333Note that distinct
functions $(X,W)$, $(X^{\prime},W^{\prime})$ may lead to the same tree, if,
for example $X(ui)=X^{\prime}(ui)=\infty$, but $X(u(i+1))\neq
X^{\prime}(u(i+1))$, but this is only a formal technicality, which we can
overcome by viewing $(X,W)$ as an appropriate _equivalence class_ of
functions.

For $u\in\mathcal{U}_{\infty}$, we let $\mathcal{P}_{i}(u)$ denote the time,
after the _birth_ of $u$, required for $u$ to produce $i$ offspring. That is,

$\mathcal{P}_{i}(u):=\sum_{j=1}^{i}X(uj)\quad\text{and}\quad\mathcal{P}(u):=\mathcal{P}_{\infty}(u)=\sum_{j=1}^{\infty}X(uj).$
(1.2)

Note that, as a result of this definition, for any
$u,v\in\mathcal{U}_{\infty}$ with $u=u_{1}\cdots u_{k}$ and $v=v_{1}\cdots
v_{\ell}$, if we set $uv_{0}:=u$ we have

$\mathcal{B}(uv)-\mathcal{B}(u)=\sum_{j=0}^{\ell-1}\left(\mathcal{P}_{v_{j+1}}(uv_{|_{j}})\right).$
(1.3)

It will also be beneficial to extend the notation $\mathcal{P}$ to arbitrary
trees $T$: for $T\subseteq\mathcal{U}_{\infty}$, we define

$\mathcal{P}_{T}(u):=\inf\left\\{t>0:\mathcal{B}(uv)-\mathcal{B}(u)<t\text{
for all }v\in T\right\\}.$ (1.4)

Thus, with the above notation $\mathcal{P}_{i}(u)=\mathcal{P}_{[i]}(u)$. We
also set $\mathcal{P}_{T}:=\mathcal{P}_{T}(\varnothing)$,
$\mathcal{P}_{i}=\mathcal{P}_{i}(\varnothing)$, and
$\mathcal{P}:=\mathcal{P}(\varnothing)$.

We generally assume a dependence between the values
$(\mathcal{P}_{i}(u))_{i\in\mathbb{N}\cup\\{\infty\\}}$ and $W_{u}$. However,
for brevity of notation, we often do not explicitly indicate this dependence.
We use the notation $\mathcal{P}_{i}$ and $\mathcal{P}$ to denote generic
copies of random variables distributed like $\mathcal{P}_{i}(u)$, and
$\mathcal{P}(u)$ respectively.

For each $u\in\mathcal{U}_{\infty}$ it will be helpful to a have a map
$\xi^{(u)}:\Omega\times[0,\infty]\rightarrow\mathbb{N}$ indicating the number
of children $u$ has produced, more precisely, we define $\xi^{(u)}(t)$ such
that

$\xi^{(u)}(t)=\begin{cases}\sum_{i=1}^{\infty}\mathbf{1}_{\\{\mathcal{P}_{i}(u)\leq
s\\}}&\text{if $t=\mathcal{B}(u)+s,s\in[0,\infty]$;}\\\
0&\text{otherwise.}\end{cases}$

With regards to the process $(\mathscr{T}_{t})_{t\geq 0}$, we define the
stopping times $(\tau_{k})_{k\in\mathbb{N}_{0}}$ such that

$\tau_{k}:=\inf\\{t\geq 0:|\mathscr{T}_{t}|\geq k\\},$

where we adopt the convention that the infimum of the empty set is $\infty$.
One readily verifies that $(|\mathscr{T}_{t}|)_{t\geq 0}$ is right-continuous,
and thus $|\mathscr{T}_{\tau_{k}}|\geq k$. For each $k\in\mathbb{N}$ we define
the tree $\mathcal{T}_{k}$ as the tree consisting of the first $k$ individuals
in $\mathscr{T}_{\tau_{k}}$ ordered by birth time, breaking ties
lexicographically. We call $\tau_{\infty}:=\lim_{k\to\infty}\tau_{k}$ the
_explosion time_ of the process. We also define the tree
$\mathcal{T}_{\infty}:=\bigcup_{k=1}^{\infty}\mathcal{T}_{k}$. Note that it
may be the case that $\left|\mathcal{T}_{\infty}\right|<\infty$; in this case
$\tau_{\infty}=\infty$ and

$\mathcal{T}_{\infty}=\left\\{x\in\mathcal{U}_{\infty}:\mathcal{B}(x)<\infty\right\\},$
(1.5)

and the set on the right-hand side is finite. If
$|\mathcal{T}_{\infty}|<\infty$, we say _extinction_ occurs, otherwise
_survival_ occurs. For a non-negative real-valued random variable $X$ and
$\lambda>0$ we let $\mathcal{M}_{\lambda}(Z),\mathcal{L}_{\lambda}(Z)$ denote
the associated moment generating function and Laplace transform, respectively,
i.e.

$\mathcal{M}_{\lambda}(Z):=\mathbb{E}\left[\mathrm{e}^{\lambda
Z}\right]\quad\text{and}\quad\mathcal{L}_{\lambda}(Z):=\mathbb{E}\left[\mathrm{e}^{-\lambda
Z}\right].$

Moreover, if the random variable $Z$ has, additionally, some dependence on a
random variable $W\in S$, we write

$\mathcal{M}_{\lambda}(Z;W):=\mathbb{E}\left[\mathrm{e}^{\lambda
Z}\Big{|}W\right]\quad\text{and}\quad\mathcal{L}_{\lambda}(Z;W):=\mathbb{E}\left[\mathrm{e}^{-\lambda
Z}\Big{|}W\right].$

In addition, for real valued random variables $Z_{1}$ and $Z_{2}$, we say
$Z_{1}\leq_{S}Z_{2}$, if, for each $a\in\mathbb{R}$

$\mathbb{P}\left(Z_{1}>a\right)\leq\mathbb{P}\left(Z_{2}>a\right).$

Finally, for $r\geq 0$ we use $\operatorname{Exp}\left(r\right)$ to denote the
exponential distribution with parameter $r$.

######  Remark 1.1.

With the more commonly used notation for CMJ branching processes, one assigns
a point process (denoted $\xi^{(u)}$) to each $u\in\mathcal{U}_{\infty}$, and
refers to the points $\sigma^{(u)}_{1}\leq\sigma^{(u)}_{2},\ldots$ associated
with this point process (in the notation used here
$\mathcal{B}(u1),\mathcal{B}(u2),\ldots$). We do not use this framework here,
because, this requires one to be able to write the measure
$\xi^{(u)}=\sum_{i=1}^{\infty}\delta_{\sigma_{i}}$, which requires one to
impose $\sigma$-finiteness assumptions on the point process (see, for example,
[48, Corollary 6.5]). This $\sigma$-finiteness is implied by the classical
Malthusian condition, but, in this general setting, we believe it is easier to
have a framework where one can directly refer to the points
$\mathcal{B}(u1),\mathcal{B}(u2),\ldots$

##  2 Statements of main results

In this paper, we are interested in properties of the infinite tree
$\mathcal{T}_{\infty}$, in particular the question of whether or not this tree
contains an infinite path or a node of infinite degree. This section deals
with results in their most general form: Section 2.1 states some global
assumptions imposed throughout the paper, Section 2.2 deals with criteria for
a node of infinite degree (or star), Section 2.3 deals with criteria for an
infinite path, and structural properties of the tree $\mathcal{T}_{\infty}$
when there is a star, and Section 2.4 deals with uniqueness properties,
providing criteria for a the appearance of a unique star or unique infinite
path (but not both) to appear almost surely. In Theorem 2.15 we also show that
in the regime where there is, almost surely, exactly one of a unique star or
infinite path, either may appear with positive probability. Finally, we
provide an overview of the proof techniques used, and the relation to existing
literature in Section 2.5.

###  2.1 Global assumptions

In general in this paper, we assume that the values of
$(X(uj))_{j\in\mathbb{N}}$ depend on $W_{u}$. We also assume that the
sequences of random variables

$((X(uj))_{j\in\mathbb{N}},W_{u})\quad\text{are i.i.d.\ for different
$u\in\mathcal{U}_{\infty}$};$ (2.1)

although we expect that some of our techniques may carry over to a more
general setting. For a given $w\in\mathcal{S}$, we let
$(X_{w}(uj))_{j\in\mathbb{N}}$ denote a sequence $(X(uj))_{j\in\mathbb{N}}$,
conditionally on the weight $W_{u}=w$. Another common assumption we use
throughout is the following: for any given $w\in S$ and any
$u\in\mathcal{U}_{\infty}$, the sequence of random variables

$(X_{w}(ui))_{i\in\mathbb{N}}\quad\text{is mutually independent.}$ (2.2)

The existence of an explosive $(X,W)$-CMJ process satisfying (2.1) is a
straightforward application of (for example) the Kolmogorov extension theorem
(indeed, this is the classical definition of a CMJ process).

We also generally assume that the event
$\left\\{|\mathcal{T}_{\infty}|=\infty\right\\}$ has positive probability, and

$\mathbb{P}\left(\tau_{\infty}<\infty\,\big{|}\,|\mathcal{T}_{\infty}|=\infty\right)=1.$
(2.3)

That is, the process is almost surely explosive, when conditioned on survival.
In general, we say an event $A$ occurs _almost surely on survival_ if
$\mathbb{P}\left(A\,\big{|}\,|\mathcal{T}_{\infty}|=\infty\right)=1$. In all
statements in this paper referring to an “explosive $(X,W)$-CMJ process”, we
assume it satisfies (2.1) and (2.3).

In this paper, we also rely on the following well-known fact in graph theory.

######  Lemma 2.1 (Kőnig’s Lemma).

Any infinite tree contains a node of infinite degree or an infinite path.

###  2.2 Sufficient criteria for a star

In this subsection, we provide sufficient criteria for the infinite tree
$\mathcal{T}_{\infty}$ to contain an infinite star. Our main assumptions are
as follows.

######  Assumption 2.2.

We have the following conditions.

  1. 1.

There exist non-negative real-valued random variables
$(Y_{n})_{n\in\mathbb{N}_{0}}$ with finite mean such that, for any $w\in S$,

$\sum_{i=n+1}^{\infty}X_{w}(i)\leq_{S}Y_{n}.$ (2.4)

  2. 2.

If we let $\mu_{n}:=\mathbb{E}\left[Y_{n}\right]$, then we also have, for some
$c\in(0,\infty)$,

$\limsup_{n\to\infty}\mathcal{M}_{c\mu^{-1}_{n}}(Y_{n})<\infty.$ (2.5)

Moreover, we assume that $(\mu_{n})_{n\in\mathbb{N}_{0}}$ is non-increasing in
$n$, with $\lim_{n\to\infty}\mu_{n}=0$.

  3. 3.

For each $n\in\mathbb{N}$ and any given $w\in S$, the random variables
$(X_{w}(i))_{i\in\mathbb{N}}$ are mutually independent.

  4. 4.

For each $n\in\mathbb{N}$,

$\displaystyle\sum_{i=n+1}^{\infty}X(i)$ $\displaystyle>0\quad\text{almost
surely},$ (2.6) and additionally, we have
$\displaystyle\mathbb{E}\left[\xi(0)\right]$
$\displaystyle=\mathbb{E}\left[\sup\\{k:X(k)=0\\}\right]<1.$ (2.7)

  5. 5.

With $c$ as appearing in Equation (2.5),

$\sum_{i=1}^{\infty}\mathbb{E}\left[\mathcal{L}_{c\mu^{-1}_{i}}(\mathcal{P}_{i}(\varnothing);W)\right]<\infty.$
(2.8)

######  Remark 2.3.

Note that under Condition 1 of Assumption 2.2, we have
$\mathbb{P}\left(\left|\mathcal{T}_{\infty}\right|=\infty\right)=1$.
$\blacktriangleleft$

######  Remark 2.4.

In Assumption 2.2 we can consider Conditions 1 and 3 as a _uniform
explosivity_ condition: it implies that, for any $u\in\mathcal{U}_{\infty}$
and any $\varepsilon>0$,

$\lim_{L\to\infty}\mathbb{P}\left(\sum_{j=L+1}^{\infty}X_{j}(u)\geq\varepsilon\,\bigg{|}\,X_{1}(u),\ldots,X_{L}(u)\right)=0,$

with the convergence uniform in $X_{1}(u),\ldots,X_{L}(u)$; a fact that is
crucial for Lemma 4.6, and hence the proof of Theorem 2.5, to hold. Condition
4 is there as a technical assumption, used, for example, in Proposition 4.4
and Lemma 4.5. It ensures that $\tau_{k}<\tau_{\infty}$ for each
$k\in\mathbb{N}$. Indeed, if, for example, $\mathbb{E}\left[\xi(0)\right]>1$,
the tree consisting of all the individuals born _instantaneously_ at time $0$
is the genealogical tree of a supercritical Bienaymé-Galton-Watson branching
process. Hence, with positive probability this tree is infinitely large, and
thus there may be no node of infinite degree in this infinite tree. Condition
2 is used to prove the Chernoff type concentration bound in Lemma 4.1 which,
when combined with the summability condition in Condition 5, leads to the
proof of the crucial Proposition 4.3.  $\blacktriangleleft$

The conditions of Assumption 2.2 allow us to formulate the following theorem.

######  Theorem 2.5 (Infinite star).

Under Assumption 2.2, almost surely the infinite tree $\mathcal{T}_{\infty}$
contains a node of infinite degree (i.e. an infinite _star_).

The proof of Theorem 2.5 appears in Section 4.1.

###  2.3 Sufficient criteria for an infinite path and structural results in
the star regime

In this subsection, we provide sufficient criteria for $\mathcal{T}_{\infty}$
to contain an infinite path and whether or not $\mathcal{T}_{\infty}$ contains
infinitely many copies of a fixed tree $T$. We first state the following
assumption.

######  Assumption 2.6.

There exists a collection of numbers $\left\\{\nu^{w}_{n}\in[0,\infty):w\in
S,n\in\mathbb{N}\right\\}$, such that for any $w\in S$,

$\displaystyle\sum_{i=1}^{\infty}\mathbb{P}\left(\mathcal{P}<\nu^{w}_{i}\right)$
$\displaystyle=\infty,$ (2.9) and
$\displaystyle\liminf_{i\to\infty}\mathbb{P}\left(\sum_{j=i+1}^{\infty}X_{w}(j)\geq\nu^{w}_{i}\right)$
$\displaystyle>0.$ (2.10)

######  Remark 2.7.

Assumption 2.6 intuitively states that, conditionally on the weight $w$ of the
root $\varnothing$, infinitely many children $i$ of $\varnothing$ produce an
infinite offspring within time $\nu_{i}^{w}$. On the other hand, the root
takes at least $\nu_{i}^{w}$ amount of time after the birth of its $i$th child
to produce an infinite offspring, with a probability that is bounded from
below, uniformly in $i$. Hence, infinitely many children $i$ explode before
their parent $\varnothing$.  $\blacktriangleleft$

We can then formulate the following theorem.

######  Theorem 2.8 (Infinite path).

Under Assumption 2.6, the tree $\mathcal{T}_{\infty}$ contains an infinite
path almost surely on survival.

The proof of Theorem 2.8 appears in Section 4.2.

Similar criteria to those related to the criteria for an infinite path allow
us to also determine results related to the _structure_ of
$\mathcal{T}_{\infty}$ in the sense that, when we know that
$\mathcal{T}_{\infty}$ contains an infinite star, certain sub-structures
appear infinitely often; others only finitely often. We define
$\mathcal{T}_{\infty}(\downarrow
u):=\left\\{v\in\mathcal{T}_{\infty}:v=uw,\;w\in\mathcal{U}_{\infty}\right\\}$
as the sub-tree in $\mathcal{T}_{\infty}$ rooted at $u$. For a fixed tree $T$
containing $\varnothing$ and $u\in\mathcal{U}_{\infty}$, we define
$uT:=\left\\{uv:v\in T\right\\}$. We say such a tree $T$ is a sub-tree rooted
at $u\in\mathcal{T}_{\infty}$, if, $uT\subseteq\mathcal{T}_{\infty}(\downarrow
u)$. Recalling Equation (1.4) we then have the following set of assumptions.

######  Assumption 2.9.

Let $(\mathscr{T}_{t})_{t\geq 0}$ be an explosive $(X,W)$-CMJ process. For a
given finite tree $T\subseteq\mathcal{U}_{\infty}$ containing $\varnothing$ we
have the following conditions.

  1. 1.

There exists a collection of numbers $\left\\{\nu^{w}_{n}\in[0,\infty):w\in
S,n\in\mathbb{N}_{0}\right\\}$, such that for any $w\in S$,

$\displaystyle\sum_{i=1}^{\infty}\mathbb{P}\left(\mathcal{P}_{T}<\nu^{w}_{i}\right)$
$\displaystyle=\infty,$ (2.11) and
$\displaystyle\liminf_{i\to\infty}\mathbb{P}\left(\sum_{i=j+1}^{\infty}X_{w}(j)\geq\nu^{w}_{i}\right)$
$\displaystyle>0.$ (2.12)

  2. 2.

For any $w\in S$ and with
$(\widetilde{X}_{w}(i),i\in\mathbb{N})\sim(X_{w}(i),i\in\mathbb{N})$,
independent of the process $(\mathscr{T}_{t})_{t\geq 0}$,

$\sum_{i=1}^{\infty}\mathbb{P}\left(\mathcal{P}_{T}<\sum_{j=i+1}^{\infty}\widetilde{X}_{w}(j)\right)<\infty.$
(2.13)

We can then formulate the following theorem.

######  Theorem 2.10 (Sub-tree count).

Let $(\mathscr{T}_{t})_{t\geq 0}$ be an explosive $(X,W)$-CMJ process. Then,
for any finite tree $T\subseteq\mathcal{U}_{\infty}$ containing $\varnothing$:

  1. 1.

If Condition 1 of Assumption 2.9 is satisfied, almost surely, if
$u\in\mathcal{T}_{\infty}$ has infinite degree, $T$ appears infinitely often
as a sub-tree rooted at a child of $u$.

  2. 2.

If Condition 2 of Assumption 2.9 is satisfied, almost surely, if
$u\in\mathcal{T}_{\infty}$ has infinite degree, $T$ appears only finitely
often as a sub-tree of a child of $u$. In particular, if Assumption 2.2 is
satisfied, almost surely, the tree $T$ appears only finitely often as a sub-
tree of $\mathcal{T}_{\infty}$.

The proof of Theorem 2.10 appears in Section 4.2.

###  2.4 Uniqueness conditions related to the existence of a star or an
infinite path

In many cases, we expect $\mathcal{T}_{\infty}$ to contain _exactly one_ node
of infinite degree or _exactly one_ infinite path and also, often expect _co-
existence_ of an infinite path and node of infinite degree to be impossible.
This leads us to the following assumption.

######  Assumption 2.11.

We have the following conditions.

  1. 1.

Condition 4 of Assumption 2.2 is satisfied.

  2. 2.

The distribution of $\mathcal{P}(\varnothing)$ contains no atom on
$[0,\infty)$.

  3. 3.

For some $\varepsilon>0$ and for each $i\in\mathbb{N}$, the distribution of
$\mathcal{B}(i)$ contains no atom on $[0,\varepsilon)$.

We then have the following result.

######  Theorem 2.12 (Unique infinite star or path).

Let $(\mathscr{T}_{t})_{t\geq 0}$ be an explosive $(X,W)$-CMJ process. Then:

  1. 1.

If Conditions 1 and 2 of Assumption 2.11 are satisfied, $\mathcal{T}_{\infty}$
contains at most $1$ node of infinite degree, almost surely.

  2. 2.

If Conditions 1 and 3 of Assumption 2.11 are satisfied, $\mathcal{T}_{\infty}$
contains at most $1$ infinite path, almost surely.

  3. 3.

If all the conditions of Assumption 2.11 are satisfied, almost surely, on
survival, $\mathcal{T}_{\infty}$ contains exactly one of the following: a node
of infinite degree, an infinite path.

The proof of Theorem 2.12 appears in Section 4.3.

######  Remark 2.13.

Though assumed to hold throughout, Theorem 2.12 can be proved without assuming
(2.2). $\blacktriangleleft$

######  Remark 2.14.

A case when the tree $\mathcal{T}_{\infty}$ has more than one infinite path
with positive probability is when _time $0$ explosion_ can occur, i.e. when
$\mathbb{E}\left[\xi(0)\right]>1$, so that $\tau_{\infty}=0$ with positive
probability, and $\mathcal{T}_{\infty}$ is the genealogical tree of a
supercritical Bienaymé-Galton-Watson branching process. This case is ruled out
by Item 2 of Assumption 2.11, which, in particular, implies that $\xi(0)=0$
almost surely.  $\blacktriangleleft$

Given Item 3 of Theorem 2.12, one might expect the event that
$\mathcal{T}_{\infty}$ contains a node of infinite degree to occur with
probability $0$ or $1$: for example, perhaps one might expect this to event to
‘look like’ a tail event, measurable with respect to the tail sigma algebra of
an appropriate filtration. The following theorem shows that this is not
actually the case in full generality.

######  Theorem 2.15.

There exists an explosive $(X,W)$-CMJ process satisfying the conditions of
Assumption 2.11 such that

$\mathbb{P}\left(\mathcal{T}_{\infty}\text{ contains a node of infinite degree
}\right)\in(0,1).$ (2.14)

Note that, applying Item 3 of Theorem 2.12, Equation (2.14) also implies that
for such an explosive $(X,W)$-CMJ process,

$\mathbb{P}\left(\mathcal{T}_{\infty}\text{ contains an infinite
path}\right)\in(0,1).$

We note that, unlike the other theorems stated in this section, the proof of
Theorem 2.15 appears in Section 5, in particular in Section 5.3.

###  2.5 Proof techniques and relation to existing literature

As mentioned in the introduction, Theorem 2.5 was proved in the case that the
$(X(i),i\in\mathbb{N})$ are independent, with
$X(i)\sim\operatorname{Exp}\left(i^{p}\right),p>1$ in [58]. The technique used
in that paper was to show that the number of nodes $u\in\mathcal{U}_{\infty}$
that are _$k$ -fertile_ in the tree $\mathcal{T}_{\infty}$ (that is, contain a
sub-tree of size at least $k+1$), is almost surely finite for all $k>1/(p-1)$
[58, Lemma 5.1], and then deduce an infinite path cannot exist, almost surely.
Applying Lemma 2.1 then yields the desired conclusion. An immediate
generalisation of these techniques to the more general setting considered here
does not allow one to to prove Theorem 2.5. Indeed, as we will see in Theorem
3.21, Theorem 2.5 applies to cases where the number of $k$-fertile nodes is
_almost surely infinite_ for _any_ $k\in\mathbb{N}$. Instead, we use a
different approach to prove Theorem 2.5. By a first moment method and
appropriate concentration bounds (Lemma 4.1), we show that the expected number
of nodes $a\in\mathcal{U}_{\infty}$, with a high enough initial index $a_{1}$,
that explodes before all of its ancestors (that is, produces infinitely many
offspring before any of its direct ancestors does), is finite (see Proposition
4.3). Combining this with a coupling argument in Proposition 4.4 (a
significant generalisation of [58, Lemma 5.3]), we show that the expected
number of nodes that explodes before all of their ancestors is finite.
Finally, the _uniform explosivity_ assumption (see Remark 2.4) allows one to
deduce that the explosion time of the process $\tau_{\infty}$ is the infimum
of the explosion times $\mathcal{B}(u)+\mathcal{P}(u)$ of individuals
$u\in\mathcal{U}_{\infty}$. Using the aforementioned first moment arguments,
we can show that this infimum coincides with an infimum over a finite set.
Hence, at $\tau_{\infty}$ there exists at least one node of infinite degree.

The proofs of Theorems 2.8 and 2.10 use a different approach: by Borel-
Cantelli arguments, we can show that _before_ the explosion time associated
with an individual, either infinitely many children explode themselves
(leading to an infinite path, cf. Theorem 2.8), or otherwise certain finite
sub-trees appear infinitely often when there is a star (cf. Theorem 2.10). The
uniqueness conditions appearing in Theorem 2.12 are reminiscent of similar
uniqueness conditions appearing, for example, previously in [58] (using the
fact that the associated distribution of $\mathcal{P}(\varnothing)$ is
smooth). However, this requires novelty when proving the existence of a unique
infinite path in the level of generality we consider (see Lemma 4.8).

##  3 Examples of applications and an open problem

In this section, we provide applications of our main results, Theorem 2.5,
Theorem 2.8, and Theorem 2.12 in the case that the inter-birth times
$(X_{w}(i))_{i\in\mathbb{N}}$ are exponentially distributed. If $X_{w}(i)$ has
an exponential distribution with parameter $f(i,w)$, say, the memory-less
property and the property of minima of exponential distributions show that
$\mathcal{T}_{\infty}$ may be interpreted as the limiting infinite tree in a
model of _$(W,f)$ -recursive trees with fitness_. In this model, evolving in
discrete time, nodes arrive one at a time, are assigned i.i.d. weights, and
connect to an existing node sampled with probability proportional to its
‘fitness function’. In this model, we are not only able to provide phase
transitions related to the emergence of an infinite path, but also apply
Theorem 2.10 to provide criteria for the emergence of a particular sub-tree
infinitely often. This is the content of Section 3.1.

In Section 3.2 we consider more concrete cases, when the weights $W$ are real-
valued, closely connected to super-linear preferential attachment models. In
Section 3.2.1 we provide some background for the analysis of such models, in
the context of existing literature. Then, Theorem 3.16 in Section 3.2 provides
a classification of the phases where one sees a unique node of infinite degree
or a unique infinite path, proving phase transitions for three different
examples. These results apply not only to the case that the values
$(X_{w}(i))_{i\in\mathbb{N}}$ have exponential distributions, but other
distribution types (see Remarks 3.6 and 3.17); which may be of interest in
applications. In Theorem 3.21 we are able to characterise the sub-trees of
children of the star that can emerge in this model. We discuss implications of
these results in the particular ‘super-linear degree’ example in Section
3.2.4, which, in particular, allows us to produce phase diagrams in Figures 1
and 2.

Finally, we discuss the proof techniques involved in Section 3.3 and state an
open problem in Section 3.4.

###  3.1 The structure of explosive recursive trees with fitness

Suppose the values of $(X_{w}(i),i\in\mathbb{N})$ are exponentially
distributed and independent. The properties related to the exponential
distribution yield that the sequence of trees
$(\mathcal{T}_{i})_{i\in\mathbb{N}}$ associated with an explosive $(X,W)$-CMJ
branching process are identical in law to a sequence of _recursive trees with
fitness_ which we define below. First, we define the _fitness function_
$f:\mathbb{N}_{0}\times S\rightarrow[0,\infty)$ to be a measurable function
such that $f(i,w)$ is the rate of the exponential random variable
$X_{w}(i+1)$.

In this section, we generally consider trees as being rooted with edges
directed away from the root, and hence the number of ‘children’ of a node
corresponds to its _out-degree_. More precisely, given a vertex labelled $v$
in a directed tree $T$ we let $\operatorname{deg}^{+}(v,T)$ denote its out-
degree in $T$. We now define the recursive tree with fitness model.

######  Definition 3.1 (Recursive tree with fitness).

Suppose that $(W_{i})_{i\in\mathbb{N}}$ are i.i.d. copies of a random variable
$W$ that takes values in $S$, and let $f:\mathbb{N}_{0}\times
S\rightarrow[0,\infty)$ denote a fitness function. A $(W,f)$-recursive tree
with fitness is the sequence of random trees
$(\mathcal{T}_{i})_{i\in\mathbb{N}}$ such that: $\mathcal{T}_{0}$ consists of
a single node $0$ with weight $W_{0}$ and for $n\geq 1$, $\mathcal{T}_{n}$ is
updated recursively from $\mathcal{T}_{n-1}$ as follows:

  1. 1.

Sample a vertex $j\in\mathcal{T}_{n-1}$ with probability proportional to its
fitness, i.e., with probability

$\frac{f(\operatorname{deg}^{+}(j,\mathcal{T}_{n-1}),W_{j})}{\sum_{j=0}^{n-1}f(\operatorname{deg}^{+}(j,\mathcal{T}_{n-1}),W_{j})}.$
(3.1)

  2. 2.

Connect $j$ with an edge directed outwards to a new vertex $n$ with weight
$W_{n}$.

######  Remark 3.2.

Due to the equivalence in law with trees associated with an $(X,W)$-CMJ
branching process, by abuse of notation we refer to a sequence of recursive
tree with fitness by $(\mathcal{T}_{i})_{i\in\mathbb{N}}$, despite the fact
that the vertex set of these trees is $\mathbb{N}_{0}$ rather than
$\mathcal{U}_{\infty}$.  $\blacktriangleleft$

######  Remark 3.3.

The correspondence between recursive trees with fitness and the trees
$(\mathcal{T}_{i})_{i\in\mathbb{N}}$ associated with an $(X,W)$-CMJ process,
when $X_{w}(i)\sim\operatorname{Exp}\left(f(i+1,w)\right)$ holds for all
$i\in\mathbb{N},w\in S$, is a consequence of the memory-less property and the
fact that the minimum of exponential random variable is also exponentially
distributed, with a rate given by the sum of the rates of the corresponding
variables; see for example [34, Section 2.1]. The use of such continuous-time
embeddings to analyse combinatorial processes was pioneered by Arthreya and
Karlin [4]. This correspondence allows us to translate our main results to the
infinite recursive tree, which we also denote by $\mathcal{T}_{\infty}$.
$\blacktriangleleft$

####  3.1.1 The star/path transition in explosive recursive trees with fitness

Our first result pertains to the existence of a node of infinite degree or an
infinite path in recursive trees with fitness. To this end, we make the
following assumption:

$\exists w^{*}\in S:\forall w\in S,j\in\mathbb{N}:f(j,w)\geq
f(j,w^{*})\quad\text{and
}\quad\sum_{j=0}^{\infty}\frac{1}{f(j,w^{*})}<\infty.$ ($w^{*}$)

That is, there exists a minimiser $w^{*}\in S$ that, uniformly in
$j\in\mathbb{N}$, minimises $f(j,\cdot)$, and the reciprocals of $f(j,w^{*})$
are summable. Moreover, we define

$\mu_{n}^{w}:=\sum_{i=n}^{\infty}\frac{1}{f(i,w)},\qquad w\in
S,n\in\mathbb{N},\quad\text{and set }\mu_{n}:=\mu_{n}^{w^{*}}.$ (3.2)

Note that $\mu_{n}^{w}\leq\mu_{n}<\infty$ for all $w\in S$ by ($w^{*}$).

######  Theorem 3.4 (Star/path in explosive recursive trees).

Let $(\mathcal{T}_{i})_{i\in\mathbb{N}}$ be a $(W,f)$-recursive tree with
fitness and assume $f$ satisfies ($w^{*}$). Then,

  1. 1.

If, for some $c<1$, we have

$\sum_{n=1}^{\infty}\mathbb{E}\left[\prod_{i=0}^{\infty}\frac{f(i,W)}{f(i,W)+c\mu_{n}^{-1}}\right]<\infty,$
(3.3)

the tree $\mathcal{T}_{\infty}$ contains a unique node of infinite degree, and
no infinite path.

  2. 2.

If either for some $c>1$ and all $w\in S$ , we have

$\sum_{n=1}^{\infty}\mathbb{E}\left[\prod_{i=0}^{\infty}\frac{f(i,W)}{f(i,W)+c(\mu^{w}_{n})^{-1}\log{n}}\right]=\infty,$
(3.4)

or, as a weaker condition, Equation (2.9) is satisfied with
$\nu^{w}_{n}:=d\mu^{w}_{n}$ for $d<1$, the tree $\mathcal{T}_{\infty}$
contains a unique infinite path, and no node of infinite degree.

The proof of Theorem 3.4 appears in Section 5, in particular Section 5.2.1.

######  Remark 3.5.

It turns out that Equation (3.4) is a sufficient condition for Equation (2.9)
to be satisfied with $\nu^{w}_{n}:=d\mu^{w}_{n}$ for $d<1$. However, we
include it as a general comparison to Equation (3.3).  $\blacktriangleleft$

######  Remark 3.6.

Analogues of Theorem 3.4 extend to more general distributions of $X_{w}(i)$,
other than exponential distributions. In particular, we can apply the same
techniques used to prove Item 2 of Theorem 3.4 whenever
$(X_{w}(i),i\in\mathbb{N})$ are independent and $\mathop{\rm
Var}\nolimits{(X_{w}(i))}\leq K\mathbb{E}\left[X_{w}(i)\right]^{2}$ for some
$K>0$, possibly depending on $w$. In this case the expected value in (3.4) is
replaced by the Laplace transform
$\mathbb{E}\left[\mathcal{L}_{c(\mu^{w}_{n})^{-1}\log{n}}(\mathcal{P}(\varnothing);W)\right]$.
See the proof in Section 5.2.1 for more details. $\blacktriangleleft$

####  3.1.2 Sub-trees in explosive recursive trees with fitness when there is
a star

In Section 2.3, we described a tree $T$ as a finite subset of the Ulam-Harris
tree containing the root, with a natural directed edge structure induced by
parents being connected to children. We apply the same notion here, upon
identifying labels of elements of $\mathcal{T}_{\infty}$ with the Ulam-Harris
labelling. For a tree $T\subseteq\mathcal{U}_{\infty}$ and
$u\in\mathcal{T}_{\infty}$ (when we label the elements of
$\mathcal{T}_{\infty}$ with the Ulam-Harris labelling), we say that $T$
appears as a sub-tree, rooted at $u$, in $\mathcal{T}_{\infty}$ if
$uT\subseteq\mathcal{T}_{\infty}$. Because the presence of ‘earlier siblings’
in a copy of a tree $T$ can influence the probability of a tree emerging
444For example, if the tree $T$ corresponds to a path, it is intuitively less
likely to have a path emerge where every node of the path is the first child
of its parent rather than a path where some nodes are born later but, by
random chance, produce children faster. it is convenient to also assume that
$T$ is _sibling closed_ , where we define as follows. If $u=u_{1}\cdots
u_{m}\in T$ then $u=u_{1}\cdots u_{m-1}\ell\in T$ for each $\ell\in[u_{m}]$.

The occurrence of a sibling-closed tree $T$ in $\mathcal{T}_{\infty}$ may also
depend on the order in which the vertices in $T$ appear, which can vary in
such a way that they preserve the lexicographic ordering. An _ordering_ of a
tree $T$ with $|T|=k+1$ vertices, for some $k\in\mathbb{N}$, is a permutation
$O:T\rightarrow\left\\{0,1,\ldots,k\right\\}$, such that $O(u)\leq O(v)$ if
and only if $u\leq_{L}v$. Given an ordering $O$, we generally refer to the
vertices of a tree $T$ with $k+1$ vertices as
$\left\\{v_{0},\ldots,v_{k}\right\\}$, where $v_{i}:=O^{-1}(i)$ for each $i$.
Given a sibling-closed tree $T$, we let $\mathcal{O}(T)$ denote the set of all
orderings of $T$. For a given ordering $O$ and $j\leq k$, we let $O_{|_{j}}$
denote the (also sibling-closed) tree on the vertex set
$\left\\{v_{0},\ldots,v_{j}\right\\}$; note that this is well defined because
$O$ preserves the order $\leq_{L}$. Also note that each $O_{|_{j}}$ inherits
the natural directed edge structure from $T$. For a given vertex $v_{i}$, with
$i\leq j$, $\operatorname{deg}^{+}(v_{i},O_{|_{j}})$ denotes its out-degree in
$O_{|_{j}}$.

We then have the following theorem.

######  Theorem 3.7 (Sub-tree counts).

Fix $k\in\mathbb{N}$, and let $(\mathcal{T}_{i})_{i\in\mathbb{N}}$ be a
$(W,f)$-recursive tree with fitness such that $f$ satisfies ($w^{*}$) and so
that $\mathcal{T}_{\infty}$ contains a unique star. Moreover, assume that for
each $w\in S$ we have $\mu_{n}^{w}\geq c_{1}(w)\mu_{n}$, where $0<c_{1}(w)\leq
1$. Let $T$ be a sibling-closed tree, with $|T|=k+1$. The tree
$\mathcal{T}_{\infty}$ contains $T$ as a sub-tree infinitely often if and only
if

$\sum_{n=1}^{\infty}\sum_{O\in\mathcal{O}(T)}\mathbb{E}\left[\prod_{j=0}^{k}\frac{\prod_{\ell=0}^{\operatorname{deg}^{+}(v_{j},T)-1}f(\ell,W_{v_{j}})}{\sum_{i=0}^{j}f(\operatorname{deg}^{+}(v_{i},O_{|_{j}}),W_{v_{i}})\mathbf{1}_{\operatorname{deg}^{+}(v_{i},O_{|_{j}})<\operatorname{deg}^{+}(v_{i},T)}+\mu^{-1}_{n}}\right]=\infty.$
(3.5)

######  Corollary 3.8.

Fix $k\in\mathbb{N}$ and assume that, for each $i\in[k]$ we have
$\mathbb{E}\left[f(i,W)^{k}\right]<\infty$. Let $T$ be a sibling-closed tree
with $k+1$ vertices. Then, under the assumptions of Theorem 3.7 the tree
$\mathcal{T}_{\infty}$ contains $T$ as a sub-tree infinitely often if and only
if $\sum_{n=1}^{\infty}\mu_{n}^{k}=\infty$.

The proof of Theorem 3.7 appears in Section 5.2.2. On the other hand, the
proof of Corollary 3.8 appears separately, in Section 6.2.1.

###  3.2 Phase transitions in specific models of explosive recursive trees
with fitness

In this section we investigate three particular cases of the results presented
in Section 3.1, where we are able to prove _phase transitions_ for the
structure of the infinite limiting tree $\mathcal{T}_{\infty}$ in terms of the
_fitness function_ and the _vertex-weight distribution_. We assume that the
vertex-weights are non-negative and real-valued, i.e. they take values in
$S=[0,\infty)$. We also assume that the fitness function $f(i,W)$ grows
_faster than linear_ in the degree (i.e. its first argument). These cases are
thus examples of _super-linear preferential attachment with fitness_.

####  3.2.1 Connection to existing literature: super-linear preferential
attachment

As alluded to in the introduction, Section 1.1, a model of recursive trees
(with fitness) that has received substantial attention the last two decades
are preferential attachment models. Such models are thought to serve as a good
explanation of the formation _real-world_ networks due the _preferential
attachment paradigm_ , which suggests that networks are constructed by adding
vertices and edges successively, in such a way that new vertices prefer to be
connected to existing vertices with large degree. In particular, many of such
models intrinsically give rise to properties also found in many real-world
networks (i.e. the scale-free property and (ultra)small-world property),
rather than such properties being imposed on the model. We refer to [29] and
the references therein for an extensive overview of the literature on such
models and their applications.

Super-linear preferential attachment is a particular type of preferential
attachment where new vertices connect to existing vertices with out-degree $i$
with a probability proportional to $f(i)$, for some fitness function
$f:\mathbb{N}_{0}\to(0,\infty)$ such that
$\sum_{i=0}^{\infty}f(i)^{-1}<\infty$. Most often, as in e.g. [16, 58, 64],
the case $f(i)=(i+1)^{p}$ for some $p>1$ is studied, though there are also
choices for $f$ that satisfy the summability condition such that
$f(i)i^{-p}\to 0$ as $i\to\infty$ for any $p>1$. We coin these functions
_barely super-linear_. Though Pólya urn models with barely super-linear
fitness functions have been studied previously [27], as far as the authors are
aware this is the first case such fitness functions are treated for
preferential attachment models.

Super-linear preferential attachment models are suggested to possibly explain
the formation of real-world networks such as the Internet, where these
networks are in a ‘preasymptotic regime’ (are of relatively small size) where
the explosive nature of the model cannot be observed yet, based on statistical
parameter estimation, simulations, and non-rigorous analysis [46, 47, 60].

The inclusion of vertex-weights allows for a more heterogeneous and hence more
realistic model, where different vertices may behave differently (in
distribution), even when their out-degree is the same, as also discussed in
the introduction. The presence of vertex-weights often leads to rich behaviour
where phase transitions based on the vertex-weight distribution can be
observed (see the introduction for examples), which we show in this section to
be case for the examples we consider here, too.

We study a number of examples for which we can apply the results in Section
3.2. We state the assumptions for the fitness function $f$ and the vertex-
weight distribution, after which we present the results related to Theorems
3.4 and 3.7. We conclude the section with a discussion of these results in
Section 3.2.4, where we also provide some interesting phase diagrams in
Figures 1 and 2, and with some open problems in Section 3.4.

####  3.2.2 Assumptions for the fitness function and vertex-weight
distribution

When stating the particular assumptions for the fitness function $f$ and the
vertex-weight distribution, it is helpful to use the notions of _slowly-
varying_ and _regularly-varying_ functions, which we recall in the following
definition.

######  Definition 3.9.

A measurable function $L:[0,\infty)\rightarrow[0,\infty)$ is said to be
_slowly varying_ if for any $a>0$ we have

$\lim_{x\to\infty}\frac{L(ax)}{L(x)}=1.$

We say a measurable function $g:[0,\infty)\rightarrow[0,\infty)$ is _regularly
varying_ with exponent $\beta\in\mathbb{R}$ if $g(x)=x^{\beta}L(x)$, where
$L:[0,\infty)\to[0,\infty)$ is slowly varying. Finally, we say that a _random
variable_ $W$ is regularly varying with exponent $z<0$ if the tail
distribution $\mathbb{P}\left(W\geq x\right)$ is a regularly-varying function
(in $x$) with exponent $z<0$.

We then assume that the fitness function satisfies the following assumption.

######  Assumption 3.10 (Fitness function).

The fitness function $f$ is such that Equation ($w^{*}$) is satisfied with
$w^{*}=0$. Furthermore, there exists $s:\mathbb{N}_{0}\to(0,\infty)$, which we
call the _degree function_ , and continuous functions
$g:[0,\infty)\to(0,\infty)$ and $h:[0,\infty)\to[0,\infty)$, which we call the
_weight functions_ , such that $f$ satisfies

$f(i,w):=g(w)s(i)+h(w),\qquad i\in\mathbb{N}_{0},w\geq 0.$ (3.6)

We then distinguish the following two cases, based on the weight functions.

  * •

Additive weights. $g\equiv 1$ and $h$ is regularly varying with exponent $1$.

  * •

Mixed weights. $g$ and $h$ are regularly varying with exponents $1$ and
$\gamma\geq 0$, respectively.

######  Remark 3.11.

The assumption that $w^{*}=0$ is not necessary, but used to simplify notation
and computations. The results presented here follow equivalently for $w^{*}>0$
as well.  $\blacktriangleleft$

######  Remark 3.12.

The function $g$ and $h$ are regularly varying with exponents $1$ and
$\gamma\geq 0$ in the mixed case; $g\equiv 1$ and $h$ is regularly varying
with exponent $1$ in the additive case. The choice of the exponents is due to
the fact that, when the vertex-weights are regularly varying with exponent
$-(\alpha-1)<0$, then $g(W)$ and $h(W)$ are random variables that are
regularly varying with exponents $-(\alpha-1)$ and $-(\alpha-1)/\gamma$,
respectively (see Lemma 6.6 for details). Hence, changing the exponent of, for
example, the regularly-varying function $g$ to $\zeta\neq 1$ in the mixed
case, is equivalent to changing the exponent of the regularly-varying random
variable $W$ from $-(\alpha-1)$ to $-(\alpha-1)/\zeta$ and changing the
exponent of the regularly-varying function $h$ from $\gamma$ to
$\gamma/\zeta$. As such, we take $\zeta=1$ without loss of generality. The
function $h$ is regularly varying with exponent $1$ in the additive case
without loss of generality for the same reason.  $\blacktriangleleft$

Depending on the precise form of the degree function, the model behaviour
markedly differs. We assume the _degree function_ $s$ satisfies the following
assumption.

######  Assumption 3.13 (Degree function).

The degree function $s:\mathbb{N}_{0}\to(0,\infty)$ satisfies one of the
following cases.

  * •

Super-linear preferential attachment. $s$ is regularly varying with exponent
$p>1$.

  * •

Barely super-linear preferential attachment. $s$ is regularly varying with
exponent $1$, such that $\sum_{i=0}^{\infty}s(i)^{-1}<\infty$.

As a particular example of the barely super-linear case, we consider

  * •

Barely super-linear log-stretched preferential attachment. For some
$\beta\in(0,1)$,

$s(i)=(i+1)\exp((\log(i+1))^{\beta}),\qquad i\in\mathbb{N}_{0}.$ (3.7)

######  Remark 3.14.

We note that these choices for the fitness function $f$ are not exhaustive,
but do cover a wide range of examples. In particular, the weight types
considered, i.e. additive or mixed weights, are common in the literature of
linear preferential attachment with fitness (see e.g. [21, 26, 53, 19, 34,
22]). When the vertex-weights are constant almost surely, the additive and
mixed cases all fall into the same classes of super-linear preferential
attachment. The barely super-linear class has not been studied previously, as
far as the authors are aware.  $\blacktriangleleft$

Finally, we require several assumptions on the distribution of the vertex-
weights. For different choices of the fitness function $f$, different
assumptions are required, which are summarised in the following overview.

######  Assumption 3.15 (Vertex-weight distribution).

The vertex-weights $(W_{i})_{i\in\mathbb{N}}$ are i.i.d. and their tail
distribution satisfies one (or more) of the following conditions.

  * •

Power law. Let $\alpha>1$. We have the following two conditions.

    1. 1.

There exist $\overline{x}>0$ and a slowly-varying function
$\overline{\ell}:[0,\infty)\to[0,\infty)$ such that

$\mathbb{P}\left(W\geq x\right)\leq\overline{\ell}(x)x^{-(\alpha-1)},\qquad
x\geq\overline{x}.$ (3.8)

    2. 2.

There exist $\underline{x}>0$ and a slowly-varying function
$\underline{\ell}:[0,\infty)\to[0,\infty)$ such that

$\mathbb{P}\left(W\geq x\right)\geq\underline{\ell}(x)x^{-(\alpha-1)},\qquad
x\geq\underline{x}.$ (3.9)

  * •

Log-stretched exponential. Let $\nu>1$. We have the following two conditions.

    1. 1.

There exist $\overline{c},\overline{x}>0$ such that

$\mathbb{P}\left(W\geq x\right)\leq\mathrm{e}^{-\overline{c}(\log
x)^{\nu}},\qquad x>\overline{x}.$ (3.10)

    2. 2.

There exist $\underline{c},\underline{x}>0$ such that

$\mathbb{P}\left(W\geq x\right)\geq\mathrm{e}^{-\underline{c}(\log
x)^{\nu}},\qquad x\geq\underline{x}.$ (3.11)

####  3.2.3 Phase transitions for super-linear preferential attachment models
with fitness

Based on these assumptions for the fitness function, degree function, and
vertex-weight distribution, we can formulate the following theorem that treats
the appearance of a unique infinite-degree vertex or a unique infinite path in
$\mathcal{T}_{\infty}$.

######  Theorem 3.16.

Let $(\mathcal{T}_{i})_{i\in\mathbb{N}}$ be a $(W,f)$-recursive tree with
fitness, where the fitness function $f$ and degree function $s$ satisfy one of
the cases in Assumptions 3.10 and 3.13, respectively, and the vertex-weight
distribution satisfies one of the cases in Assumption 3.15. The tree
$\mathcal{T}_{\infty}$ either contains a unique vertex with infinite degree
and no infinite path almost surely, or contains a unique infinite path and no
vertex with infinite degree almost surely, when the following conditions are
met, based on the _fitness function_ , _degree function_ , and _vertex-weight_
assumptions:

Fitness | Degree | Star | Path
---|---|---|---
Mixed | Super-linear |  (3.8) & $(p-1)(\alpha-1)>\big{(}\gamma-\tfrac{\gamma-1}{p}\big{)}\vee 1$ |  (3.9) & $(p-1)(\alpha-1)<\big{(}\gamma-\tfrac{\gamma-1}{p}\big{)}\vee 1$
Additive | Super-linear |  (3.8) & $p(\alpha-1)>1$ |  (3.9) & $p(\alpha-1)<1$
Mixed | Log-stretched |  (3.10) & $\beta\nu>1$ |  (3.11) & $\beta\nu<1$
Table 1: The first column represents the form of the fitness function, as in
Assumption 3.10; the second represents the form of the degree function, as in
Assumption 3.13. The third and fourth column, respectively, list the required
assumptions on the vertex-weight distribution, as in Assumption 3.15, together
with the choices of the parameters that lead to either a unique node of
infinite degree or a unique infinite path.

The proof of Theorem 3.16 appears in Section 6.1.

######  Remark 3.17.

Though Theorem 3.16 is presented for exponentially distributed inter-birth
times, we expect the same results to hold for a large family of distributions,
such that $X_{w}(uj)$ has mean $1/f(j-1,w)$ for each
$u\in\mathcal{U}_{\infty},j\in\mathbb{N}$, and $w\in[0,\infty)$. In
particular, we discuss the extension of Theorem 3.16 to the following examples
Appendix B:

  1. 1.

Gamma distribution: For each $u\in\mathcal{U}_{\infty},j\in\mathbb{N}$, and
$w\in[0,\infty)$, the inter-birth time $X_{w}(uj)$ follows a
$\mathrm{Gamma}(k,kf(j-1,w))$ distribution, for some $k>0$.

  2. 2.

Beta distribution: For each $u\in\mathcal{U}_{\infty},j\in\mathbb{N}$, and
$w\in[0,\infty)$, the inter-birth time $X_{w}(uj)$ equals
$\frac{\alpha+\beta}{\alpha}\frac{1}{f(j-1,w)}B(uj)$, where
$(B(uj))_{u\in\mathcal{U}_{\infty},j\in\mathbb{N}}$ is a sequence of i.i.d.
copies of a $\mathrm{Beta}(\alpha,\beta)$ random variable, for some
$\alpha\geq 1$ and $\beta\leq(0,1]$.

  3. 3.

Rayleigh distribution: For each $u\in\mathcal{U}_{\infty},j\in\mathbb{N}$, and
$w\in[0,\infty)$, the inter-birth time $X_{w}(uj)$ follows a
$\mathrm{Rayleigh}(\sqrt{2/\pi}/f(j-1,w))$ distribution.  $\blacktriangleleft$

######  Remark 3.18.

In Section A we discuss three more examples of barely super-linear
preferential attachment with fitness: the log-stretched case with additive
fitness, as well as a poly-log case with either additive or mixed fitness.
Again, the extension of the results to the other inter-birth time
distributions as in Remark 3.17 apply here, too.

We do not include these results here, as we cannot prove a complete phase
diagram, i.e. for certain parameter choices we cannot prove the appearance of
a unique infinite-degree vertex nor a unique infinite path.
$\blacktriangleleft$

######  Remark 3.19.

When the vertex-weights are almost surely bounded (or, in particular, a
deterministic constant), it follows from the above theorem that in all cases,
a unique vertex with infinite degree emerges in $\mathcal{T}_{\infty}$ almost
surely. Indeed, in such a case the vertex-weight distribution would satisfy,
the upper bounds in (3.8) or (3.10) for any $\alpha>1,\nu>1$. As such, we can
take $\alpha\to\infty,\nu\to\infty$ to conclude the claim. In the case
$s(i)=(i+1)^{p}$ with $p>1$, this recovers the results of Oliveira and Spencer
[58, Theorem $1.1$]. $\blacktriangleleft$

######  Remark 3.20.

It is interesting to note that, though two different techniques with distinct
assumptions are used to prove Theorems 2.5 and 2.8 (for the existence of an
infinite star or path in $\mathcal{T}_{\infty}$), the application of these two
general results in Theorem 3.16 allows us to obtain a complete phase diagram
for the three examples discussed here. $\blacktriangleleft$

When the infinite tree $\mathcal{T}_{\infty}$ contains a unique vertex with
infinite degree almost surely, we can also quantify Theorem 3.21, in the sense
that, depending on assumptions on the fitness function $f$ and vertex-weight
distribution, we can determine almost surely whether or not
$\mathcal{T}_{\infty}$ contains an infinite number of copies of which kinds of
sub-trees. We remark that we can do this in a relatively general manner,
subject to the assumption that $\mathcal{T}_{\infty}$ contains a unique vertex
with infinite degree. That is, for _any_ degree function $s$ that satisfies
the (barely) super-linear cases in Assumption 3.13 the results below apply.

To this end, we define for a finite tree $T$ and constant $z>0$,

$G_{1}=G_{1}(T,z):=\sum_{v\in
T}\operatorname{deg}^{+}(v,T)\mathbf{1}_{\operatorname{deg}^{+}(v,T)>z},\qquad
G_{2}=G_{2}(T,z):=\sum_{v\in T}\mathbf{1}_{\operatorname{deg}^{+}(v,T)>z}.$
(3.12)

We can then have the following result.

######  Theorem 3.21.

Let $(\mathcal{T}_{i})_{i\in\mathbb{N}}$ be a $(W,f)$-recursive tree with
fitness, where we assume that $f$ satisfies Assumption 3.10, that the degree
function $s$ satisfies Assumption 3.13, and that the vertex-weight
distribution satisfies (3.8) and (3.9) for some slowly-varying functions
$\underline{\ell},\overline{\ell}$, respectively, and some $\alpha>1$.
Furthermore, we assume that $\mathcal{T}_{\infty}$ contains a unique vertex
with infinite degree, almost surely. Fix $k\in\mathbb{N}$ and let $T$ be a
sibling-closed tree of size $k+1$. Then, we have the following.

  * •

Super-linear case: We take $\gamma=1$ for additive weights, $\gamma\geq 0$ for
mixed weights, and set $z=(\alpha-1)/(\gamma\vee 1)$. The tree $T$ almost
surely appears infinitely often as a sub-tree of $\mathcal{T}_{\infty}$ when

$p<1+\frac{1}{k-(G_{1}(T,z)-zG_{2}(T,z))}.$ (3.13)

The tree $T$ almost surely appears finitely often as a sub-tree of
$\mathcal{T}_{\infty}$ when

$p>1+\frac{1}{k-(G_{1}(T,z)-zG_{2}(T,z))}.$ (3.14)

  * •

Barely super-linear case: The tree $T$ appears as a sub-tree of
$\mathcal{T}_{\infty}$ infinitely often, almost surely.

The proof of Theorem 3.21 appears in Section 6.2, in particular, Section
6.2.2.

######  Remark 3.22.

In fact, we have a strengthening of Theorem 3.21 which applies to _any_
$(W,f)$-recursive tree with fitness (in particular without the assumption that
$W$ is real-valued), as long as, for any $j\in\mathbb{N}_{0}$, $f(j,W)$
satisfies (3.8) and (3.9) for some slowly-varying functions
$\overline{\ell}_{j},\underline{\ell}_{j}$, respectively, and an exponent
$z>0$, and for each $k\in\mathbb{N}_{0}$ there exists
$i_{k}\in\\{0,\ldots,k\\}$ such that $\inf_{i\leq k}f(i,w)=f(i_{k},w)$ for all
$w\in S$. See Proposition 6.5 for more details.  $\blacktriangleleft$

######  Remark 3.23.

When the vertex-weight distribution satisfies
$\mathbb{E}\left[W^{a}\right]<\infty$ for all $a>0$, it directly follows from
the assumptions on the fitness function $f$ in Assumption 3.10 and Corollary
3.8 that the results in Theorem 3.21 extend to this case, where we set
$G_{1}(T,z)=G_{2}(T,z)=0$.

Furthermore, we stress that for _all_ barely super-linear cases and for
certain super-linear cases (see the upcoming discussion), sub-trees $T$ of
_arbitrary_ size appear infinitely often as a sub-tree of
$\mathcal{T}_{\infty}$, almost surely. This is markedly different when
compared to the super-linear preferential attachment model $f(i,w)=(i+1)^{p}$
($p>1$) studied by Oliveira and Spencer in [58], where only sub-trees $T$ with
size at most $\lceil(p-1)^{-1}\rceil$ can appear infinitely often almost
surely.  $\blacktriangleleft$

####  3.2.4 Discussion related to Theorem 3.21: the super-linear case

Let us provide some intuition for Theorem 3.21 by discussing two particular
examples.

_Super-linear degree, mixed weights._ We let $f(i,w)=(w+1)(i+1)^{p}$ for some
$p>1$. That is, we consider the mixed weights case for the fitness function
$f$, with $g(x):=x+1,h\equiv 0$, and $\gamma=0$, as in Assumption 3.10, and
the super-linear case for the degree function $s$, i.e. $s(i):=(i+1)^{p}$,
$p>1$, as in Assumption 3.13. We require that $\mathcal{T}_{\infty}$ contains
a unique vertex with infinite degree almost surely, so that, by Theorem 3.16,
we assume that the vertex-weight distribution satisfies (3.8) and that
$(p-1)(\alpha-1)>1$. Then, additionally assume that the vertex-weight
distribution satisfies (3.9) with the same $\alpha>1$ but potentially with a
different slowly-varying function. Now, Theorem 3.21 states that a tree $T$ of
size $k+1$, for some $k\in\mathbb{N}$, appears infinitely often as a sub-tree
of $\mathcal{T}_{\infty}$ almost surely when

$p<1+\frac{1}{k-(G_{1}(T,\alpha-1)-(\alpha-1)G_{2}(T,\alpha-1))}.$ (3.15)

First, noting that the sum of all degrees equals $|T|-1=k$, we observe that

$G_{1}(T,\alpha-1)-(\alpha-1)G_{2}(T,\alpha-1)\in[0,k),$ (3.16)

for any choice of $T$ and $\alpha$, so that the upper bound yields a
restriction on $p$. We omit the arguments of $G_{1}$ and $G_{2}$ from here on
out for ease of writing. Combining our two assumptions we then require that

$\frac{1}{\alpha-1}<p-1<\frac{1}{k-(G_{1}-(\alpha-1)G_{2})},$ (3.17)

and we can only find $p>1$ that satisfy both inequality when

$k-(G_{1}-(\alpha-1)G_{2})<\alpha-1.$ (3.18)

Now, if $k<\alpha-1$, there is no vertex in $T$ with an out-degree larger than
$\alpha-1$, so that $G_{1}=G_{2}=0$ and the inequality is satisfied. For
$k\geq\alpha-1$ we distinguish two cases. $(i)$ There is no vertex in $T$ with
a degree larger than $\alpha-1$. It again follows that $G_{1}=G_{2}=0$, so
that the inequality in (3.18) is _not_ satisfied; $(ii)$ There exists at least
one vertex with degree larger than $\alpha-1$. Then, $k-G_{1}>0$ since $k$
equals the sum of all degrees, whilst $(\alpha-1)(1-G_{2})\leq 0$ (since
$G_{2}\geq 1$), so that (3.18) is not satisfied.

We thus conclude that, when $(p-1)(\alpha-1)>1$, only trees $T$ with size
$k+1$, where $k<\alpha-1$, appear infinitely often. In particular, we do not
require any assumptions on the _structure_ of such trees $T$; only their size
is relevant. The reversed inequality in Theorem 3.21 can be analysed in a
similar manner to derive the phase diagram in Figure 1.

_Super-linear degree, additive weights._ We let $f(i,w)=(i+1)^{p}+w$ for some
$p>1$. That is, we consider the additive weight case for the fitness function
$f$, with $h(x)=x$, as in Assumption 3.10, and the super-linear case for the
degree function $s$, i.e. $s(i)=(i+1)^{p},p>1$, as in Assumption 3.13. We make
the same assumptions as in the first example, except that we now require
$p(\alpha-1)>1$. First, when $p$ is so large that $(p-1)(\alpha-1)>1$, we can
derive the same conclusions as in the first example. When $p$ is such that

$\frac{1}{\alpha-1}\vee 1<p<1+\frac{1}{\alpha-1},$ (3.19)

different behaviour can be observed. Here, as we illustrate with the following
particular family of trees, we observe the peculiar behaviour that the
_structure_ of a tree $T$ plays a role in terms of whether it appears
infinitely or finitely often as a sub-tree in $\mathcal{T}_{\infty}$.

Let $T$ be an $m$-ary tree of size $k+1$ for some $m,k\in\mathbb{N}$ such that
$k=\ell m$ for some $\ell\in\mathbb{N}$, i.e. a tree where the $\ell$ internal
vertices (non-leaf vertices) have out-degree $m$ (note that stars are the
particular case $\ell=1$). We observe that, by distinguishing the two cases
$m>\alpha-1$ and $m\leq\alpha-1$ (where in the latter case $G_{1}=G_{2}=0$),

$G_{1}(T,\alpha-1)-(\alpha-1)G_{2}(T,\alpha-1)=\max\\{k-(\alpha-1)\ell,0\\}.$
(3.20)

As a result, recalling $k=\ell m$, an $m$-ary tree $T$ appears infinitely
often as a sub-tree of $\mathcal{T}_{\infty}$, almost surely, when

$\frac{1}{\alpha-1}\vee 1<p<1+\frac{1}{\ell\min\\{\alpha-1,m\\}}.$ (3.21)

Observe that for $\ell=1$, i.e. stars of size $k+1=m+1$, these inequalities
are satisfied by any $p$ that satisfies (3.19), so that a star of _any_ size
appears infinitely often as a sub-tree of $\mathcal{T}_{\infty}$, almost
surely, when $p$ satisfies (3.19). For $\ell\geq 2$, these inequalities can be
satisfied only when $\alpha\leq 2$ and $\ell<1/(2-\alpha)$ or when $\alpha>2$.

Again, the reversed inequality in Theorem 3.21 can be analysed in a similar
manner to derive the phase diagram in Figure 2, where some of the phases for
ternary trees ($m=3$) are shown.

We thus observe that it is possible for two trees $T_{1},T_{2}$ of sizes
$k_{1}+1<k_{2}+1$, respectively, to appear finitely and infinitely often as a
sub-tree of $\mathcal{T}_{\infty}$, almost surely. This behaviour is
completely opposite to the behaviour of the first example (or when
$(p-1)(\alpha-1)>1$ in this example).

As a final remark, any tree of any size appears infinitely often as a sub-tree
of $\mathcal{T}_{\infty}$ in the barely sub-linear case discussed in Theorem
3.21. As discussed in Section 2.5, this behaviour has not been observed in
explosive tree models studied so far.

Figure 1: The phase diagram for the case $f(i,w)=(w+1)(i+1)^{p}$. Below the
curve $(p-1)(\alpha-1)=1$ (the dark shaded region), the tree
$\mathcal{T}_{\infty}$ contains a unique infinite path, whereas above the
curve (the light shaded region) the tree contains a unique vertex of infinite
degree. Moreover, in the light shaded region, below the $k$th horizontal
dotted line, corresponding to $1+1/k$, (with $k=1,2,3,4$ visible here), any
tree of size $k+1$ appears as a sub-tree of a child of the node of infinite
degree infinitely often, whereas above the $k$th horizontal line, in the light
shaded region, trees of size $k+1$ appear only finitely often as a sub-tree of
a child of the node of infinite degree.  Figure 2: The phase diagram for the
case $f(i,w)=(i+1)^{p}+w$. Below the curve $p(\alpha-1)=1$ (the dark shaded
region), the tree $\mathcal{T}_{\infty}$ contains a unique infinite path,
whereas above the curve (the lighter shaded regions) the tree contains a
unique vertex of infinite degree. In the area above the line
$(p-1)(\alpha-1)=1$ (lightest shaded region), below the $k$th horizontal
dotted line, corresponding to $1+1/k$, (with $k=1,2,3,4$ visible here), any
tree of size $k+1$ appears as a sub-tree of a child of the node of infinite
degree infinitely often, whereas above the $k$th horizontal line, in the
lightest shaded region, trees of size $k+1$ appear only finitely often as a
sub-tree of a child of the node of infinite degree. In the area in between the
curves $p(\alpha-1)=1$ and $(p-1)(\alpha-1)=1$ (the semi-dark region) a star
of _any_ size appears as a sub-tree of a child of the node of infinite degree
infinitely often. Additionally, below the $\ell$th curve in this region,
corresponding to $(p-1)\ell\min\\{\alpha-1,3\\}=1$, (with $\ell=2,3,4$ visible
here) ternary trees of size $3\ell+1$ appear as a sub-tree of the node of
infinite degree infinitely often, whereas above the $\ell$th curve, such trees
only appear finitely often.

###  3.3 Proof techniques

The proofs of the results in Section 3 generally apply the results of Section
2. However, we are unaware of previous proofs of Lemma 5.1, used to prove
Theorem 3.4. Moreover, exploiting the memory-less property of the exponential
distribution allows the derivation of a necessary and sufficient condition for
the emergence of a structure infinitely often when $\mathcal{T}_{\infty}$
contains an infinite star, as in Theorem 3.7. The proof of this theorem, we
believe, is more elegant than the approach used to prove [58, Theorem 1.2] for
the particular case $f(i,w)=(i+1)^{p},p>1$. The assumptions made in Section
3.2 allow us to deduce a variety of phase-transitions in applied models (cf.
Theorem 3.16), which we believe extend to a fairly general family of
distributions (see Remark 3.17).

We prove the most general results, as presented in Section 3.1, in Section 5,
and prove the results for the examples presented in Section 3.2 in Section 6.

###  3.4 Open problem

It is unclear whether or not _any_ explosive $(X,W)$-CMJ process for which the
vertex-weights are almost surely constant _always_ yields an infinite star
almost surely. In other words, when assuming that the
$(X(i))_{i\in\mathbb{N}}$ are mutually independent and positive, we have the
following open problem.

######  Open problem 3.24.

Consider an explosive $(X,W)$-CMJ process $(\mathscr{T}_{t})_{t\geq 0}$, such
that $(X(i))_{i\in\mathbb{N}}$ are mutually independent and positive. Is it
the case that almost surely $\mathcal{T}_{\infty}$ contains a unique vertex
with infinite degree?

######  Remark 3.25.

In the case of the recursive tree with fitness, if
$X(i)\sim\operatorname{Exp}\left(g(i)\right)$, with $g$ unbounded, and convex,
we believe that the affirmative of Open problem 3.24 holds, by an argument
using a combination of the result of Galashin [23, Theorem 1] and Proposition
4.4.  $\blacktriangleleft$

######  Remark 3.26.

Note that the counter-example in Theorem 2.15 relies on the dependence of the
$(X(i))_{i\in\mathbb{N}}$ on the weights. Thus, if $\mathcal{T}_{\infty}$
_does_ almost surely contain a unique node of infinite degree in Open problem
3.24, one may interpret this, informally, as saying that ‘new nodes are unable
to out-compete older nodes, without the influence of a random weight’.
$\blacktriangleleft$

##  4 Proofs of main results

This section is dedicated to proving the most general results, as presented in
Section 2. We prove the existence of an infinite star (cf. Theorem 2.5) in
Section 4.1, prove the existence of of an infinite path (cf. Theorem 2.8) and
the structural result of sub-trees in the star regime (cf. Theorem 2.10) in
Section 4.2, and finally prove the uniqueness properties (cf. Theorem 2.12) in
Section 4.3.

###  4.1 Sufficient criteria for a star

This section is dedicated to the proof of Theorem 2.5. We first have the
following lemma:

######  Lemma 4.1.

Fix $k,n\in\mathbb{N}$, let $(a_{1},\ldots,a_{k})\in\mathbb{N}^{k}$. Let
$(Z_{i})_{i\in[k]}$ be independent random variables, and let
$(X(\ell))_{\ell\geq n+1}$ be as in (2.1), satisfying Conditions 1 and 2 of
Assumption 2.2. Then, there exists $n_{0}>0$ and $C=C(n_{0})>0$ such that, for
all $n\geq n_{0}$,

$\mathbb{P}\left(\sum_{i=1}^{k}Z_{i}\leq\sum_{\ell=n+1}^{\infty}X(\ell)\right)\leq\mathbb{P}\left(\sum_{i=1}^{k}Z_{i}\leq
Y_{n}\right)\leq C\prod_{j=1}^{k}\mathcal{L}_{c\mu_{n}^{-1}}(Z_{i}),$ (4.1)

where $Y_{n}$ is as in (2.4) and independent of the $(Z_{i})_{i\in[k]}$.

###### Proof.

First note that the first inequality in (4.1) is an immediate consequence of
(2.4). Then, for any $\lambda>0$,

$\displaystyle\mathbb{P}\left(\sum_{i=1}^{k}Z_{i}\leq
Y_{n}\right)=\mathbb{P}\left(\exp\left(\lambda
Y_{n}-\lambda\sum_{i=1}^{k}Z_{i}\right)\geq
1\right)\leq\mathcal{M}_{Y_{n}}(\lambda)\prod_{i=1}^{k}\mathcal{L}_{\lambda}(Z_{i}),$

where the last inequality uses Markov’s inequality and the independence of the
random variables. Next, setting $\lambda:=c\mu_{n}^{-1}$ and recalling that,
by (2.5), we can set
$C:=\limsup_{n\to\infty}\mathcal{M}_{Y_{n}}(c\mu_{n}^{-1})<\infty$, we deduce
the result. ∎

We now introduce the following terminology, used in the remainder of the
section, which, although not strictly needed, we believe makes the proofs
conceptually easier to understand. For $a,b\in\mathcal{U}_{\infty}$ we say
that

“$a$ has at least $k$ children before $b$ explodes”

if $\mathcal{B}(a)+\mathcal{P}_{k}(a)<\mathcal{B}(b)+\mathcal{P}(b)$. We say
that

“$a$ explodes before all of its ancestors”

if, for each $\ell<|a|$, we have
$\mathcal{B}(a)+\mathcal{P}(a)<\mathcal{B}(a_{|_{\ell}})+\mathcal{P}(a_{|_{\ell}})$.
Finally, for $a\in\mathcal{U}_{\infty}$ with $|a|\geq 1$, we say that
$a=a_{1}\cdots a_{m}$ is $a_{1}$-_conservative_ if, for each
$j\in\left\\{2,\ldots,m\right\\}$, we have $a_{j}\leq a_{1}$. (Note that this
implies that any $a$ such that $|a|=1$ is $a_{1}$-conservative.)

######  Lemma 4.2.

Under Assumption 2.2, there exist $\eta<1$ and $K=K(\eta)>0$ such that for all
$a_{1}>K(\eta)$, all integers $m\in\mathbb{N}$, and some constant $C>0$,

$\sum_{\begin{subarray}{c}a:|a|=m\\\ a\text{ is
$a_{1}$-conservative}\end{subarray}}\\!\\!\\!\\!\\!\\!\\!\mathbb{P}\left(a\text{
has at least $a_{1}$ children before }\varnothing\text{ explodes }\right)\leq
C\eta^{m-1}\mathbb{E}\left[\mathcal{L}_{c\mu_{a_{1}}^{-1}}(\mathcal{P}_{a_{1}};W)\right].$
(4.2)

###### Proof.

Suppose that $a=a_{1}\cdots a_{m}\in\mathcal{U}_{\infty}$. For $a$ to have at
least $a_{1}$ children before the explosion of $\varnothing$, in particular,
each of the births corresponding to the ancestors of $a$ need to occur
(leading to a term as in Equation (1.3) with $u=\varnothing$ and $v=a$). Thus,
for $a_{1}$ sufficiently large, by (1.3) and Lemma 4.1, we have

$\displaystyle\mathbb{P}\left(a\text{ has at least $a_{1}$ children before
}\varnothing\text{ explodes }\right)$
$\displaystyle=\mathbb{P}\left(\mathcal{B}(a)+\mathcal{P}_{a_{1}}(a)<\mathcal{P}(\varnothing)\right)$
(4.3)
$\displaystyle=\mathbb{P}\left(\left(\sum_{j=1}^{m-1}\mathcal{P}_{a_{j+1}}(a_{|_{j}})\right)+\mathcal{P}_{a_{1}}(a)\leq\sum_{k=a_{1}+1}^{\infty}X(k)\right)$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:moment-prob-
bound1}}}{{\leq}}C\prod_{j=1}^{m-1}\mathbb{E}\left[\mathcal{L}_{c\mu_{a_{1}}^{-1}}(\mathcal{P}_{a_{j+1}};W)\right]\times\mathbb{E}\left[\mathcal{L}_{c\mu_{a_{1}}^{-1}}(\mathcal{P}_{a_{1}};W)\right],$

where the last line follows from the fact that, by (2.1), for each
$u\in\mathcal{U}_{\infty}$ the sequence
$(\mathcal{P}_{j}(u))_{j\in\mathbb{N}}$ is independent and distributed like
$(\mathcal{P}_{j}(\varnothing))_{j\in\mathbb{N}}$. When we sum over the
possible conservative sequences $a$ that are $a_{1}$-conservative, each
$a_{j}$ takes values between $1$ and $a_{1}$, for $j=2,\ldots,m$. Thus,

$\displaystyle\sum_{\begin{subarray}{c}a:|a|=m\\\ a\text{
$a_{1}$-conservative}\end{subarray}}{}$ $\displaystyle\mathbb{P}\left(a\text{
has at least $a_{1}$ children before }\varnothing\text{ explodes }\right)$
(4.4) $\displaystyle\leq{}$
$\displaystyle\sum_{a_{2}=1}^{a_{1}}\sum_{a_{3}=1}^{a_{1}}\cdots\sum_{a_{m}=1}^{a_{1}}C\prod_{j=1}^{m-1}\mathbb{E}\left[\mathcal{L}_{c\mu_{a_{1}}^{-1}}(\mathcal{P}_{a_{j+1}};W)\right]\times\mathbb{E}\left[\mathcal{L}_{c\mu_{a_{1}}^{-1}}(\mathcal{P}_{a_{1}};W)\right]$
$\displaystyle={}$ $\displaystyle
C\left(\sum_{\ell=1}^{a_{1}}\mathbb{E}\left[\mathcal{L}_{c\mu_{a_{1}}^{-1}}(\mathcal{P}_{\ell};W)\right]\right)^{m-1}\mathbb{E}\left[\mathcal{L}_{c\mu_{a_{1}}^{-1}}(\mathcal{P}_{a_{1}};W)\right].$

We now need only show that for $a_{1}$ sufficiently large,

$\sum_{\ell=1}^{a_{1}}\mathbb{E}\left[\mathcal{L}_{c\mu^{-1}_{a_{1}}}(\mathcal{P}_{\ell};W)\right]<\eta.$

Indeed, since
$\sum_{i=\ell}^{\infty}\mathbb{E}\left[\mathcal{L}_{c\mu^{-1}_{\ell}}(\mathcal{P}_{\ell};W)\right]<\infty$
by (2.8) in Assumption 2.2, there exists $L=L(\eta)>0$ such that, for all
$a_{1}>L$,

$\sum_{\ell=L}^{a_{1}}\mathbb{E}\left[\mathcal{L}_{c\mu^{-1}_{a_{1}}}(\mathcal{P}_{\ell};W)\right]<\sum_{\ell=L}^{\infty}\mathbb{E}\left[\mathcal{L}_{c\mu^{-1}_{\ell}}(\mathcal{P}_{\ell};W)\right]<\frac{\eta}{2},$
(4.5)

where the inequality uses the fact that $c\mu_{n}^{-1}$ is non-decreasing in
$n$. On the other hand, since $\lim_{n\to\infty}c\mu_{n}^{-1}=\infty$, by
bounded convergence (bounding the integrand by $1$) we have

$\lim_{n\to\infty}\sum_{\ell=1}^{L-1}\mathbb{E}\left[\mathcal{L}_{c\mu^{-1}_{n}}(\mathcal{P}_{\ell};W)\right]=0.$

As a result, for some $K\geq L$ sufficiently large and for all $a_{1}>K$, we
arrive at

$\sum_{\ell=1}^{L-1}\mathbb{E}\left[\mathcal{L}_{c\mu^{-1}_{\ell}}(\mathcal{P}_{\ell};W)\right]<\frac{\eta}{2}.$
(4.6)

Combining Equations (4.5) and (4.6) in (4.4), we conclude the proof. ∎

The above lemma provides an upper bound for the probability of the event that
a vertex $a$ explodes before the root of the tree, in the case that $a$ is
$a_{1}$-_conservative_. However, when $a$ does not satisfy this condition, we
can view $a$ as a concatenation of a number of conservative sequences. That
is, we write $a=\overline{b}_{1}\cdots\overline{b}_{\ell}$, where
$\overline{b}_{i}=b_{i1}\ldots b_{im_{i}}$ for each $i\in[\ell]$ and for some
$\ell\in\mathbb{N},(m_{i})_{i\in[\ell]}\in\mathbb{N}^{\ell}$, and
$(b_{i,j})_{i\in[\ell],j\in[m_{i}]}$, such that $\overline{b}_{i}$ is
$b_{i1}$-conservative for each $i\in[\ell]$. By the independence of birth
processes of distinct individuals (or in fact, the independence of disjoint
sub-trees) by Equation (2.2), we are able to apply Lemma 4.2 to each
conservative sequence in the concatenation to arrive at a bound for the
expected number of individuals that explode before all its ancestors.

######  Proposition 4.3.

Under Assumption 2.2, there exists $K^{\prime}>0$ sufficiently large, such
that

$\mathbb{E}\left[\left|\left\\{a\in\mathcal{U}_{\infty}:a_{1}>K^{\prime},a\text{
explodes before all its ancestors}\right\\}\right|\right]<\infty.$ (4.7)

###### Proof.

As explained before the proposition statement, we think of sequences
$a\in\mathcal{U}_{\infty}$ as a concatenation of conservative sequences. Let
$a=a_{1}\ldots a_{m}$ be a sequence of length $m\in\mathbb{N}$, and assume
that there exist $k\in[m]$ and indices $I_{1}<I_{2}<\ldots<I_{k}$ such that
$a_{1}=:a_{I_{1}}<a_{I_{2}}<\ldots<a_{I_{k}}$. That is, the $I_{j}$ are the
indices of the running maxima of the sequence $a$. For brevity of notation, we
also set $I_{k+1}:=m+1$, and set $a_{0}=\varnothing$.

To show that $a$ explodes before all its ancestors, we think of $a$ as a
concatenation of the conservative sequences $a_{I_{j}}\cdots a_{I_{j+1}-1}$,
with $j\in[k]$. By the fact that, for each $u\in\mathcal{U}_{\infty}$, the
sequence $(\mathcal{P}_{i}(u))_{i\in\mathbb{N}}$ is independent and
distributed like $(\mathcal{P}_{i}(\varnothing))_{i\in\mathbb{N}}$, each of
these conservative sequences can be seen as corresponding to an
$a_{I_{j}}$-conservative individual rooted at $a_{I_{j}-1}$, $j\in[k]$. We can
thus apply Lemma 4.2 to all these concatenated sequences.

Since, by definition we have $a_{I_{\ell+1}}>a_{I_{\ell}}$, applying a similar
logic to (4.3) we have the following inclusion:

$\displaystyle E_{a}:={}$ $\displaystyle\\{a\text{ explodes}\text{ before any
of its ancestors explodes}\\}$ (4.8)
$\displaystyle\bigcap_{\ell=1}^{k}\\{a_{1}\cdots a_{I_{\ell+1}-1}\text{ gives
birth to at least }a_{I_{\ell}}\text{ children before }a_{1}\cdots
a_{I_{\ell}-1}\text{ explodes}\\}$ (4.9) $\displaystyle={}$
$\displaystyle\bigcap_{\ell=1}^{k}\left\\{\left(\sum_{j=I_{\ell}}^{I_{\ell+1}-2}\mathcal{P}_{a_{j+1}}(a_{|_{j}})\right)+\mathcal{P}_{a_{I_{\ell}}}(a_{|_{I_{\ell+1}-1}})\leq\sum_{i=a_{I_{\ell}}+1}^{\infty}X(a_{1}\cdots
a_{I_{\ell}-1}i)\right\\}=:\bigcap_{\ell=1}^{k}E_{a,\ell}.$ (4.10)

Now, note that the events $(E_{a,\ell},\ell\in[k])$ are not independent,
since, for a given $\ell$, the term
$\mathcal{P}_{a_{I_{\ell}}}(a_{|_{I_{\ell+1}-1}})$ appearing in $E_{a,\ell}$
may be correlated with the term
$\sum_{i=a_{I_{\ell+1}}+1}^{\infty}X(a_{1}\cdots a_{I_{\ell+1}-1}i)$ appearing
in $E_{a,\ell+1}$. However, by the third condition of Assumption 2.2, these
events are conditionally independent, given the weights of $a$ and all its
ancestors, $W_{\varnothing},W_{a_{1}},W_{a_{1}a_{2}},\ldots,W_{a}$. Thus,

$\displaystyle\mathbb{P}{}$
$\displaystyle(E_{a}\,|\,W_{\varnothing},W_{a_{1}},W_{a_{1}a_{2}},\ldots,W_{a})$
$\displaystyle=\prod_{\ell=1}^{k}\mathbb{P}\left(\left(\sum_{j=I_{\ell}}^{I_{\ell+1}-2}\mathcal{P}_{a_{j+1}}(a_{|_{j}})\right)+\mathcal{P}_{a_{I_{\ell}}}(a_{|_{I_{\ell+1}-1}})\leq\sum_{i=a_{I_{\ell}}+1}^{\infty}X(a_{1}\cdots
a_{I_{\ell}-1}i)\,\bigg{|}\,W_{\varnothing},W_{a_{1}},W_{a_{1}a_{2}},\ldots,W_{a}\right)$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:stochastic-
bound}}}{{\leq}}\prod_{\ell=1}^{k}\mathbb{P}\left(\left(\sum_{j=I_{\ell}}^{I_{\ell+1}-2}\mathcal{P}_{a_{j+1}}(a_{|_{j}})\right)+\mathcal{P}_{a_{I_{\ell}}}(a_{|_{I_{\ell+1}-1}})\leq
Y^{(a_{1}\cdots
a_{I_{\ell}-1})}_{a_{I_{\ell}}}\,\bigg{|}\,W_{\varnothing},W_{a_{1}},W_{a_{1}a_{2}},\ldots,W_{a}\right)$
$\displaystyle:=\prod_{\ell=1}^{k}\mathbb{P}\left(\widetilde{E}_{a,\ell}\,\Big{|}\,W_{\varnothing},W_{a_{1}},W_{a_{1}a_{2}},\ldots,W_{a}\right),$

where each $Y^{(a_{1}\cdots a_{I_{\ell}-1})}_{a_{I_{\ell}}}$ is independent
and distributed like $Y_{a_{I_{\ell}}}$. Now, each of the terms
$\widetilde{E}_{a,\ell}$ are independent, as the depend on different weights.
Hence, so are each of the terms appearing in the above product, so that

$\mathbb{P}\left(E_{a}\right)\leq\prod_{\ell=1}^{k}\mathbb{P}\left(\widetilde{E}_{a,\ell}\right).$
(4.11)

We now let $d_{j}:=I_{j+1}-I_{j}-1$ for $j\in[k-1]$ and $d_{k}:=m-I_{k}$
denote the number of entries between the running maxima in the sequence $a$.
We can then define, for $(d_{j})_{j\in[k]}\in\mathbb{N}_{0}^{k}$ (and with the
convention that $[0]$ is the empty set),

$\mathscr{P}_{k}(a_{I_{1}},a_{I_{2}},\ldots,a_{I_{k}},d_{1},\ldots,d_{k}):=\\{a\in\mathcal{U}_{\infty}:\text{
For all }j\in\\{1,\ldots,k\\}\text{ and all }i\in[d_{j}],\
a_{I_{j}+i}\in[a_{I_{j}}]\\}$ (4.12)

as the set of all sequences $a$ with running maxima
$a_{1}=a_{I_{1}},\ldots,a_{I_{k}}$ and $d_{j}$ many entries between the
$j^{\text{th}}$ and $(j+1)^{\text{th}}$ maximum. For ease of writing, we omit
the arguments of $\mathscr{P}_{k}$. We then write the expected value of the
number of individuals $a\in\mathcal{U}_{\infty}$ that explode before all their
ancestors such that $a_{1}>K^{\prime}$ as

$\displaystyle\sum_{\begin{subarray}{c}a\in\mathcal{U}_{\infty}\\\
a_{1}>K^{\prime}\end{subarray}}\mathbb{P}\left(E_{a}\right)=\sum_{m=1}^{\infty}\sum_{\begin{subarray}{c}a:|a|=m\\\
a_{1}>K^{\prime}\end{subarray}}\mathbb{P}\left(E_{a}\right)\leq\sum_{m=1}^{\infty}\sum_{k=1}^{m}\sum_{a_{I_{k}}>\ldots>a_{I_{1}}>K^{\prime}}\sum_{\begin{subarray}{c}(d_{\ell})_{\ell\in[k]}\in\mathbb{N}_{0}^{k}\\\
\sum_{\ell=1}^{k}d_{\ell}=m-k\end{subarray}}\sum_{a\in\mathscr{P}_{k}}\prod_{\ell=1}^{k}\mathbb{P}\left(\widetilde{E}_{a,\ell}\right).$
(4.13)

In the first step, we introduce a sum over all sequence lengths $m$. In the
second step, we furthermore sum over the number of running maxima $k$, the
values of the running maxima $a_{I_{1}},\ldots a_{I_{k}}$, the number of
entries $d_{\ell}$ between each maxima $I_{\ell}$ and $I_{\ell+1}$ (or between
$I_{k}$ and $m$ if $\ell=m$), and all sequences $a\in\mathscr{P}_{k}$ that
admit such running maxima and inter-maxima lengths. Moreover, we use (4.11) to
bound $\mathbb{P}\left(E_{a}\right)$ from above, now that we know the number
of running maxima in $a$.

We can now take the sum over $a\in\mathscr{P}_{k}$ into the product, due to
the fact that we can decompose each sequence
$a\in\mathscr{P}_{k}(a_{I_{1}},\ldots,a_{I_{k}},d_{1},\ldots d_{k})$ into a
concatenation of sequences $a^{(1)}\ldots a^{(k)}$, with
$a^{(\ell)}:=a_{I_{\ell}}\cdots
a_{I_{\ell+1}-1}\in\mathscr{P}_{1}(a_{I_{\ell}},d_{\ell})$ for each
$\ell\in[k]$. This yields, for $a_{I_{1}},\ldots,a_{I_{k}}$ and
$d_{1},\ldots,d_{k}$ fixed,

$\sum_{a\in\mathscr{P}_{k}}\prod_{\ell=1}^{k}\mathbb{P}\left(\widetilde{E}_{a,\ell}\right)=\prod_{\ell=1}^{k}\\!\\!\\!\\!\sum_{\begin{subarray}{c}a^{(\ell)}:|a^{(\ell)}|=d_{\ell}+1\\\
\text{$a^{(\ell)}$
$a_{I_{\ell}}$-conservative}\end{subarray}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\mathbb{P}\left(\widetilde{E}_{a,\ell}\right).$
(4.14)

We can then directly apply Lemma 4.2 to each of the sums in the product to
obtain, for some $\eta<1$ and with $C$ sufficiently large, the upper bound

$\prod_{\ell=1}^{k}\\!\\!\\!\\!\sum_{\begin{subarray}{c}a^{(\ell)}:|a^{(\ell)}|=d_{\ell}\\\
\text{$a^{(\ell)}$
$a_{I_{\ell}}$-conservative}\end{subarray}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\mathbb{P}\left(\widetilde{E}_{a,\ell}\right)\leq\prod_{\ell=1}^{k}C\eta^{d_{\ell}}\mathbb{E}\left[\mathcal{L}_{c\mu_{a_{I_{\ell}}}^{-1}}(\mathcal{P}_{a_{I_{\ell}}};W)\right]=C^{k}\eta^{\sum_{\ell=1}^{k}d_{\ell}}\prod_{\ell=1}^{k}\mathbb{E}\left[\mathcal{L}_{c\mu_{a_{I_{\ell}}}^{-1}}(\mathcal{P}_{a_{I_{\ell}}};W)\right].$
(4.15)

We substitute this in (4.11) to arrive at

$\displaystyle\sum_{m=1}^{\infty}{}$
$\displaystyle\sum_{k=1}^{m}\sum_{a_{I_{k}}>\ldots>a_{I_{1}}>K^{\prime}}\sum_{\begin{subarray}{c}(d_{j})_{j\in[k]}\in\mathbb{N}_{0}^{k}\\\
\sum_{\ell=1}^{k}d_{\ell}=m-k\end{subarray}}C^{k}\eta^{\sum_{\ell=1}^{k}d_{\ell}}\prod_{\ell=1}^{k}\mathbb{E}\left[\mathcal{L}_{c\mu_{a_{I_{\ell}}}^{-1}}(\mathcal{P}_{a_{I_{\ell}}};W)\right]$
(4.16)
$\displaystyle\leq\sum_{m=1}^{\infty}\sum_{k=1}^{m}\binom{m-1}{k-1}C^{k}\eta^{m-k}\sum_{a_{I_{1}}>K^{\prime}}\cdots\sum_{a_{I_{k}}>K^{\prime}}\prod_{\ell=1}^{k}\mathbb{E}\left[\mathcal{L}_{c\mu_{a_{I_{\ell}}}^{-1}}(\mathcal{P}_{a_{I_{\ell}}};W)\right]$
$\displaystyle=\sum_{m=1}^{\infty}\sum_{k=1}^{m}\binom{m-1}{k-1}C^{k}\eta^{m-k}\left(\sum_{a>K^{\prime}}\mathbb{E}\left[\mathcal{L}_{c\mu_{a}^{-1}}(\mathcal{P}_{a};W)\right]\right)^{k}.$

By (4.5) we can bound the innermost sum from above by $\eta/2$ when
$K^{\prime}$ is sufficiently large, so that we obtain the upper bound

$\sum_{m=1}^{\infty}\sum_{k=1}^{m}\binom{m-1}{k-1}C^{k}\eta^{m}2^{-k}=\frac{C}{2}\sum_{m=1}^{\infty}(1+C/2)^{m-1}\eta^{m}<\infty,$
(4.17)

where the last step follows when $\eta<(1+C/2)^{-1}$, which holds by choosing
$K^{\prime}$ sufficiently large, as follows from (4.5) and (4.6). ∎

The following proposition requires the following notation:

$\mathcal{U}_{L}:=\left\\{u\in\mathcal{U}_{\infty}:u_{i}\leq
L,i\in[|u|]\right\\}\cup\\{\varnothing\\}.$

Following [58], we say elements of $\mathcal{U}_{L}$ are $L$-_moderate_. We
also let $\mathcal{U}^{c}_{L}$ denote the set complement of $\mathcal{U}_{L}$.

######  Proposition 4.4.

Let $(\mathscr{T}_{t})_{t\geq 0}$ be a $(X,W)$-CMJ branching process
satisfying Condition 4 of Assumption 2.2. Then, almost surely, for all
$t\in(0,\infty)$, we have

$\left|\\{u\in\mathscr{T}_{t}:u\,\text{ is $L$-moderate}\\}\right|<\infty.$

###### Proof.

First, let $(X^{(L)},W^{(L)})$ denote the distribution of an auxiliary CMJ
branching process, where, if the symbol ‘$\sim$’ denotes equality in
distribution, we have $W^{(L)}\sim W$ and

$(X^{(L)}(j),W^{(L)})\sim\begin{cases}(X(j),W)&\text{ if $j\leq L$,}\\\
(\infty,W)&\text{otherwise.}\end{cases}$ (4.18)

In other words, a $\left(X^{(L)},W^{(L)}\right)$-CMJ process is truncated to
ensure that no node produces more than $L$ children. Moreover, if
$\mathcal{B}_{L}(u)$ denotes the distribution of the random variable
$\mathcal{B}(u)$ under the distribution of the $(X^{(L)},W^{(L)})$-CMJ
process, this definition ensures that if $u\in\mathcal{U}_{L}$ then
$\mathcal{B}_{L}(u)\sim\mathcal{B}(u)$. Now, note that, if
$(\mathscr{T}^{(L)}_{t})_{t\geq 0}$ denotes an $(X^{(L)},W^{(L)})$-CMJ
process, for each $t\in(0,\infty)$ we have
$\mathbb{E}_{(X^{(L)},W^{(L)})}\left[\xi(t)\right]\leq L$, and, by (2.7), also
$\mathbb{E}_{(X^{(L)},W^{(L)})}\left[\xi(0)\right]<1$. Therefore, by [45,
Theorem 3.1(b)], $(\mathscr{T}^{(L)}_{t})_{t\geq 0}$ is _conservative_ , i.e.
almost surely, for each $t\in(0,\infty)$,

$\left|\mathscr{T}^{(L)}_{t}\right|<\infty.$ (4.19)

We now construct a coupling of a $(X,W)$-CMJ branching process
$(\overline{\mathscr{T}}_{t})_{t\geq 0}$ with a $(X^{(L)},W^{(L)})$-CMJ
process $(\overline{\mathscr{T}}^{(L)}_{t})_{t\geq 0}$. Note that, by
definition, for each $L$-moderate $u\in\mathcal{U}_{L}$, we have
$X^{(L)}(u)\sim X(u)$. We then construct $(\overline{\mathscr{T}}_{t})_{t\geq
0}$ in the natural way from the random variables defining
$(\overline{\mathscr{T}}^{(L)}_{t})_{t\geq 0}$: for each
$u\in\mathcal{U}_{L}$, we set $(X(u),W_{u})=(X^{(L)}(u),W^{(L)}_{u})$, and for
each $u\in\mathcal{U}^{c}_{L}$, with $|u|=m\geq 1$, sample $X(u)$
independently, conditionally on the weight $W_{u_{|_{m-1}}}$. One readily
verifies that this coupling has the correct marginal distributions. Moreover,
on this coupling, almost surely, for each $t\geq 0$, we have

$\left|\\{u\in\overline{\mathscr{T}}_{t}:u\,\text{ is
$L$-moderate}\\}\,\right|=\left|\overline{\mathscr{T}}^{(L)}_{t}\right|\stackrel{{\scriptstyle\eqref{eq:non-
exposive-L}}}{{<}}\infty,$

as desired ∎

Recall that, for a $(X,W)$-Crump-Mode-Jagers branching process
$(\mathscr{T}_{t})_{t\geq 0}$, we have

$\tau_{\infty}=\lim_{k\to\infty}\tau_{k}=\inf\left\\{t>0:|\mathscr{T}_{t}|=\infty\right\\}.$

Recall also that we have
$\mathcal{T}_{\infty}=\bigcup_{k=1}^{\infty}\mathcal{T}_{k}=\bigcup_{k=1}^{\infty}\mathscr{T}_{\tau_{k}}$.

######  Lemma 4.5.

Let $(\mathscr{T}_{t})_{t\geq 0}$ be a $(X,W)$-CMJ branching process
satisfying Condition 4 of Assumption 2.2. Then,

$\mathcal{T}_{\infty}=\left\\{u\in\mathcal{U}_{\infty}:\mathcal{B}(u)<\tau_{\infty}\right\\}\subseteq\mathscr{T}_{\tau_{\infty}}.$
(4.20)

###### Proof.

The second inclusion is clear, hence we just prove the first equality. If
$|\mathcal{T}_{\infty}|<\infty$, in other words, the process becomes extinct,
then $\tau_{\infty}=\infty$ and the equality is clear. Otherwise, on the event
$\left\\{|\mathcal{T}_{\infty}|=\infty\right\\}$, since by (2.3) we have
$\tau_{\infty}<\infty$, it suffices to show that for any $k\in\mathbb{N}$,
$\tau_{k}<\tau_{\infty}$. First, we order elements of $\mathcal{U}_{\infty}$,
$u^{(1)},u^{(2)}\ldots,$ according to birth time, breaking ties with the
lexicographic ordering. Suppose that $\tau_{k}=\tau_{\infty}<\infty$ for some
$k\in\mathbb{N}$. Then, since $|\mathcal{T}_{\infty}|=\infty$, the set

$\Lambda=\\{u\in\mathcal{U}_{\infty}:\mathcal{B}(u)=\tau_{\infty}=\tau_{k}\\}$
(4.21)

is infinite and each element of $\Lambda$ is a descendant (though not
necessarily a child) of one of $u^{(1)},\ldots,u^{(k-1)}$. Now, there are two
(not mutually exclusive) cases: either there exists a minimal element
$u^{\prime}\in\Lambda$ such that $\Lambda$ contains infinitely many elements
of the form $u^{\prime}v\in\Lambda$, with $v\in\mathcal{U}_{\infty}$, or, one
of $u^{(1)},\ldots,u^{(k-1)}$ has infinitely many children in $\Lambda$. The
latter case occurs with probability $0$, because, by Equation (2.6), for each
$j\in[k-1]$ and $n\in\mathbb{N}$, we have $\sum_{i=n+1}^{\infty}X(u^{(j)}i)>0$
almost surely. Hence, a single individual cannot produce infinitely many
children instantaneously. But now, for the prior case, the size of the
collection

$\left\\{u^{\prime}v:v\in\mathcal{U}_{\infty}\right\\},$ (4.22)

is the total progeny of a Bienaymé-Galton-Watson branching process with
offspring distribution $\xi^{(u^{\prime})}(0)\sim\xi(0)$, and by (2.7), this
is finite almost surely. We deduce that, on
$\left\\{|\mathcal{T}_{\infty}|=\infty\right\\}$, we have
$\tau_{k}<\tau_{\infty}$ almost surely. ∎

######  Lemma 4.6.

Let $(\mathscr{T}_{t})_{t\geq 0}$ be a $(X,W)$-CMJ branching process that
satisfies Assumption 2.2. Almost surely,

$\tau_{\infty}=\inf_{u\in\mathcal{T}_{\infty}}\left\\{\mathcal{B}(u)+\mathcal{P}(u)\right\\}.$
(4.23)

###### Proof.

First, as a shorthand in this proof, we define
$\tau^{+}_{\infty}:=\inf_{u\in\mathcal{T}_{\infty}}\left\\{\mathcal{B}(u)+\mathcal{P}(u)\right\\}$,
so that we need only show that $\tau_{\infty}=\tau^{+}_{\infty}$ almost
surely. Note that, for each $u\in\mathcal{U}_{\infty}$, we have
$\tau_{\infty}\leq\mathcal{B}(u)+\mathcal{P}(u)$ and hence
$\tau_{\infty}\leq\tau^{+}_{\infty}$. Moreover, Assumption 2.2 guarantees that
$\mathcal{P}(\varnothing)<\infty$ almost surely, hence, in particular,
$\tau_{\infty}\leq\mathcal{P}(\varnothing)<\infty$. Thus, by Proposition 4.4
and Lemma 4.5, for any $L-1\in\mathbb{N}$,
$\mathcal{T}_{\infty}\subseteq\mathscr{T}_{\tau_{\infty}}$ contains only
finitely many $(L-1)$-moderate elements. Since $\mathcal{T}_{\infty}$ is
almost surely infinite (because of Condition 1 of Assumption 2.2), by the
pigeonhole principle, there must be infinitely many elements of the form
$u^{*}L\in\mathcal{T}_{\infty}$, with $u^{*}\in\mathcal{U}_{\infty}$. Now, for
such $u^{*}$ and for any $\varepsilon>0$,

$\lim_{L\to\infty}\mathbb{P}\left(\mathcal{B}(u^{*})+\mathcal{P}(u^{*})-\mathcal{B}(u^{*}L)>\varepsilon\right)=\lim_{L\to\infty}\mathbb{P}\left(\sum_{j=L+1}^{\infty}X(u^{*}j)>\varepsilon\right)\leq\lim_{L\to\infty}\mathbb{P}\left(Y_{L}>\varepsilon\right)=0.$

Formally, to find these elements $u^{*}L$ we must condition on the sigma-
algebra generated by the ‘information’ in $\mathcal{T}_{\infty}$. Thus,
suppose that
$\mathscr{W}(\mathcal{T}_{\infty}):=\bigcup_{k\in\mathbb{N}}\mathscr{W}_{\tau_{k}}$
denotes the sigma algebra generated by the random variables
$\\{(\mathcal{B}(u),W_{u}):u\in\mathcal{T}_{\infty}\\}$. Clearly,
$\tau_{\infty}$ and $\mathcal{T}_{\infty}$ are
$\mathscr{W}(\mathcal{T}_{\infty})$-measurable. Now, if (conditioning on this
sigma algebra) there exists $u^{*}\in\mathcal{T}_{\infty}$ such that for each
$j\in\mathbb{N}$ we have $u^{*}j\in\mathcal{T}_{\infty}$, then
$\mathcal{B}(u^{*}j)\leq\tau_{\infty}$ for each $j\in\mathbb{N}$. Hence,
$\mathcal{B}(u^{*})+\mathcal{P}(u^{*})=\tau_{\infty}$, and we are done.
Otherwise, for any $L\in\mathbb{N}$, we can guarantee the existence of
$u^{*}\in\mathcal{T}_{\infty}$ and a final $J_{L}\geq L$ such that
$u^{*}J_{L}\in\mathcal{T}_{\infty}$ but
$u^{*}(J_{L}+1)\notin\mathcal{T}_{\infty}$. Then, for any $\varepsilon>0$,

$\displaystyle\mathbb{P}\left(\tau^{+}_{\infty}-\tau_{\infty}>\varepsilon\,|\,\mathscr{W}(\mathcal{T}_{\infty})\right)$
$\displaystyle\leq\mathbb{P}\left(\mathcal{B}(u^{*})+\mathcal{P}(u^{*})-\tau_{\infty}>\varepsilon\,|\,\mathscr{W}(\mathcal{T}_{\infty})\right)$
$\displaystyle\leq\mathbb{P}\left(\sum_{j=J_{L}+1}^{\infty}X(u^{*}j)>\varepsilon\,\bigg{|}\,\mathscr{W}(\mathcal{T}_{\infty})\right)\leq\mathbb{P}\left(Y_{L}\geq\varepsilon\right).$

Taking limits $L\to\infty$ and then $\varepsilon\to 0$, we deduce that,
$\tau^{+}_{\infty}=\tau_{\infty}$ almost surely, as required. ∎

####  4.1.1 Proof of Theorem 2.5

###### Proof of Theorem 2.5.

Suppose that $K^{\prime}$ is taken as in Proposition 4.3. Note that we may
view any $w\in\mathcal{U}_{\infty}$ as a concatenation $w=uv$, where
$u\in\mathcal{U}_{K^{\prime}}$ is $K^{\prime}$-moderate, and $v=v_{1}\cdots
v_{k}$, where $v_{1}>K^{\prime}$ (here we also allow $v$ to be empty, so that
$K^{\prime}$-moderate nodes $w$ may also be interpreted as a concatenation).
Now, note that (on $\mathcal{B}(u)<\infty$) the birth times
$\mathcal{B}(uv)-\mathcal{B}(u)\sim\mathcal{B}(v)$, and thus, by arguments
analogous to those appearing in Proposition 4.3, for any
$u\in\mathcal{U}_{\infty}$ (in particular for $u\in\mathcal{U}_{K^{\prime}}$),

$\mathbb{E}\left[\left|\left\\{a=a_{1}\cdots
a_{m}\in\mathcal{U}_{\infty}:a_{1}>K^{\prime},ua\text{ explodes before
}ua_{|_{m-1}},ua_{|_{m-2}},\ldots,u\right\\}\right|\right]<\infty.$ (4.24)

Now, since $\tau_{\infty}<\infty$ almost surely, we infer from Proposition 4.4
with $L=K^{\prime}$, that
$|\\{u\in\mathcal{U}_{K^{\prime}}:\mathcal{B}(u)\leq\tau_{\infty}\\}|<\infty$
almost surely. Therefore, by (4.24), the set

$S:=\left\\{u\in\mathcal{U}_{\infty}:\mathcal{B}(u)\leq\tau_{\infty},u\text{
explodes before all of its ancestors}\right\\}.$ (4.25)

is finite almost surely. By the definition of $S$ and the fact that the
infimum of a finite set is attained by (at least) one of the elements, by
Lemma 4.6, almost surely there exists $u^{*}\in S$ such that

$\mathcal{B}(u^{*})+\mathcal{P}(u^{*})=\inf_{v\in
S}\\{\mathcal{B}(v)+\mathcal{P}(v)\\}=\inf_{u\in\mathcal{U}_{\infty}}\\{\mathcal{B}(u)+\mathcal{P}(u)\\}=\tau_{\infty}.$

This implies that $u^{*}$ has infinite degree in
$\mathscr{T}_{\tau_{\infty}}$. Moreover, since by Condition 1 of Assumption
2.2 we have $\sum_{i=n+1}^{\infty}X(u^{*}i)>0$ almost surely, it follows that
for each $i\in\mathbb{N}$ we have $\mathcal{B}(u^{*}i)<\tau_{\infty}$ almost
surely. Therefore, by the equality in (4.20), $u^{*}$ has infinite degree in
$\mathcal{T}_{\infty}$ as well. ∎

###  4.2 Sufficient criteria for an infinite path and structural results in
the star regime

To prove Theorem 2.8, we first state and prove the following lemma.

######  Lemma 4.7.

Let $(\mathscr{T}_{t})_{t\geq 0}$ be a $(X,W)$-CMJ branching process. Under
Assumption 2.6,

$\mathbb{P}\left(\bigcap_{u\in\mathcal{U}_{\infty}}\bigcap_{j=1}^{\infty}\bigcup_{i=j}^{\infty}\left\\{\mathcal{B}(ui)+\mathcal{P}(ui)<\mathcal{B}(u)+\mathcal{P}(u)\right\\}\right)=1.$
(4.26)

###### Proof.

We first fix $u\in\mathcal{U}_{\infty}$ and condition on the random variables
$\mathcal{B}(u)$ and $W_{u}$. We then sample each of the values of
$\mathcal{P}(ui)$, then the values of $X_{W_{u}}(ui)$, for $i\in\mathbb{N}$.
Note that for each $u\in\mathcal{U}_{\infty}$, the random variables
$(\mathcal{P}(ui))_{i\in\mathbb{N}}$ are i.i.d. and distributed like
$\mathcal{P}(i)$. Thus, by (2.9) and the converse of the Borel-Cantelli lemma,
on sampling each $\mathcal{P}(ui)$, for any $w\in S$ with probability $1$, we
have $\mathcal{P}(ui)<\nu^{w}_{i}$ infinitely often. As a result,
conditionally on the value of the weight $W_{u}$, with probability $1$ we have
$\mathcal{P}(ui)<\nu^{W_{u}}_{i}$ for infinitely many $i\in\mathbb{N}$.
Conditioning on this event, let $i_{1},i_{2},\ldots,$ denote indices such
that, for each $\ell\in\mathbb{N}$, we have
$\mathcal{P}(ui_{\ell})<\nu^{W_{u}}_{i_{\ell}}$ almost surely. Then, by
(2.10), there exists $I_{0}\in\mathbb{N}$, such that, for some
$\delta=\delta(I_{0})>0$ and for all $i_{\ell}\geq I_{0}$,

$\mathbb{P}\left(\sum_{k=i_{\ell}+1}^{\infty}X_{W_{u}}(uk)\geq\nu^{W_{u}}_{i_{\ell}}\,\bigg{|}\,W_{u}\right)\geq\delta.$

As a result, for some $\phi(i_{\ell})>i_{\ell}$ sufficiently large,

$\mathbb{P}\left(\sum_{k=i_{\ell}+1}^{\phi(i_{\ell})}X_{W_{u}}(uk)\geq\nu^{W_{u}}_{i_{j}}\,\bigg{|}\,W_{u}\right)\geq\frac{\delta}{2}.$

We now pass to a sub-sequence $(i_{\ell_{n}})_{n\in\mathbb{N}}$ of
$(i_{\ell})_{\ell\in\mathbb{N}}$, such that $i_{\ell_{1}}>I_{0}$, and
$i_{\ell_{n+1}}=\inf\\{i_{\ell}:\ell\in\mathbb{N},i_{\ell}>\phi(i_{\ell_{n}})\\}$.
Then, by Equation (2.2), conditionally on $W_{u}$, the random variables

$\left(\sum_{k=i_{\ell_{n}}+1}^{i_{\ell_{n+1}}}X_{W_{u}}(uk)\right)_{n\in\mathbb{N}}$

are independent of each other. Again applying the converse of the Borel-
Cantelli lemma, we obtain

$\mathbb{P}\left(\bigcap_{j=1}^{\infty}\bigcup_{n=j}^{\infty}\left\\{\sum_{k=i_{\ell_{n}}+1}^{i_{\ell_{n+1}}}X_{W_{u}}(uk)\geq\nu^{W_{u}}_{i_{\ell_{n}}}\right\\}\,\Bigg{|}\,\mathcal{B}(u),W_{u}\right)=1.$

But for every index $i^{*}\in(i_{\ell_{n}})_{n\in\mathbb{N}}$, we have by the
definition of the sequence $(i_{\ell})_{\ell\in\mathbb{N}}$,

$\mathcal{P}(ui^{*})<\nu^{W_{u}}_{i^{*}}\leq\sum_{i=i^{*}+1}^{\infty}X_{W_{u}}(ui).$

Adding $\mathcal{B}(u)+\sum_{i=1}^{i^{*}}X_{W_{u}}(ui)$ (which equals
$\mathcal{B}(ui^{*})$) to both sides, we deduce that, almost surely,
conditionally on $\mathcal{B}(u)$ and $W_{u}$,

$\mathcal{B}(ui^{*})+\mathcal{P}(ui^{*})<\mathcal{B}(u)+\mathcal{P}(u).$

Then, by taking expectations over $\mathcal{B}(u)$ and $W_{u}$, we have

$\mathbb{P}\left(\bigcap_{j=1}^{\infty}\bigcup_{i=j}^{\infty}\left\\{\mathcal{B}(ui)+\mathcal{P}(ui)<\mathcal{B}(u)+\mathcal{P}(u)\right\\}\right)=1.$
(4.27)

But now, since $\mathcal{U}_{\infty}$ is countable, we deduce (4.26). ∎

####  4.2.1 Proof of Theorem 2.8

###### Proof of Theorem 2.8.

On $\left\\{\left|\mathcal{T}_{\infty}\right|=\infty\right\\}$, let us first
assume that $\mathcal{T}_{\infty}$ does not contain a node of infinite degree.
It then immediately follows from Kőnigs Lemma (Lemma 2.1) that
$\mathcal{T}_{\infty}$ contains an infinite path. We then assume, on
$\left\\{\left|\mathcal{T}_{\infty}\right|=\infty\right\\}$, that there exists
$u^{*}\in\mathcal{T}_{\infty}$ such that $u^{*}$ has infinite degree, i.e.
$\mathcal{B}(u^{*})+\mathcal{P}(u^{*})=\tau_{\infty}$. But then, by Equation
(4.26) from Lemma 4.7, there must be a child of $u^{*}$, $u^{*}j$ say, such
that
$\mathcal{B}(u^{*}j)+\mathcal{P}(u^{*}j)<\mathcal{B}(u^{*})+\mathcal{P}(u^{*})=\tau_{\infty}$,
a contradiction. ∎

####  4.2.2 Proof of Theorem 2.10

###### Proof of Theorem 2.10.

For each $u\in\mathcal{U}_{\infty}$, we set

$(\mathscr{T}^{(u)}_{t})_{t\geq
0}:=\left\\{uv\in\mathcal{U}_{\infty}:\sum_{j=0}^{\ell-1}\left(\mathcal{P}_{v_{j+1}}(uv_{|_{j}})\leq
t\right)\right\\},$

where we recall that if $v=v_{1}\cdots v_{m}$ then $uv_{|_{j}}=uv_{1}\cdots
v_{j}$. Note that, if $\mathcal{B}(u)<\infty$, by (1.3) we have
$\mathscr{T}^{(u)}_{t}=\left\\{uv:uv\in\mathscr{T}_{t+\mathcal{B}(u)}\right\\}.$
However, the definition we use allows us to define
$(\mathscr{T}^{(u)}_{t})_{t\geq 0}$ even when $\mathcal{B}(u)=\infty$. Note
that, by (2.1), $(\mathscr{T}^{(u)}_{t})_{t\geq 0}\sim(\mathscr{T}_{t})_{t\geq
0}$, and for each $u\in\mathcal{U}_{\infty}$, the
$((\mathscr{T}^{(ui)}_{t})_{t\geq 0})_{i\in\mathbb{N}}$ are i.i.d. Now, upon
sampling each of the random variables $(X(ui))_{i\in\mathbb{N}}$, (regardless
of whether $\mathcal{B}(u)<\infty$ or not), recalling the notation from (1.4),
note that if we have

$\mathcal{P}_{T}(ui)<\sum_{k=i+1}^{\infty}X(uk),$

then, if $\mathcal{B}(u)+\mathcal{P}(u)<\infty$, we have
$\mathcal{B}(ui)+\mathcal{P}_{T}(ui)<\mathcal{B}(u)+\mathcal{P}(u)$. Now, by
exploiting an almost identical argument to the proof of Lemma 4.7 (as in
Equations (2.9) and (2.10)), combining Equations (2.11) and (2.12) from
Condition 1 of Assumption 2.9 allows us to deduce that

$\mathbb{P}\left(\bigcap_{u\in\mathcal{U}_{\infty}}\bigcap_{j=1}^{\infty}\bigcup_{i=j}^{\infty}\left\\{\mathcal{P}_{T}(ui)<\sum_{k=i+1}^{\infty}X(uk)\right\\}\right)=1.$
(4.28)

But then, this implies that if a node $u^{*}\in\mathcal{U}_{\infty}$ has
infinite degree in $\mathcal{T}_{\infty}$, there exist infinitely many indices
$i$ such that
$\mathcal{B}(u^{*}i)+\mathcal{P}_{T}(u^{*}i)<\mathcal{B}(u^{*})+\mathcal{P}(u^{*})$,
and hence, by Lemma 4.5, that $(u^{*}i)T\subseteq\mathcal{T}_{\infty}$. This
proves the first statement.

For the second statement, by Equation (2.13) we have

$\displaystyle\sum_{i=1}^{\infty}\mathbb{P}\left(\mathcal{P}_{T}(ui)<\sum_{k=i+1}^{\infty}X(uk)\,\bigg{|}\,W_{u}\right)<\infty,$
(4.29)

almost surely. Thus, by a conditional analogue of the Borel-Cantelli lemma,

$\mathbb{P}\left(\bigcap_{j=1}^{\infty}\bigcup_{i=j}^{\infty}\left\\{\mathcal{P}_{T}(ui)<\sum_{k=i+1}^{\infty}X(uk)\right\\}\,\bigg{|}\,W_{u}\right)=0,$

almost surely. Taking expectations over $W_{u}$ and a union bound over
$u\in\mathcal{U}_{\infty}$, we deduce that

$\mathbb{P}\left(\bigcup_{u\in\mathcal{U}_{\infty}}\bigcap_{j=1}^{\infty}\bigcup_{i=j}^{\infty}\left\\{\mathcal{P}_{T}(ui)<\sum_{k=i+1}^{\infty}X(uk)\right\\}\right)=0.$

This implies that, if $u^{*}$ is such that
$\mathcal{B}(u^{*})+\mathcal{P}(u^{*})=\tau_{\infty}$, almost surely, there
exist only finitely many indices $i$ such that $T$ appears as a sub-tree of
$u^{*}i$ in $\mathcal{T}_{\infty}$.

The final statement in Item 3 follows from the proof of Theorem 2.5, Equation
4.25 in particular, which states that $\mathcal{T}_{\infty}$ contains a finite
number of stars $u^{*}$ in $\mathcal{T}_{\infty}$ almost surely under
Assumption 2.2. ∎

###  4.3 Uniqueness conditions related to the existence of a star or an
infinite path

In this section, it is useful to introduce some extra notation. First, recall
that, given $u\in\mathcal{U}_{\infty}$, the random variable
$\mathcal{B}(u)+\mathcal{P}(u)$ determines the time at which $u$ ‘explodes’,
in the sense that, if $\sigma=\mathcal{B}(u)+\mathcal{P}(u)$, the individual
$u$ has infinite degree in $\mathscr{T}_{\sigma}$. We also define the random
variable $\tau_{\operatorname{path}}(u)$ as the amount of time taken after the
‘birth’ of $u$, for there to be an infinite path containing $u$ in the process
$(\mathscr{T}_{t})_{t\geq 0}$. To make this more precise, we extend the
notation for elements $v\in\mathcal{U}_{\infty}$ to
$v\in\mathbb{N}^{\mathbb{N}}$: for $v=v_{1}v_{2}\cdots\in\mathbb{N}^{\infty}$
and $\ell\in\mathbb{N}$, we set $v_{|_{\ell}}=v_{1}v_{2}\cdots
v_{\ell}\in\mathcal{U}_{\infty}$. Then, for $u\in\mathcal{U}_{\infty}$ we set

$\tau_{\operatorname{path}}(u):=\inf_{t\geq 0}\left\\{\exists
v\in\mathbb{N}^{\infty}:\sum_{j=0}^{i-1}\left(\mathcal{P}_{v_{j+1}}(uv_{|_{j}})\right)\leq
t\text{ for all }i\in\mathbb{N}\right\\}.$

Thus, by this definition, if
$\sigma=\mathcal{B}(u)+\tau_{\operatorname{path}}(u)$ then
$\mathscr{T}_{\sigma}$ contains an infinite path passing through $u$.

The approach we use in this section is surprisingly simple, and reminiscent of
the approach used, for example, in [58] to show a unique node has infinite
degree: we show that, for each $u\in\mathcal{U}_{\infty}$, the random
variables $\tau_{\operatorname{path}}(u)$ or $\mathcal{P}(u)$ have
distributions that contain no atoms on $[0,\infty)$. We use this to show that
for any pair $u,v\in\mathcal{U}_{\infty}$, (which have ‘independent’ sub-
trees), the probability that both have infinite degrees, or lie on infinite
paths simultaneously is $0$. As $\mathcal{U}_{\infty}$ is countable, we can
readily take a union bound over all these pairs, and deduce the result.
Condition 2 of Assumption 2.11 (and (2.1)) already provides this property to
$\mathcal{P}(u)$. For $\tau_{\operatorname{path}}(u)$ we use the following
result.

######  Lemma 4.8.

Let $(\mathscr{T}_{t})_{t\geq 0}$ be an explosive $(X,W)$-CMJ process. Under
Condition 3 of Assumption 2.11, the distribution of
$\tau_{\operatorname{path}}(\varnothing)$ contains no atom on $[0,\infty)$.

###### Proof.

We argue by contradiction and suppose that
$\tau_{\operatorname{path}}(\varnothing)$ contains an atom. Set

$\widetilde{a}:=\inf\left\\{t\in[0,\infty):\mathbb{P}\left(\tau_{\operatorname{path}}(\varnothing)=t\right)>0\right\\}.$
(4.30)

Now, exploiting Condition 3 of Assumption 2.11 and the definition of
$\widetilde{a}$, let $a$ be such that
$\mathbb{P}\left(\tau_{\operatorname{path}}(\varnothing)=a\right)>0$, and
$a-\widetilde{a}<\varepsilon$ (with $\varepsilon$ as in Condition 3). Let
$\mathcal{G}_{1}$ denote the sigma algebra generated by
$(\mathcal{B}(i))_{i\in\mathbb{N}}$. The ancestral node $\varnothing$ contains
an infinite path precisely when one of its children lies on an infinite path.
Thus,

$\displaystyle\mathbb{P}\left(\tau_{\operatorname{path}}(\varnothing)=a\,\big{|}\,\mathcal{G}_{1}\right)$
$\displaystyle=\mathbb{P}\left(\bigcup_{i=1}^{\infty}\left\\{\tau_{\operatorname{path}}(i)=a-\mathcal{B}(i)\right\\}\,\bigg{|}\,\mathcal{G}_{1}\right)$
(4.31)
$\displaystyle\leq\sum_{i=1}^{\infty}\mathbb{P}\left(\tau_{\operatorname{path}}(i)=a-\mathcal{B}(i)\,\bigg{|}\,\mathcal{G}_{1}\right).$
(4.32)

Now, as the event $\\{\tau_{\operatorname{path}}(i)=a-\mathcal{B}(i)\\}$
depends on $\mathcal{G}_{1}$ only via the sigma algebra generated by
$\mathcal{B}(i)$, we may re-write the summands on the right hand side as

$\displaystyle\mathbb{P}\left(\tau_{\operatorname{path}}(i)=a-\mathcal{B}(i)\,\bigg{|}\,\mathcal{B}(i)\right)$
$\displaystyle=\mathbb{P}\left(\tau_{\operatorname{path}}(i)=a-\mathcal{B}(i)\,\bigg{|}\,\mathcal{B}(i)\right)\mathbf{1}_{\left\\{\mathcal{B}(i)<\varepsilon\right\\}}$
$\displaystyle\hskip
28.45274pt+\mathbb{P}\left(\tau_{\operatorname{path}}(i)=a-\mathcal{B}(i)\,\bigg{|}\,\mathcal{B}(i)\right)\mathbf{1}_{\left\\{\mathcal{B}(i)\geq\varepsilon\right\\}}.$

Now, note that (by (2.1)), as $\tau_{\operatorname{path}}(i)$ is identically
distributed to $\tau_{\operatorname{path}}(\varnothing)$, the distribution of
$\tau_{\operatorname{path}}(i)$ has no atom smaller than
$\widetilde{a}>a-\varepsilon$. As a result, on the event
$\mathcal{B}(i)\geq\varepsilon$,

$\mathbb{P}\left(\tau_{\operatorname{path}}(i)=a-\mathcal{B}(i)\,\bigg{|}\,\mathcal{B}(i)\right)=0,\quad\text{
almost surely. }$

Combining this with (4.31), this leads to the inequality

$\mathbb{P}\left(\tau_{\operatorname{path}}(\varnothing)=a\,\big{|}\,\mathcal{G}_{1}\right)\leq\sum_{i=1}^{\infty}\mathbb{P}\left(\tau_{\operatorname{path}}(i)=a-\mathcal{B}(i)\,\bigg{|}\,\mathcal{B}(i)\right)\mathbf{1}_{\left\\{\mathcal{B}(i)<\varepsilon\right\\}},$

and since
$\mathbb{P}\left(\tau_{\operatorname{path}}(\varnothing)=a\right)>0$, it must
be the case that for some $i$,

$0<\mathbb{P}\left(\tau_{\operatorname{path}}(i)=a-\mathcal{B}(i),\mathcal{B}(i)<\varepsilon\right)=\mathbb{E}\left[\mathbb{P}\left(\tau_{\operatorname{path}}(i)=a-\mathcal{B}(i)\,\bigg{|}\,\mathcal{B}(i)\right)\mathbf{1}_{\left\\{\mathcal{B}(i)<\varepsilon\right\\}}\right].$

But now, when we integrate over the possible values of $\mathcal{B}(i)$ on the
right-hand side, this implies that

$\left\\{\mathcal{B}(i)\in[0,\varepsilon):\mathbb{P}\left(\tau_{\operatorname{path}}(i)=a-\mathcal{B}(i)\,\bigg{|}\,\mathcal{B}(i)\right)>0\right\\}$

is a set of positive measure with respect to $\mathbb{P}$. But then this
implies that, with respect to the distribution induced by $\mathcal{B}(i)$,
the set

$\left\\{x\in[0,\varepsilon):\mathbb{P}\left(\tau_{\operatorname{path}}(i)=a-x\right)>0\right\\},$
(4.33)

has positive measure. But now, as the set of atoms of the distribution of
$\tau_{\operatorname{path}}(i)$ (as with any finite measure) must always be
countable, (4.33) must be countable. As the distribution of $\mathcal{B}(i)$
contains no atoms on $[0,\varepsilon)$ by Condition 3 in Assumption 2.11,
countable subsets of $[0,\varepsilon)$ are null sets with respect to the
distribution induced by $\mathcal{B}(i)$; this implies that (4.33) must be a
null set, a contradiction. ∎

####  4.3.1 Proof of Theorem 2.12

###### Proof of Theorem 2.12.

The first and second statements of the theorem are clearly satisfied on
$\left\\{|\mathcal{T}_{\infty}|<\infty\right\\}$. Now note that, for
$\mathcal{T}_{\infty}$ to have two nodes of infinite degree, there must be two
elements $u,v\in\mathcal{U}_{\infty}$ such that

$\mathcal{B}(u)+\mathcal{P}(u)=\mathcal{B}(v)+\mathcal{P}(v)=\tau_{\infty}.$

By Equation (2.3), $\tau_{\infty}<\infty$ almost surely on
$\left\\{|\mathcal{T}_{\infty}|=\infty\right\\}$, hence the left-hand side
must also be finite. But now, note that, as long as $v$ is not an ancestor of
$u$, (which is the case if $v>_{L}u$ with respect to the lexicographical
ordering), then $\mathcal{P}(v)$ is independent of
$\mathcal{B}(u),\mathcal{B}(v)$, and $\mathcal{P}(u)$. Moreover, by Condition
2 of Assumption 2.11, $\mathcal{P}(v)$ has no atom on $[0,\infty)$. Therefore,
for $v>_{L}u$ we have,

$\mathbb{P}\left(\mathcal{P}(v)=\mathcal{P}(u)+\mathcal{B}(v)-\mathcal{B}(u)\,\bigg{|}\,\mathcal{B}(u),\mathcal{B}(v),\mathcal{P}(v)\right)\mathbf{1}_{\\{\mathcal{B}(u),\mathcal{B}(v),\mathcal{P}(u)<\infty\\}}=0\quad\text{almost
surely, }$

and hence, for any $u,v\in\mathcal{U}_{\infty}$ with $u\neq v$,
$\mathbb{P}\left(\mathcal{B}(u)+\mathcal{P}(u)=\mathcal{B}(v)+\mathcal{P}(v),\mathcal{B}(u)+\mathcal{P}(u)<\infty\right)=0$.
But then, since $\mathcal{U}_{\infty}$ is countable, taking a union bound, we
deduce

$\displaystyle\mathbb{P}\left(\text{$\mathcal{T}_{\infty}$ has two nodes of
infinite degree}\right)$ (4.34) $\displaystyle\hskip
28.45274pt\leq\mathbb{P}\left(\bigcup_{u,v\in\mathcal{U}_{\infty},u\neq
v}\big{\\{}\mathcal{B}(u)+\mathcal{P}(u)=\mathcal{B}(v)+\mathcal{P}(v),\mathcal{B}(u)+\mathcal{P}(u)<\infty\big{\\}}\right)$
$\displaystyle\hskip 28.45274pt\leq\sum_{u,v\in\mathcal{U}_{\infty},u\neq
v}\mathbb{P}\big{(}\mathcal{B}(u)+\mathcal{P}(u)=\mathcal{B}(v)+\mathcal{P}(v),\mathcal{B}(u)+\mathcal{P}(u)<\infty\big{)}=0.$

This proves the first statement of the theorem. In a similar manner, using
Condition 3 of Assumption 2.11 and Lemma 4.8, we have

$\displaystyle\mathbb{P}\left(\text{$\mathcal{T}_{\infty}$ has two infinite
paths}\right)$ (4.35) $\displaystyle\hskip
28.45274pt\leq\mathbb{P}\left(\bigcup_{u,v\in\mathcal{U}_{\infty},u\neq
v}\big{\\{}\mathcal{B}(u)+\tau_{\operatorname{path}}(u)=\mathcal{B}(v)+\tau_{\operatorname{path}}(v),\mathcal{B}(u)+\tau_{\operatorname{path}}(u)<\infty\big{\\}}\right)$
$\displaystyle\hskip 28.45274pt\leq\sum_{u,v\in\mathcal{U}_{\infty},u\neq
v}\mathbb{P}\big{(}\mathcal{B}(u)+\tau_{\operatorname{path}}(u)=\mathcal{B}(v)+\tau_{\operatorname{path}}(v),\mathcal{B}(u)+\tau_{\operatorname{path}}(u)<\infty\big{)}=0,$

proving the second statement. Finally, for the third statement we need only
prove that a node of infinite degree and an infinite path cannot co-exist.
Note that there may be $u$ such that $\mathcal{P}(u)$ and
$\tau_{\operatorname{path}}(\varnothing)$ are correlated, for example, if
$\varnothing$ is a parent of $u$. But, noting
$\mathbb{N}^{k}=\left\\{u\in\mathcal{U}_{\infty}:|u|=k\right\\}$,

$\displaystyle\left\\{\tau_{\operatorname{path}}(\varnothing)=\mathcal{B}(u)+\mathcal{P}(u),\tau_{\operatorname{path}}(\varnothing)<\infty\right\\}\subseteq\bigcup_{v\in\mathbb{N}^{|u|+1}}\left\\{\mathcal{B}(v)+\tau_{\operatorname{path}}(v)=\mathcal{B}(u)+\mathcal{P}(u),\mathcal{B}(v)+\tau_{\operatorname{path}}(v)<\infty\right\\}.$

Now, for $v\in\mathbb{N}^{|u|+1}$, $\tau_{\operatorname{path}}(v)$ _is_
independent of $u$, and therefore, for each $v\in\mathbb{N}^{|u|+1}$ we have

$\displaystyle\mathbb{P}\left(\mathcal{B}(v)+\tau_{\operatorname{path}}(v)=\mathcal{B}(u)+\mathcal{P}(u)\,\big{|}\,\mathcal{B}(v),\mathcal{B}(u),\mathcal{P}(u)\right)\mathbf{1}_{\\{\mathcal{B}(v),\mathcal{B}(u),\mathcal{P}(u)<\infty\\}}$
$\displaystyle\hskip
56.9055pt=\mathbb{P}\left(\tau_{\operatorname{path}}(v)=\mathcal{B}(u)+\mathcal{P}(u)-\mathcal{B}(v)\,\big{|}\,\mathcal{B}(v),\mathcal{B}(u),\mathcal{P}(u)\right)\mathbf{1}_{\\{\mathcal{B}(v),\mathcal{B}(u),\mathcal{P}(u)<\infty\\}}=0,$

almost surely. Therefore, again using a union bound, we have

$\displaystyle\mathbb{P}\left(\text{$\mathcal{T}_{\infty}$ has an infinite