# On a sufficient condition for explosion in CMJ branching processes and
applications to recursive trees

T. Iyer111Weierstrass Institute for Applied Analysis and Stochastics,
Mohrenstrasse 39, 10117 Berlin, Germany.

(December 22, 2023)

###### Abstract

We provide sufficient criteria for explosion in Crump-Mode-Jagers branching
process, via the process producing an infinite path in finite time. As an
application, we deduce a curious phase-transition in the infinite tree
associated with a class of recursive tree models with fitness, showing that in
one regime every node in the tree has infinite degree, whilst in another, the
tree is locally finite, with a unique infinite path. The latter class
encompasses many models studied in the literature, including the weighted
random recursive tree, the preferential attachment tree with additive fitness,
and the Bianconi-Barabási model, or preferential attachment tree with
multiplicative fitness.

Keywords: Explosive Crump-Mode-Jagers branching processes, Bianconi-Barabási
model, preferential attachment with fitness, weighted random recursive trees.

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

##  1 Introduction

In Crump-Mode-Jagers (CMJ) branching processes, an ancestral individual
produces offspring according to a random collection of “birth times” on the
non-negative real line (representing time). At each birth time, a new
individual begins to produce offspring, according to a collection of points
identically distributed to those associated with the ancestral individual, but
now shifted by their birth time, and one is generally interested in features
of the population as time varies. For example, if for some $t\in[0,\infty)$,
there exists infinitely many individuals at time $t$, one says that explosion
occurs.

Suppose that $\xi(t)$ denotes the random number of individuals produced by the
ancestral individual by time $t$ (with $\xi(0)$ denoting the number of
individuals produced “instantaneously”). A result of Komjáthy [20, Theorem
3.1(b)] states that, if $\xi(t)<\infty$ almost surely for all $t>0$, and for
some $t_{0}>0$, we have $\mathbb{E}\left[\xi(t_{0})\right]<1$, explosion does
not occur. This is, equivalent to having $\mathbb{E}\left[\xi(0)\right]<1$ and
$\mathbb{E}\left[\xi(t)\right]<\infty$ for some $t>0$. In this short note, we
provide a sufficient condition that guarantees explosion in CMJ branching
processes, via the emergence of an infinite ancestral path of individuals in
finite time (see Theorem 3.2 and Corollary 3.3).

CMJ processes have been well studied in the so called _Malthusian_ regime (for
example [26, 28, 19]), however, far fewer results are available outside the
Malthusian regime, including, in particular, the regime where explosion may
occur. In this regard, Komjáthy [20] has made a number of foundational
contributions, under the assumption that $\xi(t)<\infty$ almost surely for all
$t>0$, (that is _sideways explosion_ does not occur), including characterising
the distribution of the explosion time in terms of the solution of a
functional fixed point equation. Necessary and sufficient conditions for
explosion in _branching random walks_ with plump offspring distributions have
been provided in [1], where the authors showed that this property is
equivalent, in this case, to a weaker condition called min-summability. This
was extended to _age dependent branching processes_ , and _processes with
incubation_ in [20, Section 5 and Section 7]. In a related work [4], the
authors provide sufficient criteria for _local explosion_ in growth-
fragmentation processes. More recently, when one allows for the possibility of
sideways explosion, sufficient criteria have been provided for explosion to
occur via an infinite path, or by a single node having infinite degree in
[18].

###  1.1 Random recursive trees with fitness

One commonly used application of CMJ branching process is to evolving random
tree models, see, for example, [31, 5, 16, 27]. In _recursive trees with
fitness_ , nodes $n$, labelled by the natural numbers, arrive one at a time,
and are assigned an i.i.d. random weight $W_{n}$. This node then is connected
with an edge directed outwards from a randomly selected target node $v$. The
node $v$ is selected at the $n$th time-step with probability proportional to a
_fitness_ function $f(\operatorname{deg}^{+}(v),W_{v})$ which incorporates
information about the out-degree of $v$ at the $n$th time-step. Particular
instances of this model include various forms of inhomogeneous preferential
attachment models, such as the Bianconi-Barabási model (introduced in [6]) and
preferential attachment with additive fitness (introduced in [14], with
various mathematical properties proved in [23, 21, 32]); and the weighted
random recursive tree [9, 29, 30]. Inhomogeneous preferential attachment
models are often used as models for the evolution of complex networks arising
in applications. As preferential attachment models tend to favour ‘early’
arriving nodes, a topic of interest is when ‘newer’ nodes can out-compete
older nodes to attain influence in the network. In this context, one is often
interested in whether or not in these models a fixed node remains the node of
maximal degree during the evolution of the network, or the index of maximum
degree changes infinitely often (i.e., whether or not there is a _persistent
hub_ , see, for example, [12, 15, 3, 23]).

The inhomogeneities in this model mean that other interesting effects can
occur: suppose that $N_{k}(n)$ denotes the number of nodes of out-degree $k$
in the model at the $n$th time-step. Note that this implies that
$\sum_{k=0}^{\infty}kN_{k}(n)/n=1$, since there are $n$ edges in the tree at
the $n$th time-step. Suppose also that $\lim_{n\to\infty}\frac{N_{k}(n)}{n}$
exists for all $k$, which we denote by $p_{k}$. Then it is conjectured [17]
that, if

$\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,
$\sum_{k=0}^{\infty}kp_{k}<1$, so that a positive fraction of ‘mass’ of edges
is lost to a sub-linear number of nodes of ‘large degrees’. This effect, which
has been proved in a number of particular instances, is known as
_condensation_ (see, for example, [8, 11, 13, 10]). Moreover, if the sum does
not converge for _any_ $\lambda>0$, an _extreme condensation effect_ is
believed to occur, where $\sum_{k=0}^{\infty}kp_{k}=0$. One of the goals of
this article is to investigate this extreme condensation regime, in a scenario
when $\sum_{i=1}^{\infty}\frac{1}{f(i,W)}=\infty$ almost surely (compared to
the investigations in [18] which deals with the case that
$\sum_{i=1}^{\infty}\frac{1}{f(i,W)}<\infty$ almost surely). As we will see,
an interesting phase transition occurs in a particular case of this regime,
where in one phase, every node in the infinite tree associated with the model
has infinite degree, whilst in another phase, this tree is locally finite,
with a single infinite path. One may interpret the latter regime as an extreme
effect of competition from ‘newer’ nodes, with so much mass of edges carried
away by these nodes, that any individual in the infinite tree only has finite
out-degree.

###  1.2 Overview

Section 2 deals with preliminaries: a formal description of the model (which
generalises the classical CMJ framework) and notation in Section 2.1, and
measure theoretic technicalities in Section 2.2. The main results appear in
Section 3: in Theorem 3.2 and Corollary 3.3 we provide a sufficient condition
for explosion to occur via an infinite path appearing in finite time. These
results use facts from Section 3.1 where we note that a number of properties
of CMJ processes that are ‘inherited’, including explosion, occur with
probability $0$ or $1$, when one conditions on ‘survival’ of the process.
Section 3.3 deals with applications to the recursive tree with fitness model:
Theorem 3.4 provides a classification of the structure of the infinite tree
$\mathcal{T}_{\infty}$ associated with this model, whilst Theorem 3.5 applies
these results to a ‘linear fitness’ regime, proving the aforementioned phase-
transition. This theorem is applicable to many existing models including the
Bianconi-Barabási model, preferential attachment model with additive fitness,
and the weighted random recursive tree.

##  2 Preliminaries

###  2.1 Notation and model preliminaries

