Expected number of induced subtrees shared by two independent copies of the terminal tree in a critical branching process

Consider a rooted binary tree $T$, with $n$ leaves (pendant vertices) labelled by elements from $[n]$. We visualize this tree with the root on top and the leaves at bottom. Given $S\subset[n]$, let $v(S)\in V(T)$ denote the lowest common ancestor of leaves in $S$, ($\text{LCA}(S)$.) Introduce the subtree of $T$ formed by the paths from $v(S)$ to leaves in $S$. Ignoring (suppressing) degree-2 vertices of this subtree (except the root itself), we obtain a rooted binary tree with leaf-set $S$. This binary tree is called “a tree induced by $S$ in $T$”.

Finden and Gordon [11] and Gordon [13] introduced a notion of a “maximum agreement subtree” (MAST) for a pair of such trees $T^{\prime}$ and $T^{\prime\prime}$: it is a tree $\mathcal{T}$ with a largest leaf-set $S\subset[n]$ such that $\mathcal{T}$ is induced by $S$ both in $T^{\prime}$ and $T^{\prime\prime}$. In a pioneering paper [7], Bryant, McKenzie and Steel addressed the problem of a likely order of $\text{MAST}(T^{\prime}_{n},T^{\prime\prime}_{n})$ when $T^{\prime}_{n}$ and $T^{\prime\prime}_{n}$ are two independent copies of a random binary tree $T_{n}$. To quote from [7], such a problem is “relevant when comparing evolutionary trees for the same set of species that have been constructed from two quite different types of data”.

It was proved in [7] that $\text{MAST}(T^{\prime}_{n},T^{\prime\prime}_{n})\leq(1+o(1))e2^{-1/2}n^{1/2}$ with probability $1-o(1)$ as $n\to\infty$. The proof was based on a remarkable property of the uniformly random rooted binary tree, and of few other tree models, known as “sampling consistency”, see Aldous [1]. As observed by Aldous [3], [4], sampling consistency makes this model conceptually close to a uniformly random permutation of $[n]$. Combinatorially, it means that a rooted binary tree $\mathcal{T}$ with with a leaf-set $S\subset[n]$, $|S|=s$, is induced by $S$ in exactly $\frac{(2n-3)!!}{(2a-3)!!}$ rooted binary trees with leaf-set $[n]$, regardless of choice of $\mathcal{T}$. Probabilistically, the rooted binary tree induced by $S$ in $T_{n}$ is distributed uniformly on the set of all $(2s-3)!!$ such trees. Mike Steel [23] pointed out that the sampling consistency of the rooted binary tree follows directly from a recursive process for generating all the rooted trees in which $S$ induces $\mathcal{T}$.

Bernstein, Ho, Long, Steel, St. John, and Sullivant [6] established a qualitatively similar upper bound $O(n^{1/2})$ for the likely size of a common induced subtree in a harder case of Yule-Harding tree, again relying on sampling consistency of this tree model. Recently Misra and Sullivant [19] were able to prove the estimate $\Theta(n^{1/2})$ for the case when two independent binary trees with $n$ labelled leaves are obtained by selecting independently, and uniformly at random, two leaf-labelings of the same unlabelled tree. Using the classic results on the length of the longest increasing subsequence in the uniformly random permutation, the authors of [6] established a first power-law lower bound $cn^{1/8}$ for the likely size of the common induced subtree in the case of the uniform rooted binary tree, and a lower bound $cn^{a-o(1)}$, $a=0.344\dots$, for the Yule-Harding model. Very recently, Aldous [3] proved that a maximum agreement rooted subtree for two independent, uniform, unrooted trees is likely to have $n^{\frac{\sqrt{3}-1}{2}-o(1)}\approx n^{0.366}$ leaves, at least. It was mentioned in [3] that an upper bound $O(n^{1/2})$ could be obtained by “the first moment method (calculating the expected number of large common subtrees)”.

In this paper we show that the total number of unrooted trees with leaf-set $[n]$, which contains a rooted subtree induced by $S\subset[n]$, $s<n$, is $\frac{(2n-5)!!}{(2s-3)!!}$. It follows that a rooted binary tree induced by $S$ in the uniformly random unrooted tree on $[n]$ is again distributed uniformly on the set of all $(2s-3)!!$ rooted trees. Using the asymptotic estimate from [7], we have: a maximum agreement rooted subtree for two independent copies of the uniformly random unrooted tree is likely to have at most $(1+o(1))e2^{-1/2}n^{1/2}$ leaves.

