2. Proof of Theorem 1

In this section we prove our main result, Theorem 1. Recall that the size of the root cluster is related to the clonal CMJ-process with generic birth process $\Xi^{(p_{n})}$ whose intensity measure $\mu^{(p_{n})}$ is given in (2). The starting point is to investigate the asymptotic behavior of the $\phi$ -counted clonal process $Z_{\varnothing}^{(p_{n}), \phi} = (Z_{\varnothing}^{(p_{n}), \phi}(t), t \geq 0)$ as $p_{n} \rightarrow 1$ and $t \rightarrow \infty$ . The approach relies crucially on the use of a remarkable martingale that can be found in the work of Nerman [Reference Nerman28]. More precisely, we improve the results in [Reference Nerman28] and [Reference Jagers and Nerman21] on the convergence of Nerman’s martingale in order to hold uniformly in the percolation parameter (see Lemmas 2 and 3 below). Then these results and further remarks are put together to conclude with the proof of Theorem 1.

Recall that $(\textbf{A4})$ implies that there exists $n^{\ast} \in \mathbb{N}$ such that for $n \geq n^{\ast}$ there is $\alpha_{p_{n}} > 0$ (the Malthusian parameter of $\mu^{(p_{n})}$ ) such that $\hat{\mu}^{(p_{n})}(\alpha_{p_{n}}) =1$ . This implies that $\mu^{(p_{n})}(\infty) = p_{n} \mathbb{E}[N] > 1$ (i.e. the clonal process is supercritical). Since $\alpha_{p_{n}} \rightarrow \alpha$ as $p_{n} \rightarrow 1$ , we choose $n^{\ast}$ large enough such that $0 < \theta_{1} < \inf_{n \geq n^{\ast}} \alpha_{p_{n}}$ , where $\theta_{1}$ satisfies (A4)–(A5). Moreover, consider $n^{\ast}$ even larger such that $0 < \theta_{2} < \inf_{n \geq n^{\ast}} \alpha_{p_{n}}$ and $0 < \theta_{3} < 2\inf_{n \geq n^{\ast}} \alpha_{p_{n}}$ , where $\theta_{2}$ and $\theta_{3}$ satisfy $(\textbf{A6})$ and $(\textbf{A7})$ , respectively.

Remark 1. Note for future reference that $\mu_{\alpha}^{(p_{n})}({\textrm{d}} t) \coloneqq {\textrm{e}}^{-t\alpha_{p_{n}}} \mu^{(p_{n})}({\textrm{d}} t)$ , for $n \geq n^{\ast}$ , is a probability measure concentrated on $(0, \infty)$ . Moreover, condition $(\textbf{A4})$ implies that

(4) \begin{equation}\bar{\mu}^{(p_{n})}(\alpha_{p_{n}}) \,:\!= \int_{0}^{\infty} t \mu_{\alpha}^{(p_{n})}(\textrm{d} t) < \infty.\end{equation}

We write $W^{(p_{n}), \phi}_{\varnothing} = (W^{(p_{n}), \phi}_{\varnothing}(t), t \geq 0)$ for the process given by

\begin{equation*} W^{(p_{n}), \phi}_{\varnothing}(t) \coloneqq {\textrm{e}}^{-t\alpha_{p_{n}} } Z^{(p_{n}), \phi}_{\varnothing}(t), \quad t \geq 0.\end{equation*}

For $p_{n} \equiv 1$ , we sometimes remove the superscript $(p_{n})$ and the subscript $\varnothing$ from the previous notations. That is, we write $W^{\phi} = (W^{\phi}(t), t \geq 0)$ for the process given by $W^{\phi}(t) \coloneqq {\textrm{e}}^{-t\alpha } Z^{\phi}(t)$ . For $n \geq n^{\ast}$ , consider the characteristic

(5) \begin{equation}\psi^{(p_{n})}(t) = \mathds{1}_{\{ t \geq 0 \}} \,{\textrm{e}}^{t\alpha_{p_{n}}} \int_{t}^{\infty} \,{\textrm{e}}^{-s\alpha_{p_{n}} } \Xi^{(p_{n})}(\textrm{d} s), \quad t \geq 0.\end{equation}

The next lemma shows that $\psi^{(p_{n})}$ satisfies the conditions (A6)–(A7).

Proof. For $t \geq 0$ and $0 < \theta < \alpha_{p_{n}}$ , we note that $\psi^{(p_{n})}(t) \leq {\textrm{e}}^{t\theta} \int_{t}^{\infty} \,{\textrm{e}}^{-s\theta} \Xi(\textrm{d} s) \leq {\textrm{e}}^{t\theta} \hat{\Xi}(\theta)$ . This inequality and conditions (A4)–(A5) imply our claim. □

Henceforth, and for the sake of simplicity, we omit the superscript $(p_{n})$ from $\psi^{(p_{n})}$ and only write $\psi$ for the characteristic defined in (5).

It is well known that the process $W^{(p_{n}), \psi}_{\varnothing}$ is a nonnegative square-integrable martingale whose terminal value will be denoted by $W^{(p_{n}), \psi}_{\varnothing}(\infty)$ . Furthermore, $W^{(p_{n}), \psi}_{\varnothing}(\infty) \geq 0$ almost surely (see [Reference Nerman28, Proposition 2.4] for the proof of the martingale property and [Reference Jagers and Nerman21, Theorem 4.1 and Corollary 4.2] for the convergence result). In particular, if $p_{n}\equiv1$ , [Reference Jagers and Nerman21, Corollary 4.2] and condition $(\textbf{A3})$ imply that $W^{(p_{n}), \psi}(\infty) = W^{\psi}(\infty) >0$ almost surely. An important result established by Nerman [Reference Nerman28] and Jagers and Nerman [Reference Jagers and Nerman21, Theorem 4.3] (see also Jagers [Reference Jagers20, Section 6.10]) implies that, for $n \geq n^{\ast}$ ,

(6) \begin{equation}\lim_{t \rightarrow \infty} W^{(p_{n}), \phi}_{\varnothing}(t) = m_{\infty}^{(p_{n}), \phi} W^{(p_{n}), \psi}_{\varnothing}(\infty),\end{equation}

almost surely and in $L_{2}(\mathbb{P})$ , where

(7) \begin{equation}m_{\infty}^{(p_{n}), \phi} \coloneqq \dfrac{\mathbb{E}[\hat{\phi}(\alpha_{p_{n}})]}{\alpha_{p} \bar{\mu}^{(p_{n})}(\alpha_{p_{n}})} < \infty,\end{equation}

with $\bar{\mu}^{(p_{n})}(\alpha_{p_{n}})$ defined in (4).

The next two results are the key ingredients in the proof of Theorem 1. The first lemma shows that the $L_{2}(\mathbb{P})$ convergence of the square-integrable martingale $W^{(p_{n}), \psi}_{\varnothing}$ holds uniformly for $n \geq n^{\ast}$ . Furthermore, it shows that the $L_{2}(\mathbb{P})$ convergence in (6) also holds uniformly for $n \geq n^{\ast}$ . The second lemma establishes an even stronger convergence result by showing that the convergence remains true as $t \rightarrow \infty$ and $p_{n} \rightarrow 1$ .

Lemma 2. Assume that conditions $(\textbf{A1})$ – $(\textbf{A5})$ are fulfilled. We have

\begin{equation*}\lim_{t \rightarrow \infty} \sup_{n \geq n^{\ast}} \mathbb{E} \Big[ \sup_{s\geq t} | W^{(p_{n}), \psi}_{\varnothing}(s) - W^{(p_{n}), \psi}_{\varnothing}(\infty) |^{2} \Big] = 0,\end{equation*}

where $\psi$ is defined in (5). Furthermore, if $\phi$ is a characteristic that does not depend on $p_{n}$ and that satisfies $(\textbf{A6})$ – $(\textbf{A7})$ , then we have

\begin{equation*}\lim_{t \rightarrow \infty} \sup_{n \geq n^{\ast}} \mathbb{E} [ | W^{(p_{n}), \phi}_{\varnothing}(t) - m_{\infty}^{(p_{n}), \phi}W^{(p_{n}), \psi}_{\varnothing}(\infty) |^{2} ] = 0.\end{equation*}

Lemma 3. Assume that conditions $(\textbf{A1})$ – $(\textbf{A5})$ are fulfilled. For a characteristic $\phi$ that does not depend on $p_{n}$ and that satisfies $(\textbf{A6})$ – $(\textbf{A7})$ , we have

\begin{equation*}\lim_{n \rightarrow \infty, t \rightarrow \infty} \mathbb{E} [ | W_{\varnothing}^{(p_{n}), \phi}(t) - m_{\infty}^{\phi} W^{\psi}(\infty) |^{2} ] = 0,\end{equation*}

where $\psi$ is defined in (5) with $p_{n} \equiv 1$ (the limit must be understood as a double limit).

The proofs of these lemmas are rather technical and it is convenient to postpone their proofs to the Appendix. We will then finish the proof of Theorem 1, but first we need the next result.

Proof. Recall the definition of $\hat{\mu}(\kern-2pt\cdot\kern-2pt)$ in (1). Recall also that (A4) implies that $\hat{\mu}(\kern-2pt\cdot\kern-2pt)$ is a continuous monotone decreasing function on $(\theta_{1}, \infty)$ , where $\theta_{1}$ is defined in $(\textbf{A4})$ . Furthermore, (A4) and the dominated convergence theorem show that $\hat{\mu}(\kern-2pt\cdot\kern-2pt)$ is differentiable with continuous derivative given by

