Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-25T09:09:34.428Z Has data issue: false hasContentIssue false

Invariant Galton–Watson trees: metric properties and attraction with respect to generalized dynamical pruning

Published online by Cambridge University Press:  12 January 2023

Yevgeniy Kovchegov*
Affiliation:
Oregon State University
Guochen Xu*
Affiliation:
Oregon State University
Ilya Zaliapin*
Affiliation:
University of Nevada Reno
*
*Postal address: Department of Mathematics, Oregon State University, Corvallis, OR 97331-4605, USA.
*Postal address: Department of Mathematics, Oregon State University, Corvallis, OR 97331-4605, USA.
****Postal address: Department of Mathematics and Statistics, University of Nevada Reno, Reno, NV 89557-0172, USA. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

The invariant Galton–Watson (IGW) tree measures are a one-parameter family of critical Galton–Watson measures invariant with respect to a large class of tree reduction operations. Such operations include the generalized dynamical pruning (also known as hereditary reduction in a real tree setting) that eliminates descendant subtrees according to the value of an arbitrary subtree function that is monotone nondecreasing with respect to an isometry-induced partial tree order. We show that, under a mild regularity condition, the IGW measures are attractors of arbitrary critical Galton–Watson measures with respect to the generalized dynamical pruning. We also derive the distributions of height, length, and size of the IGW trees.

Type
Original Article
Copyright
© The Author(s), 2023. Published by Cambridge University Press on behalf of Applied Probability Trust

1. Introduction

In this paper we continue the study of the critical branching processes with the progeny generating function $Q(z)=z+q(1-z)^{1/q}$ for a given parameter $q \in [1/2,1)$ . The importance of these processes was previously observed in [Reference Abraham and Delmas1, Reference Duquesne and Le Gall7, Reference Duquesne and Winkel9, Reference Kovchegov and Zaliapin20, Reference Kovchegov and Zaliapin21, Reference Le Jan23, Reference Neveu25, Reference Zolotarev32]. The random tree measures induced by these branching processes are called here the invariant Galton–Watson (IGW) measures. This paper has two goals. First, we establish the main metric properties of the IGW trees: the distributions of their height, length, and size (the number of edges). These distributions are well-studied for a special case of the IGW process with $q=1/2$ that coincides with the critical binary Galton–Watson process [Reference Kovchegov and Zaliapin20]. Here we establish the results for the general case of $q \in [1/2,1)$ . Second, we extend the results of [Reference Kovchegov and Zaliapin21], where the IGW trees were shown to be the attractors of the pushforward measures under the iterative application of Horton pruning (eliminating tree leaves followed by a series reduction). Here, we obtain analogous results under a much broader generalized dynamical pruning introduced in [Reference Kovchegov and Zaliapin19]. Since the generalized dynamical pruning can be expressed via the hereditary reduction of [Reference Duquesne and Winkel9], the attractor property of IGW tree measures holds for the hereditary reduction as well. Also, the IGW trees turn out to be the attractors under the Bernoulli leaf coloring, a tree reduction studied in [Reference Duquesne and Winkel8].

The paper is organized as follows. Section 2 contains all the necessary background. The results are stated in Section 3 and proved in Section 4. The paper concludes with a discussion in Section 5. Appendix A contains the statement of the Lagrange inversion theorem used in this paper. In Appendix B, Karamata’s theorem and its converse are stated. Appendix C contains a proof of Lemma 2.5.

2. Background

2.1. Spaces of trees

A tree is called rooted if one of its vertices, denoted by $\rho$ , is designated as the tree root. The existence of root imposes a parent–offspring relation between each pair of adjacent vertices: the one closer to the root is called the parent, and the other the offspring. A tree is called reduced if it has no vertices of degree 2, with the root as the only possible exception. Let ${\mathcal{T}}$ denote the space of finite unlabeled rooted reduced trees with no planar embedding. The absence of planar embedding is the absence of order among the offspring of the same parent. The space ${\mathcal{T}}$ includes the empty tree $\phi$ comprising a root vertex $\rho$ and no edges.

Let ${\mathcal{L}}$ denote the space of trees from ${\mathcal{T}}$ equipped with edge lengths. Thus, a tree in ${\mathcal{L}}$ is itself a metric space. A metric tree $T\in{\mathcal{L}}$ can be considered as a metric space with distance $d(\cdot,\cdot)$ induced by the Lebesgue measure along the tree edges [Reference Kovchegov and Zaliapin20]. Hence, a metric tree $T\in{\mathcal{L}}$ can be represented as a pair $T=(S,d)$ , where S represents the space and d is the metric defined on the space S. The operator ${\rm{\small SHAPE}}(T)\,:\, {\mathcal{L}}\to{\mathcal{T}}$ projects a tree $T\in{\mathcal{L}}$ with edge lengths on a tree in ${\mathcal{T}}$ that retains the combinatorial structure of T (and drops the edge length assignment).

A nonempty rooted tree is called planted if its root $\rho$ has degree one. In this case the only edge connected to the root is called the stem. If the root $\rho$ is of degree $\geq 2$ then the tree is called stemless. We denote by ${\mathcal{T}}^{|}$ and ${\mathcal{T}}^{\vee}$ the subspaces of ${\mathcal{T}}$ consisting of planted and stemless trees, respectively. Similarly, ${\mathcal{L}}^{|}$ and ${\mathcal{L}}^{\vee}$ are the subspaces of ${\mathcal{L}}$ consisting of planted and stemless trees. Additionally, we include the empty tree $\phi=\{\rho\}$ as an element in each of these subspaces, ${\mathcal{T}}^{|}$ , ${\mathcal{T}}^{\vee}$ , ${\mathcal{L}}^{|}$ , and ${\mathcal{L}}^{\vee}$ , defined above.

2.2. Galton–Watson tree measures

Consider a Galton–Watson branching process with a given progeny distribution (probability mass function) $\{q_k\}$ , $k=0, 1,2,\dots$ . More specifically, we consider a discrete-time Markov process that begins with a single progenitor, which produces a single offspring (hence the trees we examine are planted). At each later step, each existing population member produces $k\ge 0$ offspring with probability $q_k$ , independently from the prior history of the process; see [Reference Athreya and Ney3, Reference Harris13].

A Galton–Watson tree is forme d by the trajectory of the Galton–Watson branching process, with the progenitor corresponding to the tree root $\rho$ . The single offspring of the progenitor is represented in the tree by the vertex connected to the tree root by the stem [Reference Kovchegov and Zaliapin20]. We denote by $\mathcal{GW}(\{q_k\})$ the probability measure on ${\mathcal{T}}^{|}$ induced by the Galton–Watson process with progeny distribution $\{q_k\}$ . Assuming $q_1<1$ , the resulting tree is finite with probability one if and only if $\sum_{k=0}^\infty k q_k\leq 1$ , i.e., the Galton–Watson process is either subcritical or critical. In this paper we let $q_1=0$ so that the Galton–Watson process generates a reduced tree.

For a given probability mass function $\{q_k\}$ with $q_1=0$ and a positive real $\lambda$ , consider a random tree T in ${\mathcal{L}}^|$ satisfying ${\rm{\small SHAPE}}(T) \stackrel{d}{\sim} \mathcal{GW}(\{q_k\})$ , and such that, conditioned on ${\rm{\small SHAPE}}(T)$ , the edge lengths are distributed as independent and identically distributed (i.i.d.) exponential random variables with parameter $\lambda$ . Let $\mathcal{GW}(\{q_k\},\lambda)$ denote the distribution of the random tree T thus defined. Measures $\mathcal{GW}(\{q_k\})$ and $\mathcal{GW}(\{q_k\},\lambda)$ induced by critical (or subcritical) branching processes will be called critical (or subcritical) Galton–Watson measures.

2.3. Invariant Galton–Watson measures

The invariant Galton–Watson measures form a single-parameter family of critical Galton–Watson measures $\mathcal{GW}(\{q_k\})$ with $q_1=0$ on ${\mathcal{T}}^|$ , which we define as follows.

Definition 2.1. (Invariant Galton--Watson measures in ${\mathcal{T}}^|$ ) For a given $q \in [1/2,1)$ , a critical Galton–Watson measure $\mathcal{GW}(\{q_k\})$ on ${\mathcal{T}}^|$ is said to be the invariant Galton–Watson (IGW) measure with parameter q, and denoted by $\mathcal{IGW}(q)$ , if its generating function is given by

(1) \begin{equation}Q(z)=z+q(1-z)^{1/q}.\end{equation}

The respective branching probabilities are $q_0=q$ , $q_1=0$ , $q_2=(1-q)/2q$ , and

(2) \begin{equation}q_k= {1-q \over k!\,q}\, \prod\limits_{i=2}^{k-1}(i-1/q) \quad \text{for } k\geq 3.\end{equation}

Here, if $q=1/2$ , then the distribution is critical binary, i.e., $\mathcal{GW}(q_0\!= q_2\!=\!1/2)$ . If $q \in (1/2,1)$ , the distribution is of Zipf type with

(3) \begin{equation}q_k={(1-q) \Gamma(k-1/q) \over q \Gamma(2-1/q) \,k!} \sim C k^{-(1+q)/q}, \,\text{ where }\,C={1-q \over q\,\Gamma(2-1/q)}.\end{equation}

We notice that

\begin{equation*}Q^{\prime}(z) = 1-(1-z)^{1/q-1},\quad Q^{\prime\prime}(z) = (1-z)^{1/q-2},\end{equation*}

which implies that $Q^{\prime}(1)=1$ , that is, the IGW processes are critical, and $Q^{\prime\prime}(1)<\infty$ , that is, the offspring distribution’s second moment is finite, if and only if $q=1/2$ .

These tree measures (Definition 2.1) are also known as stable Galton–Watson trees or Galton–Watson trees with stable offspring distribution [Reference Duquesne and Winkel9]. They have previously been considered in the work of Zolotarev [Reference Zolotarev32], Neveu [Reference Neveu25], Le Jan [Reference Le Jan23], Duquesne and Le Gall [Reference Duquesne and Le Gall7], Abraham and Delmas [Reference Abraham and Delmas1], and Duquesne and Winkel [Reference Duquesne and Winkel9]. Moreover, in [Reference Neveu25], Neveu regards the generating functions (1) to be the most important in the critical case.

The definition of the IGW measure can be extended to ${\mathcal{L}}^|$ by assigning i.i.d. exponentially distributed edge lengths.

Definition 2.2. (Invariant Galton--Watson measures in ${\mathcal{L}}^|$ ) For a given $q \in [1/2,1)$ and $\lambda>0$ , a random tree T in ${\mathcal{L}}^|$ is said to be an exponential invariant Galton–Watson tree if it satisfies the following properties:

  1. (i) ${\rm{\small SHAPE}}(T) \stackrel{d}{\sim} \mathcal{IGW}(q)$ ;

  2. (ii) conditioned on ${\rm{\small SHAPE}}(T)$ , the edge lengths are distributed as i.i.d. exponential random variables with parameter $\lambda>0$ .

Such a tree is denoted by $\mathcal{IGW}(q,\lambda)$ . In other words, $T\stackrel{d}{\sim}\mathcal{GW}(\{q_k\},\lambda)$ with $q_k$ as in (2).

2.4. Invariance and attractor properties of IGW family under Horton pruning

Horton pruning of a tree T (in ${\mathcal{T}}$ or ${\mathcal{L}}$ ) is done by removing all the leaves of T (leaf vertices together with the corresponding adjacent edges) followed by consecutive series reduction (removing degree-two vertices by merging adjacent edges into one and adding up their lengths for a tree in ${\mathcal{L}}$ ). The resulting reduced tree is denoted by ${\mathcal{R}}(T)$ . We refer to [Reference Kovchegov and Zaliapin20] for a detailed treatment of Horton pruning. The Horton pruning operator ${\mathcal{R}}$ induces a map on ${\mathcal{T}}$ (or ${\mathcal{L}}$ ). The trajectory of each tree T under iterative application of ${\mathcal{R}}$ , i.e.,

(4) \begin{equation}T\equiv{\mathcal{R}}^0(T)\to {\mathcal{R}}^1(T) \to\dots\to{\mathcal{R}}^k(T)=\phi,\end{equation}

is uniquely defined and finite with the empty tree $\phi$ as the (only) fixed point. In [Reference Kovchegov and Zaliapin19], it was established that, under iterative Horton pruning, the $\mathcal{IGW}(q)$ measures are the attractors of all critical Galton–Watson trees that satisfy the following regularity assumption.

Assumption 2.1. Consider a critical Galton–Watson measure $\mathcal{GW}(\{q_k\})$ with $q_1=0$ and the respective progeny generating function Q(z). We assume that the following limit exists:

(5) \begin{equation}\lim\limits_{x \rightarrow 1-}{Q(x)-x \over (1-x)\big(1-Q^{\prime}(x)\big)}.\end{equation}

We will use function g(x) defined in the following proposition from [Reference Kovchegov and Zaliapin19].

Proposition 2.1. ([Reference Kovchegov and Zaliapin21].) Consider a critical Galton–Watson measure $\mathcal{GW}(\{q_k\})$ with $q_1=0$ and the respective progeny generating function Q(z). Then

\begin{equation*}Q(x)-x=(1-x)^2 g(x),\end{equation*}

where g(x) is defined as follows. Let $X \stackrel{d}{\sim} \{q_k\}$ be a progeny random variable; then

(6) \begin{equation}g(x)=\sum\limits_{m=0}^\infty {\mathbb{E}} \big[(X-m-1)_+\big] \, x^m \,=\sum\limits_{m=0}^\infty \sum\limits_{k=m+1}^\infty (k-m-1)q_k \,x^m,\end{equation}

where $\,x_+=\max\{x,0\}$ .

An important limit is defined in the following lemma.

Lemma 2.1. ([Reference Kovchegov and Zaliapin21].) Consider a critical Galton–Watson measure $\mathcal{GW}(\{q_k\})$ with $q_1=0$ . If Assumption 2.1 is satisfied, then for g(x) defined in (6) the limit

(7) \begin{equation}\lim\limits_{x \rightarrow 1-}\left({\ln{g(x)} \over -\ln(1-x)}\right)=L\end{equation}