The proof of this $\frac{(2n-5)!!}{(2s-3)!!}$ result suggested that a bound $O(n^{1/2})$ might, just might, be obtained for a broad class of random rooted trees that includes the rooted binary tree, by using a probabilistic counterpart of the two-phase counting procedure. Consider a Markov branching process with a given offspring distribution $\mathbb{p}=\{p_{j}\}_{j\geq 0}$. If $p_{0}>0$ and $\sum_{j}jp_{j}=1$ (critical case), then the process is almost surely extinct.

Let $T_{t}$ be the random terminal tree, and let $T_{n}$ be $T_{t}$ conditioned on the event “$T_{t}$ has $n$ leaves”, which we label, uniformly at random, by elements of $[n]$. The uniform binary rooted tree is a special case corresponding to $p_{0}=p_{2}=1/2$. In general, we assume that $p_{1}=0$, $\text{g.c.d.}(j:\,p_{j+1}>0)=1$, and that $P(s):=\sum_{j}p_{j}s^{j}$ has convergence radius $R>1$, all the conditions being met by the binary case. We will show that $\mathbb{P}_{n}:=\mathbb{P}(T_{t}\text{ has }n\text{ leaves})>0$ for all $n$, meaning that $T_{n}$ is well-defined for all $n$.

Finally, an out-degree of a vertex in $T_{n}$ may now exceed $2$. So we add to the definition of a tree $\mathcal{T}$, induced by $S$ in $T_{n}$, a condition: the out-degree of every vertex from $V(\mathcal{T})$ in $T_{n}$ is the same as its out-degree in $\mathcal{T}$.

Under the conditions above, we prove that a rooted binary tree $\mathcal{T}$ with leaf-set $S\subset[n]$, and edge-set $E(\mathcal{T})$, is induced by $S$ in $T_{n}$ with probability

Here $\Phi(y)$ ($\Phi_{1}(y)$, respectively) is the probability generating function of the total number of leaves in the terminal tree (conditioned on the event “the progenitor has at least two children”, respectively.). We will check that for $p_{0}=p_{2}=1/2$ this formula reduces to $\frac{1}{(2s-3)!!}$. Note that in general, because of the factor $\mathbb{P}(\mathcal{T})$, and $e(\mathcal{T})$, the probability of $\mathcal{T}$ being induced by $S$ in $T_{n}$ depends not only on $|S|$, but also on the whole out-degree sequence of $\mathcal{T}$.

We use the above identity to prove the following claim. Let

Then, for $\varepsilon\in(0,1/2]$, with probability $\geq 1-(1-\varepsilon)^{(1+\varepsilon)c(\mathbb{p})n^{1/2}}$, the largest number of leaves in an induced subtree shared by two independent copies of the conditioned terminal tree $T_{n}$ is at most $(1+\varepsilon)c(\mathbb{p})n^{1/2}$.

For a wide ranging exposition of combinatorial/probabilistic problems and methods in theory of phylogeny, we refer the reader to a book [22] by Steel.

Consider a rooted binary tree $T$ with leaf-set $[n]$. For a given $S\subset[n]$, there exists a subtree with leaf-set $S$, which is rooted at the lowest vertex common to all $|S|$ paths leading away from $S$ toward the root of $T$. The vertex set of this lowest common ancestor (LCA) tree is the set of all vertices from the paths in question. Ignoring degree-2 vertices of this subtree (except the root itself), we obtain a rooted binary tree $\mathcal{T}$. This LCA subtree has a name “a tree induced by $S$ in $T$”, see [3].

Let $T^{\prime}_{n},T^{{}^{\prime\prime}}_{n}$ be two independent copies of the uniformly random rooted binary tree with leaf-set $[n]$. Let $X_{n,a}$ denote the random total number of leaf-sets $S\subset[n]$ of cardinality $a$ that induce the same rooted subtree in $T_{n}^{\prime}$ and $T^{{}^{\prime\prime}}_{n}$. Bernstein et al. [6] proved that

The proof was based on sampling consistency of the random tree $T_{n}$, so that $N(\mathcal{T})$, the number of rooted trees on $[n]$ in which $S$ induces a given rooted tree $\mathcal{T}$ on $S$, is $\frac{(2n-3)!!}{(2a-3)!!}$, thus dependent only on the leaf-set size.