In general, we will follow similar notation to that used in [18]. First, we
use $\mathbb{N}:=\\{1,2,\ldots\\}$, $\mathbb{N}_{0}:=\mathbb{N}\cup 0$,
$\mathbb{N}_{\infty}:=\mathbb{N}\cup\infty$. We consider _individuals_ 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$. We consider a Crump-Mode-Jagers branching process as a random
labelling of the elements of $\mathcal{U}_{\infty}$ with elements of
$[0,\infty]$, one considers _birth-times_ 222In principle, one may also
consider labelling structures that allow these labels to take values in an
arbitrary vector space.. In order to do so, we assume the existence of a
complete probability space $(\Omega,\Sigma,\mathbb{P})$ and equip
$\mathcal{U}_{\infty}$ with the sigma algebra generated by singleton sets. We
then, assume the existence of a random (measurable) function
$X:\Omega\times\mathcal{U}_{\infty}\rightarrow[0,\infty]$, where, for
$u\in\mathcal{U}_{\infty}$, we think of $X(uj)$ as the _displacement_ or
_waiting time_ between the $(j-1)$th and $j$th child of $u$. 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.

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$.
Given $\ell\leq|u|$, we set $u_{|_{\ell}}:=u_{1}\cdots u_{\ell}$. 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.

For each $t\in[0,\infty]$, we set
$\mathscr{T}_{t}=\\{(x,\mathcal{B}(x))\in\mathcal{U}_{\infty}\times[0,\infty]:\mathcal{B}(x)\leq
t\\}$, we think of this as the _genealogical tree_ of individuals with birth
time at most $t$. We also define for each $k\in\mathbb{N}_{0}$,
$G_{k}:=\left\\{(x,\mathcal{B}(x))\in\mathcal{U}_{\infty}\times[0,\infty]:|x|\leq
k\right\\}$. We set $\mathscr{T}_{\infty}:=\bigcup_{k\in\mathbb{N}}G_{k}$. We
denote by $(\mathcal{F}_{t})_{t\geq 0}$ and
$(\mathcal{G}_{k})_{k\in\mathbb{N}_{0}}$ the natural filtrations generated by
$(\mathscr{T}_{t})_{t\geq 0}$ and $(G_{k})_{k\in\mathbb{N}}$
respectively333More formally, we view $(\mathscr{T}_{t})_{t\geq 0}$ as a
measurable mapping
$\Omega\times[0,\infty)\times\mathcal{U}_{\infty}\rightarrow[0,\infty]$,
where, $\mathscr{T}_{t}(u)=\mathcal{B}(u)\mathbf{1}_{\mathcal{B}(u)\leq
t}+\infty\mathbf{1}_{\mathcal{B}(u)>t}$. Likewise, we view
$(G_{k})_{k\in\mathbb{N}_{0}}$ as a measurable map
$\Omega\times\mathbb{N}_{0}\times\mathcal{U}_{\infty}\rightarrow[0,\infty]$,
where, $G_{k}(u)=\mathcal{B}(u)\mathbf{1}_{|u|\leq k}$. Also, as a formality,
by taking completions if necessary, we assume that each $\mathcal{F}_{t}$ and
$\mathcal{G}_{k}$ is complete.. In relation 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\\}$. 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. For a given choice of $X$, we say that
$\mathscr{T}_{\infty}$ is an $X$-_Crump-Mode-Jagers (CMJ) branching process_.
We also use this term in regards to the stochastic processes
$(\mathscr{T}_{t})_{t\geq 0}$ and $(G_{k})_{k\in\mathbb{N}_{0}}$. We say that
the process $\mathscr{T}_{\infty}$ _survives_ if for all $k\in\mathbb{N}$
there exists $u\in\mathbb{N}^{k}$ such that $\mathcal{B}(u)<\infty$; in other
words, individuals $u$ of arbitrarily large size $|u|$ are born. In this
paper, we denote the event of survival by $\mathcal{S}$.

It will be helpful to have notation concerning “shifts” of
$\mathscr{T}_{\infty}$ representing the sub-tree associated with some
$u\in\mathcal{U}_{\infty}$. With regards to birth-times, for any
$v\in\mathcal{U}_{\infty}$ we define

$\mathcal{B}^{(u)}(v):=\begin{cases}\mathcal{B}(uv)-\mathcal{B}(u)&\text{if
$\mathcal{B}(u)<\infty$}\\\ \infty&\text{otherwise.}\end{cases}$

For $u\in\mathcal{U}_{\infty}$, we define $\mathscr{T}_{\infty}^{\downarrow
u}:=\left\\{(x,\mathcal{B}^{(u)}(x)),x\in\mathcal{U}_{\infty}\right\\}$.

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}_{0}$ 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{B}^{(u)}(i)\leq\mathcal{B}(u)+t\\}}&\text{if
$\mathcal{B}(u)<\infty$;}\\\ 0&\text{otherwise.}\end{cases}$

We denote by $\xi(t):=\xi^{(\varnothing)}(t)$.

###  2.2 Measure theoretical technicalities

Formally, we consider $\mathscr{T}_{\infty}$, (and
$\mathscr{T}_{\infty}^{\downarrow u}$ for $u\in\mathcal{U}_{\infty}$) as
random mappings $\Omega\times\mathcal{U}_{\infty}\rightarrow[0,\infty]$, such
that $u\mapsto\mathcal{B}(u)$. Viewing the branching process in this way (as a
random function from $\mathcal{U}_{\infty}$ to $[0,\infty]$) it will be
helpful to define a sigma algebra on the space of such functions (which we
denote by $[0,\infty]^{\mathcal{U}_{\infty}}$), representing _properties_ of
the branching process that can be “measured”. In particular, we will want to
ensure events involving uncountable unions, such as “there exists an infinite
path in finite time”, can be measured, and this is the reason for the
technicalities in this section.

In this regard, given $X$, and hence $\mathcal{B}$, we define the function
$\iota_{\mathcal{B}}:\Omega\rightarrow[0,\infty]^{\mathcal{U}_{\infty}}$ such
that $\omega\mapsto\mathcal{B}(\cdot,\omega)$. We equip
$[0,\infty]^{\mathcal{U}_{\infty}}$ with the pushforward sigma algebra induced
by the map $\iota_{\mathcal{B}}$, that is, the sigma algebra
$\mathcal{J}:=\left\\{A\subseteq[0,\infty]^{\mathcal{U}_{\infty}}:\iota_{\mathcal{B}}^{-1}(A)\in\Sigma\right\\}$.
The following is a foundational definition from descriptive set theory. Here,
we reformulate Definition 1.10.1. [7]:

######  Definition 2.1 (Souslin scheme).

Given a collection of subsets $\mathcal{C}$ of a given set $S$, a _Souslin
scheme_ over $\mathcal{C}$ is a mapping that associates to every sequence
$n_{1}\cdots n_{k}$ of natural numbers, a set $C_{n_{1},\cdots
n_{k}}\in\mathcal{C}$. A Souslin operation is the map that associates, to
every Souslin scheme $\left\\{C_{n_{1},\cdots n_{k}},n_{1}\cdots
n_{k}\in\mathcal{U}_{\infty}\right\\}$ over $\mathcal{C}$, the set

$\bigcup_{(n_{i})\in\mathbb{N}^{\infty}}\bigcap_{k=1}^{\infty}C_{n_{1}\cdots
n_{k}}.$

The collection of such sets, along with the empty set is denoted
$\mathcal{A}(\mathcal{C})$

The following beautiful theorem is also classical from descriptive set theory,
here we reformulate Theorem 1.10.5. [7]:

######  Theorem 2.1.

Suppose that a sigma algebra $\mathcal{C}$ is complete with respect to a
finite, non-negative measure $\mu$. Then
$\mathcal{A}(\mathcal{C})=\mathcal{C}$.

This theorem shows that, since $(\Omega,\Sigma,\mathbb{P})$ is a complete
probability space, a number of events, expressed as uncountable unions, are
measurable. In particular, if, for $u\in\mathcal{U}_{\infty}$ we define the
random variable

$\tau_{\operatorname{path}}(u):=\inf_{t\geq
0}\left\\{\exists(n_{k})\in\mathbb{N}^{\infty}:\forall
k\in\mathbb{N}\;\mathcal{B}^{(u)}(n_{1}\cdots n_{k})\leq t\right\\}.$

Then, as an application of Theorem 2.1, we know that, for any
$t\in[0,\infty]$, the event $\left\\{\tau_{\operatorname{path}}(u)<t\right\\}$
is measurable (in particular, that $\tau_{\operatorname{path}}(u)$ is a random
variable). For brevity, we write
$\tau_{\operatorname{path}}:=\tau_{\operatorname{path}}(\varnothing)$. We say
that _vertical explosion_ occurs if $\tau_{\operatorname{path}}<\infty$. This
terminology complements the notion of _sideways explosion_ introduced in [20],
when $\sum_{i=1}^{\infty}X(i)<\infty$ with positive probability.

##  3 Main results and proofs

In general in this paper, we will assume the following throughout:

$((X(uj))_{j\in\mathbb{N}})\quad\text{are independent \ for different
$u\in\mathcal{U}_{\infty}$}.$ (1)

Note that this implies that for distinct $u_{1},u_{2}\in\mathcal{U}_{\infty}$
with $|u_{1}|=|u_{2}|$ (hence, with distinct sub-trees), the values of
$(\mathcal{B}^{(u_{1})}(v))_{v\in\mathcal{U}_{\infty}}$ and
$(\mathcal{B}^{(u_{2})}(v))_{v\in\mathcal{U}_{\infty}}$ are independent on
$\mathcal{B}(u_{1}),\mathcal{B}(u_{2})<\infty$, hence so are the sub-trees
$\mathscr{T}^{\downarrow u_{1}}_{\infty},\mathscr{T}^{\downarrow
u_{2}}_{\infty}$.

We will also, mostly, require the following assumption:

######  Assumption 3.1.

We have

$\mathscr{T}^{\downarrow
u}_{\infty}\sim\mathscr{T}_{\infty}\quad\text{on}\quad\left\\{\mathcal{B}(u)<\infty\right\\}.$
(2)

More formally, the regular conditional distribution of
$\mathscr{T}^{\downarrow u}_{\infty}$ on
$\left\\{\mathcal{B}(u)<\infty\right\\}$ coincides with the distribution of
$\mathscr{T}_{\infty}$.

Note that Assumption 3.1 is the classical definition of a CMJ branching
process, and is the same as assuming that $((X(uj))_{j\in\mathbb{N}})\text{are
i.i.d. \ for different $u\in\mathcal{U}_{\infty}$}$, hence this assumption is
stronger than Equation (1).

###  3.1 Inherited properties and a conditional $0-1$ law

Given a set $\mathcal{P}\in\mathcal{J}$, we say that $\mathscr{T}_{\infty}$
has _property_ $\mathcal{P}$ if $\mathscr{T}_{\infty}\in\mathcal{P}$. Using
the map
$\iota_{\mathcal{B}}:\Omega\rightarrow[0,\infty]^{\mathcal{U}_{\infty}}$, we
often identify properties with events $B\in\Sigma$ in the probability space
$(\Omega,\Sigma,\mathbb{P})$.

######  Definition 3.2 (Inherited and bidirectionally inherited properties).

We say that a property $\mathcal{P}$ is _inherited_ if, whenever
$\mathscr{T}_{\infty}\in\mathcal{P}$, then, for each $i$ with
$\mathcal{B}(i)<\infty$, we have $\mathscr{T}_{\infty}^{\downarrow
i}\in\mathcal{P}$, and, moreover, $\mathscr{T}_{\infty}\in\mathcal{P}$ if the
event $\mathcal{S}^{c}$ occurs. We say that a property $\mathcal{P}$ is
_bidirectionally inherited_ if it is inherited and it is the case that
$\mathscr{T}_{\infty}\in\mathcal{P}$, if and only if for each $i$ with
$\mathcal{B}(i)<\infty$, we have $\mathscr{T}_{\infty}^{\downarrow
i}\in\mathcal{P}$.

######  Examples 3.1.

Some examples of inherited properties include
$\\{\tau_{\operatorname{path}}<\infty\\}^{c}$ and
$\\{\tau_{\infty}<\infty\\}^{c}$. Indeed, if the process does not produce an
infinite path in finite time, there cannot be a sub-tree of a child of the
root born in finite time that produces an infinite path in finite time.
Similar logic applies to the event of explosion. The event
$\\{\tau_{\operatorname{path}}<\infty\\}^{c}$ is also bidirectionally
inherited: if every sub-tree of a child of the root born in finite time does
not produce an infinite path in finite time, the process does not produce an
infinite path in finite time. However, note that it is not the case that
$\\{\tau_{\infty}<\infty\\}^{c}$ is bidirectionally inherited in general (when
Assumption 3.1 is not satisfied). Indeed, we may, for example, have that
$\sum_{j=1}^{\infty}X(j)<\infty$ almost surely, whilst for each
$u\in\mathcal{U}_{\infty}$ with $|u|\geq 1$, $X(uj)>\varepsilon$ almost
surely. Then, every sub-tree of a child of the root born in finite time may be
non-explosive, but the process still explodes.  $\blacktriangleleft$

The following is already well-known for inherited properties, at least with
respect to Bienaymé-Galton-Watson processes and CMJ processes satisfying
Assumption 3.1 (see, for example, [25, Proposition 5.6]). We provide proof
here for completeness.

######  Proposition 3.1 (Conditional $0-1$ law).

Let $\mathscr{T}_{\infty}$ be an $X$-CMJ branching process. Then, we have the
following:

  1. 1.

If Assumption 3.1 is satisfied, then, for any inherited property
$\mathcal{P}$, we have
$\mathbb{P}\left(\mathscr{T}_{\infty}\in\mathcal{P}\right)=1$ or, if
$\mathbb{P}\left(\mathcal{S}\right)>0$, we have
$\mathbb{P}\left(\mathscr{T}_{\infty}\in\mathcal{P}\,|\,\mathcal{S}\right)=0$.
In particular, if $\mathbb{P}\left(\mathcal{S}\right)>0$,
$\mathbb{P}\left(\mathscr{T}_{\infty}\in\mathcal{P}\,|\,\mathcal{S}\right)\in\\{0,1\\}$.

  2. 2.

More generally, only assuming Equation (1), if, for each $k\in\mathbb{N}$, the
set $\left\\{u_{i}\in\mathbb{N}^{k}:\mathcal{B}(u_{i})<\infty\right\\}$ is
deterministic (which, in particular, implies that $\mathcal{S}$ is a
deterministic property), then, for any bidirectionally inherited property
$\mathcal{P}$, we have
$\mathbb{P}\left(\mathscr{T}_{\infty}\in\mathcal{P}\right)\in\left\\{0,1\right\\}$.

###### Proof.