exists, and

\begin{equation*}\lim\limits_{x \rightarrow 1-}{Q(x)-x \over (1-x)(1-Q^{\prime}(x))}={1 \over 2-L}.\end{equation*}

The following three results (Lemmas 2.2, 2.3, and 2.4) concerning the applicability of Assumption 2.1 and the limit L in (7) were established in [Reference Kovchegov and Zaliapin21].

Lemma 2.2. ([Reference Kovchegov and Zaliapin21].) Consider a critical Galton–Watson measure $\mathcal{GW}(\{q_k\})$ with $q_1=0$ . For a progeny variable $X \stackrel{d}{\sim} \{q_k\}$ and g(x) in (6), if

(8) \begin{equation}{\mathbb{E}}[X^{2-\epsilon}]=\sum \limits_{k=0}^\infty k^{2-\epsilon}q_k \,<\infty \qquad \forall \epsilon>0,\end{equation}

then $L=\lim\limits_{x \rightarrow 1-}\left({\ln{g(x)} \over -\ln(1-x)}\right)=0$ . If moreover the second moment is finite, i.e.,

\begin{equation*}{\mathbb{E}}[X^2]=\sum \limits_{k=0}^\infty k^2q_k <\infty,\end{equation*}

then Assumption 2.1 is satisfied with $\, \lim\limits_{x \rightarrow 1-}{Q(x)-x \over (1-x)(1-Q^{\prime}(x))}={1 \over 2}$ .

The next lemma provides a basic regularity condition for Assumption 2.1 to hold.

Lemma 2.3. (Regularity condition [Reference Kovchegov and Zaliapin21].) Consider a critical Galton–Watson measure $\mathcal{GW}(\{q_k\})$ with $q_1=0$ and infinite second moment, i.e., $\sum\limits_{k=0}^\infty k^2 q_k =\infty$ . Suppose that for the progeny variable $X \stackrel{d}{\sim} \{q_k\}$ the following limit exists:

(9) \begin{equation}\Lambda=\lim\limits_{k \rightarrow \infty}{k \over {\mathbb{E}}[X\,|\,X\geq k]}=\lim\limits_{k \rightarrow\infty}{ k\sum\limits_{m=k}^\infty \!q_m \over \sum\limits_{m=k}^\infty \! mq_m}.\end{equation}

Then Assumption 2.1 is satisfied with $\, \lim\limits_{x \rightarrow 1-}{Q(x)-x \over (1-x)(1-Q^{\prime}(x))}=1-\Lambda \,$ and $\,L=2+{1 \over 1-\Lambda}$ .

The next lemma follows immediately from Lemma 2.3.

Lemma 2.4. (Zipf distribution [Reference Kovchegov and Zaliapin21].) Consider a critical Galton–Watson process $\mathcal{GW}(\{q_k\})$ with $q_1=0$ and offspring distribution $\{q_k\}$ of Zipf type:

(10) \begin{equation}q_k \sim Ck^{-(\alpha+1)} \quad \text{ with } \alpha \in (1,2] \text{ and } C>0.\end{equation}

Then Assumption 2.1 is satisfied, and

(11) \begin{equation}L=\lim\limits_{x \rightarrow 1-}\left({\ln{g(x)} \over -\ln(1-x)}\right)=2-\alpha.\end{equation}

In Sections 3.2 and 3.3 of this paper we consider generalizations of the following two theorems, which were proved in [Reference Kovchegov and Zaliapin21].

Theorem 2.1. (Self-similarity under Horton pruning [Reference Kovchegov and Zaliapin21].) Consider a critical or subcritical Galton–Watson measure $\mu \equiv \mathcal{GW}(\{q_k\})$ with $q_1=0$ that satisfies Assumption 2.1. Then a Galton–Watson measure $\mu$ is Horton-prune-invariant (self-similar), i.e., the pushforward measure $\nu(T)=\mu \circ {\mathcal{R}}^{-1}(T) = \mu \big({\mathcal{R}}^{-1}(T)\big)$ satisfies $\,\nu\left(T\,|T\ne\phi\right)=\mu(T)$ , if and only if $\mu$ is the IGW measure $\mathcal{IGW}(q)$ with $q\in[1/2,1)$ .

Theorem 2.2. (IGW attractors under iterative Horton pruning [Reference Kovchegov and Zaliapin21].) Consider a critical Galton–Watson measure $\rho_0 \equiv\mathcal{GW}(\{q_k\})$ with $q_1=0$ on ${\mathcal{T}}^|$ . Starting with $k=0$ , and for each consecutive integer, let $\nu_k={\mathcal{R}}_*(\rho_k)$ denote the pushforward probability measure induced by the pruning operator, i.e., $\nu_k(T)=\rho_k \circ {\mathcal{R}}^{-1}(T) = \rho_k \big({\mathcal{R}}^{-1}(T)\big)$ , and set $\rho_{k+1}(T)=\nu_k\left(T |T\ne\phi\right)$ . Suppose Assumption 2.1 is satisfied. Then, for any $T\in{\mathcal{T}}^|$ ,

\begin{equation*}\lim_{k\to\infty}\rho_k(T)=\rho^*(T),\end{equation*}

where $\rho^*$ denotes the IGW measure $\mathcal{IGW}(q)$ with $q={1 \over 2-L}$ and L as defined in (7).

Finally, if the Galton–Watson measure $\rho_0 \equiv\mathcal{GW}(\{q_k\})$ is subcritical, then $\rho_k(T)$ converges to a point mass measure, $\mathcal{GW}(q_0\!=\!1)$ .

2.5. Generalized dynamical pruning

Given a metric tree $T=(S,d) \in {\mathcal{L}}$ and a point $x \in S$ , let $\Delta_{x,T}$ be the descendant tree of x: the tree comprising all points of T descendant to x, including x. Then $\Delta_{x,T}$ is itself a tree in ${\mathcal{L}}$ with the root at x.

Let $T_1=(S_1,d_1)$ and $T_2=(S_2,d_2)$ be two metric rooted trees, and let $\rho_1$ denote the root of $T_1$ . A function $f\,:\,T_1 \rightarrow T_2$ is said to be an isometry if ${\sf Image}[f] \subseteq \Delta_{f(\rho_1),T_2}$ and for all pairs $x,y \in T_1$ ,

\begin{equation*}d_2\big(f(x),f(y)\big)=d_1(x,y).\end{equation*}

We use the above-defined notion of isometry to define a partial order in the space ${\mathcal{L}}$ as follows. We say that $T_1$ is less than or equal to $T_2$ , and write $T_1\preceq T_2$ , if there is an isometry $f\,:\,T_1 \rightarrow T_2$ . The relation $\preceq$ is a partial order as it satisfies the reflexivity, antisymmetry, and transitivity conditions. We say that a function $\varphi\,:\,{\mathcal{L}} \rightarrow \mathbb{R}$ is monotone nondecreasing with respect to the partial order $\preceq $ if $\varphi(T_1) \leq \varphi(T_2)$ whenever $T_1 \preceq T_2.$

Next, we recall the definition of the generalized dynamical pruning as stated in [Reference Kovchegov and Zaliapin19, Reference Kovchegov and Zaliapin20]. Consider a monotone nondecreasing function $\varphi\,:\,{\mathcal{L}} \rightarrow \mathbb{R}_+$ with respect to the above-defined partial order $\preceq$ . We define the generalized dynamical pruning operator $\mathcal{S}_t(\varphi,T)\,:\,{\mathcal{L}}\rightarrow{\mathcal{L}}$ induced by $\varphi$ for any given time parameter $t\ge 0$ as

(12) \begin{equation}\mathcal{S}_t(\varphi,T)\,:\!=\,\{\rho\}\cup\Big\{x \in T\setminus\rho \,:\, \varphi\big(\Delta_{x,T}\big)\geq t \Big\},\end{equation}

where $\rho$ denotes the root of the tree T. Informally, the operator $\mathcal{S}_t$ cuts all subtrees $\Delta_{x,T}$ for which the value of $\varphi$ is below the threshold t, and always keeps the tree root.

Below we discuss some well-studied examples of generalized dynamical pruning.

Example 2.1. (Pruning via the Horton--Strahler order) The Horton–Strahler order [Reference Burd, Waymire and Winn5, Reference Kovchegov and Zaliapin17, Reference Kovchegov and Zaliapin20, Reference Peckham29] was initially introduced in the context of geomorphology. It can be defined via the operation of Horton pruning ${\mathcal{R}}$ . The Horton–Strahler order ${\sf ord}(T)$ of a planted tree from ${\mathcal{L}}^|$ (or ${\mathcal{T}}^|$ ) is the minimal number of prunings necessary to eliminate a tree T. The Horton–Strahler order ${\sf ord}(T)$ of a stemless tree from ${\mathcal{L}}^\vee$ (or ${\mathcal{T}}^\vee$ ) equals one plus the minimal number of prunings necessary to eliminate a tree T. For a tree T in either ${\mathcal{T}}$ or ${\mathcal{L}}$ , consider

(13) \begin{equation}\varphi(T) = {\sf ord}(T)-1.\end{equation}

For $k \in \mathbb{N}$ , let $\,{\mathcal{R}}^k\,$ denote the kth iteration of Horton pruning ${\mathcal{R}}$ , i.e., $\,{\mathcal{R}}^0(T)=T$ and $\,{\mathcal{R}}^k= \underbrace{{\mathcal{R}} \circ \dots \circ {\mathcal{R}}}_{k \text{ times}}$ . With the function $\varphi$ as in (13), the generalized dynamical pruning operator $\mathcal{S}_t={\mathcal{R}}^{\lfloor t \rfloor}$ satisfies the discrete semigroup property [Reference Kovchegov and Zaliapin19, Reference Kovchegov and Zaliapin20]:

\begin{equation*}{\mathcal{S}}_t\circ{\mathcal{S}}_s={\mathcal{S}}_{t+s} \text{ for any } t,s\in \mathbb{N}_0,\end{equation*}

as $\, {{\mathcal{R}}}^t \circ {{\mathcal{R}}}^s ={{\mathcal{R}}}^{t+s}$ . A recent survey of results related to invariance of a tree distribution with respect to Horton pruning is given in [Reference Kovchegov and Zaliapin20].

Example 2.2. (Pruning via the tree height) If we let the $\varphi(T)$ be the height function, i.e., for a tree $T \in{\mathcal{L}}$ , let

(14) \begin{equation}\varphi(T) = {\rm{\small HEIGHT}}(T),\end{equation}

then the generalized dynamical pruning $\mathcal{S}_t({\cdot})=\mathcal{S}_t(\varphi,\cdot)$ will coincide with the continuous pruning (leaf-length erasure) studied in Neveu [Reference Neveu25], which established the invariance of critical binary Galton–Watson measures with i.i.d. exponential edge lengths with respect to this operation. In this case the operator $\mathcal{S}_t$ is known to satisfy the continuous semigroup property [Reference Duquesne and Winkel9, Reference Kovchegov and Zaliapin19, Reference Neveu25]:

\begin{equation*}{\mathcal{S}}_t\circ{\mathcal{S}}_s={\mathcal{S}}_{t+s} \text{ for any } t,s\ge 0.\end{equation*}

Example 2.3. (Pruning via the tree length) Let the function $\varphi(T)$ equal the total length of $T\in{\mathcal{L}}$ :

(15) \begin{equation}\varphi(T) = {\rm{\small LENGTH}}(T).\end{equation}

The pruning operator $\mathcal{S}_t({\cdot})=\mathcal{S}_t(\varphi,\cdot)$ with the pruning function $\varphi$ as in (15) coincides with the potential dynamics of the continuum mechanics formulation of the one-dimensional ballistic annihilation model $A+A \rightarrow \varnothing$ [Reference Kovchegov and Zaliapin19]. Importantly, the operator $\mathcal{S}_t$ induced by the length function $\varphi$ as in (15) does not satisfy the semigroup property (discrete or continuous); i.e., $\,{\mathcal{S}}_t\circ{\mathcal{S}}_s \not={\mathcal{S}}_{t+s}$ [Reference Kovchegov and Zaliapin19].

Example 2.4. (Pruning via the number of leaves) Let ${\rm{\small LEAVES}}(T)$ denote the number of leaves in a tree T. Then

(16) \begin{equation}\varphi(T) = {\rm{\small LEAVES}}(T)\end{equation}

is another monotone nondecreasing function. The generalized dynamical pruning operator $\mathcal{S}_t({\cdot})=\mathcal{S}_t(\varphi,\cdot)$ induced by $\varphi$ as in (16) does not satisfy the semigroup property, whether discrete or continuous. This type of pruning naturally arises in the context of Shreve stream ordering in hydrodynamics.

2.6. Generalized dynamical pruning as a hereditary reduction

Duquesne and Winkel [Reference Duquesne and Winkel9] introduced a very general kind of tree reduction in the context of complete locally compact rooted (CLCR) real trees, which include all the trees in ${\mathcal{L}}$ . In [Reference Duquesne and Winkel9], a hereditary property A is defined as a Borel subset in the space $\mathbb{T}$ of CLCR real trees (more precisely, their equivalence classes under isometry) equipped with the pointed Gromov–Hausdorff metric such that for a CLCR real tree $T \in \mathbb{T}$ and any $x\in T$ ,

\begin{equation*}\Delta_{x,T} \in A \quad \Rightarrow \quad T=\Delta_{\rho,T} \in A.\end{equation*}

As an example of a hereditary property, one may consider $A=\{T \in \mathbb{T} \,:\, {\rm{\small HEIGHT}}(T)\geq t\}$ .

A hereditary property $A \subset \mathbb{T}$ induces a hereditary reduction operator $R_A\,:\,\mathbb{T} \to \mathbb{T}$ defined as

(17) \begin{equation}R_A(T)\,:\!=\,\{\rho\}\cup\big\{x \in T\setminus\rho \,:\, \Delta_{x,T} \in A \big\}.\end{equation}

The following result was proved in [Reference Duquesne and Winkel9, Theorem 2.18].

