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.

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.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.

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)$ .