(8) \begin{equation}\hat{\mu}^{\prime}(\theta) \coloneqq \dfrac{\textrm{d} }{\textrm{d} s} \hat{\mu}(s) \bigg |_{s = \theta} = - \int_{0}^{\infty} t \,{\textrm{e}}^{-\theta t} \mu(\textrm{d} t) \quad \text{for } \theta \in (\theta_{1}, \infty).\end{equation}

Since $p_{n} \in (0,1)$ , we have $\alpha_{p_{n}} < \alpha$ for $n \geq n^{\ast}$ . Then, for $n \geq n^{\ast}$ , the mean value theorem implies that there exists $\varepsilon_{n} \in (\alpha_{p_{n}}, \alpha)$ such that

\begin{equation*}\hat{\mu}^{\prime}(\varepsilon_{n}) = \dfrac{\hat{\mu}(\alpha) - \hat{\mu}(\alpha_{p_{n}})}{\alpha - \alpha_{p_{n}}}.\end{equation*}

Recall that (A4) implies that $\hat{\mu}(\alpha) = 1$ and $\hat{\mu}(\alpha_{p_{n}}) = 1/p_{n}$ . Moreover, we have $0 < \bar{\mu}(\alpha) < - \hat{\mu}^{\prime}(\varepsilon_{n}) < \infty$ , where $\bar{\mu}(\alpha)$ is defined in (3). Hence

\begin{equation*}\alpha - \alpha_{p_{n}} = - \hat{\mu}^{\prime}(\varepsilon_{n})^{-1} \dfrac{1-p_{n}}{p_{n}}.\end{equation*}

Finally, we use the continuity of $\hat{\mu}^{\prime}(\kern-2pt\cdot\kern-2pt)$ , since $\alpha_{p_{n}} \rightarrow \alpha$ , as $ n \rightarrow \infty$ , and $ - \hat{\mu}^{\prime}(\alpha) = \bar{\mu}(\alpha)$ . □

Proof of Theorem 1. We deduce from Lemmas 2 and 3 that

\begin{equation*}\lim_{n \rightarrow \infty} \,{\textrm{e}}^{-\alpha \tau_{n}^{\phi}} Z(\tau_{n}^{\phi}) = \lim_{n \rightarrow \infty} \,{\textrm{e}}^{-\alpha_{p_{n}} \tau_{n}^{\phi}} Z_{\varnothing}^{(p_{n})}(\tau_{n}^{\phi}) = m_{\infty} W^{\psi}(\infty),\end{equation*}

in probability, where $\psi$ is defined in (5) with $p_{n} \equiv1$ and $m_{\infty} = (\alpha \bar{\mu}(\alpha))^{-1} \in (0, \infty)$ ; see Remark 2. Proposition 1 implies that $\lim_{n \rightarrow \infty} n^{-1} Z(\tau_{n}^{\phi}) = \mathbb{E}[\hat{\phi}(\alpha)]$ a.s. Then

\begin{equation*}\lim_{n \rightarrow \infty} n^{{\alpha_{p_{n}}}/{\alpha}} \,{\textrm{e}}^{-\alpha_{p_{n}} \tau_{n}^{\phi}} = m_{\infty} \mathbb{E}^{-1}[\hat{\phi}(\alpha)] W^{\psi}(\infty).\end{equation*}

Since $W^{\psi}(\infty) > 0$ almost surely (by $(\textbf{A3})$ together with [Reference Jagers and Nerman21, Corollary 4.2]), we obtain that

\begin{equation*}\lim_{n \rightarrow \infty} n^{-{\alpha_{p_{n}}}/{\alpha}} Z_{\varnothing}^{(p_{n})}(\tau_{n}^{\phi})= \mathbb{E}[\hat{\phi}(\alpha)],\end{equation*}

in probability. Therefore our claim follows by Lemma 4. □

3. Applications

In this section we use Theorem 1 to deduce known and new results on the existence of a giant percolation cluster in the supercritical regime for several families of trees. We begin in Subsection 3.1 with some examples where the result has been established in [Reference Bertoin7]. In Subsections 3.2, 3.3, 3.4, and 3.5 we present several new examples.

3.1. General preferential attachment trees

We introduce the procedure studied by Rudas, Tóth, and Valkó [Reference Rudas, Tóth and Valkó35] and Rudas and Tóth [Reference Rudas and Tóth34] to grow a so-called general preferential attachment tree. Fix a sequence of nonnegative weights $\textbf{w} = (w_{k})_{k=0}^{\infty}$ with $w_{0} >0$ . Start the construction from a unique tree with a single vertex and build a random tree $T_{n}^{(\textbf{w})}$ with n vertices recursively as follows. Suppose that $T_{n}^{(\textbf{w})}$ has been constructed for $n \geq 1$ , and for every vertex $v \in T_{n}^{(\textbf{w})}$ let $d_{n}^{+}(v)$ denote its outdegree. Given $T_{n}^{(\textbf{w})}$ , the tree $T_{n+1}^{(\textbf{w})}$ is derived from $T_{n}^{(\textbf{w})}$ by incorporating a new vertex u and creating an edge between u and a vertex $v_{n} \in T_{n}^{(\textbf{w})}$ chosen at random according to the law

\begin{equation*}\mathbb{P}(v_{n} = v \mid T_{n}^{(\textbf{w})}) = w_{d_{n}^{+}(v)} \bigg( \sum_{v^{\prime}} w_{d_{n}^{+}(v^{\prime})} \mathds{1}_{\{v^{\prime} \in T_{n}^{(\textbf{w})} \}}\bigg)^{-1} \quad \text{for } v \in T_{n}^{(\textbf{w})}.\end{equation*}

We point out that different choices of the sequence $\textbf{w}$ yield well-known families of trees. Some of these families are summarized in Table 1; see [Reference Szymański36], [Reference Aldous1], [Reference Mahmoud26], and [Reference Pittel32] for background.

Preferential attachment trees can be constructed via CMJ-processes as in Definition 1. More precisely, consider the characteristic (or weight) $\phi \equiv 1$ and a CMJ-process with birth times $\xi_{i} = \sum_{k=1}^{i} X_{k}$ for $i \in \mathbb{N} \cup \{0\}$ (with the convention $\xi_{0} = \sum_{k=1}^{0} X_{k} =0$ ), where $X_{i} = \xi_{i} - \xi_{i-1}$ , for $i \in \mathbb{N}$ , are independent random variables and distributed according as an exponential random variable of parameter $w_{i-1}$ . In other words, we find that the process $(\Xi([0,t]), t\geq 0)$ is a pure birth process starting at 0 with birth rate $w_{k}$ when the state is $k \in \mathbb{N} \cup \{0\}$ . In this example, the lifetime of the individuals $\lambda \equiv \infty$ . Henceforth we assume that the pure birth process $(\Xi([0,t]), t\geq 0)$ is non-explosive, that is,

Table 1:

Examples of general preferential attachment trees.

(9) \begin{equation}\sum_{k=0}^{\infty} \dfrac{1}{w_{k}} = \infty;\end{equation}

see [Reference Athreya2] for details. This implies that each individual in the CMJ-process has a.s. a finite number of children in each finite interval. Furthermore, note that $\hat{\Xi}(\theta) = \sum_{k=1}^{\infty} {\textrm{e}}^{-\theta \xi_{k}}$ for $\theta >0$ . Then

\begin{equation*}\hat{\mu}(\theta) = \sum_{k=1}^{\infty} \mathbb{E}[{\textrm{e}}^{-\theta \xi_{k}}] = \sum_{k=1}^{\infty} \prod_{i=1}^{k} \mathbb{E}[{\textrm{e}}^{-\theta X_{i}}] = \sum_{k=1}^{\infty} \prod_{i=0}^{k-1} \dfrac{1}{1+\theta/w_{i}}.\end{equation*}

Assume that

(E1) \begin{equation*} \text{there exists $ \varepsilon_{1} >0 $ such that $ 1 < \hat{\mu}(\varepsilon_{1}) < \infty$.} \tag{\textbf{E1}}\end{equation*}

This implies that $w_{1} > 0$ and that the condition of non-explosion (9) is fulfilled. At the same time, it should be plain that condition $(\textbf{A4})$ is verified. Thus the Malthusian parameter exists, that is, there exists $\alpha > \varepsilon_{1}$ such that $\hat{\mu}(\alpha) =1$ . Finally, we further assume that

(E2) \begin{equation*} \operatorname{Var} ( \hat{\Xi}(\varepsilon_{1})) < \infty \tag{\textbf{E2}}.\end{equation*}

Hence the conditions (A1)–(A7) are satisfied and Theorem 1 implies the following result.

Corollary 1. In the supercritical regime, under $(\textbf{E1})$ – $(\textbf{E2})$ , we have

\begin{equation*}\lim_{n \rightarrow \infty} n^{-1} |T_{n}^{(\textbf{w})}| = \text{e}^{-c/(\alpha \bar{\mu}(\alpha))} \quad \textit{in probability}.\end{equation*}

Finally, Corollary 1 allows us to recover some of the cases studied in [Reference Bertoin7]; see [Reference Holmgren and Janson19, Section 6] for details of the calculations. See Table 2.

Table 2:

Some values of $\hat{\mu}(\theta)$ , $\alpha$ , and $\bar{\mu}(\alpha)$ for several distributions.

3.2. The m-ary search tree