Theorem 2.3. (Evolution of Galton--Watson trees under hereditary reduction [Reference Duquesne and Winkel9].) Consider a critical or subcritical Galton–Watson measure $\mu\equiv\mathcal{GW}(\{q_k\},\lambda)$ ( $q_1=0$ ) on ${\mathcal{L}}^|$ with generating function Q(z). For a hereditary property $A \subset \mathbb{T}$ , let $\nu$ denote the corresponding pushforward probability measure induced by the hereditary reduction $R_A$ :

\begin{equation*}\nu(T)=\mu \circ R_A^{-1}(T) = \mu \big(R_A^{-1}(T)\big).\end{equation*}

Then $\nu\big(T \in \cdot \,|R_A(T)\not= \phi\big)\stackrel{d}{=}\mathcal{GW}\left(\{g_k\},\, \lambda \big(1-Q^{\prime}(1-p)\big)\right)$ is a Galton–Watson tree measure over ${\mathcal{L}}^|$ with independent exponential edge lengths with parameter $\lambda \big(1-Q^{\prime}(1-p)\big)$ , and generating function

(18) \begin{equation}G(z)=z+ {Q\big((1-p)+pz\big)-(1-p) -pz \over p\big(1-Q^{\prime}(1-p)\big)},\end{equation}

where $\,p=\mathbb{P}\big(R_A(T)\not= \phi\big)$ .

Observe the following direct link between the operations of generalized dynamical pruning and hereditary reduction. Consider a Borel measurable monotone nondecreasing function $\varphi\,:\,{\mathcal{L}} \rightarrow \mathbb{R}_+$ . Then, for a fixed $t \geq 0$ , the Borel set

(19) \begin{equation}A=\{T \in \mathbb{T} \,:\, \varphi(T)\geq t\}\end{equation}

is a hereditary property, and therefore $\,\mathcal{S}_t(\varphi,T)=R_A(T)\,$ is a hereditary reduction.

The composition of two hereditary properties A and A was defined in [Reference Duquesne and Winkel9, Definition 2.12] as the set

\begin{equation*}A^{\prime} \circ A=\{T \in \mathbb{T} \,:\, R_A(T)\in A^{\prime} \}.\end{equation*}

Consequently, in Lemma 2.13 of [Reference Duquesne and Winkel9], the hereditary reductions were shown to satisfy the composition property, $\,R_{A^{\prime} \circ A}=R_{A^{\prime}} \circ R_A$ . Importantly, if we let $A_t$ denote the hereditary property in (19), then

\begin{equation*}A_t \circ A_s \not= A_{s+t}\end{equation*}

for many (or rather, all but a few) functions $\varphi$ , e.g. for $\varphi(T)={\rm{\small LENGTH}}(T)$ . Speaking of the exceptions, the equation $A_t \circ A_s = A_{s+t}$ is known to hold for $\varphi(T)={\rm{\small HEIGHT}}(T)$ with real $s,t \in [0,\infty)$ , corresponding to Neveu (leaf-length) erasure as in Example 2.2, and for $\varphi(T)={\sf ord}(T)-1$ with integer $s,t \in \mathbb{Z}_+$ , corresponding to Horton pruning as in Example 2.1.

We will need the following adaptation of Theorem 2.3 for generalized dynamical pruning.

Lemma 2.5. (Pruning Galton--Watson trees) Consider a critical or subcritical Galton–Watson measure $\mu\equiv\mathcal{GW}(\{q_k\},\lambda)$ ( $q_1=0$ ) on ${\mathcal{L}}^|$ with generating function Q(z). For a monotone nondecreasing function $\varphi\,:\,{\mathcal{L}} \rightarrow \mathbb{R}_+$ , let $\nu$ denote the corresponding pushforward probability measure induced by the pruning operator $\mathcal{S}_t(T)=\mathcal{S}_t(\varphi,T)$ :

\begin{equation*}\nu(T)=\mu \circ \mathcal{S}_t^{-1}(T) = \mu \big(\mathcal{S}_t^{-1}(T)\big).\end{equation*}

Then $\nu\big(T \in \cdot \,|T\not= \phi\big)\stackrel{d}{=}\mathcal{GW}\left(\{g_k\},\, \lambda \big(1-Q^{\prime}(1-p_t)\big)\right)$ is a Galton–Watson tree measure over ${\mathcal{L}}^|$ with independent exponential edge lengths with parameter $\lambda \big(1-Q^{\prime}(1-p_t)\big)$ , offspring probabilities

(20) \begin{align}g_0 & = {Q(1-p_t)-(1-p_t) \over p_t\big(1-Q^{\prime}(1-p_t)\big)},\quad g_1=0,\nonumber\\g_m & = {p_t^{m-1} \over m!} Q^{(m)}\!(1-p_t) \,(1-Q^{\prime}(1-p_t))^{-1} \quad (m \geq 2),\end{align}

where $\,p_t=p_t(\lambda,\varphi)=\mathbb{P}\big({\mathcal{S}}_t(\varphi,T) \not= \phi\big)$ , and generating function

(21) \begin{align}G(z)=z+ {Q\big((1-p_t)+p_t z\big)-(1-p_t) -p_t z \over p_t\big(1-Q^{\prime}(1-p_t)\big)}.\end{align}

Moreover, if $\mu(T\in \cdot)$ is critical, then so is $\nu\big(T \in \cdot \,\big|\,T\not= \phi\big)$ .

An alternative proof of Lemma 2.5 can be found in Appendix C. Since Lemma 2.5 deals with the finite-leaf trees $({\rm{\small LEAVES}}(T)<\infty$ ), for this lemma and its proof, as well as the whole set-up of generalized dynamical pruning, we do not need to introduce the Gromov–Hausdorff metric and to require the function $\varphi\,:\,{\mathcal{L}} \rightarrow \mathbb{R}_+$ to be Borel measurable.

2.7. Bernoulli leaf coloring

Duquesne and Winkel considered the following type of tree reduction in [Reference Duquesne and Winkel8]. Fix a probability $p \in [0, 1)$ . For a finite tree $T \in {\mathcal{T}}^|$ (or ${\mathcal{L}}^|$ ), select a subset of its leaves via performing ${\rm{\small LEAVES}}(T)$ independent Bernoulli trials, where each leaf is independently selected in with probability $1-p$ . Let $\mathcal{C}_p(T)$ be the minimal subtree of T that contains all selected leaves and the root $\rho$ . If T is a random tree, then so is $\mathcal{C}_p(T)$ . Notice that $\mathcal{C}_p$ is a random operator induced by a countable sequence of independent Bernoulli random variables.

Theorem 2.4. (Evolution of Galton--Watson trees under Bernoulli leaf coloring [Reference Duquesne and Winkel8].) Consider a critical or subcritical Galton–Watson measure $\mu\equiv\mathcal{GW}(\{q_k\})$ ( $q_1=0$ ) on ${\mathcal{T}}^|$ with generating function Q(z). Then, for a given $p \in [0, 1)$ , $\,\mu\big(\mathcal{C}_p(T) \in \cdot \,|\,\mathcal{C}_p(T)\not= \phi\big)\,$ is a Galton–Watson tree measure over ${\mathcal{T}}^|$ with the generating function

(22) \begin{equation}G_p(z)=z+ {Q\big((1-p)+g_pz\big)-(1-g_p) -g_pz \over g_p\big(1-Q^{\prime}(1-g_p)\big)},\end{equation}

where $\,g_p=\mathbb{P}\big(\mathcal{C}_p(T)\not= \phi\big)$ .

Theorem 2.4 readily implies that the IGW trees are invariant with respect to Bernoulli leaf coloring.

3. Results

3.1. Metric properties of invariant Galton–Watson trees

Here we derive explicit formulas for selected metric properties of $\mathcal{IGW}(q)$ and $\mathcal{IGW}(q,\lambda)$ trees in the respective spaces ${\mathcal{T}}^|$ and ${\mathcal{L}}^|$ . This includes the distributions of the tree height (Theorem 3.1), the tree length (Theorem 3.2), and the tree size (number of edges) (Theorem 3.3), as well as the tail asymptotics for the distributions of the tree length (Proposition 3.1) and tree size (Proposition 3.2). The proofs are collected in Section 4.1.

Theorem 3.1. (Tree height distribution.) Let $T\in{\mathcal{L}}^|$ be an IGW tree with parameters $q \in [1/2,1)$ and $\lambda>0$ , i.e., $T\stackrel{d}{\sim}\mathcal{IGW}(q,\lambda)$ . Then the height of the tree T has the cumulative distribution function

\begin{equation*}H(x)=\mathbb{P}\big({\rm{\small HEIGHT}}(T) \leq x\big)=1-\big(\lambda(1-q) x+1\big)^{-q/(1-q)}, \qquad x\geq 0.\end{equation*}

Notice that for the case $q=1/2$ , we have $H(x)={\lambda x \over \lambda x +2}$ , which matches the result in [Reference Kovchegov and Zaliapin20].

Theorem 3.2. (Tree length distribution.) Let $T\in{\mathcal{L}}^|$ be an IGW tree with parameters $q \in [1/2,1)$ and $\lambda>0$ , i.e., $T\stackrel{d}{\sim}\mathcal{IGW}(q,\lambda)$ . Then the length of the tree T has the probability density function

(23) \begin{equation}\ell(x)=\sum_{n=1}^{\infty}({-}1)^{n-1}\frac{\Gamma(n/q+1)}{n!\,(n-1)!\,\Gamma(n/q-n+2)}(\lambda q)^n x^{n-1}, \qquad x\geq 0,\end{equation}

and the cumulative distribution function

(24) \begin{equation}L(x)=\mathbb{P}\big({\rm{\small LENGTH}}(T) \leq x\big)=\sum_{n=1}^{\infty}({-}1)^{n-1}\frac{\Gamma(n/q+1)}{n!\,n!\,\Gamma(n/q-n+2)}(\lambda q)^n x^n, \qquad x\geq 0.\end{equation}

Example 3.1. Let $q={1 \over 2}$ . Then $\ell(x)$ is already known (see [Reference Kovchegov and Zaliapin19, Reference Kovchegov and Zaliapin20]):

(25) \begin{equation}\ell(x)=\frac{1}{x}e^{-\lambda x}I_1(\lambda x)=\sum_{n=0}^{\infty}\frac{\lambda^{2n+1}x^{2n}e^{-\lambda x}}{2^{2n+1} \, (n+1)! \, n!}.\end{equation}

Next, we use the multinomial approach to show that (25) matches Equation (23) for $q={1 \over 2}$ . First, we rewrite (25):

(26) \begin{align}\ell(x)&=e^{-\lambda x}\sum_{n=0}^{\infty}\frac{\lambda^{2n+1}}{2^{2n+1}\,(n+1)!\,n!}x^{2n}\nonumber\\&=\sum_{k=0}^{\infty}\frac{({-}\lambda)^k}{k!}x^k\sum_{n=0}^{\infty}\frac{\lambda^{2n+1}}{2^{2n+1}\,(n+1)! \, n!}x^{2n} \nonumber \\&=\sum\limits_{m=0}^\infty \left(\sum\limits_{k+2n=m}{({-}1)^k 2^{-2n-1} \over k!\,(n+1)! \, n!} \right)\lambda^{m+1} x^m\nonumber\\&=\sum\limits_{m=0}^\infty \left(\sum\limits_{k+2n=m}{({-}2)^k\over k!\, (n+1)! \, n!} \right){\lambda^{m+1} x^m \over 2^{m+1}}.\end{align}

Recall that

\begin{equation*}\big(z+z^{-1}+a\big)^{m+1}=\sum\limits_{n+k+j=m+1} {(m+1)! \over n!\, k! \,j!} z^n z^{-j} a^k,\end{equation*}

and

\begin{equation*}\frac{1}{2\pi i}\oint_{|z|=1} z^{n-j}dz = \delta_{j,n+1},\end{equation*}

and therefore

\begin{eqnarray*}{{1 \over 2\pi i}\oint\limits_{|z|=1}\big(z+z^{-1}+a\big)^m \,dz}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\\&=&\sum\limits_{n+k+j=m+1} {(m+1)! \over n!\,k!\,j!}a^k {1 \over 2\pi i}\oint\limits_{|z|=1} z^{n-j} \,dz\\&=&\sum\limits_{k+2n=m} {(m+1)! \over n!\, (n+1)!\,k!}a^k,\end{eqnarray*}

implying

\begin{equation*}\sum\limits_{k+2n=m} {1\over n!\, (n+1)!\, k!}a^k={1 \over 2\pi i (m+1)! }\oint\limits_{|z|=1}\big(z+z^{-1}+a\big)^{m+1} \,dz.\end{equation*}

Now,

\begin{eqnarray*}{{1 \over 2\pi i}\oint\limits_{|z|=1}\big(z+z^{-1}-2\big)^{m+1} \,dz}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\\&=&{1 \over 2\pi i}\oint\limits_{|z|=1}{(z-1)^{2m+2} \over z^{m+1}} \,dz\\&=&{1 \over 2\pi i}\oint\limits_{|z|=1}\sum\limits_{j=0}^{2m+2}\left(\begin{array}{c}2m+2\\j\end{array}\right)({-}1)^j z^{j-m-1} \,dz\\&=&({-}1)^m \left(\begin{array}{c}2m+2\\m\end{array}\right).\end{eqnarray*}

Hence,

(27) \begin{eqnarray}\sum\limits_{k+2n=m}{({-}2)^k \over k!\, (n+1)!\, n!}&=&{1 \over (m+1)! }\,{1 \over 2\pi i}\oint\limits_{|z|=1}\big(z+z^{-1}-2\big)^{m+1} \,dz\nonumber\\&=&({-}1)^m{1 \over (m+1)!}\left(\begin{array}{c}2m+2\\m\end{array}\right).\end{eqnarray}

Thus, substituting (27) into (26), we obtain