First note that by definition, for any inherited property $\mathcal{P}$,
$\mathcal{S}^{c}$ implies $\mathscr{T}_{\infty}\in\mathcal{P}$. We first
recall the definition of $\mathcal{G}_{k}$, the sigma algebra generated by
$G_{k}$, the birth times of all individuals up to the $k$th generation of the
process. Now, $\mathscr{T}_{\infty}\in\mathcal{P}$ implies that, for all
$i\in\mathbb{N}$, with $\mathcal{B}(i)<\infty$ we have
$\mathscr{T}^{\downarrow i}_{\infty}\in\mathcal{P}$. Applying this
recursively, for all $x\in\mathbb{N}^{k}$ with $\mathcal{B}(x)<\infty$, we
have $\mathscr{T}^{\downarrow x}_{\infty}\in\mathcal{P}$. By Equation (1) the
sub-trees $(\mathscr{T}^{\downarrow
u_{i}}_{\infty}:|u_{i}|=k,\mathcal{B}(u_{i})<\infty)$ are mutually
independent, conditional on the values $\mathcal{B}(u_{i}),|u_{i}|=k$. Thus,

$\displaystyle\mathbb{P}\left(\mathscr{T}_{\infty}\in\mathcal{P}\,|\,\mathcal{G}_{\leq
k}\right)$
$\displaystyle\leq\left(\prod_{u_{i}\in\mathbb{N}^{k}:\mathcal{B}(u_{i})<\infty}\mathbb{P}\left(\mathscr{T}^{\downarrow
u_{i}}_{\infty}\in\mathcal{P}\,\bigg{|}\,\mathcal{B}(u_{i})<\infty\right)\right)\mathbf{1}\left\\{\exists
u\in\mathbb{N}^{k}:\mathcal{B}(u)<\infty\right\\}$ $\displaystyle\hskip
85.35826pt+\mathbf{1}\left\\{\forall
u\in\mathbb{N}^{k}:\mathcal{B}(u)=\infty\right\\}$ (3)
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:sub-tree-identical-
law}}}{{=}}\mathbb{P}\left(\mathscr{T}_{\infty}\in\mathcal{P}\right)\mathbf{1}\left\\{\exists
x\in\mathbb{N}^{k}:\mathcal{B}(x)<\infty\right\\}+\mathbf{1}\left\\{\forall
x\in\mathbb{N}^{k}:\mathcal{B}(x)=\infty\right\\}.$ (4)

Taking limits as $k\to\infty$, by the Lévy zero-one law, the left-hand side is
an indicator random variable, whilst the two indicators on the right-hand side
converge almost surely to $\mathbf{1}\left\\{\mathcal{S}\right\\}$ and
$\mathbf{1}\left\\{\mathcal{S}^{c}\right\\}$ respectively. Thus, almost
surely, we have

$\displaystyle\mathbf{1}\left\\{\mathscr{T}_{\infty}\in\mathcal{P}\right\\}$
$\displaystyle\leq\mathbb{P}\left(\mathscr{T}_{\infty}\in\mathcal{P}\right)\mathbf{1}\left\\{\mathcal{S}\right\\}+\mathbf{1}\left\\{\mathcal{S}^{c}\right\\}.$
(5)

This inequality implies that if
$\mathbb{P}\left(\left\\{\mathscr{T}_{\infty}\in\mathcal{P}\right\\}\cap\mathcal{S}\right)>0$,
it must be the case that
$\mathbb{P}\left(\mathscr{T}_{\infty}\in\mathcal{P}\right)=1$, from which we
deduce Item 1.

For Item 2, note that since for all $k\in\mathbb{N}$, the set
$\left\\{u_{i}\in\mathbb{N}^{k}:\mathcal{B}(u_{i})<\infty\right\\}$ is
deterministic, and $\mathcal{P}$ is bidirectionally recursive, by independence
of the associated sub-trees we have

$\mathbb{P}\left(\mathcal{T}_{\infty}\in\mathcal{P}\right)=\prod_{u_{i}\in\mathbb{N}^{k}:\mathcal{B}(u_{i})<\infty}\mathbb{P}\left(\mathscr{T}^{\downarrow
u_{i}}_{\infty}\in\mathcal{P}\right)=\mathbb{P}\left(\bigcap_{k\in\mathbb{N}}\bigcap_{u_{i}\in\mathbb{N}^{k}:\mathcal{B}(u_{i})<\infty}\mathscr{T}^{\downarrow
u_{i}}_{\infty}\in\mathcal{P}\right).$

By (1), and the fact that
$\left\\{u_{i}\in\mathbb{N}^{k}:\mathcal{B}(u_{i})<\infty\right\\}$ is
deterministic, the right-hand side is a tail event with respect to
$(\mathcal{G}_{k})_{k\in\mathbb{N}}$, and we may apply the Kolmogorov $0-1$
law. ∎

######  Remark 3.2.

Note that the proof of Item 1 in Proposition 3.1 can be made slightly more
general than assuming Assumption 3.1. Indeed, for (3.1), we need only assume
that, for example, for $u1\in\mathcal{U}_{\infty}$, with
$u\in\mathcal{U}_{\infty}$ (i.e, the first child of an individual), we have
$\mathscr{T}^{\downarrow u1}_{\infty}\sim\mathscr{T}_{\infty}$ on
$\left\\{\mathcal{B}(u1)<\infty\right\\}$.  $\blacktriangleleft$

###  3.2 A sufficient criteria for vertical explosion

######  Theorem 3.2.

Let $\mathscr{T}_{\infty}$ be an $X$-CMJ branching process satisfying
Assumption 3.1. Suppose that, for sequences
$(t_{i})\in[0,\infty)^{\mathbb{N}}$, $(M_{i})\in\mathbb{N}^{\mathbb{N}}$, with
$\sum_{i=1}^{\infty}t_{i}<\infty$ we have

$\sum_{i=1}^{\infty}\mathbb{P}\left(\xi(t_{i})\leq
M_{i+1}\right)^{M_{i}}<\infty.$ (6)

Then,
$\mathbb{P}\left(\tau_{\operatorname{path}}<\infty\,|\,\mathcal{S}\right)=1$.

######  Remark 3.3.

Note that, since
$\mathbb{P}\left(\tau_{\operatorname{path}}<\infty\,|\,\mathcal{S}\right)\leq\mathbb{P}\left(\tau_{\infty}<\infty\,|\,\mathcal{S}\right)$,
Theorem 3.2 also provides a sufficient condition for $\mathscr{T}_{\infty}$ to
be explosive on survival. Note also that in the case that $\xi(t)<\infty$
almost surely, for all $t>0$, the tree $\mathcal{T}_{\infty}$ (i.e, the
genealogical tree at the explosion time), must be locally finite. By an
application of Kőnig’s lemma, which states that any locally finite graph has
an infinite path, it follows that, in this case, $\tau_{\infty}$ and
$\tau_{\operatorname{path}}$ coincide.  $\blacktriangleleft$

######  Remark 3.4.

Note that the $i$th summand in (6) is non-increasing in $t_{i}$ and $M_{i}$,
but non-decreasing in $M_{i+1}$. We also note that (6) cannot be satisfied if
$\mathbb{E}\left[\xi(t_{0})\right]<1$, for some $t_{0}>0$, which, by a similar
argument to [20, Theorem 3.1(b)], is a sufficient condition for
$\tau_{\operatorname{path}}=\infty$ almost surely. Indeed, if this were the
case, then, first, note that it cannot be the case that the sequence
$(M_{i})_{i\in\mathbb{N}}$ is bounded above by some $M\in\mathbb{N}$,
otherwise, we can bound the summands from below by a “worst case”
$\mathbb{P}\left(\xi(t_{0})\leq 1\right)^{M}>0$, showing that the sum
diverges. Therefore, there are infinitely many terms such that
$M_{i+1}/M_{i}>1$ and $t_{i}\leq t_{0}$, for which