The m-ary search trees, where $m \geq 2$ is a fixed integer, were first introduced in [Reference Muntz and Uzgalis27]. In particular, $m=2$ corresponds to the binary search tree described in Table 1 (Section 3.1). An m-ary search tree is an m-ary tree constructed recursively from a sequence of keys (real numbers), where each vertex stores up to $m-1$ keys. More precisely, we start from a tree containing just an empty vertex (the root). Assume that the keys are i.i.d. random variables with a continuous distribution on $\mathbb{R}$ . Then add keys one by one until the $(m-1)$ th key is placed in the root (i.e. the root becomes full) and add m new empty vertices as children of the root. Furthermore, the $m-1$ keys in the root divide the set of real numbers into m intervals $I_{1}, \ldots, I_{m}$ that we associate with each of the m children of the root. Then each further key is passed to one of the children of the root depending on which interval it belongs to, that is, a key in $I_{i}$ is stored in the ith child. Finally, we continue by iterating this procedure in an obvious way every time a vertex becomes full. This construction yields the extended m-ary search tree. In this setting, the vertices containing at least one key are called internal and the empty vertices are called external. In this work we have decided to eliminate the external vertices and consider the tree consisting of the internal nodes only. This is the m-ary search tree (in any case our results also apply to extended m-ary search tree). We also consider m-ary search trees with a fixed number of keys, say $n \in \mathbb{N}$ . In other words, we stop the previous procedure at the time when the nth key is added and let $T_{n}^{(m)}$ denote the resulting (random) m-ary search tree with n keys. Note that the number of vertices of $T_{n}^{(m)}$ is actually random.

Following [Reference Holmgren and Janson19, Section 7.2], we can construct $T_{n}^{(m)}$ as the family tree of a CMJ-process. Consider a continuous-time version of the construction procedure of an m-ary search tree and start with one vertex (the root) with a single key. The root acquires more keys after successive independent waiting times $Y_{2}, \ldots, Y_{m-1}$ , where $Y_{i}$ is an exponential random variable of parameter $i \in \{2, \ldots, m\}$ . At the arrival of the $(m-1)$ th key, at time $\sum_{i=2}^{m-1} Y_{i}$ (with the convention that the sum is equal to 0 when $m=2$ ), the root gets m children with one key for each of them, marked by $1, \ldots, m$ , with the child k born after a further waiting time $X_{k}$ , i.e. at time $\sum_{i=2}^{m-1} Y_{i} + X_{k}$ , where $X_{1}, \ldots, X_{m}$ are independent and exponentially distributed random variables of parameter 1. Finally, we continue growing the tree in an obvious way. Clearly, the CMJ-process associated with an m-ary search tree possesses birth times $\xi_{k} = \sum_{i=2}^{m-1} Y_{i} + X_{k}$ , for $k =1, \ldots, m$ (note that $N=m$ is non-random), and lifetime of each individual $\lambda \equiv \infty$ . By considering the characteristic

\begin{equation*}\phi_{m}(t) = k \quad \text{for } \sum_{i=2}^{k}Y_{i} \leq t < \sum_{i=2}^{k+1} Y_{i}, \quad \text{and} \quad k =1, 2, \ldots, m-1, \ t\geq 0,\end{equation*}

we see that $T^{\phi_{m}}_{n}$ , in Definition 1, is a random m-ary search tree with n keys. Note that

\[\hat{\Xi}(\theta) = \sum_{k=1}^{m} \exp\bigg({-}\theta \bigg( \sum_{i=2}^{m-1} Y_{i} + X_{k} \bigg)\bigg).\]

Hence a simple computation implies that

(10) \begin{equation}\hat{\mu}(\theta) = \sum_{k=1}^{m} \mathbb{E} \Bigg[\exp \Bigg({-}\theta \Bigg( \sum_{i=2}^{m-1} Y_{i} + X_{k} \Bigg) \Bigg) \Bigg] = m ! \prod_{i=1}^{m-1} (i+\theta)^{-1}, \quad \theta > -1.\end{equation}

In particular, we see that the Malthusian parameter is $\alpha =1$ . Furthermore,

\begin{equation*}\mathbb{E} [\hat{\Xi}(\theta)^{2} ] = \hat{\mu}(2\theta) \bigg( 1 + \dfrac{(m-1)(m-2)}{m} \dfrac{1+2\theta}{(1+\theta)^{2}}\bigg), \quad \theta > -1/2,\end{equation*}

which implies that $\operatorname{Var}(\hat{\Xi}(\theta)) < \infty$ for $\theta > -1/2$ . Thus it should be clear that conditions (A1)–(A7) are satisfied. Consequently, Theorem 1 implies the following result.

Corollary 2. In the supercritical regime, we have $\lim_{n \rightarrow \infty} n^{-1} |T^{(m)}_{n}| = 2(H_{m}-1) \text{e}^{-c/(H_{m} -1)}$ in probability, where $H_{m} = \sum_{i=1}^{m} i^{-1}$ .

Proof. The result follows from Theorem 1 by computing $\bar{\mu}(1)$ and $\mathbb{E}[\hat{\phi}_{m}(1)]$ . Note that (8) and (10) show that $\bar{\mu}(1) = - \hat{\mu}^{\prime}(1) = H_{m}-1$ . Note also that

\begin{equation*}\hat{\phi}_{m}(1) = \int_{0}^{\infty} \,{\textrm{e}}^{-t} \phi_{m}(t) \,\textrm{d} t = 1 + \sum_{k=2}^{m-1} \,{\textrm{e}}^{- \sum_{i=2}^{k} Y_{i}}.\end{equation*}

Therefore a direct computation shows that

\begin{equation*}\mathbb{E}[\hat{\phi}_{m}(1)] = 1 + \sum_{k=2}^{m-1} \mathbb{E}[{\textrm{e}}^{- \sum_{i=2}^{k} Y_{i}}] = 1 + 2 \sum_{k=2}^{m-1} \dfrac{1}{k+1} = 2(H_{m}-1),\end{equation*}

which concludes the proof.□

3.3. Median-of- $(2 \ell+ 1)$ binary search tree

The random median-of- $(2\ell+1)$ binary search tree, for $\ell \in \mathbb{N}$ (see e.g. [Reference Devroye13]), is a modification of the binary search tree (or 2-ary search tree), where each internal vertex contains exactly one key, but each external vertex can contain up to $2\ell$ keys (recall that keys are real numbers).

This tree is constructed recursively from an initial tree with a single external vertex without any keys. Then we add keys one by one until the $(2\ell+1)$ th key is placed at this first external vertex (or to another external vertex later in the process). The vertex becomes an internal one with two new external vertices as its children, say $v_{L}$ and $v_{R}$ . Immediately, the median of the $2\ell+1$ keys at the vertex is computed and put at the external vertex, while the $\ell$ keys that are smaller than the median are put in the left child $v_{L}$ and the $\ell$ keys that are larger than the median are put in the right child $v_{R}$ . We continue by adding new keys to the root and send them to the left or to the right whenever they are smaller or larger than the median of the first $2\ell+1$ keys. Finally, we iterate this procedure in an obvious way in order to grow the tree until $n \in \mathbb{N}$ keys have been added. We let $T_{n}^{(\ell)}$ denote the random median-of- $(2\ell + 1)$ binary search tree with n keys.

Following [Reference Holmgren and Janson19, Section 8], we can construct a median-of- $(2\ell + 1)$ binary search tree via a CMJ-process. Start with one vertex (the root) with $\ell$ keys (note that this is not a problem because the first $\ell$ keys always go there). Then each external vertex will contain between $\ell$ and $2\ell$ keys, throughout the process. On the other hand, a vertex acquires $\ell+1$ additional keys after successive independent waiting times $Y_{1}, \ldots, Y_{\ell+1}$ , where $Y_{i}$ has exponential distribution of parameter $\ell+i$ , for $i=1, \ldots, \ell+1$ . At the time when the $(\ell+1)$ th key arrives, the vertex immediately gets two children, each containing $\ell$ keys. Therefore it should be clear that the CMJ-process related to the median-of- $(2\ell+ 1)$ binary search tree has birth times $\xi_{1}=\xi_{2} = \sum_{i=1}^{\ell+1} Y_{i}$ (in distribution) and where each individual has lifetime $\lambda \equiv \infty$ . In this case $N=2$ . Define the characteristic

\begin{equation*}\phi_{\ell}(t) = \begin{cases} \ell+k & \sum_{i=1}^{k} Y_{i} \leq t < \sum_{i=1}^{k+1} Y_{i} , \ 0 \leq k \leq \ell, \\[6pt] 1 & \sum_{i=1}^{\ell+1} Y_{i} \leq t, \end{cases}\end{equation*}

for $t \geq 0$ (with the convention $\sum_{i=1}^{0}Y_{i} = 0$ ). Therefore the tree $T_{n}^{\phi_{\ell}}$ in Definition 1 is a median-of- $(2\ell + 1)$ binary search tree with n keys. In this example, note that $\hat{\Xi}(\theta) = 2\exp({-}\theta \sum_{i=1}^{\ell+1} Y_{i})$ . Hence

(11) \begin{equation}\hat{\mu}(\theta) = \mathbb{E} \Bigg[ 2\exp \Bigg({-}\theta \sum_{i=1}^{\ell+1} Y_{i} \Bigg)\Bigg] =2 \prod_{i=1}^{\ell+1} \dfrac{\ell+i}{\ell+i+\theta}, \quad \theta > - (\ell +1).\end{equation}

We deduce that the Malthusian parameter is $\alpha =1$ . Furthermore, it is not difficult to see that