\begin{eqnarray*}\ell(x)&=&\sum\limits_{m=0}^\infty ({-}1)^m{1 \over (m+1)!}\left(\begin{array}{c}2m+2\\m\end{array}\right){\lambda^{m+1} x^m \over 2^{m+1}}\\&=&\sum\limits_{m=0}^\infty ({-}1)^m{(2m+2)! \over (m+1)! \,m! \,(m+2)!}(\lambda q)^{m+1} x^m\\&=&\sum\limits_{m=0}^\infty ({-}1)^m{\Gamma\big((m+1)/q+1\big) \over (m+1)! \,m! \, \Gamma\big((m+1)/q - m+1)}(\lambda q)^{m+1} x^m\end{eqnarray*}

for $q={1 \over 2}$ , as in Equation (23) from Theorem 3.2.

The following proposition is needed because computing the cumulative distribution function L(x) in (24) becomes difficult (even numerically) for all values of $q \not={1 \over 2}$ , i.e., for $q \in (1/2,1)$ .

Proposition 3.1. (Tail of the tree length distribution.) Let $T\stackrel{d}{\sim}\mathcal{IGW}(q,\lambda)$ be an IGW tree in ${\mathcal{L}}^|$ with parameters $q \in [1/2,1)$ and $\lambda>0$ . Then the cumulative distribution function L(x) in (24) satisfies

(28) \begin{equation}1-L(x) \sim {1 \over (\lambda q)^q \,\Gamma(1-q)} x^{-q}.\end{equation}

Example 3.2. For $q={1 \over 2}$ , L(x) is expressed as follows [Reference Kovchegov and Zaliapin19, Reference Kovchegov and Zaliapin20]:

\begin{equation*}L(x)=1-e^{-\lambda x}\big(I_0(\lambda x)+I_1(\lambda x)\big).\end{equation*}

Thus, since $I_a(z) \sim {1 \over \sqrt{2\pi z}}e^z$ for all $a \geq 0$ , we have

\begin{equation*}1-L(x)=e^{-\lambda x}\big(I_0(\lambda x)+I_1(\lambda x)\big) \sim \sqrt{2 \over \lambda \pi}x^{-1/2}={1 \over (\lambda q)^q \,\Gamma(1-q)}x^{-q}\quad \text{ for }\,q={1 \over 2}\end{equation*}

as $\,\Gamma(1/2)=\sqrt{\pi}$ . This matches the general case in Proposition 3.1.

The following is a discrete analogue of Theorem 3.2.

Theorem 3.3. (Tree size distribution.) Let $T\in{\mathcal{T}}^|$ be an IGW tree with parameters $q \in [1/2,1)$ , i.e., $T\stackrel{d}{\sim}\mathcal{IGW}(q)$ . Then the number of edges in T is distributed with the probability mass function

(29) \begin{equation}\alpha(n)=\sum\limits_{k=1}^n ({-}1)^{k-1} \left(\begin{array}{c}n-1\\k-1\end{array}\right){\Gamma(k/q+1) \over k!\,\Gamma(k/q -k+2)}\,q^k \qquad \text{ for } n=1,2,\dots,\end{equation}

with the cumulative distribution function

(30) \begin{equation}\mathcal{A}(x)=\sum\limits_{k=1}^{\lfloor x \rfloor} ({-}1)^{k-1} \left(\begin{array}{c}\lfloor x \rfloor\\k\end{array}\right){\Gamma(k/q+1) \over k!\,\Gamma(k/q -k+2)}\,q^k, \qquad x \geq 1.\end{equation}

The next proposition is analogous to Proposition 3.1 and has a similar proof. It gives an estimate on the tail distribution $1-\mathcal{A}(x)$ .

Proposition 3.2. (Tail of the tree size distribution.) Let $T\stackrel{d}{\sim}\mathcal{IGW}(q)$ be an IGW tree in ${\mathcal{T}}^|$ with parameters $q \in [1/2,1)$ . Then the cumulative distribution function $\mathcal{A}(x)$ in (30) satisfies

(31) \begin{equation}1-\mathcal{A}(x) \sim {1 \over q^q \,\Gamma(1-q)} x^{-q}.\end{equation}

3.2. Invariance under generalized dynamical pruning

Here we consider invariance (Proposition 3.3) and uniqueness (Lemma 3.1) properties of $\mathcal{IGW}(q,\lambda)$ measures under generalized dynamical prunings. Although both Proposition 3.3 and Lemma 3.1 follow immediately from the results of Duquesne and Winkel [Reference Duquesne and Winkel9, Section 3.2.1], alternative proofs of these statements that do not rely on a real tree setting are presented in Section 4.2.

We say that a Galton–Watson tree measure $\mu$ is invariant under the operation of pruning $\mathcal{S}_t({\cdot})=\mathcal{S}_t(\varphi,\cdot)$ if for $\,T \stackrel{d}{\sim} \mu$ ,

\begin{equation*}\mathbb{P}\big({\rm{\small SHAPE}}(\mathcal{S}_t(T))=\tau \,\big|\,\mathcal{S}_t(T)\not=\phi \big)=\mu\big({\rm{\small SHAPE}}(T)=\tau\big), \qquad \text{ for all }\, \tau \in {\mathcal{T}}^|.\end{equation*}

Proposition 3.3. (Invariance with respect to generalized dynamical pruning.) Let $T\stackrel{d}{\sim}\mathcal{IGW}(q,\lambda)$ be an IGW tree with parameters $q \in [1/2,1)$ and $\lambda>0$ . Then, for any monotone nondecreasing function $\varphi\,:\,{\mathcal{L}}^|\rightarrow\mathbb{R}_+$ and any $t>0$ , we have

\begin{equation*}T^t\,:\!=\,\{{\mathcal{S}}_t(\varphi,T)|{\mathcal{S}}_t(\varphi,T) \not= \phi\} \stackrel{d}{\sim}\mathcal{IGW}\left(q,\,{\mathcal{E}} _t(\lambda)\right),\end{equation*}

where ${\mathcal{E}} _t(\lambda)=\lambda p_t^{(1-q)/q}$ and $p_t=p_t(\lambda,\varphi)=\mathbb{P}({\mathcal{S}}_t(\varphi,T) \not= \phi)$ .

In other words, Proposition 3.3 yields the invariance of an $\mathcal{IGW}(q,\lambda)$ measure under generalized dynamical prunings $\mathcal{S}_t$ . For $\varphi(T) = {\sf ord}(T)-1$ , Proposition 3.3 yields the ‘if’ part of Theorem 2.1. Next, we formulate the following uniqueness result.

Lemma 3.1. (Uniqueness of IGW measures.) Consider a critical Galton–Watson tree measure $\mu\equiv\mathcal{GW}(\{q_k\},\lambda)$ ( $q_1=0$ ) on ${\mathcal{L}}^|$ , and let $T\stackrel{d}{\sim} \mu$ . Let $\varphi\,:\,{\mathcal{L}} \rightarrow \mathbb{R}_+$ be a monotone nondecreasing function such that $\,p_t=\mathbb{P}({\mathcal{S}}_t(\varphi,T) \not= \phi)\,$ is a decreasing function of t, mapping $[0,\infty)$ onto (0, 1]. Then $\mu$ is invariant under the operation of pruning $\mathcal{S}_t(T)=\mathcal{S}_t(\varphi,T)$ if and only if $\mu\equiv \mathcal{IGW}(q_0,\lambda)$ .

Notice that Lemma 3.1 does not imply the uniqueness result in Theorem 2.1, which is valid under the regularity assumption, Assumption 2.1. Next, we list some examples where the assumptions of Lemma 3.1 are satisfied.

Example 3.3. Let $\varphi(T)={\rm{\small HEIGHT}}(T)$ . Consider a critical Galton–Watson tree measure $\mu\equiv\mathcal{GW}(\{q_k\},\lambda)$ ( $q_1=0$ ) on ${\mathcal{L}}^|$ , and let $T\stackrel{d}{\sim} \mu$ . Then $1-p_t=P_{1,0}(t)$ is the probability of extinction by time t of the critical continuous-time branching process. Since $P_{1,0}(t)$ is a continuous function of t that maps $[0,\infty)$ onto [0, 1), Lemma 3.1 implies that $IGW(q,\lambda)$ is the only class of Galton–Watson measures that are invariant under the generalized dynamical pruning with $\varphi(T)={\rm{\small HEIGHT}}(T)$ .

Example 3.4. Let $\varphi(T)={\rm{\small LENGTH}}(T)$ . Consider a critical Galton–Watson tree measure $\mu\equiv\mathcal{GW}(\{q_k\},\lambda)$ ( $q_1=0$ ) on ${\mathcal{L}}^|$ , and let $T\stackrel{d}{\sim} \mu$ . Denote by N the number of edges in T. Then the density function of ${\rm{\small LENGTH}}(T)$ can be expressed as $\,\sum\limits_{k=1}^{\infty}\mathbb{P}(N=k)f_{k,\lambda}(x)$ , where $f_{k,\lambda}(x)$ is a gamma function $\,f_{k,\lambda}(x)={\lambda^k \over \Gamma(k)}x^{k-1}e^{-\lambda x}$ . Hence, the cumulative distribution function of ${\rm{\small LENGTH}}(T)$ ,

\begin{equation*}\mathbb{P}({\rm{\small LENGTH}}(T) \leq t)=1-p_t,\end{equation*}

is a continuous function of t mapping $[0,\infty)$ onto [0, 1). Thus, by Lemma 3.1, $IGW(q,\lambda)$ is the only class of Galton–Watson measures invariant under the generalized dynamical pruning with $\varphi(T)={\rm{\small LENGTH}}(T)$ .

Next, we check that Proposition 3.3 and Theorem 3.1 are consistent with this semigroup property of the generalized dynamical pruning induced by $\varphi(T)={\rm{\small HEIGHT}}(T)$ as in Example 2.2. Indeed, for $T\stackrel{d}{\sim}\mathcal{IGW}(q,\lambda)$ , Proposition 3.3 yields

\begin{equation*}T^t\,:\!=\,\{{\mathcal{S}}_t(\varphi,T)|{\mathcal{S}}_t(\varphi,T) \not= \phi\} \stackrel{d}{\sim} \mathcal{IGW}\left(q,\,{\mathcal{E}} _t(\lambda)\right),\end{equation*}

where by Theorem 3.1, ${\mathcal{E}} _t(\lambda)=\lambda p_t^{(1-q)/q}={\lambda \over \lambda(1-q) t+1}$ . Hence,

\begin{equation*}{\mathcal{E}}_s \circ {\mathcal{E}}_t (\lambda)={\mathcal{E}}_s \big({\mathcal{E}}_t (\lambda)\big)={\mathcal{E}}_{t+s} (\lambda),\end{equation*}

which reaffirms the semigroup property of ${\mathcal{S}}_t$ for $\varphi(T)={\rm{\small HEIGHT}}(T)$ .

3.3. Invariant Galton–Watson trees $\mathcal{IGW}(q)$ as attractors

The following result extends Theorem 2.2 to all generalized dynamical pruning operators $\mathcal{S}_t(T)=\mathcal{S}_t(\varphi,T)$ .

Theorem 3.4. (IGW attractors under generalized dynamical pruning.) Consider a Galton–Watson measure $\mu \equiv\mathcal{GW}(\{q_k\}, \lambda)$ with $q_1=0$ on ${\mathcal{L}}^|$ . Suppose the measure is critical and Assumption 2.1 is satisfied. Then, for any random tree $T\in{\mathcal{L}}^|$ distributed according to $\mu$ , i.e., $\,T \stackrel{d}{\sim} \mu$ ,

\begin{equation*}\lim_{t\to\infty}\mathbb{P}\big({\rm{\small SHAPE}}(\mathcal{S}_t(T))=\tau \,\big|\,\mathcal{S}_t(T)\not=\phi \big)=\mu^*(\tau), \qquad { for\ all }\, \tau \in {\mathcal{T}}^|,\end{equation*}

where $\mu^*$ denotes the IGW measure $\mathcal{IGW}(q)$ with $q={1 \over 2-L}$ and L defined in (7).

Finally, suppose the Galton–Watson measure $\mu \equiv\mathcal{GW}(\{q_k\},\lambda)$ (with $q_1=0$ ) is subcritical; then for $\,T \stackrel{d}{\sim} \mu$ , the distribution $\mathbb{P}\big({\rm{\small SHAPE}}(\mathcal{S}_t(T))=\cdot \,\big|\,\mathcal{S}_t(T)\not=\phi \big)$ converges to a point mass measure on the tree reduced to a stem, $\mathcal{GW}(q_0\!=\!1)$ .

Theorem 3.4 is proved in Section 4.3.

The next two corollaries of Theorem 3.4 follow immediately from Lemmas 2.2 and 2.4.

Corollary 3.1. (Attraction property of critical Galton--Watson trees of Zipf type.) Consider a critical Galton–Watson process $\mu \equiv \mathcal{GW}(\{q_k\})$ with $q_1=0$ , with offspring distribution $q_k$ of Zipf type, i.e., $q_k \sim C k^{-(\alpha+1)}$ , with $\alpha \in (1,2]$ and $C>0$ . Then, for a random tree $T\in{\mathcal{L}}^|$ distributed according to $\mu$ , i.e., $\,T \stackrel{d}{\sim} \mu$ ,

\begin{equation*}\lim_{t\to\infty}\mathbb{P}\big({\rm{\small SHAPE}}(\mathcal{S}_t(T))=\tau \,\big|\,\mathcal{S}_t(T)\not=\phi \big)=\mu^*(\tau), \qquad { for\ all }\, \tau \in {\mathcal{T}}^|,\end{equation*}

where $\mu^*$ is the IGW measure $\mathcal{IGW}\left({1 \over \alpha}\right)$ .

Corollary 3.2. (Attraction property of critical binary Galton--Watson tree [Reference Burd, Waymire and Winn5].) Consider a critical Galton–Watson process $\mu \equiv \mathcal{GW}(\{q_k\})$ with $q_1=0$ . Assume one of the following two conditions holds:

  1. (a) The second moment assumption is satisfied:

    \begin{equation*}\sum \limits_{k=2}^\infty k^2 q_k <\infty.\end{equation*}
  2. (b) Assumption 2.1 is satisfied, and the ‘ $2-$ ’ moment assumption is satisfied, i.e.,

    \begin{equation*}\sum \limits_{k=2}^\infty k^{2-\epsilon}q_k <\infty \qquad \forall \epsilon>0.\end{equation*}