$\displaystyle\mathbb{P}\left(\xi(t_{i})\leq M_{i+1}\right)^{M_{i}}$
$\displaystyle\geq(1-\mathbb{P}\left(\xi(t_{0})\leq
M_{i+1}\right))^{M_{i}}\geq\left(1-\frac{M_{i}}{M_{i+1}}\mathbb{E}\left[\xi(t_{0})\right]\right)>0,$

where the second to last inequality uses Markov’s and Bernoulli’s
inequalities. We again deduce that the sum diverges.  $\blacktriangleleft$

Before we prove Theorem 3.2, we prove the following corollary:

######  Corollary 3.3.

Let $\mathscr{T}_{\infty}$ be an $X$-CMJ branching process satisfying
Assumption 3.1. Suppose that there exists
$\varepsilon,\varepsilon^{\prime},x_{0}>0$, $\gamma<1$ such that, for all
$t\in(0,\varepsilon^{\prime})$, and $x\geq x_{0}$, we have

$\mathbb{P}\left(\xi(t)>x\right)>2x^{-1}(\log{x})^{1+\varepsilon}t.$

Then
$\mathbb{P}\left(\tau_{\operatorname{path}}<\infty\,|\,\mathcal{S}\right)=1$.

######  Remark 3.5.

Corollary 3.3 is only a particular example of an application of Theorem 3.2,
and better conditions may be obtained by applying Theorem 3.2 directly.
$\blacktriangleleft$

###### Proof of Corollary 3.3.

In Theorem 3.2, we choose $M_{i}:=2^{i}$, and $t_{i}:=i^{-(1+\varepsilon/2)}$.
Then, note that

$\mathbb{P}\left(\xi(t_{i})>2^{i+1}\right)>2^{-i}(\log{2})^{1+\varepsilon}i^{1+\varepsilon}i^{-(1+\varepsilon/2)}=2^{-i}(\log{2})^{1+\varepsilon}i^{\varepsilon/2}.$

Therefore, we have

$\displaystyle\mathbb{P}\left(\xi(t_{i})\leq
2^{i+1}\right)^{2^{i}}=\left(1-\mathbb{P}\left(\xi(t_{i})>2^{i+1}\right)\right)^{2^{i}}\leq
e^{-2^{i}\mathbb{P}\left(\xi(t_{i})>2^{i+1}\right)}\leq
e^{-i^{\varepsilon/2}(\log{2})^{1+\varepsilon}}.$

The above bound is summable in $i$, hence we conclude the result. ∎

We now prove Theorem 3.2.

###### Proof of Theorem 3.2.

In order to prove this theorem, we first define the nested sequence of events
$\mathcal{E}_{1}\supseteq\mathcal{E}_{2}\cdots$, such that

$\mathcal{E}_{1}:=\left\\{\exists
u_{1}\in\left\\{1,2,\ldots,M_{1}\right\\}:\xi^{(u_{1})}(t_{1})>M_{2}\right\\},$

and, recursively,

$\mathcal{E}_{i+1}:=\mathcal{E}_{i}\cap\left\\{\exists
u_{i+1}\in\left\\{1,\ldots,M_{i+1}\right\\}:\xi^{(u_{1}\cdots
u_{i}u_{i+1})}(t_{i+1})>M_{i+2}\right\\}.$

One may regard these events as a ‘search’ for an infinite path
$u_{1}u_{2}\ldots,$ in finite time; each event $\mathcal{E}_{i+1}$ involves a
search for a node $u_{i+1}$ to extend the path $u_{1}\cdots u_{i}$ in time
$t_{i+1}$. As a result, if we set $t^{*}:=\sum_{i=1}^{\infty}t_{i}$, we have

$\lim_{i\to\infty}\mathcal{E}_{i}=\bigcap_{i=1}^{\infty}\mathcal{E}_{i}\subseteq\left\\{\tau_{\operatorname{path}}\leq
t^{*}\right\\}.$

On the other hand, recall that the processes $\xi^{(u_{1}\cdots
u_{i}1)},\ldots,\xi^{(u_{1}\cdots u_{i}M_{i+1})}$ are independent of
$u_{1}\cdots u_{i}$ and $\mathcal{E}_{i}$, and identically distributed to
$\xi$. Consequentially,

$\displaystyle\mathbb{P}\left(\mathcal{E}_{i+1}\,\bigg{|}\,\mathcal{E}_{i}\right)$
$\displaystyle=\mathbb{P}\left(\left\\{\exists
u_{i+1}\in\left\\{1,\ldots,M_{i+1}\right\\}:\xi^{(u_{1}\cdots
u_{i}u_{i+1})}(t_{i+1})>M_{i+2}\right\\}\right)$
$\displaystyle=1-\prod_{u_{i+1}=1}^{M_{i+1}}\mathbb{P}\left(\xi^{(u_{1}\cdots
u_{i}u_{i+1})}(t_{i+1})\leq M_{i+2}\right)=1-\mathbb{P}\left(\xi(t_{i+1})\leq
M_{i+2}\right)^{M_{i+1}}.$

Consequentially, by the chain rule (setting $\mathcal{E}_{0}=\Omega$), we have

$\mathbb{P}\left(\bigcap_{i=1}^{\infty}\mathcal{E}_{i}\right)=\lim_{j\to\infty}\mathbb{P}\left(\mathcal{E}_{j}\right)=\lim_{j\to\infty}\prod_{\ell=1}^{j}\mathbb{P}\left(\mathcal{E}_{\ell}\,\bigg{|}\,\mathcal{E}_{\ell-1}\right)=\prod_{\ell=1}^{\infty}\left(1-\mathbb{P}\left(\xi(t_{\ell})\leq
M_{\ell+1}\right)^{M_{\ell}}\right)>0$

since $\sum_{\ell=1}^{\infty}\mathbb{P}\left(\xi(t_{\ell})\leq
M_{\ell+1}\right)^{M_{\ell}}<\infty$. Since
$\\{\tau_{\operatorname{path}}<\infty\\}$ is an inherited property, we deduce
the result by applying Proposition 3.1. ∎

######  Remark 3.6.

It is possible to weaken Assumption 3.1 in the proof of Theorem 3.2, to
include some dependence of $\xi^{(u)}$ on $|u|$. For example, we could assume
that each $\xi^{(u)}$ with $|u|=i$ were i.i.d. on $\mathcal{B}(u)<\infty$,
depending only on $i$. If $\xi_{i}$ denotes the distribution of $\xi^{(u)}$,
on $\mathcal{B}(u)<\infty$, with $|u|=i$, then the $i$th summand in Equation
(6) could be replaced by $\mathbb{P}\left(\xi_{i}(t_{i})\leq
M_{i+1}\right)^{M_{i}}$. This would, in this case, provide criteria for
$\mathbb{P}\left(\tau_{\operatorname{path}}<\infty\right)>0$, and, if we know
that for each $i\in\mathbb{N}_{0}$ we have
$\lim_{t\to\infty}\xi_{i}(t)=\infty$, Item 2 of Proposition 3.1 implies that
$\mathbb{P}\left(\tau_{\operatorname{path}}<\infty\right)=1$.
$\blacktriangleleft$

###  3.3 Applications to recursive trees with fitness