\begin{equation*}\operatorname{Var} (\hat{\Xi}(\theta)) = 2 \hat{\mu}(2\theta) - \hat{\mu}(\theta)^{2} < \infty, \quad \theta > - (\ell +1)/2.\end{equation*}

Thus it should be plain that all the conditions (A1)–(A7) are satisfied. Consequently, Theorem 1 implies the following result.

Corollary 3. In the supercritical regime, we have

\begin{equation*}\lim_{n \rightarrow \infty} n^{-1} |T_{n}^{(\ell)}| = (\ell +1)(H_{2 \ell +2}-H_{\ell +1}) \,{\textrm{e}}^{-c(H_{2 \ell +2}-H_{\ell +1})^{-1}}, \quad \textit{in probability}.\end{equation*}

Proof. By Theorem 1, we only need to compute $\bar{\mu}(1)$ and $\mathbb{E}[\hat{\phi}_{\ell}(1)]$ . Note that (8) and (11) show that $\bar{\mu}(1) = - \hat{\mu}^{\prime}(1) = H_{2 \ell +2}-H_{\ell +1}$ . Note also that

\begin{equation*}\hat{\phi}_{\ell}(1) = \int_{0}^{\infty} \,{\textrm{e}}^{-t} \hat{\phi}_{\ell}(t) \,\textrm{d} t = \sum_{k=0}^{\ell} ({\textrm{e}}^{-t\sum_{i=1}^{k} Y_{i}} - {\textrm{e}}^{-t\sum_{i=1}^{k+1} Y_{i}} ) + {\textrm{e}}^{-t\sum_{i=1}^{\ell+1} Y_{i}}.\end{equation*}

Therefore a simple but tedious computation implies that $\mathbb{E}[\hat{\phi}_{\ell}(1)] = (\ell +1)(H_{2 \ell +2}\break -H_{\ell +1})$ .□

3.4. Fragmentation trees

In this section we study family trees induced by fragmentation processes. These processes were introduced in [Reference Kolmogoroff24]; see also [Reference Bertoin6] and [Reference Janson and Neininger22] for general background and further references. Fix $b \geq 2$ and consider a random vector $\textbf{V} = (V_{1}, \ldots, V_{b})$ ; this is the so-called dislocation law. Assume that $0 \leq V_{i} < 1$ a.s., for $i =1, \ldots, b$ , and $\sum_{i=1}^{b} V_{i} = 1$ , that is, $\textbf{V}$ belongs to the standard simplex.

We then describe the construction of the fragmentation tree. Start with a vertex (the root) with mass $x_{0}$ . This vertex has b children with masses $x_{0}V_{1}, \ldots, x_{0}V_{b}$ , that is, we break $x_{0}$ into b pieces with masses driven by the dislocation law $\textbf{V}$ . Consider a threshold $x_{1} \in (0, x_{0}]$ , and continue recursively with each vertex that has mass larger than $x_{1}$ , using new (independent) copies of $\textbf{V}$ each time. The process terminates a.s. after a finite number of steps, leaving a finite set of vertices (or fragments) with masses smaller than $x_{1}$ . We regard the vertices of mass larger than $x_{1}$ that occur during this process as the internal vertices and the resulting vertices of mass strictly less than $x_{1}$ as external. Note that the fragmentation tree depends only on the ratio $x_{0}/x_{1}$ , so we denote it by $T_{x_{0}/x_{1}}^\textrm{f}$ .

One can relate the fragmentation process to a CMJ-process by regarding a fragment of mass x as born at time $\log(x_{0}/x)$ . In other words, a vertex will have b children that are born at times $\xi_{i} = - \log V_{i}$ , for $i =1, \ldots, b$ (observe that $N=b$ in this case). If $V_{i}=0$ , we have $\xi_{i} = \infty$ , meaning that this child is not born, and thus a vertex has fewer than b children. Note also that the lifetime $\lambda = \infty$ . Finally, it is easy to see that the fragmentation tree $T_{x_{0}/x_{1}}^\textrm{f}$ is the same as the family tree of this CMJ-process at time $\log(x_{0}/x_{1})$ , i.e. $T(\log(x_{0}/x_{1}))$ in the notation of Section 1.1.

By using the characteristic $\phi \equiv 1$ , we define the fragmentation tree $T_{n}^\textrm{f} \coloneqq T(\tau_{n}^{\phi})$ of fixed size $n \in \mathbb{N}$ as in Definition 1. This means that we choose a threshold $x_{1} > 0$ to be the mass of the nth largest fragment in the process, so that there will be exactly n fragments of size $x_{1}$ (unless there is a tie). In this case, note that $\hat{\Xi}(\theta) = \sum_{i=1}^{b} \,{\textrm{e}}^{- \theta \xi_{i}} = \sum_{i=1}^{b} V_{i}^{\theta}$ . Then

(12) \begin{equation}\hat{\mu}(\theta) = \sum_{i=1}^{b} \mathbb{E}[V_{i}^{\theta}], \quad \theta \geq 0.\end{equation}

Thus we conclude that the Malthusian parameter is $\alpha=1$ . This has the consequence that the martingale $W^{\psi}$ (with $p_{n} \equiv 1$ ), in Section 2, is constant 1. Then we find that its limit $W^{\psi}(\infty) \equiv 1$ . Furthermore, we also find that $\operatorname{Var} (\hat{\Xi}(\theta) ) < \infty$ , for $\theta \geq 0$ . Thus the conditions (A1)–(A7) are satisfied and Theorem 1 implies the following result.

Corollary 4. In the supercritical regime, we have $\lim_{n \rightarrow \infty} n^{-1}|T_{n}^\textrm{f}| = {\textrm{e}}^{-{c}/{ \beta}}$ , in probability, where $\beta \coloneqq \sum_{i=1}^{b} \mathbb{E}[V_{i} \log(1/V_{i})]$ .

Proof. The result follows from Theorem 1. Since $\phi \equiv 1$ , we need only compute $\bar{\mu}(1)$ , but note that (8) and (12) imply that $\bar{\mu}(1) = - \hat{\mu}^{\prime}(1) = \beta$ .□

Example 1. (Binary splitting.) Consider $b =2$ and $\textbf{V} = (V_{1}, V_{2}) =(V_{1}, 1-V_{1})$ , where $V_{1}$ is a uniform random variable on (0,1). Thus, at each fragmentation event, the fragment is split into two parts, with uniformly random sizes. In the corresponding CMJ-process the birth times $\xi_{1}$ and $\xi_{2}$ are exponential random variables with parameter 1, where one of them determines the other by ${\textrm{e}}^{-\xi_{1}} + {\textrm{e}}^{-\xi_{2}} = 1$ . Furthermore, $\hat{\mu}(\theta) = (1+\theta)^{-1}$ for $\theta \geq 0$ , and $\bar{\mu}(1) = 1/2$ . Finally, note also that there are similarities with the CMJ-process associated with the binary search tree in Table 1 (Section 3.1); the difference is that there $\xi_{1}$ and $\xi_{2}$ are independent, while here they are dependent.

Finally, we should mention that the split trees defined by Devroye [Reference Devroye14] are related to fragmentation trees. A split tree is a b-ary tree defined using a number of balls that enter the root and are distributed (randomly and recursively) to the subtrees of the root and further down in the tree according to certain rules that are based on a splitting law $\textbf{V}$ ; see [Reference Devroye14] for details. For instance, binary search trees are a particular type of split tree. Percolation on split trees will be studied in another paper.

3.5. Homogeneous CMJ-trees

Let $\Lambda$ be a finite positive measure on $(0, \infty]$ with total mass $b \coloneqq \Lambda((0, \infty])$ such that $m\coloneqq \int_{(0, \infty]} t \Lambda({\textrm{d}} t)$ satisfies

(E3) \begin{equation} 1 < m < \infty. \end{equation}

Consider a CMJ-process with birth process $\Xi$ whose intensity measure is given by $\mu(\textrm{d}t) = \textrm{d}t \Lambda((t, \infty])$ . Moreover, each individual has lifetime given by a random variable $\lambda$ with distribution $\Lambda(\kern-2pt\cdot\kern-2pt) /b$ . Note that, conditional on the birth time and lifetime, the birth point process of an individual is distributed as a Poisson point process during his life. We can say that the CMJ-process is homogeneous (constant birth rate) and binary (birth occurs singly). Set

\begin{equation*}\Psi(\theta) = \theta - \int_{(0, \infty]}(1-{\textrm{e}}^{-\theta t}) \Lambda(\textrm{d} t), \quad \theta \geq 0,\end{equation*}

and observe that $\Psi$ is a convex function such that $\Psi(0+) =0$ and $\Psi^{\prime}(0+) = 1-m < 0$ . Hence there exists a unique $\alpha > 0$ such that $\Psi(\alpha) = 0$ .

In this section we are interested in studying Bernoulli bond-percolation on the family tree of this CMJ-process. More precisely, we consider the characteristic $\phi \equiv 1$ and define the CMJ-tree $T_{n}^{\textrm{hom}} \coloneqq T(\tau^{\phi}_{n})$ as in Definition 1. The family tree of this particular CMJ-process was called a splitting tree in [Reference Geiger17], [Reference Geiger and Kersting18], and [Reference Lambert25]. Further, these papers studied the case when $\Lambda$ is not necessary finite, but for simplicity we have decided to restrict ourselves to finite measures. Nevertheless, our results can be applied to the general case.