Then, for a random tree $T\in{\mathcal{L}}^|$ distributed according to $\mu$ , i.e., $\,T \stackrel{d}{\sim} \mu$ ,

\begin{equation*}\lim_{t\to\infty}\mathbb{P}\big({\rm{\small SHAPE}}(\mathcal{S}_t(T))=\tau \,\big|\,\mathcal{S}_t(T)\not=\phi \big)=\mu^*(\tau), \qquad \text{ for all }\, \tau \in {\mathcal{T}}^|,\end{equation*}

where $\mu^*$ is the critical binary Galton–Watson measure $\mathcal{IGW}(1/2)$ .

Next, we state a result for the Bernoulli leaf coloring operator $\mathcal{C}_p$ (see Section 2.7), which is analogous to the one in Theorem 3.4.

Theorem 3.5. (IGW attractors under Bernoulli leaf coloring.) Consider a Galton–Watson measure $\mu \equiv\mathcal{GW}(\{q_k\})$ with $q_1=0$ on ${\mathcal{T}}^|$ . Suppose the measure is critical and Assumption 2.1 is satisfied. Then, for a random tree $T\in{\mathcal{T}}^|$ distributed according to $\mu$ , i.e., $\,T \stackrel{d}{\sim} \mu$ ,

\begin{equation*}\lim_{p \to 1-}\mathbb{P}\big(\mathcal{C}_p(T)=\tau \,|\,\mathcal{C}_p(T)\not= \phi\big)=\mu^*(\tau), \qquad \text{ for all }\, \tau \in {\mathcal{T}}^|,\end{equation*}

where $\mu^*$ denotes the IGW measure $\mathcal{IGW}(q)$ with $q={1 \over 2-L}$ and L as defined in (7).

Suppose $\mu \equiv\mathcal{GW}(\{q_k\})$ (with $q_1=0$ ) is subcritical; then for $\,T \stackrel{d}{\sim} \mu$ , the conditional distribution $\mathbb{P}\big(\mathcal{C}_p(T)=\cdot \,|\,\mathcal{C}_p(T)\not= \phi\big)$ converges to a point mass measure on the tree reduced to the stem, $\mathcal{GW}(q_0\!=\!1)$ .

Theorem 3.5 is proved in Section 4.3.

Finally, another result analogous to Theorem 3.4 can be obtained for iterative hereditary reductions (see Section 2.6).

Theorem 3.6. (IGW attractors under generalized hereditary reductions.) Consider a Galton–Watson measure $\mu \equiv\mathcal{GW}(\{q_k\}, \lambda)$ with $q_1=0$ on ${\mathcal{L}}^|$ . Suppose the measure is critical and Assumption 2.1 is satisfied. Let $T\in{\mathcal{L}}^|$ be a random tree distributed according to $\mu$ , and let $H_1,\,H_2,\dots$ be a sequence of hereditary properties satisfying

\begin{equation*}\lim\limits_{n \to \infty}\mathbb{P}\big(R_{H_n}\circ \dots \circ R_{H_1}(T) \not= \phi \big)=0,\end{equation*}

where $R_{H_1},\,R_{H_2},\dots$ are the corresponding hereditary reductions. Then, for $\,T \stackrel{d}{\sim} \mu$ ,

\begin{equation*}\lim_{t\to\infty}\mathbb{P}\big({\rm{\small SHAPE}}(\mathcal{S}_t(T))=\tau \,\big|\,\mathcal{S}_t(T)\not=\phi \big)=\mu^*(\tau), \qquad \text{ for all }\, \tau \in {\mathcal{T}}^|,\end{equation*}

where $\mu^*$ denotes the IGW measure $\mathcal{IGW}(q)$ with $q={1 \over 2-L}$ and L as defined in (7).

If $\mu$ is a subcritical Galton–Watson measure, then for $\,T \stackrel{d}{\sim} \mu$ , the conditional distribution $\mathbb{P}\big({\rm{\small SHAPE}}(\mathcal{S}_t(T))=\cdot \,\big|\,\mathcal{S}_t(T)\not=\phi \big)$ converges to a point mass measure on the tree reduced to the stem, $\mathcal{GW}(q_0\!=\!1)$ .

Theorem 3.6 is proved in Section 4.3.

4. Proofs

4.1. Metric properties of invariant Galton–Watson trees

Proof of Theorem 3.1. Consider a tree $T\stackrel{d}{\sim}\mathcal{IGW}(q,\lambda)$ . Let X denote the length of the stem connecting the random tree’s root $\rho$ to the root’s only child vertex $v_0$ . Let $K={\sf br}(v_0)$ be the branching number of $v_0$ , and let the K subtrees branching out of $v_0$ be denoted by $T_i, 1 \le i \le K$ . Let H(x) be the cumulative distribution function for the height of T. Then, for each subtree $T_i\stackrel{d}{\sim}\mathcal{IGW}(q,\lambda)$ , its height ${\rm{\small HEIGHT}}(T_i)$ has the same cumulative distribution function H(x). The number of subtrees $K\stackrel{d}{\sim} q_k$ has generating function $Q(z)=z+q(1-z)^{1/q}$ . Let M(x) denote the cumulative distribution function of $\,\max\limits_{1 \le i \le K}\{{\rm{\small HEIGHT}}(T_i)\}$ ; then

(32) \begin{align}M(x)&=\mathbb{P}\big(\max\limits_{1 \le i \le K}\{{\rm{\small HEIGHT}}(T_i)\} \leq x\big)=\sum\limits_{k=0}^\infty q_k \mathbb{P}\big(\max\limits_{1 \le i \le K}\{{\rm{\small HEIGHT}}(T_i)\} \leq x \,\big|\, K=k\big) \nonumber \\&=\sum\limits_{k=0}^\infty q_k \mathbb{P}\big({\rm{\small HEIGHT}}(T) \leq x\big)^k=\sum\limits_{k=0}^\infty q_k \big(H(x)\big)^k \nonumber \\&=(Q\circ H)(x)=H(x)+q\big(1-H(x) \big)^{1/q}.\end{align}

The stem length X is an exponentially distributed random variable with parameter $\lambda$ and density function $\varphi_\lambda(x)=\lambda \exp\{-\lambda x\} {\textbf{1}}_{x \geq 0}$ . Since $\,{\rm{\small HEIGHT}}(T)=X+\max\limits_{1 \le i \le K}\{{\rm{\small HEIGHT}}(T_i)\}$ , we have

(33) \begin{equation}H(x) = \varphi_\lambda \ast M(x).\end{equation}

We will use the following notation: let $\widehat{g}(t)=\int\limits_{-\infty}^\infty e^{itx} g(x) \,dx$ denote the Fourier transform of g(x). Equations (32) and (33) yield

\begin{equation*}H(x)=\varphi_\lambda \ast (Q\circ H)(x).\end{equation*}

Taking the Fourier transform, we obtain

\begin{equation*}\widehat{H}(t)={\lambda \over \lambda-it}\, \left(\widehat{H}(t)+q\widehat{\big(1-H \big)^{1/q}}(t)\right),\end{equation*}

which simplifies to

\begin{equation*}it\widehat{H}(t)+\lambda q \widehat{\big(1-H \big)^{1/q}}(t)=0,\end{equation*}

where

\begin{equation*}\widehat{\big(1-H \big)^{1/q}}(t)=\int\limits_{-\infty}^\infty e^{itx} \big(1-H(x) \big)^{1/q} \,dx.\end{equation*}

Therefore,

(34) \begin{equation}\int\limits_{-\infty}^\infty e^{itx} \left(itH(x)+\lambda q\big(1-H(x) \big)^{1/q}\right) \,dx=0 \qquad \forall t \in \mathbb{R},\end{equation}

where integration by parts yields

(35) \begin{equation}\int\limits_{-\infty}^\infty e^{itx}it H(x)\,dx=-\int\limits_{-\infty}^\infty e^{itx}H^{\prime}(x)\,dx.\end{equation}

Substituting (35) back into (34) yields

\begin{equation*}\int\limits_{-\infty}^\infty e^{itx} \left(H^{\prime}(x)-\lambda q\big(1-H(x) \big)^{1/q}\right) \,dx=0 \qquad \forall t \in \mathbb{R},\end{equation*}

which by Parseval’s equation implies the following ordinary differential equation:

(36) \begin{equation}H^{\prime}(x)=\lambda q\big(1-H(x) \big)^{1/q}.\end{equation}

Next, we solve the differential equation (36) above via integration, obtaining

(37) \begin{equation}H(x)=1-\big((\lambda x+C)(1-q)\big)^{-{q \over 1-q}},\end{equation}

where C is a scalar. Since H(x) is the cumulative distribution function of a positive random variable ${\rm{\small HEIGHT}}(T)$ , we have $H(0)=0$ , implying $C={1 \over 1-q}$ . Thus, for $q \in \left[{1 \over 2},1\right)$ ,

\begin{equation*}H(x)=1-\left(\left(\lambda x+\frac{1}{1-q}\right)(1-q)\right)^{-{q \over 1-q}}=1-\big(\lambda(1-q) x+1\big)^{-q/(1-q)}.\end{equation*}

Next, we use the following application of the Lagrange inversion theorem (Theorem A.1).

Lemma 4.1. Let $q \in [1/2,1)$ be given. Suppose $W=W(z)$ is an analytic function satisfying the equation

\begin{equation*}z={W \over (1-W)^{1/q}}\end{equation*}

in a neighborhood of the origin, where we take the $-\pi< \arg(z)<\pi$ branch of the function $z^{1/q}$ . Then, for z near the origin, we have

(38) \begin{equation}W=\sum_{n=1}^{\infty}({-}1)^{n-1}\frac{\Gamma(n/q+1)}{n!\,\Gamma(n/q-n+2)}z^n.\end{equation}

Observe that the conclusion of Lemma 4.1 also applies in a real-valued setting, under the assumption of infinite differentiability of $W\,:\,\mathbb{R} \to \mathbb{R}$ . Here, if $z={W \over (1-W)^{1/q}}$ for $z \in \mathbb{R}$ in a neighborhood of the origin on the real line, then the power series expansion (38) holds in proximity to 0.

Proof of Lemma 4.1. We notice that the function $f(w)={w \over (1-w)^{1/q}}$ is analytic at $w=0$ , and $f^{\prime}(0)=1 \not=0$ . Thus, we can apply the Lagrange inversion theorem (Theorem A.1) to express W in terms of z power series. Now, since

\begin{equation*}\left({w \over f(w)}\right)^n=(1-w)^{n/q},\end{equation*}

we have

\begin{eqnarray*}\frac{d^{n-1}}{dw^{n-1}}\left({w \over f(w)}\right)^{\!\!n}\!\Bigg|_{W=0}&=&({-}1)^{n-1}(n/q)(n/q-1)\dots(n/q-n+2)\\&=&({-}1)^{n-1}\frac{\Gamma(n/q+1)}{\Gamma(n/q-n+2)}.\end{eqnarray*}

Therefore, by the Lagrange inversion theorem (Theorem A.1), we obtain

\begin{equation*}W=\sum_{n=1}^{\infty}{z^n \over n!} \left[{d^{n-1} \over dw^{n-1}}\left({w \over f(w)}\right)^{\!\!n}\right]_{w=0}=\sum_{n=1}^{\infty}({-}1)^{n-1}\frac{\Gamma(n/q+1)}{n!\,\Gamma(n/q-n+2)}z^n.\end{equation*}

Proof of Theorem 3.2. Consider a tree $T\stackrel{d}{\sim}\mathcal{IGW}(q,\lambda)$ consisting of a stem of length X that connects the root $\rho$ to its child vertex $v_0$ , and $K={\sf br}(v_0)$ subtrees $T_i$ , $1 \le i \le K$ , branching out from $v_0$ . Let $\ell(x)$ be the density function of the length of T. Notice that the length of each subtree $T_i$ is also $\ell(x)$ -distributed. The random variable $K\stackrel{d}{\sim} q_k$ has generating function $Q(z)=z+q(1-z)^{1/q}$ . Letting N(x) denote the probability density function of $\,\sum\limits_{1 \le i \le K}\{{\rm{\small LENGTH}}(T_i)\}$ , we have

(39) \begin{equation}N(x)=\sum_{k=0}^\infty q_k \ell_k(x), \quad \text{ where } \ell_k(x)=\underbrace{\ell \ast \dots \ast \ell}_{k \text{ times}}(x).\end{equation}

Observe that $\,{\rm{\small LENGTH}}(T)=X+\sum\limits_{1 \le i \le K}\{{\rm{\small LENGTH}}(T_i)\}$ , where X has exponential probability density function $\varphi_\lambda(x)=\lambda \exp\{-\lambda x\} {\textbf{1}}_{x \geq 0}$ . Thus, $\ell(x)$ can be represented as the following convolution:

(40) \begin{equation}\ell(x) = \varphi_\lambda \ast N(x).\end{equation}

For $t \geq 0$ , let the function ${\mathcal{L}}[g](t)=\int\limits_0^\infty e^{-tx} g(x) \,dx$ denote the Laplace transform of g. Then (39) and (40) imply

\begin{equation*}{\mathcal{L}}[\ell](t)={\mathcal{L}}[\varphi_\lambda](t) \,{\mathcal{L}}[N](t)={\mathcal{L}}[\varphi_\lambda](t) \,Q\big({\mathcal{L}}[\ell](t)\big)={\lambda \over \lambda+t} \left({\mathcal{L}}[\ell](t)+q\big(1-{\mathcal{L}}[\ell](t) \big)^{1/q}\right),\end{equation*}

which simplifies to

(41) \begin{equation}t{\mathcal{L}}[\ell](t)=\lambda q\big(1-{\mathcal{L}}[\ell](t) \big)^{1/q}.\end{equation}

Letting $\,z={\lambda q \over t}$ and $\Lambda={\mathcal{L}}[\ell]\left({\lambda q \over z}\right)={\mathcal{L}}[\ell](t)$ , we have

\begin{equation*}z={\Lambda \over (1-\Lambda)^{1/q}}.\end{equation*}

Then Lemma 4.1 yields