In this section, we apply our results to a discrete model of trees, called
_recursive trees with fitness_. Here, we assume that the values of
$(X(i),i\in\mathbb{N})$ depend on an additional source of randomness: a random
weight $W$ taking values in a measure space $(\mathcal{W},\mathscr{W})$. We
also assume the existence of a measurable _fitness function_
$f:\mathbb{N}_{0}\times\mathcal{W}\rightarrow[0,\infty)$, such that, given a
weight $w$, the values $(X_{w}(i),i\in\mathbb{N})$ are independent and
exponentially distributed, such that $f(i,w)$ is the rate of the exponential
random variable $X_{w}(i+1)$. Then, the properties of the exponential
distribution, namely related to taking the minimum of independent exponential
random variables, and the memory-less property, yield that the sequence of
trees $(\mathcal{T}_{i})_{i\in\mathbb{N}}$ associated with an $X$-CMJ
branching process are identical in law (up to relabelling), to a sequence of
recursive trees with fitness which we define below. We remark that the use of
such continuous-time embeddings to analyse combinatorial processes is
classical, and was pioneered by Arthreya and Karlin [2].

In this section, we 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_. Given a vertex labelled $v$ in a directed tree $T$ we denote its
out-degree by $\operatorname{deg}^{+}(v,T)$.

######  Definition 3.3 (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 $\mathcal{W}$, 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}$ by:

  1. 1.

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

  2. 2.

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

######  Remark 3.7.

Because of the equivalence in law with trees associated with an $X$-CMJ
branching process, we also refer to a sequence of recursive tree with fitness
by $(\mathcal{T}_{i})_{i\in\mathbb{N}}$, despite the fact that the vertices of
these trees are labelled with elements of $\mathbb{N}_{0}$ rather than
$\mathcal{U}_{\infty}$.  $\blacktriangleleft$

####  3.3.1 A classification theorem

Our first main result concerns the general structure of the infinite tree
$\mathcal{T}_{\infty}:=\bigcup_{i\in\mathbb{N}}\mathcal{T}_{i}$, associated
with a $(W,f)$-recursive tree with fitness. We continue to refer to notation
and terminology associated with the corresponding $X$-CMJ process. Recall that
we either have $\mathbb{P}\left(\tau_{\infty}=\infty\right)=1$ or
$\mathbb{P}\left(\tau_{\infty}=\infty\right)=1-\mathbb{P}\left(\mathcal{S}\right)$.

Given a weight $w\in\mathcal{S}$, we denote by

$\operatorname{d}_{\max{}}(w):=\sup{\left\\{i:f(i,w)>0\right\\}}.$

######  Theorem 3.4.

Suppose $\mathcal{T}_{\infty}$ denotes the limiting infinite tree associated
with a $(W,f)$-recursive tree with fitness. Then,

  1. 1.

On the event $\left\\{\tau_{\infty}=\infty\right\\}$, every vertex
$i\in\mathcal{T}_{\infty}$ has
$\operatorname{deg}^{+}(i,\mathcal{T}_{\infty})=\operatorname{d}_{\max{}}(w_{i})+1$
(which may be infinite).

  2. 2.

On the event $\left\\{\tau_{\infty}<\infty\right\\}$, there are two cases:

    1. (a)

Either the tree $\mathcal{T}_{\infty}$ has a single vertex of infinite degree,
and finite height (i.e., the distance of any node from $0$ is finite);

    2. (b)

Alternatively, the tree $\mathcal{T}_{\infty}$ has a unique infinite path, and
every vertex in $\mathcal{T}_{\infty}$ has finite degree.

  3. 3.

If $\sum_{i=1}^{\infty}\frac{1}{f(i,W)}=\infty$ for almost all
$W\in\mathcal{W}$, on the event $\left\\{\tau_{\infty}<\infty\right\\}$ the
tree $\mathcal{T}_{\infty}$ has a unique infinite path, and every vertex in
$\mathcal{T}_{\infty}$ has finite degree.

In the proof, we refer to the $X$-CMJ process associated with
$\mathcal{T}_{\infty}$, and refer to nodes $i\in\mathcal{T}_{\infty}$ by their
Ulam-Harris label.

###### Proof.

For Item 1, we first show that each individual $u\in\mathscr{T}_{\infty}$ with
$\mathcal{B}(u)<\infty$, and associated weight $W_{u}$ we have
$|ui\in\mathcal{U}_{\infty}:\mathcal{B}(ui)<\infty|=\operatorname{d}_{\max{}}(W_{u})$.
Indeed, one readily checks that

$\sum_{i=1}^{\operatorname{d}_{\max{}}(W_{u})+1}X_{ui}<\infty\quad\text{almost
surely,}$

hence if $\mathcal{B}(u)<\infty$, we deduce the claim. We conclude the result
by observing that on the event $\\{\tau_{\infty}=\infty\\}$, the tree
associated with $\\{u\in\mathscr{T}_{\infty}:\mathcal{B}(u)<\infty\\}$
coincides with $\mathcal{T}_{\infty}$.

Item 2 is a particular case of [18, Theorem 2.12], noting that all of the
conditions of [18, Assumption 2.11] are met. Item 3 follows as a consequence.
Indeed, note that, for any $u\in\mathcal{U}_{\infty}$, since
$\sum_{i=1}^{\infty}\frac{1}{f(i,W)}=\infty$ we have

$\sum_{i=1}^{\infty}X(ui)=\infty\quad\text{almost surely.}$

But, on $\\{\tau_{\infty}<\infty\\}$, for there to be a node of infinite
degree in $\mathcal{T}_{\infty}$, we require the existence of
$u\in\mathcal{U}_{\infty}$ such that $\sum_{i=1}^{\infty}X(ui)<\infty$ (i.e.
such that all of the children of $u$ are produced in finite time). Since
$\mathcal{U}_{\infty}$ is countable, we deduce that this occurs with
probability $0$. ∎

####  3.3.2 Applications to linear fitness models, including Bianconi-Barabási
trees

In this section, we apply our results to the $(W,f)$-recursive tree with
fitness in the case that the space of weights $\mathcal{W}:=[0,\infty)^{2}$,
and the fitness function takes the following form:

$f(i,(U,V))=Ui+V.$ (8)

We believe our results may extend to more general cases, but this form allows
us to apply existing theory regarding pure birth processes with linear rates,
to effectively analyse the process $(\xi(t))_{t\geq 0}$ associated with the
$X$-CMJ branching process. Indeed, given $u\in\mathcal{U}_{\infty}$ since each
$X_{W_{u}}(i)$ is independent, and exponentially distributed with parameter
$U_{u}i+V_{u}$. We deduce that if $\mathcal{B}(u)<\infty$, conditional on
$W_{u}=(U_{u},V_{u})\in[0,\infty)^{2}$ the associated process
$\xi^{(u)}_{(U_{u},V_{u})}(t)$ is a pure-birth process, with values in
$\mathbb{N}_{0}$, with initial condition $0$, and transitions from $i$ to
$i+1$ at rate $U_{u}i+V_{u}$.

In the statement of Theorem 3.5, for brevity of notation, we formally set
$(e^{xt}-1)/x:=t$ when $x=0$. For example, in Equation (8) below, this avoids
having to make distinctions in the expression based on whether or not $U=0$.

######  Theorem 3.5 (Infinite path transition).

Suppose that $\mathcal{T}_{\infty}$ denotes the limiting infinite tree
associated with a $(W,f)$-recursive tree with fitness satisfying Equation (8).
Assume, moreover, that $\mathbb{P}\left((U,V)=(0,0)\right)=0$. Then,

  1. 1.