In [Reference Richard33, Chapter 3], the author studied this CMJ-process under neutral rare mutations, where mutations occur at birth with probability $1-p \in [0,1]$ . The difference from our setting is that in [Reference Richard33, Chapter 3] the probability of mutation (or percolation parameter) does not depend on the ‘size’ of the tree. Therefore the result in this section may be of independent interest.

We now check that assumptions (A1)–(A7) are satisfied. Clearly, (A1)–(A2) are fulfilled by the assumptions made on $\Lambda$ . Note that in this case $(\textbf{A3})$ is not fulfilled. Nevertheless, [Reference Richard33, Proposition 2.1; see also (2.1)] shows that the extinction probability $\mathbb{P}(Z(\infty) < \infty) = 1-\alpha/b < 1$ . This has the consequence that the limit of the martingale $W^{\psi}$ (with $p_{n}\equiv 1$ ), in Section 2, is strictly positive (i.e. $W^{\psi}(\infty) > 0$ a.s.) on the event $\{Z(\infty) = \infty\}$ ; see [Reference Jagers and Nerman21, Corollary 4.2]. Thus our results hold conditioned on the event $\{Z(\infty) = \infty\}$ since $(\textbf{A3})$ is only needed to guarantee that $W^{\psi}(\infty) > 0$ almost surely. On the other hand,

\begin{equation*}\hat{\mu}(\theta) = \int_{0}^{\infty} \int_{(t, \infty]} \,{\textrm{e}}^{-\theta t} \,\textrm{d} t \Lambda(\textrm{d} u) = \int_{(0, \infty]} \dfrac{1-{\textrm{e}}^{-\theta t}}{\theta} \Lambda(\textrm{d} t) = \dfrac{\theta-\Psi(\theta)}{\theta}, \quad \theta \geq 0,\end{equation*}

which clearly shows that $(\textbf{A4})$ is satisfied. Moreover, the Malthusian parameter is given by $\alpha > 0$ . Note also that Campbell’s formula implies that

\begin{equation*}\operatorname{Var} (\hat{\Xi}(\theta)) = \int_{0}^{\infty} \int_{(t, \infty]} \,{\textrm{e}}^{-2\theta t} \,\textrm{d} t \Lambda(\textrm{d} u) = \dfrac{2\theta-\Psi(2\theta)}{2\theta} < \infty, \quad \theta \geq 0,\end{equation*}

which implies $(\textbf{A5})$ . Finally, (A6)–(A7) follow immediately since $\phi \equiv 1$ . Therefore Theorem 1 implies the following result.

Corollary 5. In the supercritical regime and under (E3), conditional on the event $\{Z(\infty) = \infty\}$ , we have $\lim_{n \rightarrow \infty} n^{-1} |T_{n}^{\textrm{hom}}| = \text{e}^{-c/(\Psi^{\prime}(\alpha))}$ , in probability.

Proof. The result follows from Theorem 1 by computing $\bar{\mu}(\alpha)$ since $\phi \equiv 1$ . This follows from (3):

\begin{align*} \bar{\mu}(\alpha) & = \int_{0}^{\infty} t \,{\textrm{e}}^{- \alpha t} \mu(\textrm{d} t) \\[4pt] & = \int_{0}^{\infty} \int_{(t, \infty]} t \,{\textrm{e}}^{-\alpha t} \,\textrm{d} t \Lambda(\textrm{d} u) \\[4pt] & = \int_{(0, \infty]} \bigg(\!-\dfrac{t \,{\textrm{e}}^{-\alpha t}}{\alpha} + \dfrac{1-{\textrm{e}}^{-\alpha t}}{\alpha^{2}} \bigg) \Lambda(\textrm{d} t) \\[4pt] & = \dfrac{\Psi^{\prime}(\alpha)}{\alpha}.\end{align*}

□

Appendix A. Proofs of Lemmas 2 and 3

In this section we establish some general results on the long time behavior of the CMJ-process with neutral mutations that may be of independent interest. It will be helpful to write p rather than $p_{n}$ , omitting the integer n from the notation. To be more precise, we consider that the percolation parameter is a real number $p \in [0,1]$ and study the behavior of the $\phi$ -counted clonal process $Z_{\varnothing}^{(p), \phi} = (Z_{\varnothing}^{(p), \phi}(t), t \geq 0)$ as $p \rightarrow 1$ and $t \rightarrow \infty$ . Recall that $\Xi^{(p)}$ denotes the generic birth process of the clonal CMJ-process whose intensity measure $\mu^{(p)}$ is defined in (2).

Note that $(\textbf{A4})$ implies that there exists $p^{\ast} \in (0,1)$ such that for $p \in [p^{\ast},1]$ there exists ${\alpha_{p} > 0}$ (the Malthusian parameter of $\mu^{(p)}$ ) such that $\hat{\mu}^{(p)}(\alpha_{p}) =1$ . This implies that $p \mathbb{E}[N] > 1$ (i.e. the clonal process is supercritical). Since $\alpha_{p} \rightarrow \alpha$ as $p \rightarrow 1$ , we choose $p^{\ast}$ such that $0 < \theta_{1} < \alpha_{p^{\ast}}$ where $\theta_{1}$ satisfies (A4)–(A5). Furthermore, we also consider $p^{\ast}$ such that $0 < \theta_{2} < \alpha_{p^{\ast}}$ and $0 < \theta_{3} < 2\alpha_{p^{\ast}}$ , where $\theta_{2}$ and $\theta_{3}$ satisfy $(\textbf{A6})$ and $(\textbf{A7})$ , respectively.

We start by recalling some well-known results about the moments of $Z_{\varnothing}^{(p), \phi}$ . For $k \in \mathbb{N} \cup \{ 0 \}$ , we let $\nu^{\ast k}$ denote the k-fold convolution of a measure $\nu$ on $[0, \infty)$ (here $\nu^{\ast 0}$ is a unit point mass at 0).

Theorem 2. Assume that conditions $(\textbf{A1})$ – $(\textbf{A4})$ are fulfilled. For a characteristic $\phi$ that may depend on p, we have

\begin{equation*}\mathbb{E}[ Z_{\varnothing}^{(p), \phi}(t) ] = \int_{0}^{t} \mathbb{E}[\phi(t-s)] \sum_{k=0}^{\infty} (\mu^{(p)})^{\ast k} (\textrm{d} s), \quad t \geq 0.\end{equation*}

Furthermore, if $\mathbb{E}[\phi(t)]$ is bounded on finite intervals,

\begin{equation*}\operatorname{Var} ( Z_{\varnothing}^{(p), \phi}(t) ) = \int_{0}^{t} h_{\varnothing}(t-s) \sum_{k=0}^{\infty} (\mu^{(p)})^{\ast k} (\textrm{d} s), \quad t \geq 0,\end{equation*}

with

(13) \begin{equation}h_{\varnothing}^{(p)}(t) = \operatorname{Var} \bigg(\phi_{\varnothing}(t) + \int_{0}^{t} \mathbb{E} [ Z_{\varnothing}^{(p), \phi}(t-s) ] \Xi_{\varnothing}^{(p)}(\textrm{d} s) \bigg), \quad t \geq 0,\end{equation}

and where $(\Xi_{\varnothing}^{(p)}, \phi_{\varnothing})$ is the birth process and weight associated with the progenitor of the population.

Proof. The first claim is a consequence of [Reference Jagers and Nerman21, Theorem 3.1]. Note that $(\textbf{A1})$ and $(\textbf{A4})$ imply that the measure $\sum_{k=0}^{\infty} (\mu^{(p)})^{\ast k} (\textrm{d} t)$ is finite. Moreover, $\mathbb{E}[ Z_{\varnothing}^{(p), \phi}(t)] < \infty$ , for $t \geq 0$ , since $\mathbb{E}[\phi(t)]$ is bounded on finite intervals. Therefore the second claim follows from [Reference Jagers and Nerman21, Theorem 3.2].□

We next provide an improvement of the results of [Reference Jagers20, Theorem 6.9.2] and [Reference Jagers and Nerman21, Theorem 3.5] on the asymptotic behavior of the first and second moment of the clonal CMJ-process. Recall that we write $W^{(p), \phi}_{\varnothing} = (W^{(p), \phi}_{\varnothing}(t), t \geq 0)$ for the process given by $W^{(p), \phi}_{\varnothing}(t) \coloneqq {\textrm{e}}^{-t\alpha_{p} } Z^{(p), \phi}_{\varnothing}(t)$ , for $t \geq 0$ . Set

\begin{equation*}m_{t}^{(p), \phi} = \mathbb{E} [ W^{(p), \phi}_{\varnothing}(t) ], \quad t \geq 0.\end{equation*}

Recall also that for $p\equiv1$ we sometimes remove the superscript (p) and the subscript $\varnothing$ from the previous notations. That is, we write $W^{\phi} = (W^{\phi}(t), t \geq 0)$ for the processes given by $W^{\phi}(t) \coloneqq {\textrm{e}}^{-t\alpha } Z^{\phi}(t)$ and $m_{t}^{\phi} = \mathbb{E} [ W^{\phi}(t) ]$ .

Proof. We only prove (i). The proof of (ii) follows from exactly same argument and Lemma 1 (i). Recall from Remark 1 that $\mu_{\alpha}^{(p)}({\textrm{d}} t) \coloneqq {\textrm{e}}^{-t\alpha_{p}} \mu^{(p)}({\textrm{d}} t)$ , for $p \in [p^{\ast}, 1]$ , is a probability measure on $(0, \infty)$ . Theorem 2 implies that

