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
The respective branching probabilities are $q_0=q$ , $q_1=0$ , $q_2=(1-q)/2q$ , and
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
We notice that
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:
-
(i) ${\rm{\small SHAPE}}(T) \stackrel{d}{\sim} \mathcal{IGW}(q)$ ;
-
(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.,
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:
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
where g(x) is defined as follows. Let $X \stackrel{d}{\sim} \{q_k\}$ be a progeny random variable; then
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
exists, and
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
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.,
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:
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:
Then Assumption 2.1 is satisfied, and
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}}^|$ ,
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$ ,
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
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
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]:
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
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]:
Example 2.3. (Pruning via the tree length) Let the function $\varphi(T)$ equal the total length of $T\in{\mathcal{L}}$ :
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
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$ ,
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
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$ :
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
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
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
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
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)$ :
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
where $\,p_t=p_t(\lambda,\varphi)=\mathbb{P}\big({\mathcal{S}}_t(\varphi,T) \not= \phi\big)$ , and generating function
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
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
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
and the cumulative distribution function
Example 3.1. Let $q={1 \over 2}$ . Then $\ell(x)$ is already known (see [Reference Kovchegov and Zaliapin19, Reference Kovchegov and Zaliapin20]):
Next, we use the multinomial approach to show that (25) matches Equation (23) for $q={1 \over 2}$ . First, we rewrite (25):
Recall that
and
and therefore
implying
Now,
Hence,
Thus, substituting (27) into (26), we obtain
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
Example 3.2. For $q={1 \over 2}$ , L(x) is expressed as follows [Reference Kovchegov and Zaliapin19, Reference Kovchegov and Zaliapin20]:
Thus, since $I_a(z) \sim {1 \over \sqrt{2\pi z}}e^z$ for all $a \geq 0$ , we have
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
with the cumulative distribution function
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
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$ ,
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
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)$ ,
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
where by Theorem 3.1, ${\mathcal{E}} _t(\lambda)=\lambda p_t^{(1-q)/q}={\lambda \over \lambda(1-q) t+1}$ . Hence,
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$ ,
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$ ,
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:
-
(a) The second moment assumption is satisfied:
\begin{equation*}\sum \limits_{k=2}^\infty k^2 q_k <\infty.\end{equation*} -
(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$ ,
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$ ,
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
where $R_{H_1},\,R_{H_2},\dots$ are the corresponding hereditary reductions. Then, for $\,T \stackrel{d}{\sim} \mu$ ,
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)$ .
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
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
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
Taking the Fourier transform, we obtain
which simplifies to
where
Therefore,
where integration by parts yields
Substituting (35) back into (34) yields
which by Parseval’s equation implies the following ordinary differential equation:
Next, we solve the differential equation (36) above via integration, obtaining
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)$ ,
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
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
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
we have
Therefore, by the Lagrange inversion theorem (Theorem A.1), we obtain
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
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:
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
which simplifies to
Letting $\,z={\lambda q \over t}$ and $\Lambda={\mathcal{L}}[\ell]\left({\lambda q \over z}\right)={\mathcal{L}}[\ell](t)$ , we have
Then Lemma 4.1 yields
Finally, we invert the Laplace transform ${\mathcal{L}}[\ell](t)$ , obtaining
Proof of Proposition 3.1. Observe that
Thus, by (41), we have
and therefore,
Hence, by the Hardy–Littlewood–Karamata Tauberian theorem for Laplace transforms [Reference Feller12],
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
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,
and therefore,
Lemma 4.1 yields
Thus, since $\,a(z)=\sum\limits_{n=1}^\infty z^n \,\alpha(n)$ , Equation (29) follows. Finally, the cumulative distribution function equals
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
The rest of the proof follows from Lemma 2.5 as
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
Combining the above yields
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
Let $R(z)=\frac{Q(z)-z}{q_0}$ ; then Equation (44) can be rewritten as
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
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
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:
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)$ ,
and
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
exists and and is equal to the limit L defined in (7).
Proof. Note that for $x \in ({-}1,1)$ ,
Thus, by Assumption 2.1, the limit
either exists or is equal to $\,\pm\infty$ . Hence, by L’Hôpital’s rule,
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.,
Proof. For $\alpha>-L-1$ , L’Hôpital’s rule and Lemma 4.2 yield
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
where L is as defined in (7).
If the Galton–Watson measure $\mathcal{GW}(\{q_k\})$ (with $q_1=0$ ) is subcritical, then
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
Thus, as
Lemma 4.2 yields
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
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
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
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.
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:
Moreover, for any $\varphi\,:\,\mathbb{C}\to\mathbb{C}$ analytic in a neighborhood around the origin,
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
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
and
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:
-
(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$ . -
(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.,
Let $T|_{=s}$ denote the points in T at distance s from the root $\rho$ , i.e.,
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
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. 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. 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
be a sigma-algebra generated by the future events of $\,\mathcal{S}_t(\varphi,T)|_{=s}$ , after time s. Then, since
we have
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. 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. 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
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$ ,
Therefore, for $m \geq 2$ ,
The corresponding generating function of $\{g_k\}$ is equal to
by the binomial theorem. Next, we plug $z=1$ into (50), obtaining
as $G(1)=1$ . Hence, (50) can be rewritten as (21). We proceed by differentiating ${d \over dz}$ in (21), obtaining
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
Hence, by Wald’s equation, the edge lengths in $\mathcal{S}_t(\varphi,T)$ are independent exponential random variables, each with rate
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.