If, for some $t>0$, we have

$\mathbb{E}\left[\frac{V(e^{Ut}-1)}{U}\right]<\infty,$ (9)

then, every node in $\mathcal{T}_{\infty}$ has infinite degree.

  2. 2.

Otherwise, if there exists $\varepsilon,\varepsilon^{\prime},c,x_{0}>0$, such
that for all $t\in(0,\varepsilon^{\prime})$, for all $x\geq x_{0}$, we have

$\mathbb{P}\left(\left\\{\frac{V(e^{Ut}-1)}{U}>x\right\\}\cap\left\\{U/V<c\right\\}\right)>2x^{-1}(\log{x})^{1+\varepsilon}t,$
(10)

then $\mathcal{T}_{\infty}$ is locally finite, with a unique infinite path.

######  Remark 3.8.

In view of Remark 3.5, as Item 2 of Theorem 3.5 uses Corollary 3.3, this
result may be improved by directly applying Theorem 3.2. Moreover, in view of
Remark 3.6, we believe it is possible to use a strengthening of [18, Theorem
2.12] to provide a sufficient criteria for Item 2 of Theorem 3.5 to hold when
there is also some dependence of the fitness function $f$ on the distance of
the node from the root.  $\blacktriangleleft$

######  Examples 3.9.

Having the fitness function satisfy Equation 8 encompasses a number of
existing cases of the model. The case $U=0$ corresponds to the weighted random
recursive tree, the case $U=1$ corresponds to the preferential attachment
model with additive fitness, whilst the case $U=V$ corresponds to the
Bianconi-Barabási model, or preferential attachment with multiplicative
fitness. In these cases, the conditions in Equations (9) and (10) simplify so
that

  1. 1.

In the Bianconi-Barabási model, if, for some $t>0$, we have
$\mathbb{E}\left[e^{Ut}\right]<\infty$, every node in $\mathcal{T}_{\infty}$
has infinite degree, whilst if $U$ fails to admit a moment generating function
by having, for $t\in(0,\varepsilon^{\prime})$, $x\geq x_{0}$
$\mathbb{P}\left(e^{Ut}>x\right)>2x^{-1}(\log{x})^{1+\varepsilon}t$,
$\mathcal{T}_{\infty}$ is locally finite, with a unique infinite path.

  2. 2.

In the weighted random recursive tree if $\mathbb{E}\left[V\right]<\infty$,
every node in $\mathcal{T}_{\infty}$ has infinite degree, whilst one may
verify that if, for some $\nu>0$,
$\mathbb{P}\left(V>x\right)>2x^{-1}(\log{x})^{1+\nu}$ for all $x$ sufficiently
large, $\mathcal{T}_{\infty}$ is locally finite, with a unique infinite path.
(For the latter case, one has to choose
$\varepsilon,\varepsilon^{\prime},x_{0}>0$ accordingly, and note that
$\lim_{t\to 0}t^{1/(1+\nu)}\log{t}=0$). In the preferential attachment model
with additive fitness, analagous conditions suffice, noting that since
$e^{t}-1>t$,
$\mathbb{P}\left(V>\frac{x}{e^{t}-1}\right)\geq\mathbb{P}\left(V>\frac{x}{t}\right)$.
We remark that the infinite path regimes in both these models encompass the
extreme disorder regimes in the results of [24, 23, 22], where the maximal
degree associated with the model grows linearly in the size of the tree.

$\blacktriangleleft$

In order to proof Theorem 3.5, we require the following lemma:

######  Lemma 3.6 (Mean and second moment of linear pure birth processes).

Let $\left(\mathcal{X}(t)\right)_{t\geq 0}$ be a pure birth process with
$\mathcal{X}(0)=0$ and rates such that $k$ transitions to $k+1$ at rate
$c_{1}k+c_{2}$, for some constants $c_{1},c_{2}>0$. Then, for each $t\geq 0$,
with $r:=c_{2}/c_{1}$, we have

$\mathbb{E}\left[\mathcal{X}(t)\right]=\begin{cases}r(e^{c_{1}t}-1)&\text{if
$c_{1}>0$}\\\ c_{2}t&\text{if $c_{1}=0$},\end{cases}$ (11)

whilst

$\mathbb{E}\left[(\mathcal{X}(t))^{2}\right]=\begin{cases}(r(e^{c_{1}t}-1))^{2}+r(e^{c_{1}t}-1)e^{c_{1}t}&\text{if
$c_{1}>0$}\\\ (c_{2}t)^{2}+c_{2}t&\text{if $c_{1}=0$}.\end{cases}$ (12)

###### Proof.

The cases where $c_{1}=0$ follows from the fact that
$\left(\mathcal{X}(t)\right)_{t\geq 0}$ is a homogeneous Poisson process, with
rate $c_{2}$. Otherwise, one can directly solve the Kolmogorov forward
equations associated with the pure jump process (see [16, Theorem A.7]) to see
that the probability generating function is given by

$\mathbb{E}\left[z^{\mathcal{X}(t)}\right]=\left(\frac{e^{-c_{1}t}}{1-z\left(1-e^{-c_{1}t}\right)}\right)^{r},$
(13)

from which we deduce the claim. ∎

We will also use the well-known Paley-Zygmund inequality, whose proof we omit.

######  Lemma 3.7 (Paley-Zygmund Inequality).

Let $Z$ be a non-negative random variable with finite variance, and let
$d\in(0,1)$. Then,

$\mathbb{P}\left(Z\geq
d\mathbb{E}\left[Z\right]\right)\geq(1-d)^{2}\frac{\mathbb{E}\left[Z\right]^{2}}{\mathbb{E}\left[Z^{2}\right]}.$
(14)

As with the statement of Theorem 3.5, in the proof below, we also formally set
$(e^{xt}-1)/x:=t$ when $x=0$. This allows us to unify the different cases
appearing in Equations (11) and (12) into a single expression.

###### Proof.

First note that since $\mathbb{P}\left((U,V)=(0,0)\right)=0$, we have
$\mathbb{P}\left(\mathcal{S}\right)=1$. For Item 1, we note that this
condition, combined with Equation (11) from Lemma 3.6, implies that, for some
$t>0$, with regards to the associated $X$-CMJ branching process, we have
$\mathbb{E}\left[\xi(t)\right]=\mathbb{E}\left[\mathbb{E}\left[\xi_{(U,V)}(t)\right]\right]<\infty$.
Moreover, note that, $\xi(t)<\infty$ almost surely, for each $t>0$. By [20,
Theorem 3.1(b)], we deduce that
$\mathbb{P}\left(\tau_{\infty}=\infty\right)=1$, which, when combined with
Item 1 of Theorem 3.4, implies the claim.

Otherwise, note that, by Equations (11) and (12), on $\\{U/V<c\\}$, we have

$\mathbb{E}\left[\xi_{(U,V)}(t)^{2}\right]\leq(1+c)\mathbb{E}\left[\xi_{(U,V)}(t)\right]^{2}+\mathbb{E}\left[\xi_{(U,V)}(t)\right].$

Therefore, uniformly across all $(U,V)\in[0,\infty)^{2}$, with $U/V<c$ such
that

$\mathbb{E}\left[\xi_{(U,V)}(t)\right]=\frac{V(e^{Ut}-1)}{U}>\frac{1}{1+c},\quad\text{say,
we have
}\quad\frac{\mathbb{E}\left[\xi_{(U,V)}(t)\right]^{2}}{\mathbb{E}\left[(\xi_{(U,V)}(t))^{2}\right]}\geq\frac{1}{2(1+c)}.$
(15)