\begin{equation*}m_{t}^{(p), \phi} = \int_{0}^{t} \,{\textrm{e}}^{- (t-s) \alpha_{p}} \mathbb{E}[\phi(t-s)] \sum_{k=0}^{\infty} (\mu_{\alpha}^{(p)})^{\ast k} (\textrm{d} s), \quad t \geq 0,\end{equation*}

where we have used that

\begin{equation*}{\textrm{e}}^{- s\alpha_{p}}\sum_{k=0}^{\infty} (\mu^{(p)})^{\ast k} (\textrm{d} s) = \sum_{k=0}^{\infty} (\mu_{\alpha}^{(p)})^{\ast k} (\textrm{d} s).\end{equation*}

From $(\textbf{A6})$ , we deduce that the family of functions $t \mapsto {\textrm{e}}^{-t\alpha_{p}} \mathbb{E}[\phi(t)]$ , for $p \in [p^{\ast}, 1]$ , it is uniformly directly Riemann integrable (see [Reference Tsirelson37, Definition 2.8]). Furthermore, $(\textbf{A4})$ implies that the family of probability measures $\{ \mu_{\alpha}^{(p)}\colon p \in [p^{\ast}, 1] \}$ is weakly compact (treated as a set of measure on $(0,\infty)$ ), and uniformly integrable, that is,

\begin{equation*}\lim_{a \rightarrow \infty} \sup_{p \in [p^{\ast}, 1]} \int_{[a, \infty)} t \mu_{\alpha}^{(p)}(\textrm{d}t) = 0.\end{equation*}

Therefore the point (i) is a consequence of the uniform version of the key renewal theorem [Reference Tsirelson37, Theorem 2.12] since $\mu$ satisfies $(\textbf{A2})$ . The second claim in (i) follows from the definition of $m_{\infty}^{(p), \phi}$ by noting that

\begin{equation*}\alpha_{p^{\ast}} \leq \alpha_{p} \leq \alpha, \quad \bar{\mu}^{(p)}(\alpha_{p}) \geq p^{\ast}\bar{\mu}^{(1)}(\alpha) \quad \text{and} \quad \mathbb{E}[\hat{\phi}(\alpha_{p})] \leq \dfrac{\alpha}{ \alpha_{p^{\ast}}} \mathbb{E}[\hat{\phi}(\alpha_{p^{\ast}})];\end{equation*}

we also need to recall that $\bar{\mu}^{(1)}(\alpha) >0$ by Remark 2. □

By Proposition 2,

\begin{equation*}v_{t}^{(p), \phi} = \operatorname{Var} ( W^{(p), \phi}_{\varnothing}(t) ), \quad t \geq 0,\end{equation*}

is well-defined. For $p \equiv 1$ , we sometimes write $v_{t}^{\phi} = \operatorname{Var} ( W^{\phi}(t) )$ , for $t \geq 0$ .

Proof. We only prove (i). The proofs of (ii) and (iii) follow similarly by using Lemma 1 and Remark 3. Theorem 2 implies that

\begin{equation*}v_{t}^{(p), \phi} = \int_{0}^{t} \,{\textrm{e}}^{-2(t-s)\alpha_{p}} h^{(p)}_{\varnothing}(t-s) \,{\textrm{e}}^{-2s\alpha_{p}} \sum_{k=0}^{\infty} (\mu^{(p)})^{\ast k} (\textrm{d} s), \quad t \geq 0,\end{equation*}

where the function $h^{(p)}_{\varnothing}$ is defined in (13). First, note the identity

(14) \begin{equation}\int_{0}^{\infty} \,{\textrm{e}}^{-2s \alpha_{p} } \sum_{k=0}^{\infty} (\mu^{(p)})^{\ast k} (\textrm{d} s) = \sum_{k=0}^{\infty} \hat{\mu}^{(p)}(2 \alpha_{p})^{k} = \dfrac{1}{1-\hat{\mu}^{(p)}(2 \alpha_{p})} < \infty,\end{equation}

since $\hat{\mu}^{(p)}(2 \alpha_{p}) < \hat{\mu}^{(p)}(\alpha_{p}) =1$ . Then the triangle inequality implies that

(15) \begin{align} & |v_{t}^{(p), \phi} -v_{\infty}^{(p), \phi} | \notag \\* &\quad \leq \int_{0}^{t}\,{\textrm{e}}^{-2(t-s)\alpha_{p}} \operatorname{Var}(\phi_{\varnothing}(t-s)) \,{\textrm{e}}^{ -2s\alpha_{p}} \sum_{k=0}^{\infty} (\mu^{(p)})^{\ast k} (\textrm{d} s) \notag \\*& \quad \quad\, + 2\int_{0}^{t}\,{\textrm{e}}^{-(t-s)\alpha_{p}} \bigg| \operatorname{Cov} \bigg(\phi_{\varnothing}(t-s), \int_{0}^{t-s} m_{t-s-u}^{(p), \phi} \,{\textrm{e}}^{-u \alpha_{p}} \Xi^{(p)}_{\varnothing}(\textrm{d} u) \bigg)\bigg| \,{\textrm{e}}^{ -2s\alpha_{p}} \sum_{k=0}^{\infty} (\mu^{(p)})^{\ast k} (\textrm{d} s) \notag \\*& \quad \quad\, + \int_{0}^{\infty} g^{(p)}(t-s) \,{\textrm{e}}^{-2s\alpha_{p}} \sum_{k=0}^{\infty} (\mu^{(p)})^{\ast k} (\textrm{d} s),\end{align}

where $(\Xi_{\varnothing}^{(p)}, \phi_{\varnothing})$ is the birth process and weight associated with the progenitor of the population, and

\begin{equation*}g^{(p)}(t-s) = \bigg | \mathds{1}_{\{ s\in [0,t] \}} \operatorname{Var} \bigg( \int_{0}^{t-s} m_{t-s-u}^{(p), \phi} \,{\textrm{e}}^{-u\alpha_{p}} \Xi^{(p)}_{\varnothing}(\textrm{d} u) \bigg) - ( m_{\infty}^{(p), \phi} )^{2}\operatorname{Var}(\hat{\Xi}^{(p)}_{\varnothing}(\alpha_{p})) \bigg|.\end{equation*}

Let $I_{1}^{(p)}(t)$ , $I_{2}^{(p)}(t)$ , and $I_{3}^{(p)}(t)$ , respectively, denote the first, second, and third terms on the right-hand side of (15). Then the claim in Proposition 3 follows by showing that

1. (a) $\lim_{t \rightarrow \infty} \sup_{p \in [p^{\ast}, 1]} I_{1}^{(p)}(t) = 0$ ,

2. (b) $\lim_{t \rightarrow \infty} \sup_{p \in [p^{\ast}, 1]} I_{2}^{(p)}(t) = 0$ , and

3. (c) $\lim_{t \rightarrow \infty} \sup_{p \in [p^{\ast}, 1]} I_{3}^{(p)}(t) = 0$ .

We start by showing (a). By assumption $(\textbf{A7})$ ,

(16) \begin{equation}\lim_{t \rightarrow \infty} \sup_{p \in [p^{\ast}, 1]} \,{\textrm{e}}^{-2t\alpha_{p}} \operatorname{Var}(\phi(t)) \leq \lim_{t \rightarrow \infty} \,{\textrm{e}}^{-2t\alpha_{p^{\ast}}} \operatorname{Var}(\phi(t)) = 0.\end{equation}

Then (14) and the dominated convergence theorem prove point (a).

Next we show (b). The Cauchy–Schwarz inequality and Proposition 2 imply that

\begin{align*}& \bigg| \operatorname{Cov} \bigg(\phi_{\varnothing}(t), \int_{0}^{t} m_{t-u}^{(p), \phi} \,{\textrm{e}}^{-u \alpha_{p}} \Xi^{(p)}_{\varnothing}(\textrm{d} u) \bigg)\bigg| \\* & \quad \leq (\operatorname{Var}(\phi_{\varnothing}(t)))^{{1}/{2}} \bigg( \operatorname{Var}\bigg( \int_{0}^{t} m_{t-u}^{(p), \phi} \,{\textrm{e}}^{-u \alpha_{p}} \Xi^{(p)}_{\varnothing}(\textrm{d} u)\bigg) \bigg)^{{1}/{2}} \\*& \quad \leq \bigg(\operatorname{Var}(\phi_{\varnothing}(t)) \operatorname{Var}\bigg( \int_{0}^{t} \,{\textrm{e}}^{-u \alpha_{p}} \Xi^{(p)}_{\varnothing}(\textrm{d} u)\bigg) \bigg)^{{1}/{2}} \sup_{t \geq 0} \sup_{p \in [p^{\ast},1]} m_{t}^{(p), \phi}.\end{align*}

Since ${\textrm{e}}^{-u\alpha_{p} } \Xi^{(p)}(\textrm{d} u)$ is dominated by ${\textrm{e}}^{-u\alpha_{p^{\ast}}} \Xi(\textrm{d} u)$ , (A4)–(A5) and (16) allow us to deduce that

\begin{equation*}\lim_{t \rightarrow \infty} \sup_{p \in [p^{\ast}, 1]} \,{\textrm{e}}^{-t\alpha_{p}} \bigg| \operatorname{Cov} \bigg(\phi_{\varnothing}(t), \int_{0}^{t} m_{t-u}^{(p), \phi} \,{\textrm{e}}^{-u \alpha_{p}} \Xi^{(p)}_{\varnothing}(\textrm{d} u) \bigg) \bigg| = 0.\end{equation*}