\begin{equation*}{\mathcal{L}}[\ell](t)=\Lambda=\sum_{n=1}^{\infty}({-}1)^{n-1}{\Gamma(n/q+1) \over n!\, \Gamma(n/q-n+2)}\frac{(\lambda q)^n}{t^n}.\end{equation*}

Finally, we invert the Laplace transform ${\mathcal{L}}[\ell](t)$ , obtaining

\begin{equation*}\ell(x)=\sum_{n=1}^{\infty}({-}1)^{n-1} {\Gamma(n/q+1) \over n! \,(n-1)! \,\Gamma(n/q-n+2)}(\lambda q)^n x^{n-1}.\end{equation*}

Proof of Proposition 3.1. Observe that

\begin{align*}1-{\mathcal{L}}[\ell](t) &= \int\limits_0^\infty (1-e^{-tx})\,\ell(x) \,dx = t \int\limits_0^\infty \int\limits_0^x e^{-ty} \,\ell(x) \,dy\,dx \\&= t \int\limits_0^\infty e^{-ty} \, \int\limits_y^\infty \ell(x) \,dx\,dy = t \int\limits_0^\infty e^{-ty} \, \big(1-L(y)\big)\,dy =t\,{\mathcal{L}}[1\!-\!L](t).\end{align*}

Thus, by (41), we have

\begin{equation*}t{\mathcal{L}}[\ell](t)=\lambda q\big(1-{\mathcal{L}}[\ell](t) \big)^{1/q}=\lambda q \,t^{1/q}\,\big({\mathcal{L}}[1\!-\!L](t) \big)^{1/q},\end{equation*}

and therefore,

\begin{equation*}{\mathcal{L}}[1\!-\!L](t)={1 \over t^{1-q}} {\big({\mathcal{L}}[\ell](t)\big)^q \over (\lambda q)^q},\quad \text{ where }\quad \lim\limits_{t\to 0+}{\big({\mathcal{L}}[\ell](t)\big)^q \over (\lambda q)^q}={1 \over (\lambda q)^q}.\end{equation*}

Hence, by the Hardy–Littlewood–Karamata Tauberian theorem for Laplace transforms [Reference Feller12],

\begin{equation*}1-L(x) \sim {1 \over (\lambda q)^q \,\Gamma(1-q)}x^{-q}.\end{equation*}

Proof of Theorem 3.3. Observe that in a reduced tree $T \in {\mathcal{T}}^| \setminus \{\phi\}$ , the number of edges equals one plus the number of edges in all subtrees splitting from the stem. Therefore, $\alpha(0)=0$ , $\alpha(1)=q_0$ , and

\begin{equation*}\alpha(n+1)=\sum_{k=1}^n q_k\, \underbrace{\alpha \ast \dots \ast \alpha}_{k \text{ times}}(n), \qquad n=1,2,\dots.\end{equation*}

Therefore, the generating function $\,a(z)=\sum\limits_{n=1}^\infty z^n \,\alpha(n)\,$ satisfies $\,a(z)=z\,Q\big(a(z)\big)$ . Hence,

(42) \begin{equation}a(z)=z\,\Big(a(z)+q\big(1-a(z)\big)^{1/q}\Big),\end{equation}

and therefore,

\begin{equation*}w={a \over (1-a)^{1/q}}, \qquad \text{ where } a=a(z) \text{ and } w={q z \over 1-z}.\end{equation*}

Lemma 4.1 yields

\begin{align*}a(z)&=\sum_{k=1}^{\infty} \sum\limits_{n=k}^\infty ({-}1)^{k-1} \left(\begin{array}{c}n-1\\k-1\end{array}\right){\Gamma(k/q+1)\over k!\,\Gamma(k/q -k+2)}\,q^k z^n \\&=\sum\limits_{n=1}^\infty z^n \sum_{k=1}^n ({-}1)^{k-1} \left(\begin{array}{c}n-1\\k-1\end{array}\right){\Gamma(k/q+1)\over k!\,\Gamma(k/q -k+2)}\,q^k.\end{align*}

Thus, since $\,a(z)=\sum\limits_{n=1}^\infty z^n \,\alpha(n)$ , Equation (29) follows. Finally, the cumulative distribution function equals

\begin{align*}\mathcal{A}(x)&=\sum\limits_{n=1}^{\lfloor x \rfloor} \alpha(n) =\sum\limits_{n=1}^{\lfloor x \rfloor} \sum_{k=1}^n ({-}1)^{k-1} \left(\begin{array}{c}n-1\\k-1\end{array}\right){\Gamma(k/q+1)\over k!\,\Gamma(k/q -k+2)}\,q^k\\&=\sum_{k=1}^{\lfloor x \rfloor}({-}1)^{k-1} \left(\sum\limits_{n=k}^{\lfloor x \rfloor} \left(\begin{array}{c}n-1\\k-1\end{array}\right)\right){\Gamma(k/q+1)\over k!\,\Gamma(k/q -k+2)}\,q^k\\&=\sum\limits_{k=1}^{\lfloor x \rfloor} ({-}1)^{k-1} \left(\begin{array}{c}\lfloor x \rfloor\\k\end{array}\right){\Gamma(k/q+1) \over k!\,\Gamma(k/q -k+2)}\,q^k\end{align*}

for all real $\,x \geq 1$ , and (30) holds.

4.2. Invariance under generalized dynamical pruning

Proof of Proposition 3.3. For $q \in [1/2,1)$ and $Q(z)=z+q(1-z)^{1/q}$ , Equation (21) in Lemma 2.5 implies

\begin{align*}G(z)&=z+{Q\big(1-p_t+p_t z\big)-(1-p_t)-zp_t \over p_t\big(1-Q^{\prime}(1-p_t)\big)}\\&=z+p_t^{-1/q}\left(Q\big(z+(1-z)(1-p_t)\big)-(1-p_t) -zp_t \right)\\&=z+p_t^{-1/q}q p_t^{1/q}(1-z)^{1/q} =Q(z).\end{align*}

The rest of the proof follows from Lemma 2.5 as

(43) \begin{equation}\lambda \big(1-Q^{\prime}(1-p_t)\big)=\lambda p_t^{(1-q)/q},\end{equation}

yielding $\, \mathcal{S}_t(T) \stackrel{d}{\sim} \mathcal{IGW}\big(q,\lambda p_t^{(1-q)/q}\big)$ .

Proof of Lemma 3.1. From Lemma 2.5, we have

\begin{equation*}g_0={Q\big(1-p_t\big)-(1-p_t) \over p_t\big(1-Q^{\prime}(1-p_t)\big)}\quad \text{ and }\quad G(z)=z+{Q\big(1-p_t+p_t z\big)-(1-p_t)-p_t z \over p_t\big(1-Q^{\prime}(1-p_t)\big)}.\end{equation*}

Combining the above yields

\begin{equation*}G(z)=z+g_0{Q\big(1-p_t+p_t z\big)-(1-p_t)-p_t z \over Q\big(1-p_t\big)-(1-p_t)}.\end{equation*}

Suppose $\mu$ is invariant under the operation of pruning $\mathcal{S}_t(T)=\mathcal{S}_t(\varphi,T)$ ; then $G(z)=Q(z)$ and $g_0=q_0$ , implying

(44) \begin{equation}Q(z)=z+q_0{Q\big(1-p_t+p_t z\big)-(1-p_t)-p_t z \over Q\big(1-p_t\big)-(1-p_t)}.\end{equation}

Let $R(z)=\frac{Q(z)-z}{q_0}$ ; then Equation (44) can be rewritten as

\begin{equation*}R(z)=\frac{R(1-p_t+p_tz)}{R(1-p_t)}.\end{equation*}

Thus, for $\ell(z)=\ln(R(1-z))$ , we have $\ell(1-z)+\ell(p_t)=\ell\big(p_t (1-z)\big)$ as $1-p_t+p_tz=1-p_t(1-z)$ .

Therefore, $\,\ell\big(p_t x\big)=\ell(x)+\ell(p_t)$ . Let $r(y)=\ell\big(e^y\big)$ ; then

(45) \begin{equation}r(y+\varepsilon_t)=r(y)+r(\varepsilon_t) \qquad \forall t\geq 0,\end{equation}

where $\varepsilon_t=\ln{p_t}$ . Here $r(0)=\ln R(0) =0$ .

We notice that the domain of r(y) is $y\in ({-}\infty,0]$ , and

\begin{equation*}\{\varepsilon_t \,:\, t \in [0,\infty)\}= ({-}\infty,0],\end{equation*}

as $1-p_t$ is an increasing function of t mapping $[0,\infty)$ onto [0, 1). Hence, Equation (45) implies the following Cauchy functional equation:

(46) \begin{equation}r(y+\varepsilon)=r(y)+r(\varepsilon) \qquad \forall y,\varepsilon \in ({-}\infty,0].\end{equation}

The general Cauchy functional equation states that, assuming

  • continuity ( $f(x) \in C(\mathbb{R})$ ) and

  • additivity ( $\,f(x+y)=f(x)+f(y)$ for all $x,y \in \mathbb{R}$ ),

the function $f(x)=cx$ for some $c\in \mathbb{R}$ . Notice that (46) is a sub-case of the general Cauchy functional equation restricted to a half-line, and therefore has the same linear solution and the same proof. Thus, (46) yields that $r(y)=\kappa y$ for some constant $\kappa$ .

Thus, we have $\ell(x)=\kappa\ln(x)$ ,

\begin{equation*}\kappa\ln(1-z)=\ell(1-z)=\ln R(z)=\ln\left(\frac{Q(z)-z}{q_0}\right),\end{equation*}

and

\begin{equation*}Q(z)=z+q_0(1-z)^\kappa.\end{equation*}

Finally, $\,q_1=0\,$ yields $\,Q^{\prime}(0)=0$ . Therefore, $\,Q^{\prime}(z)=1-q_0 \kappa(1-z)^{\kappa-1}\,$ implies $\,\kappa={1 \over q_0}$ .

4.3. Invariant Galton–Watson trees $\mathcal{IGW}(q)$ as attractors

First we prove the following result, related to Lemma 2.1.

Lemma 4.2. Consider a critical Galton–Watson measure $\mathcal{GW}(\{q_k\})$ with $q_1=0$ . If Assumption 2.1 is satisfied, then for g(x) defined in (6), the limit

(47) \begin{equation}\lim\limits_{x \rightarrow 1-}{(1-x)g^{\prime}(x) \over g(x)}\end{equation}

exists and and is equal to the limit L defined in (7).

Proof. Note that for $x \in ({-}1,1)$ ,

\begin{equation*}{Q(x)-x \over (1-x)\big(1-Q^{\prime}(x)\big)}={1 \over 2-{(1-x)g^{\prime}(x) \over g(x)}}.\end{equation*}

Thus, by Assumption 2.1, the limit

\begin{equation*}\lim\limits_{x \rightarrow 1-}{(1-x)g^{\prime}(x) \over g(x)}\end{equation*}

either exists or is equal to $\,\pm\infty$ . Hence, by L’Hôpital’s rule,

\begin{equation*}L=\lim\limits_{x \rightarrow 1-}\left({\ln{g(x)} \over -\ln(1-x)}\right)=\lim\limits_{x \rightarrow 1-}{(1-x)g^{\prime}(x) \over g(x)}.\end{equation*}

Before proving Theorem 3.4, we will need the following result.

Lemma 4.3. Consider a critical Galton–Watson measure $\mathcal{GW}(\{q_k\})$ with $q_1=0$ , let g(x) be as defined in (6), and let L be as defined in (7). If Assumption 2.1 is satisfied, then $g(1-1/y)$ is a regularly varying function (Definition B.1) with index L, i.e.,

(48) \begin{equation}\lim\limits_{x \to 1-}{g\left(\left(1-{1 \over r}\right)+{1 \over r}x\right) \over g(x)}=\lim\limits_{y \to \infty}{g\left(1-{1 \over ry}\right) \over g\left(1-{1 \over y}\right)}=r^L \qquad \text{ for all }\, r>0.\end{equation}

Proof. For $\alpha>-L-1$ , L’Hôpital’s rule and Lemma 4.2 yield

\begin{align*}\lim\limits_{y \to \infty}{y^{\alpha+1}g(1-1/y) \over \int\limits_a^y s^\alpha g(1-1/s)\,ds}&=\lim\limits_{y \to \infty}{(\alpha+1)y^\alpha g(1-1/y)+ y^{\alpha-1}g^{\prime}(1-1/y) \over y^\alpha g(1-1/y)} \\&=\alpha+1+\lim\limits_{y \to \infty}{y^{\alpha-1}g^{\prime}(1-1/y) \over y^\alpha g(1-1/y)} \\&=\alpha+1+\lim\limits_{x \rightarrow 1-}{(1-x)g^{\prime}(x) \over g(x)} =\alpha+1+L.\end{align*}

Hence, by the converse of Karamata’s theorem (Theorem B.2), $g(1-1/y)$ is a regularly varying function with index L, and (48) holds.

The following lemma will be the instrument for establishing that $\mathcal{IGW}(q)$ trees are attractors.

Lemma 4.4. Consider a Galton–Watson measure $\mathcal{GW}(\{q_k\})$ with $q_1=0$ on ${\mathcal{T}}^|$ . Suppose the measure is critical and Assumption 2.1 is satisfied. Then its progeny generating function Q(z) satisfies

\begin{equation*}\lim\limits_{x \rightarrow 1-}{Q\big(z+(1-z)x\big)-\big(z+(1-z)x\big) \over (1-x)(1-Q^{\prime}(x))}={1 \over 2-L}(1-z)^{2-L},\end{equation*}

where L is as defined in (7).

If the Galton–Watson measure $\mathcal{GW}(\{q_k\})$ (with $q_1=0$ ) is subcritical, then

\begin{equation*}\lim\limits_{x \rightarrow 1-}{Q\big(z+(1-z)x\big)-\big(z+(1-z)x\big) \over (1-x)(1-Q^{\prime}(x))}=1-z.\end{equation*}

Proof. Consider a critical Galton–Watson measure $\mathcal{GW}(\{q_k\})$ with $q_1=0$ and progeny generating function Q(z). For $x,z \in ({-}1,1)$ , we have