Following [3] (see Introduction), we consider the case when a binary tree with leaf-set $[n]$ is unrooted. Let now $T^{\prime}_{n},T^{{}^{\prime\prime}}_{n}$ be two independent copies of the uniformly random (unrooted) binary tree with leaf-set $[n]$. Let $X_{n,a}$ denote the random total number of leaf-sets $S\subset[n]$ of cardinality $a$ that induce the same rooted subtree in $T_{n}^{\prime}$ and $T^{{}^{\prime\prime}}_{n}$.

Consider a branching process initiated by a single progenitor. This process is visualized as a growing rooted tree. The root is the progenitor, connected by edges to each of the vertices, that represent the root’s “children”, i.e. the root’s immediate offspring. Each of the children becomes the root of the corresponding (sub)tree, so that the ordered children of all these roots are the grandchildren of the progenitor. We obviously get a recursively defined process; it delivers a nested sequence of trees, which is either infinite, or terminates at a moment when none of the members of the last generation have children.

The classic Galton-Watson branching process is the case when the number of each member’s children (a) is independent of those numbers for all members from the preceding and current generations and (b) has the same distribution $\{p_{j}\}_{j\geq 0}$, $(\sum_{j}p_{j}=1)$. It is well-known that if $p_{0}>0$ and $\sum_{j\geq 0}jp_{j}=1$, then the process terminates with probability $1$, Harris [15]. Let $T_{t}$ denote the terminal tree. Given a finite rooted tree, $T$, we have

where $d(v,T)$ is the out-degree of vertex $v\in V(T)$. $X_{t}:=|V(T_{t})|$, the total population size by the extinction time, has the probability generating function (p.g.f) $F(x):=\mathbb{E}[x^{X_{t}}]$, $|x|\leq 1$, that satisfies

Indeed, introducing $F_{\tau}(x)$ the p.g.f. of the total cardinality of the first $\tau$ generations, we have

So letting $\tau\to\infty$, we obtain (3.1). In the same vein, consider the pair $(X_{t},Y_{t})$, where $Y_{t}:\bigl{|}\{v\in V(T_{t}):\,d(v,T_{t})=0\}\bigr{|}$ is the total number of leaves (zero out-degree vertices) of the terminal tree. Then denoting $G(x,y)=\mathbb{E}\bigl{[}x^{X_{t}}y^{Y_{t}}\bigr{]}$, $(|x|,\,|y|\leq 1)$, we have

So, with $\Phi(y):=\mathbb{E}\bigl{[}y^{Y}\bigr{]}=G(1,y)$, we get

Importantly, this identity allows us to deal directly with the leaf set at the extinction moment: $\mathbb{P}_{k}:=[y^{k}]\,\Phi(y)$ is the probability that $T_{t}$ has $k$ leaves. In particular, $\mathbb{P}_{1}=[y^{1}]\Phi(y)=p_{0}>0$. More generally, $\mathbb{P}_{k}>0$ for all $k\geq 1$. meaning that $\mathbb{P}(T_{t}\text{ has }k\text{ leaves})>0$ for all $k\geq 1$. Indeed, for $k\geq 2$, we have

so the claim follows by easy induction on $k$.

If $p_{0}=p_{2}=1/2$, then the branching process is a nested sequence of binary trees. The equation (3.3) yields

So the terminal tree $T_{t}$ has $n$ leaves with probability $\frac{(2n-3)!!}{2^{n}n!}>0$. On this event, call it $A_{n}$, the total number of vertices is $2n-1$, and each of rooted binary trees with $2n-1$ vertices is a value of the terminal tree of the same probability $(1/2)^{2n-1}$. Conditionally on the event $A_{n}$, we label, uniformly at random, the leaves of $T_{t}$ by elements of $[n]$ and use notation $T_{n}$ for the resulting uniformly random, rooted binary tree.

This is a promising sign that we can extend what we did for the uniformly random binary trees, i.e. for $p_{0}=p_{2}=1/2$, for a more general offspring distribution $\{p_{j}\}$.

We continue to assume that $p_{1}=0$. The notion of an induced subtree needs to be expanded, since an out-degree of a vertex now may exceed $2$. Let $\mathcal{T}$ be a tree with a leaf-set $S\subset[n]$, such that every non-leaf vertex of $\mathcal{T}$ has out-degree $2$, at least. We say that $S$ induces $\mathcal{T}$ in a tree $T_{n}$ provided that: (a) the LCA subtree for $S$ in $T_{n}$ is $\mathcal{T}$ if we ignore vertices of total degree $2$ in this LCA subtree; (b) the out-degree of every other vertex in the LCA of $S$ in $T_{n}$ is the same as its out-degree in $\mathcal{T}$.