Hence an application of the dominated convergence theorem shows (b).

Finally, we prove (c). We show that

(17) \begin{equation} \lim_{t \rightarrow \infty} \sup_{p \in [p^{\ast}, 1]} g^{(p)}(t-s) = 0,\end{equation}

which together with an application of the dominated convergence theorem implies (c). Observe that

(18) \begin{align}g^{(p)}(t-s) & \leq g_{1}^{(p)}(t-s) + g_{2}^{(p)}(t-s) + g_{3}^{(p)}(t-s) \notag \\*& \quad\, + g_{4}^{(p)}(t-s) + \mathds{1}_{\{ s\in (t,\infty) \}} ( m_{\infty}^{(p), \phi} )^{2}\operatorname{Var}(\hat{\Xi}^{(p)}(\alpha_{p})),\end{align}

where

\begin{align*}g_{1}^{(p)}(t-s) & = \mathds{1}_{\{ s\in [0,t] \}} \operatorname{Var}\bigg( \int_{0}^{t-s} ( m_{t-s-u}^{(p), \phi} - m_{\infty}^{(p), \phi} ) \,{\textrm{e}}^{-u\alpha_{p}} \Xi^{(p)}(\textrm{d} u) \bigg),\\* g_{2}^{(p)}(t-s)& = 2 \mathds{1}_{\{ s\in [0,t] \}}\bigg| \operatorname{Cov}\bigg( \int_{0}^{t-s} ( m_{t-s-u}^{(p), \phi} - m_{\infty}^{(p), \phi} ) \,{\textrm{e}}^{-u\alpha_{p}} \Xi^{(p)}(\textrm{d} u),\\* &\qquad m_{\infty}^{(p), \phi} \int_{0}^{t-s} \,{\textrm{e}}^{-u\alpha_{p}} \Xi^{(p)}(\textrm{d} u) \bigg) \bigg|,\\*g_{3}^{(p)}(t-s) & = 2 ( m_{\infty}^{(p), \phi} )^{2} \mathds{1}_{\{ s\in [0,t] \}}\bigg| \operatorname{Cov}\bigg( \hat{\Xi}^{(p)}(\alpha_{p}), \int_{t-s}^{\infty} \,{\textrm{e}}^{-u\alpha_{p}} \Xi^{(p)}(\textrm{d} u) \bigg) \bigg|, \quad \text{and}\\*g_{4}^{(p)}(t-s) & = \mathds{1}_{\{ s\in [0,t] \}} ( m_{\infty}^{(p), \phi} )^{2} \operatorname{Var}\bigg( \int_{t-s}^{\infty} \,{\textrm{e}}^{-u\alpha_{p}} \Xi^{(p)}(\textrm{d} u) \bigg).\end{align*}

Proposition 2 and $(\textbf{A5})$ imply that

(19) \begin{equation}\lim_{t \rightarrow \infty} \sup_{p \in [p^{\ast}, 1]} g_{4}^{(p)}(t-s) = 0,\end{equation}

and

(20) \begin{equation}\lim_{t \rightarrow \infty} \sup_{p \in [p^{\ast}, 1]} \mathds{1}_{\{ s\in (t,\infty) \}} ( m_{\infty}^{(p), \phi} )^{2}\operatorname{Var}(\hat{\Xi}^{(p)}(\alpha_{p})) = 0.\end{equation}

Furthermore, Proposition 2 implies that

\begin{equation*} \sup_{t \geq 0} \sup_{p \in [p^{\ast}, 1]} | m_{t}^{(p), \phi} - m_{\infty}^{(p), \phi} | < \infty.\end{equation*}

Recall that ${\textrm{e}}^{-s \alpha_{p} } \Xi^{(p)}(\textrm{d} s)$ is dominated by ${\textrm{e}}^{-s\alpha_{p^{\ast}}} \Xi(\textrm{d} s)$ and that $\int_{0}^{\infty} \,{\textrm{e}}^{-s\alpha_{p^{\ast}} } \Xi(\textrm{d} s) < \infty$ , by $(\textbf{A4})$ . Thus the dominated convergence theorem shows that

\begin{equation*} \lim_{t \rightarrow \infty} \sup_{p \in [p^{\ast}, 1]} \bigg| \mathds{1}_{\{ s\in [0,t] \}} \int_{0}^{t-s} ( m_{t-s-u}^{(p), \phi} - m_{\infty}^{(p), \phi} ) \,{\textrm{e}}^{-u\alpha_{p}} \Xi^{(p)}(\textrm{d} u) \bigg| = 0,\end{equation*}

almost surely. This implies that

(21) \begin{equation} \lim_{t \rightarrow \infty} \sup_{p \in [p^{\ast}, 1]} g_{1}^{(p)}(t-s) = 0,\end{equation}

once again using the dominated convergence theorem. Similarly, we can deduce that

(22) \begin{equation}\lim_{t \rightarrow \infty} \sup_{p \in [p^{\ast}, 1]} g_{2}^{(p)}(t-s) = 0 \quad \text{and} \quad \lim_{t \rightarrow \infty} \sup_{p \in [p^{\ast}, 1]} g_{3}^{(p)}(t-s) = 0.\end{equation}

Finally, our claim in (17) follows by combining (18), (19), (20), (21), and (22). □

We now have all the ingredients to prove Lemma 2.

Proof of Lemma 2. Note that

(23) \begin{align}& \mathbb{E} \Big[ \sup_{s\geq t} | W^{(p), \psi}_{\varnothing}(s) - W^{(p), \psi}_{\varnothing}(\infty) |^{2} \Big] \notag \\*& \quad \leq 2 \mathbb{E} [ | W^{(p), \psi}_{\varnothing}(t) - W^{(p), \psi}_{\varnothing}(\infty) |^{2} ] + 2 \mathbb{E} \Big[ \sup_{s\geq t} | W^{(p), \psi}_{\varnothing}(s) - W^{(p), \psi}_{\varnothing}(t) |^{2} \Big]\end{align}

for $t \geq 0$ . On the one hand, from properties of square-integrable martingales, we obtain that

(24) \begin{equation}\mathbb{E}[ | W^{(p), \psi}_{\varnothing}(t) - W^{(p), \psi}_{\varnothing}(\infty) |^{2} ] = \mathbb{E}[ W^{(p), \psi}_{\varnothing}(\infty)^{2} ] - \mathbb{E}[ W^{(p), \psi}_{\varnothing}(t)^{2} ]\end{equation}

for $t \geq 0$ . On the other hand, by Doob’s inequality

(25) \begin{equation}\mathbb{E} \Big[ \sup_{s\geq t} | W^{(p), \psi}_{\varnothing}(s) - W^{(p), \psi}_{\varnothing}(t) |^{2} \Big] \leq 4 \mathbb{E}[ W^{(p), \psi}_{\varnothing}(\infty)^{2} ] - 4\mathbb{E}[ W^{(p), \psi}_{\varnothing}(t)^{2} ]\end{equation}

for $t \geq 0$ . By combining (23), (24), and (25), we deduce that

\begin{align*}& \mathbb{E}\Big[ \sup_{s \geq t} | W^{(p), \psi}_{\varnothing}(s) - W^{(p),\psi}_{\varnothing}(\infty) |^{2} \Big] \\*& \quad \leq 10 ( v_{\infty}^{(p), \psi} - v_{t}^{(p), \psi} ) + 10 ( ( m_{\infty}^{(p), \psi} )^{2}- ( m_{t}^{(p), \psi} )^{2} ) \\*& \quad = 10 ( v_{\infty}^{(p), \psi} - v_{t}^{(p), \psi} )\end{align*}

since $W^{(p), \psi}_{\varnothing}$ is a martingale. Therefore the first statement follows from Proposition 3. We turn our attention to the second claim. Observe that

(26) \begin{align}& \mathbb{E} [ | W^{(p), \phi}_{\varnothing}(t) - m_{\infty}^{(p), \phi}W^{(p), \psi}_{\varnothing}(\infty) |^{2} ] \notag \\*& \quad \leq 2 \mathbb{E} [ | W^{(p), \phi}_{\varnothing}(t) - m_{\infty}^{(p), \phi}W^{(p), \psi}_{\varnothing}(t) |^{2} ] + 2 (m_{\infty}^{(p), \phi} )^{2} \mathbb{E} [ | W^{(p), \psi}_{\varnothing}(t) - W^{(p), \psi}_{\varnothing}(\infty) |^{2} ],\end{align}

for $t \geq 0$ . It follows from the first part that

\begin{equation*}\lim_{t \rightarrow \infty} \sup_{p \in [p^{\ast},1]} \mathbb{E} [ | W^{(p), \psi}_{\varnothing}(t) - W^{(p), \psi}_{\varnothing}(\infty) |^{2} ] = 0.\end{equation*}

In order to conclude, it is enough to show that the first term on the right-hand side of (26) tends to 0 uniformly on $p \in [p^{\ast},1]$ as $t \rightarrow \infty$ . By Proposition 2, this is equivalent to showing that

(27) \begin{equation}\lim_{t \rightarrow \infty} \sup_{p \in [p^{\ast},1]} \operatorname{Var} ( W^{(p), \phi}_{\varnothing}(t) - m_{\infty}^{(p), \phi}W^{(p), \psi}_{\varnothing}(t) ) = 0\end{equation}