\begin{equation*}Q\big(z+(1-z)x\big)-\big(z+(1-z)x\big)=(1-z)^2 (1-x)^2\, g\big(z+(1-z)x\big).\end{equation*}

Thus, as

\begin{equation*}1-Q^{\prime}(x)=2(1-x)g(x)-(1-x)^2g^{\prime}(x),\end{equation*}

Lemma 4.2 yields

\begin{align*}\lim\limits_{x \rightarrow 1-}&{Q\big(z+(1-z)x\big)-\big(z+(1-z)x\big) \over (1-x)(1-Q^{\prime}(x))}= (1-z)^2 \lim\limits_{x \rightarrow 1-}{g\big(z+(1-z)x\big) \over 2g(x)-(1-x)g^{\prime}(x)} \\&= (1-z)^2 \lim\limits_{x \rightarrow 1-}{g\big(z+(1-z)x\big) \over \left(2-{(1-x)g^{\prime}(x) \over g(x)}\right)g(x)} = {1 \over 2-L}(1-z)^2 \lim\limits_{x \rightarrow 1-}{g\big(z+(1-z)x\big) \over g(x)} \\&= {1 \over 2-L}(1-z)^2 (1-z)^{-L} = {1 \over 2-L}(1-z)^{2-L}\end{align*}

by (48) with $r={1 \over 1-z}$ . The main statement in Lemma 4.4 follows.

Now, if we consider a subcritical Galton–Watson measure $\mathcal{GW}(\{q_k\})$ with $q_1=0$ and progeny generating function Q(z), then $Q^{\prime}(1)<1$ , and

\begin{align*}\lim\limits_{x \rightarrow 1-}&{Q\big(z+(1-z)x\big)-\big(z+(1-z)x\big) \over (1-x)(1-Q^{\prime}(x))}\\&={1 \over 1-Q^{\prime}(1)} \lim\limits_{x \rightarrow 1-}{Q\big(z+(1-z)x\big)-\big(z+(1-z)x\big) \over 1-x} \\&={1-z \over 1-Q^{\prime}(1)} \lim\limits_{x \rightarrow 1-}{Q\big(1-(1-z)(1-x)\big)-Q(1)+(1-z)(1-x) \over (1-z)(1-x)} =1-z.\end{align*}

We are now ready to prove Theorem 3.4.

Proof of Theorem 3.4. Suppose $\mu \equiv\mathcal{GW}(\{q_k\}, \lambda)$ with $q_1=0$ is critical and Assumption 2.1 holds. Then, by Equation (21) in Lemma 2.5 and Lemma 4.4, the generating function of $\,{\rm{\small SHAPE}}(\mathcal{S}_t(T))$ converges to

\begin{align*}z&+ \lim\limits_{t \to \infty} {Q\big(z+(1-z)(1-p_t)\big)-(1-p_t) -zp_t \over p_t\big(1-Q^{\prime}(1-p_t)\big)}\\&=z+\lim\limits_{x \rightarrow 1-}{Q\big(z+(1-z)x\big)-\big(z+(1-z)x\big) \over (1-x)(1-Q^{\prime}(x))} \\&=z+{1 \over 2-L}(1-z)^{2-L},\end{align*}

the generating function of $\mathcal{IGW}(q)$ with $q={1 \over 2-L}$ and L as defined in (7).

If the Galton–Watson measure $\mu \equiv\mathcal{GW}(\{q_k\}, \lambda)$ (with $q_1=0$ ) is subcritical, then Lemma 2.5 and Lemma 4.4 yield convergence of the generating function of $\,{\rm{\small SHAPE}}(\mathcal{S}_t(T))$ to

\begin{align*}z&+ \lim\limits_{t \to \infty} {Q\big(z+(1-z)(1-p_t)\big)-(1-p_t) -zp_t \over p_t\big(1-Q^{\prime}(1-p_t)\big)}\\&=z+\lim\limits_{x \rightarrow 1-}{Q\big(z+(1-z)x\big)-\big(z+(1-z)x\big) \over (1-x)(1-Q^{\prime}(x))} \\&=z+(1-z) =1,\end{align*}

the generating function of $\mathcal{GW}(q_0\!=\!1)$ . Hence, for $\,T \stackrel{d}{\sim} \mu$ , the conditional distribution $\mathbb{P}\big({\rm{\small SHAPE}}(\mathcal{S}_t(T))=\cdot \,\big|\,\mathcal{S}_t(T)\not=\phi \big)$ converges to a point mass measure, $\mathcal{GW}(q_0\!=\!1)$ .

Proof of Theorem 3.5. Analogously to the proof of Theorem 3.4 above, Theorem 3.5 follows from the formula (22) in Theorem 2.4 and Lemma 4.4.

Proof of Theorem 3.6. Following the steps in the proof of Theorem 3.4 above, Theorem 3.6 follows from the formula (18) in Theorem 2.3 with $p=\mathbb{P}\big(R_{H_n}\circ \dots \circ R_{H_1}(T) \not= \phi \big)$ and Lemma 4.4.

5. Discussion

In this work, we established the metric and attractor properties of the IGW branching processes with respect to a family of the generalized dynamical pruning operators. Informally, these operators eliminate a tree from leaves toward the root and are flexible enough to accommodate a number of classic (e.g. continuous erasure) and custom (e.g. erasure by the number of leaves) tree elimination rules. Together with the richness of the IGW family, which includes power-law offspring distributions with tail indices in the range between 1 and 2, this makes the results presented a useful tool for a variety of physical and mathematical problems.

Observe that erasing a random tree in accordance with the generalized dynamical pruning describes a coalescence dynamics—the merging of particles represented by the tree leaves into consecutively larger clusters represented by the internal vertices. The invariance and attractor properties of the IGW branching processes can be used to study a number of merger dynamics. For example, the continuum ballistic annihilation process (a ballistic motion of random-velocity particles that annihilate at contact) has been shown in [Reference Kovchegov and Zaliapin19] to correspond to a generalized dynamical pruning with $\varphi(T) = {\rm{\small LENGTH}}(T)$ , as in Example 2.3. The invariance of the critical binary Galton–Watson measure $\mathcal{IGW}(1/2, \lambda)$ under the generalized dynamical pruning was used in [Reference Kovchegov and Zaliapin19] to obtain an explicit analytical description of the annihilation dynamics for a special case of the initial two-valued velocity alternating at the instances of a Poisson process. Similarly, the generalized dynamical pruning with $\varphi(T) = {\rm{\small HEIGHT}}(T)$ as in Example 2.2 corresponds to the one-dimensional Zeldovich model in cosmology. The invariance results in this work may provide an interesting analytical insight into the dynamics of these and other models of coalescence.

The IGW branching processes arise naturally in seismological data that are traditionally modeled by branching processes with immigration; see [Reference Kovchegov, Zaliapin and Ben-Zion22] for a review and discussion. In essence, a sequence of earthquakes in a region is represented as a collection of clusters, each of which is initiated by an immigrant (the first cluster event). It has been shown in [Reference Kovchegov, Zaliapin and Ben-Zion22] that the IGW process provides a close approximation to the existing earthquake occurrence models and to the observed earthquake cluster statistics in southern California. The metric properties of the IGW trees have a meaningful interpretation in the seismological setting, where the edge lengths represent inter-event times. The attraction property of the IGW processes allows one to construct a robust earthquake modeling framework, which is stable with respect to various catalogue uncertainties. The IGW processes may provide a useful model in other areas that deal with imprecisely observed data represented by trees.

We conclude with an open problem. Lemma 3.1 established the uniqueness of the IGW processes as the invariants of the generalized dynamical pruning. The results of Duquesne and Winkel [Reference Duquesne and Winkel8] (see Theorem 2.4 of this paper) show that the IGW processes are invariant with respect to a broader set of tree reductions. It would be interesting to describe all tree transforming operators that preserve the IGW invariance (and attraction) property.

Appendix A. Lagrange inversion theorem

The Lagrange inversion theorem (also known as the Lagrange inversion formula) can be found in Whittaker and Watson [Reference Whittaker and Watson31] and in Abramowitz and Stegun [Reference Abramowitz and Stegun2].

Theorem A.1. (Lagrange inversion theorem.) Consider a function $g\,:\,\mathbb{C}\to\mathbb{C}$ such that g(w) is analytic in a neighborhood of the origin, $g(0)=0$ , and $g^{\prime}(0)\not=0$ . Then $g^{-1}$ can be expressed as the following power series near the origin:

\begin{equation*}g^{-1}(z)=\sum\limits_{n=1}^\infty {z^n \over n!} \left[{d^{n-1} \over dw^{n-1}}\left({w \over g(w)}\right)^n\right]_{w=0}.\end{equation*}

Moreover, for any $\varphi\,:\,\mathbb{C}\to\mathbb{C}$ analytic in a neighborhood around the origin,

\begin{equation*}\varphi\big(g^{-1}(z)\big)=\varphi(0)+\sum\limits_{n=1}^\infty {z^n \over n!} \left[{d^{n-1} \over dw^{n-1}}\left(\varphi^{\prime}(w){w \over g(w)}\right)^n\right]_{w=0}.\end{equation*}

Appendix B. Regularly varying functions

We define regularly varying functions and state Karamata’s theorems. See [Reference Bingham, Goldie and Teugels4] for a rigorous treatment of the theory of regularly varying functions.

Definition B.1. A positive measurable function f(x) is said to be regularly varying with index $\beta \in\mathbb{R}$ if

\begin{equation*}\lim\limits_{x \to \infty}{f(rx) \over f(x)}=r^\beta \qquad \text{ for all }\, r>0.\end{equation*}

Theorem B.1. (Karamata’s theorem, direct part [Reference Bingham, Goldie and Teugels4].) Let $f(x)\,:\,[a,\infty) \to [a,\infty)$ be a regularly varying function with index $\beta \in\mathbb{R}$ . Then

\begin{equation*}\lim\limits_{x \to \infty}{x^{\alpha+1}f(x) \over \int\limits_a^x y^\alpha f(y)\,dy}=\alpha+\beta+1 \qquad \text{ for all }\,\alpha>-\beta-1\end{equation*}

and

\begin{equation*}\lim\limits_{x \to \infty}{x^{\alpha+1}f(x) \over \int\limits_x^\infty y^\alpha f(y)\,dy}=-(\alpha+\beta+1) \qquad \text{ for all }\,\alpha<-\beta-1.\end{equation*}

We will use the following converse to the above Karamata’s theorem.

Theorem B.2. (Karamata’s theorem, converse [Reference Bingham, Goldie and Teugels4].) Let f(x) be a positive, measurable, and locally integrable function on $[a,\infty)$ and $\beta \in\mathbb{R}$ . Then the following hold:

  1. (a) If there exists $\alpha>-\beta-1$ such that

    \begin{equation*}\lim\limits_{x \to \infty}{x^{\alpha+1}f(x) \over \int\limits_a^x y^\alpha f(y)\,dy}=\alpha+\beta+1,\end{equation*}
    then f(x) is a regularly varying function with index $\beta$ .
  2. (b) If, for some $\alpha<-\beta-1$ ,

    \begin{equation*}\lim\limits_{x \to \infty}{x^{\alpha+1}f(x) \over \int\limits_x^\infty y^\alpha f(y)\,dy}=-(\alpha+\beta+1),\end{equation*}
    then f(x) is a regularly varying function with index $\beta$ .

Appendix C. Proof of Lemma 2.5

Proof of Lemma 2.5. First we show that the tree $\mathcal{S}_t(\varphi,T)$ obtained by pruning a Galton–Watson tree $T \stackrel{d}{\sim} \mu\equiv\mathcal{GW}(\{q_k\},\lambda)$ is also distributed as a Galton–Watson tree.

For $T \stackrel{d}{\sim} \mu$ and $s \geq 0$ , let $T|_{\leq s}$ denote a subtree of T consisting of all points x in the metric space T at distance no greater than s from the root $\rho$ , i.e.,

\begin{equation*}T|_{\leq s}=\{x \in T\,:\, d(x,\rho)\leq s\}.\end{equation*}

Let $T|_{=s}$ denote the points in T at distance s from the root $\rho$ , i.e.,

\begin{equation*}T|_{=s}=\{x \in T\,:\, d(x,\rho)=s\}.\end{equation*}

Let ${\mathcal{F}}_s^0=\sigma\big(T|_{\leq s}\big)$ be a sigma-algebra generated by the history up to time s (including branching history) of the Galton–Watson process that induces T. The future of the Galton–Watson process after time s consists of the descendant subtrees

\begin{equation*}\big\{\Delta_{x,T}\,:\,x \in T|_{=s} \big\}.\end{equation*}

Let ${\mathcal{F}}^{\prime}_s=\sigma\big(\Delta_{x,T}\,:\,x \in T|_{=s}\big)$ be a sigma-algebra generated by the future events after time s. The measure $\mu$ being a Galton–Watson measure (i.e., $\mu\equiv\mathcal{GW}(\{q_k\},\lambda)$ ) is equivalent to $T|_{=s}$ being a continuous-time Markov branching process (see [Reference Athreya and Ney3, Reference Harris13]). That is, there exists a filtration ${\mathcal{F}}_s \supset {\mathcal{F}}_s^0$ such that the following hold:

  1. 1. The Markov property is satisfied:

    \begin{equation*}\mathbb{P}\big(A\,\big|\,{\mathcal{F}}_s \big) \,=\, \mathbb{P}\big(A\,\big| T|_{=s}\big) \qquad \forall A \in {\mathcal{F}}^{\prime}_s.\end{equation*}
  2. 2. Conditioned on $T|_{=s}$ , the subtrees $\big\{\Delta_{x,T}\,:\,x \in T|_{=s} \big\}$ of T, denoted here by

    \begin{equation*}\Big(\big\{\Delta_{x,T}\,:\,x \in T|_{=s} \big\} \Big| T|_{=s}\Big),\end{equation*}
    are independent.

Next, let

\begin{equation*}\mathcal{I}_s=\sigma\big(\Delta_{x,\mathcal{S}_t(\varphi,T)}\,:\, x \in \mathcal{S}_t(\varphi,T)|_{=s}\big)\end{equation*}