Thus, by the Paley-Zygmund inequality (Lemma 3.7), we deduce that, for
$d\in(0,1)$ all $x\geq x_{0}$, $t\in(0,\varepsilon^{\prime})$, we have

$\displaystyle\mathbb{P}\left(\xi(t)>x\right)$
$\displaystyle=\mathbb{E}\left[\mathbb{P}\left(\xi_{(U,V)}(t)>x\right)\right]\geq\mathbb{E}\left[\mathbb{P}\left(\xi_{(U,V)}(t)\geq
d\mathbb{E}\left[\xi_{(U,V)}(t)\right]\right)\mathbf{1}\left\\{\mathbb{E}\left[\xi_{(U,V)}(t)\right]>x/d\right\\}\right]$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:paley-
zygmund},\eqref{eq:moment-
bound}}}{{\geq}}\frac{(1-d)^{2}}{2(1+c)}\mathbb{P}\left(\left\\{\frac{V(e^{Ut}-1)}{U}>x/d\right\\}\cap\left\\{U/V<c\right\\}\right)$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:weight-expl-
case}}}{{\geq}}\frac{(1-d)^{2}(x/d)^{-1}(\log{(x/d)})^{1+\varepsilon}t}{1+c}$
$\displaystyle\geq 2x^{-1}(\log{x})^{1+\varepsilon^{\prime\prime}}t,$

for some $\varepsilon^{\prime\prime}<\varepsilon$, where the last inequality
is satisfied by making $x_{0}$ larger if necessary. By Corollary 3.3, we
deduce that $\tau_{\operatorname{path}}<\infty$, almost surely, so that, in
particular, $\tau_{\infty}<\infty$ almost surely. As
$\sum_{i=1}^{\infty}\frac{1}{Ui+V}=\infty$ almost surely, we deduce the result
by applying Item 3 of Theorem 3.4. ∎

## Acknowledgements

We thank Bas Lodewijks and Jonas Köppl for helpful discussions. The author is
funded by Deutsche Forschungsgemeinschaft (DFG) through DFG Project no.
$443759178$, and would like to also acknowledge previous funding from the LMS
Early Career Fellowship ECF-1920-55, which helped support this research.

## References

  * [1] O. Amini, L. Devroye, S. Griffiths, and N. Olver.  On explosions in heavy-tailed branching random walks.  Ann. Probab., 41(3B):1864–1899, 2013.
  * [2] K. B. Athreya and S. Karlin.  Embedding of urn schemes into continuous time Markov branching processes and related limit theorems.  Ann. Math. Statist., 39:1801–1817, 1968.
  * [3] S. Banerjee and S. Bhamidi.  Persistence of hubs in growing random networks.  Probab. Theory Related Fields, 180(3-4):891–953, 2021.
  * [4] J. Bertoin and R. Stephenson.  Local explosion in self-similar growth-fragmentation processes.  Electron. Commun. Probab., 21:Paper No. 66, 12, 2016.
  * [5] S. Bhamidi.  Universal techniques to analyze preferential attachment trees: global and local analysis, 2007.  Unpublished manuscript.
  * [6] G. Bianconi and A.-L. Barabási.  Bose-Einstein condensation in complex networks.  Phys. Rev. Lett., 86 24:5632–5, 2001.
  * [7] V. I. Bogachev.  Measure theory. Vol. I, II.  Springer-Verlag, Berlin, 2007.
  * [8] C. Borgs, J. Chayes, C. Daskalakis, and S. Roch.  First to market is not everything: an analysis of preferential attachment with fitness.  In STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 135–144. ACM, New York, 2007.
  * [9] K. A. Borovkov and V. A. Vatutin.  On the asymptotic behaviour of random recursive trees in random environments.  Adv. in Appl. Probab., 38(4):1047–1070, 2006.
  * [10] S. Dereich.  Preferential attachment with fitness: unfolding the condensate.  Electron. J. Probab., 21:Paper No. 3, 38, 2016.
  * [11] S. Dereich, C. Mailler, and P. Mörters.  Nonextensive condensation in reinforced branching processes.  Ann. Appl. Probab., 27(4):2539–2568, 2017.
  * [12] S. Dereich and P. Mörters.  Random networks with sublinear preferential attachment: degree evolutions.  Electron. J. Probab., 14:no. 43, 1222–1267, 2009.
  * [13] S. Dereich and M. Ortgiese.  Robust analysis of preferential attachment models with fitness.  Combin. Probab. Comput., 23(3):386–411, 2014.
  * [14] G. Ergün and G. Rodgers.  Growing random networks with fitness.  Phys. A., 303(1):261 – 272, 2002.
  * [15] P. Galashin.  Existence of a persistent hub in the convex preferential attachment model.  arXiv preprint arXiv:1310.7513, 2013.
  * [16] C. Holmgren and S. Janson.  Fringe trees, Crump-Mode-Jagers branching processes and $m$-ary search trees.  Probab. Surv., 14:53–154, 2017.
  * [17] T. Iyer.  Degree distributions in recursive trees with fitnesses.  Adv. in Appl. Probab., 55(2):407–443, 2023.
  * [18] T. Iyer and B. Lodewijks.  On the structure of genealogical trees associated with explosive Crump-Mode-Jagers branching processes.  arXiv preprint arXiv:2311:14664, 2023.
  * [19] J. F. C. Kingman.  The first birth problem for an age-dependent branching process.  Ann. Probab., 3(5):790–801, 10 1975.
  * [20] J. Komjáthy.  Explosive Crump-Mode-Jagers branching processes.  arXiv preprint arXiv:1602.01657, 2016.
  * [21] T. Y. Y. Lo.  Weak local limit of preferential attachment random trees with additive fitness, 2021.
  * [22] B. Lodewijks.  Location of high-degree vertices in weighted recursive graphs with bounded random weights.  To appear in the Journal of Applied Probability, 2021.
  * [23] B. Lodewijks and M. Ortgiese.  The maximal degree in random recursive graphs with random weights.  arXiv preprint arXiv:2007.05438, 2020.
  * [24] B. Lodewijks and M. Ortgiese.  A phase transition for preferential attachment models with additive fitness.  Electron. J. Probab., 25:Paper No. 146, 54, 2020.
  * [25] R. Lyons and Y. Peres.  Probability on trees and networks, volume 42 of Cambridge Series in Statistical and Probabilistic Mathematics.  Cambridge University Press, New York, 2016.
  * [26] O. Nerman.  On the convergence of supercritical general (C-M-J) branching processes.  Z. Wahrsch. Verw. Gebiete, 57(3):365–395, 1981.
  * [27] R. Oliveira and J. Spencer.  Connectivity transitions in networks with super-linear preferential attachment.  Internet Math., 2(2):121–163, 2005.
  * [28] P. Olofsson.  The $x\log x$ condition for general branching processes.  J. Appl. Probab., 35(3):537–544, 1998.
  * [29] M. Pain and D. Sénizergues.  Correction terms for the height of weighted recursive trees.  Ann. Appl. Probab., 32(4):3027–3059, 2022.
  * [30] M. Pain and D. Sénizergues.  Height of weighted recursive trees with sub-polynomially growing total weight.  arXiv preprint arXiv:2204.05908, 2022.
  * [31] A. Rudas, B. Tóth, and B. Valkó.  Random trees and general branching processes.  Random Structures Algorithms, 31(2):186–202, 2007.
  * [32] D. Sénizergues.  Geometry of weighted recursive and affine preferential attachment trees.  Electronic Journal of Probability, 26:1–56, 2021.