since $W^{(p), \phi}_{\varnothing}(t) + m_{\infty}^{(p), \phi}W^{(p), \psi}_{\varnothing}(t) = W^{(p), \phi^{\prime}}_{\varnothing}(t)$ , where $ \phi^{\prime}(t) = \phi(t) + m_{\infty}^{(p), \phi} \psi(t)$ . But (27) follows from Proposition 3, Remark 3, and the identity

\begin{align*}& \operatorname{Var} ( W^{(p), \phi}_{\varnothing}(t) - m_{\infty}^{(p), \phi}W^{(p), \psi}_{\varnothing}(t) ) \\*& \quad = 2 \operatorname{Var} ( W^{(p), \phi}_{\varnothing}(t) ) + 2 \operatorname{Var} ( m_{\infty}^{(p), \phi}W^{(p), \psi}_{\varnothing}(t) ) - \operatorname{Var} ( W^{(p), \phi}_{\varnothing}(t) + m_{\infty}^{(p), \phi}W^{(p), \psi}_{\varnothing}(t) ).\end{align*}

□

Finally, we conclude this section with the proof of Lemma 3. The idea of the proof is similar to that of [Reference Bertoin and Uribe Bravo10, Lemma 3].

Proof of Lemma 3. We first prove that the double limit

(28) \begin{equation} \lim_{p \rightarrow 1, t \rightarrow \infty} W_{\varnothing}^{(p), \phi}(t) \ \text{exists in $ L_{2}(\mathbb{P})$.}\end{equation}

Denote the $L_{2}(\mathbb{P})$ -norm by $\| \cdot \|_{2}$ . We claim that

(29) \begin{equation} \lim_{p \rightarrow 1} \| W^{(p), \phi}_{\varnothing}(t) - W^{ \phi}(t) \|_{2} = 0 \quad \text{for } t \geq 0.\end{equation}

Recall that at each birth event, independently of all the other individuals, the newborn is a clone of its parent with probability p or a mutant with probability $1-p$ . Then it should be plain from the thinning property of point measure processes that the birth process of the mutant children of the ancestor $\varnothing$ , denoted by $\Xi_{\varnothing}^{(p), \text{m}}$ , has intensity measure given $(1-p) \mu (\textrm{d}t)$ . Furthermore, the latter is independent of the birth process of the clonal children of the ancestor described in Section 1.2. Let $Z^{(p), \text{m}} = (Z^{(p), \text{m}}(t), t\geq 0 )$ be the process that counts the number of mutants born up to time $t \geq 0$ and define

\begin{equation*}b^{(p)}_{1} = \inf \{t \geq 0\colon Z^{(p), \text{m}}(t) > 0 \}\end{equation*}

to be the first birth time of a mutant. Plainly, $\lim_{p \rightarrow 1} b^{(p)}_{1} = \infty$ in probability, and the probability of the event $\{ t \geq b^{(p)}_{1} \}$ can be made as small as we wish by choosing p sufficiently close to 1. On the one hand, as $ Z^{(p), \phi}_{\varnothing}(t) \leq Z^{ \phi}(t)$ , we have

\begin{equation*}\mathbb{E} [ | W^{(p), \phi}_{\varnothing}(t) -W^{ \phi}(t) |^{2}, t \geq b^{(p)}_{1} ] \leq ({\textrm{e}}^{2(\alpha-\alpha_{p}) t} + 1 ) \mathbb{E} [ | W^{ \phi}(t) |^{2}, t \geq b^{(p)}_{1} ] {,}\end{equation*}

and the right-hand side goes to 0 as $p \rightarrow 1$ . On the other hand, on the event $\{ t < b^{(p)}_{1} \}$ , we have $ Z^{(p), \phi}_{\varnothing}(t) = Z^{ \phi}(t)$ and hence $ W^{(p), \phi}_{\varnothing}(t) = {\textrm{e}}^{(\alpha-\alpha_{p}) t} W^{ \phi}(t)$ . This yields

\begin{equation*}\mathbb{E} [ | W^{(p), \phi}_{\varnothing}(t_{\varepsilon}) -W^{ \phi}(t) |^{2}, t < b^{(p)}_{1} ] \leq ({\textrm{e}}^{(\alpha-\alpha_{p}) t} - 1 ) \mathbb{E} [ | W^{ \phi}(t) |^{2} ]{,}\end{equation*}

and the right-hand side goes to 0 as $p \rightarrow 1$ . This establishes the convergence in (29).

Let $\varepsilon > 0$ be arbitrary. By Lemma 2, we can find $t_{\varepsilon} > 0$ such that

(30) \begin{equation} \sup_{p \in [p^{\ast},1]} \| W^{(p), \phi}_{\varnothing}(s) - m_{\infty}^{(p), \phi}W^{(p), \psi}_{\varnothing}(\infty) \|_{2} \leq \dfrac{\varepsilon}{6} \quad \text{for all } s \geq t_{\varepsilon}.\end{equation}

By using (29), we obtain that for $s \geq t_{\varepsilon}$ there is $ \delta_{\varepsilon} > 0$ such that $1-p < \delta_{\varepsilon} $ (for $p \in [p^{\ast}, 1)$ ) implies that

(31) \begin{equation} \| W^{(p), \phi}_{\varnothing}(s) - W^{ \phi}(s) \|_{2} \leq \dfrac{\varepsilon}{6}.\end{equation}

Let us take $s_{1}, s_{2} \geq t_{\varepsilon}$ and $p_{1}, p_{2} \in [p^{\ast}, 1)$ such that $1-p_{1} < \delta_{\varepsilon} $ and $1-p_{2} < \delta_{\varepsilon} $ . The Minkowski inequality implies that for $s \geq t_{\varepsilon}$

\begin{align*}& \| W^{(p_{1}), \phi}_{\varnothing}(s_{1}) - W^{(p_{2}), \phi}_{\varnothing}(s_{2}) \|_{2} \\*& \quad \leq \| W^{(p_{1}), \phi}_{\varnothing}(s_{1}) - m_{\infty}^{(p_{1}), \phi}W^{(p_{1}), \psi}_{\varnothing}(\infty) \|_{2} + \| W^{(p_{1}), \phi}_{\varnothing}(s) - m_{\infty}^{(p_{1}), \phi}W^{(p_{1}), \psi}_{\varnothing}(\infty) \|_{2} \\& \quad\quad\, + \| W^{(p_{1}), \phi}_{\varnothing}(s) - W^{ \phi}(s) \|_{2} + \| W^{(p_{2}), \phi}_{\varnothing}(s) - W^{ \phi}(s) \|_{2} \\*& \quad\quad\, + \| W^{(p_{2}), \phi}_{\varnothing}(s_{2}) - m_{\infty}^{(p_{2}), \phi}W^{(p_{2}), \psi}_{\varnothing}(\infty) \|_{2} + \| W^{(p_{2}), \phi}_{\varnothing}(s) - m_{\infty}^{(p_{2}), \phi}W^{(p_{2}), \psi}_{\varnothing}(\infty) \|_{2}.\end{align*}

By (30) and (31), we deduce that $\| W^{(p_{1}), \phi}_{\varnothing}(s_{1}) - W^{(p_{2}), \phi}_{\varnothing}(s_{2}) \|_{2} \leq \varepsilon$ . Thus $W^{(p), \phi}_{\varnothing}(t)$ is $L_{2}(\mathbb{P})$ -Cauchy. Therefore the claim in (28) follows from the well-known completeness of $L_{2}(\mathbb{P})$ ; see [Reference Bartle3, Theorem 6.14].

Finally, we show that the claim in Lemma 3 holds. Note that (28) implies that there exists a square-integrable variable $\overline{W}$ such that $\lim_{p \rightarrow 1, t \rightarrow \infty} W_{\varnothing}^{(p), \phi}(t) = \overline{W}$ in $L_{2}(\mathbb{P})$ . Thus it is enough to show that $\overline{W} = m_{\infty}^{\phi} W^{\psi}(\infty)$ , where $\psi$ is defined in (5) with $p\equiv1$ . In this direction, for $t \geq 0$ , recall that (29) shows that $\lim_{p \rightarrow 1} W_{\varnothing}^{(p), \phi}(t) = W^{\phi}(t)$ in $L_{2}(\mathbb{P})$ . Furthermore, Lemma 2 implies that

(32) \begin{equation}\lim_{t \rightarrow \infty} \lim_{p \rightarrow 1} W_{\varnothing}^{(p), \phi}(t) = \lim_{t \rightarrow \infty} W^{\phi}(t) = m_{\infty}^{\phi} W^{\psi}(\infty), \quad \text{in $ L_{2}(\mathbb{P})$.}\end{equation}

On the other hand, (28) implies that for $\varepsilon > 0$ there are $\delta_{\varepsilon}, t_{\varepsilon} > 0$ such that for $1-p < \delta_{\varepsilon}$ (for $p \in [p^{\ast}, 1)$ ) and $s \geq t_{\varepsilon}$ we have $\| W^{(p), \phi}_{\varnothing}(s) - \overline{W} \|_{2} \leq \varepsilon$ . Hence (29) and an application of the dominated convergence theorem allow us to conclude that

\begin{equation*}\lim_{p \rightarrow 1} \| W^{(p), \phi}_{\varnothing}(s) - \overline{W} \|_{2} = \| W^{\phi}(s) - \overline{W} \|_{2} \leq \varepsilon,\end{equation*}

i.e. $\lim_{t \rightarrow \infty} \lim_{p \rightarrow 1} W_{\varnothing}^{(p), \phi}(t) = \overline{W}$ in $L_{2}(\mathbb{P})$ , which combined with (32) concludes the proof. □