Let $\mathcal{T}$ be a tree with the leaf-set $S$, $|S|=a<n$, $b\leq n-a$. Let $A_{n}(\mathcal{T},b)\subset A_{n}$ be the event: (i) some $b$ elements from $[n]\setminus S$ are chosen as the leaves of all the complementary subtrees rooted at degree -2 vertices sprinkled on the edges of $\mathcal{T}$, forming a composed tree with $a+b$ leaves; (ii) the tree with $n$ leaves is obtained by using the remaining $n-a-b$ leaves and an extra leaf which is the root of the tree composed in step (i). The event $A_{n}(\mathcal{T},b)$ is partitioned into disjoint $\binom{n-a}{b}$ events corresponding to all choices to select $b$ elements of $[n]\setminus S$ in question.

Let $e(\mathcal{T})$ be the total number of edges in $\mathcal{T}$. For each of these choices, on the event $A_{n}(\mathcal{T},b)$ we must have some $k\leq b$ trees with ordered roots on some of $e(\mathcal{T})$ edges, and with their respective, nonempty, leaf-set labels forming an ordered set partition of the set of $b$ leaves. The root of each of these trees has one child down the host “edge” of $\mathcal{T}$, and all the remaining children outside edges of $\mathcal{T}$. Since $p_{1}=0$, the number of other children of a root is $j$ with conditional probability $(1-p_{0})^{-1}p_{j+1}$. So the number of leaves of the subtrees rooted at the children is $i$ with probability $[y^{i}]\Phi_{1}(y)$, where

Therefore, conditionally on “$S$ induces $\mathcal{T}$”, a given set of $b$ elements of $[n]$ is the leaf-set of these complementary trees with probability

Explanation: $k$ is a generic total number of trees rooted at ordered internal points of some $j$ edges of $\mathcal{T}$; $b_{t}$ is a generic number of leaves of a $t$-th tree; the product of two binomial coefficients in the top line is the number of ways to pick $j$ edges of $\mathcal{T}$ and to select an ordered, $j$-long, composition of $k$; the sum is the probability that the $k$ trees have $b$ leaves in total.

With these complementary trees attached, we obtain a tree with $a+b$ leaves. So for $A_{n}(\mathcal{T},b)$ to hold, we view the root of this tree (i.e. the root of $\mathcal{T}$) as a leaf and complete determination of a tree with $n$ leaves by constructing an auxiliary tree with $1$ plus $(n-a-b)$ remaining leaves. Therefore using the definition of $\Phi(y)$, we have

Here $\mathbb{P}(\mathcal{T}):=\prod_{v\in V_{\text{int}}(\mathcal{T})}p_{d(v,\mathcal{T})}$, where $\{d(v,\mathcal{T})\}$ is the out-degree sequence of non-leaf vertices of $\mathcal{T}$.

Using $j\,[y^{j}]\Phi(y)=[y^{j-1}]\Phi^{\prime}(y)$, $j\geq 1$, and summing the last equation for $0\leq b\leq n-a$, we obtain

For a partial check of (3.5), let us return to $p_{0}=p_{2}=1/2$. Here

Therefore

so, by (3.5), we have

Since $\mathbb{P}(A_{n})=\frac{(2n-3)!!}{2^{n}n!}$, we conclude that

for every binary tree $\mathcal{T}$ with leaf-set $S\subset[n]$, $|S|=a$. The LHS is the probability that $S$ induces $\mathcal{T}$ in the uniformly random binary tree $T_{n}$.

To summarize, we proved

Note. For $p_{0}=p_{2}=1/2$, $\mathbb{P}\bigl{(}A_{n}(\mathcal{T})\bigr{)}$ turned out to be dependent only on the number of leaves of $\mathcal{T}$. The formula (3.7) clearly shows that, in general, this probability depends on shape of $\mathcal{T}$. Fortunately, this dependence is confined to a single factor $\mathbb{P}(\mathcal{T})$, since the rest depends on two scalars, $a$ and $e(\mathcal{T})$. Importantly, these quantities are of the same order of magnitude. Indeed, if $\mathbb{P}(\mathcal{T})>0$ then $e(\mathcal{T})\geq\max\bigl{(}a,2|V_{\text{int}}(\mathcal{T})|\bigr{)}$, i.e.

so that