be a sigma-algebra generated by the future events of $\,\mathcal{S}_t(\varphi,T)|_{=s}$ , after time s. Then, since

\begin{align*}\big\{\Delta_{x,\mathcal{S}_t(\varphi,T)}\,:\,x \in \mathcal{S}_t(\varphi,T)|_{=s} \big\}&=\big\{\mathcal{S}_t(\varphi,\Delta_{x,T})\,:\,x \in \mathcal{S}_t(\varphi,T)|_{=s} \big\}\\&=\big\{\mathcal{S}_t(\varphi,\Delta_{x,T})\,:\,x \in T|_{=s}\, \text{ such that }\, \mathcal{S}_t(\varphi,\Delta_{x,T})\not= \phi \big\},\end{align*}

we have

\begin{equation*}\mathcal{I}_s =\sigma\big(S(\varphi,\Delta_{x,T})\,:\, x \in T|_{=s}\big) \, \subset {\mathcal{F}}^{\prime}_s.\end{equation*}

We claim that conditioned on the event $\{\mathcal{S}_t(\varphi,T)\not= \phi\}$ , the partition/annihilation evolution $\,\mathcal{S}_t(\varphi,T)|_{=s}\,$ is a continuous-time Markov branching process with respect to the filtration ${\mathcal{F}}_s$ . Indeed, we have the following:

  1. 1. The Markov property is satisfied:

    \begin{equation*}\mathbb{P}\big(A\,\big|\,{\mathcal{F}}_s \big) \,=\, \mathbb{P}\big(A\,\big| T|_{=s}\big) \,=\, \mathbb{P}\big(A\,\big| \mathcal{S}_t(\varphi,T)|_{=s}\big) \qquad \forall A \in {\mathcal{I}}_s \, \subset {\mathcal{F}}^{\prime}_s.\end{equation*}
    Let $\mathbb{P}_{\not= \phi}(A)=\mathbb{P}(A|\,\mathcal{S}_t(\varphi,T)\not= \phi)$ . Then
    \begin{equation*}\mathbb{P}_{\not= \phi}\big(A\,\big|\,{\mathcal{F}}_s \big) \,=\, \mathbb{P}_{\not= \phi}\big(A\,\big| \mathcal{S}_t(\varphi,T)|_{=s}\big) \qquad \forall A \in {\mathcal{I}}_s.\end{equation*}
  2. 2. Conditioned on $\mathcal{S}_t(\varphi,T)|_{= s}$ , the subtrees

    \begin{equation*}\big\{\Delta_{x,\mathcal{S}_t(\varphi,T)}\,:\,x \in \mathcal{S}_t(\varphi,T)|_{=s} \big\}=\big\{\mathcal{S}_t(\varphi,\Delta_{x,T})\,:\,x \in T|_{=s},\, \mathcal{S}_t(\varphi,\Delta_{x,T})\not= \phi \big\}\end{equation*}
    of $\mathcal{S}_t(\varphi,T)$ are independent.

In order to characterize the dendritic structure of $\mathcal{S}_t(\varphi,T)$ , we start an upward exploration from the root $\rho \in T$ and proceed to the nearest internal vertex v of T (i.e., ${\sf par}(v)=\rho$ ). For a pair of integers $k \geq 2$ and $m \geq 0$ , we have

(49) \begin{equation}\mathbb{P}\big({\sf br}_T(v)=k, \, {\sf br}_{\mathcal{S}_t(\varphi,T)}(v)=m \,\big|\,\mathcal{S}_t(\varphi,T)\not=\phi\big)=\binom{k}{m}(1-p_t)^{k-m} p_t^m {q_k \over p_t},\end{equation}

where ${\sf br}_T(v)$ and ${\sf br}_{\mathcal{S}_t(\varphi,T)}(v)$ denote the branching numbers of the vertex v in T and $\mathcal{S}_t(\varphi,T)$ respectively. Here, the event ${\sf br}_{\mathcal{S}_t(\varphi,T)}(v)=1$ corresponds to the case when the vertex v is removed via series reduction. Thus, the case $m=1$ will be treated separately.

Next, we would like to find an expression for the branching probability $g_m$ of a pruned tree $\mathcal{S}_t(\varphi,T)$ . For a given integer $m \geq 2$ ,

\begin{equation*}\mathbb{P}\big({\sf br}_{\mathcal{S}_t(\varphi,T)}(v)=m \,\big|\,\mathcal{S}_t(\varphi,T)\not=\phi \big)=(1-p_t)^{-m} p_t^{m-1} \sum\limits_{k = m}^\infty \binom{k}{m} (1-p_t)^{k} q_k.\end{equation*}

Therefore, for $m \geq 2$ ,

\begin{align*}g_m &= \mathbb{P}\big({\sf br}_{\mathcal{S}_t(\varphi,T)}(v)=m \,\big|\,\mathcal{S}_t(\varphi,T)\not=\phi, \, {\sf br}_{\mathcal{S}_t(\varphi,T)}(v)\not= 1 \big) \nonumber \\&=(1-p_t)^{-m} p_t^{m-1} {\sum\limits_{k = m}^\infty \binom{k}{m} p^k q_k \over 1-(1-p_t)^{-1}\sum\limits_{k = 2}^\infty k p^k q_k} ={p_t^{m-1} \over m!} Q^{(m)}(1-p_t) \,(1-Q^{\prime}(1-p_t))^{-1}.\end{align*}

The corresponding generating function of $\{g_k\}$ is equal to

(50) \begin{align}G(z) & =\sum\limits_{m=0}^\infty z^m g_m=g_0+ {p_t^{-1} \over 1-(1-p_t)^{-1}\sum\limits_{k = 2}^\infty k p^k q_k}\sum\limits_{m=2}^\infty \sum\limits_{k = m}^\infty \big(z(1-p_t)^{-1}p_t\big)^m \binom{k}{m} p^k q_k\nonumber \\&= g_0+ {p_t^{-1} \over 1-(1-p_t)^{-1}\sum\limits_{k = 2}^\infty k p^k q_k} \sum\limits_{k=2}^\infty \sum\limits_{m = 2}^k \binom{k}{m} \big(z(1-p_t)^{-1}p_t\big)^m p^k q_k\nonumber \\&= g_0+ {p_t^{-1} \over 1-Q^{\prime}(1-p_t)}\left(Q\big(z+(1-z)(1-p_t)\big)-Q(1-p_t) -zp^{\prime}_tQ(1-p_t) \right) \nonumber \\&=z+g_0+ {Q\big(z+(1-z)(1-p_t)\big)-Q(1-p_t) -zp_t \over p_t\big(1-Q^{\prime}(1-p_t)\big)},\end{align}

by the binomial theorem. Next, we plug $z=1$ into (50), obtaining

\begin{equation*}g_0={Q(1-p_t)-(1-p_t) \over p_t\big(1-Q^{\prime}(1-p_t)\big)},\end{equation*}

as $G(1)=1$ . Hence, (50) can be rewritten as (21). We proceed by differentiating ${d \over dz}$ in (21), obtaining

(51) \begin{equation}G^{\prime} (z)={Q^{\prime}(1-p_t+zp_t)-Q^{\prime}(1-p_t) \over 1-Q^{\prime}(1-p_t)}.\end{equation}

An edge in $\mathcal{S}_t(\varphi,T)$ is a union of edges in the tree obtained after pruning T, but before the series reduction, separated by the degree-two vertices. The probability of a degree-two vertex after pruning (but before the series reduction) is

\begin{equation*}\sum\limits_{k=2}^\infty q_k k p_t (1-p_t)^{k-1}=p^{\prime}_tQ (1-p_t).\end{equation*}

Hence, by Wald’s equation, the edge lengths in $\mathcal{S}_t(\varphi,T)$ are independent exponential random variables, each with rate

\begin{equation*}\lambda \big(1-Q^{\prime}(1-p_t)\big).\end{equation*}

Finally, we observe that if $\mu(T)$ is critical, then $Q^{\prime}(1)=1$ and (51) imply $G^{\prime} (1)=1$ . That is, $\nu(T\,|T\not= \phi)$ is a critical Galton–Watson measure.

Acknowledgement

We are thankful to Matthias Winkel for pointing out to us the connection between the generalized dynamical pruning and the hereditary reduction.

Funding information

This research is supported by NSF awards DMS-1412557 (Y. K.) and EAR-1723033 (I. Z.).

Competing interests

There were no competing interests to declare which arose during the preparation or publication process of this article.

References

Abraham, R. and Delmas, J. F. (2015). $\beta $ -coalescents and stable Galton–Watson trees. ALEA Lat. Am. J. Prob. Math. Statist. 12, 451476.Google Scholar
Abramowitz, M. and Stegun, I. A. (eds) (1964). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. National Bureau of Standards, Washington, DC.Google Scholar
Athreya, K. B. and Ney, P. E. (1972). Branching Processes. Springer, Berlin, Heidelberg.CrossRefGoogle Scholar
Bingham, N. H., Goldie, C. M. and Teugels, J. L. (1989). Regular Variation. Cambridge University Press.Google Scholar
Burd, G. A., Waymire, E. C. and Winn, R. D. (2000). A self-similar invariance of critical binary Galton–Watson trees. Bernoulli 6, 121.CrossRefGoogle Scholar
Devroye, L. and Kruszewski, P. (1994). A note on the Horton–Strahler number for random trees. Inf. Process. Lett. 56, 9599.CrossRefGoogle Scholar
Duquesne, T. and Le Gall, J.-F. (2002). Random Trees, Lévy Processes and Spatial Branching Processes (Astérisque 281). Société Mathématique de France, Paris.Google Scholar
Duquesne, T. and Winkel, M. (2007). Growth of Lévy trees. Prob. Theory Relat. Fields 139, 313371.CrossRefGoogle Scholar
Duquesne, T. and Winkel, M. (2019). Hereditary tree growth and Lévy forests. Stoch. Process. Appl. 129, 36903747.CrossRefGoogle Scholar
Evans, S. N. (2008). Probability and Real Trees: École d’Été de Probabilités de Saint-Flour XXXV-2005. Springer, Berlin, Heidelberg.CrossRefGoogle Scholar
Evans, S. N., Pitman, J. and Winter, A. (2006). Rayleigh processes, real trees, and root growth with re-grafting. Prob. Theory Relat. Fields 134, 81126.CrossRefGoogle Scholar
Feller, W. (1971). An Introduction to Probability Theory and Its Applications, Vol. II, 2nd edn. John Wiley, New York.Google Scholar
Harris, T. E. (1963). The Theory of Branching Processes. Springer, Berlin, Heidelberg.CrossRefGoogle Scholar
He, H. and Winkel, M. (2014). Invariance principles for pruning processes of Galton–Watson trees. Preprint. Available at https://arxiv.org/abs/1409.1014.Google Scholar
Horton, R. E. (1945). Erosional development of streams and their drainage basins: hydrophysical approach to quantitative morphology. Geol. Soc. Amer. Bull. 56, 275370.CrossRefGoogle Scholar
Kesten, H. (1987) Subdiffusive behavior of random walk on a random cluster. Ann. Inst. H. Poincaré Prob. Statist. 22, 425487.Google Scholar
Kovchegov, Y. and Zaliapin, I. (2016). Horton law in self-similar trees. Fractals 24, article no. 1650017.CrossRefGoogle Scholar
Kovchegov, Y. and Zaliapin, I. (2019). Random self-similar trees and a hierarchical branching process. Stoch. Process. Appl. 129, 25282560.CrossRefGoogle Scholar
Kovchegov, Y. and Zaliapin, I. (2020). Dynamical pruning of rooted trees with applications to 1D ballistic annihilation. J. Statist. Phys. 181, 618672.CrossRefGoogle Scholar
Kovchegov, Y. and Zaliapin, I. (2020). Random self-similar trees: A mathematical theory of Horton laws. Prob. Surveys 17, 1213.CrossRefGoogle Scholar
Kovchegov, Y. and Zaliapin, I. (2021). Invariance and attraction properties of Galton–Watson trees. Bernoulli 27, 17891823.CrossRefGoogle Scholar
Kovchegov, Y., Zaliapin, I. and Ben-Zion, Y. (2022) Invariant Galton–Watson branching process for earthquake occurrence. To appear in Geophys. J. Internat. Available at https://doi.org/10.1093/gji/ggac204.CrossRefGoogle Scholar
Le Jan, Y. (1991). Superprocesses and projective limits of branching Markov process. Ann. Inst. H. Poincaré Prob. Statist. 27, 91106.Google Scholar
McConnell, M. and Gupta, V. (2008). A proof of the Horton law of stream numbers for the Tokunaga model of river networks. Fractals 16, 227233.CrossRefGoogle Scholar
Neveu, J. (1986). Erasing a branching tree. Adv. Appl. Prob. 1, 101108.Google Scholar
Neveu, J. and Pitman, J. (1989). Renewal property of the extrema and tree property of the excursion of a one-dimensional Brownian motion. In Séminaire de Probabilités XXIII, Springer, Berlin, Heidelberg, pp. 239247.CrossRefGoogle Scholar
Neveu, J. and Pitman, J. (1989). The branching process in a Brownian excursion. In Séminaire de Probabilités XXIII, Springer, Berlin, Heidelberg, pp. 248257.CrossRefGoogle Scholar
Newman, W. I., Turcotte, D. L. and Gabrielov, A. M. (1997). Fractal trees with side branching. Fractals 5, 603614.CrossRefGoogle Scholar
Peckham, S. D. (1995). New results for self-similar trees with applications to river networks. Water Resources Res. 31, 10231029.CrossRefGoogle Scholar
Strahler, A. N. (1957). Quantitative analysis of watershed geomorphology. Trans. Am. Geophys. Union 38, 913920.CrossRefGoogle Scholar
Whittaker, E. T. and Watson, G. N. (1927). A Course of Modern Analysis, 4th edn. Cambridge University Press.Google Scholar
Zolotarev, V. M. (1957). More exact statements of several theorems in the theory of branching processes. Theory Prob. Appl. 2, 256266.CrossRefGoogle Scholar