# Fringe trees of Patricia tries and compressed binary search trees

Svante Janson  Department of Mathematics, Uppsala University, PO Box 480,
SE-751 06 Uppsala, Sweden<EMAIL_ADDRESS>
(Date: 2 May, 2024)

###### Abstract.

We study the distribution of fringe trees in Patricia tries and compressed
binary search trees; both cases are random binary trees that have been
compressed by deleting vertices of outdegree 1 so that they are random full
binary trees. The main results are central limit theorems for the number of
fringe trees of a given type, which imply quenched and annealed limit results
for the fringe tree distribution; for Patricia tries, this is complicated by
periodic oscillations in the usual manner. We also consider extended fringe
trees. The results are derived from earlier results for uncompressed tries and
binary search trees. In the case of compressed binary search trees, it seems
difficult to give a closed formula for the asymptotic fringe tree
distribution, but we provide a recursion and give examples.

###### 2020 Mathematics Subject Classification:

60C05, 05C05, 60F05

Supported by the Knut and Alice Wallenberg Foundation and the Swedish Research
Council

##  1\. Introduction

We consider in this paper fringe tree distributions for some different types
of random binary trees. It is well known that there are two types of tress
that are called binary trees. We use the following (common, but not universal)
notation. A _binary tree_ is a rooted tree such that each child of a node is
labelled either _left_ or _right_ , and each node has at most one left and at
most one right child. A _full binary tree_ is a binary tree where each node
has outdegree 0 or 2. (In the latter case, it thus has one left and one right
node.) A _leaf_ is a node with no children (i.e., outdegree 0). The _size_
$|T|$ of a tree $T$ is its number of nodes. All trees in the paper are non-
empty, finite, and binary (and thus rooted), except when we explicitly say
otherwise.

Is is well known that a full binary tree has odd size, and that there is a
bijection between binary trees of size $n\geq 1$ and full binary trees of size
$2n+1$ defined as follows: given a binary tree, add new leaves at all possible
places, i.e., add one new leaf to each node of outdegree 1, and two new leaves
to each node of outdegree 0; conversely, given a full binary tree, delete all
its leaves. For many purposes, the two types of binary trees are thus
equivalent, but both types are important, and there are several reasons for
studying both types of binary trees.

In the present paper we will mainly study another relation between binary
trees and full binary trees. Given a binary tree $T$, its _compression_
${\widehat{T}}$ is the full binary tree obtained by deleting all nodes of
outdegree 1 (and connecting the remaining nodes in the obvious way). This is
obviously not a bijection; there is no way to reconstruct the binary tree
without further information. Note also that the size of the compressed tree
typically is smaller; we have $1\leq|{\widehat{T}}|\leq|T|$, and every size in
this range is possible.

One well known example of compression is for tries: a _trie_ is a binary tree
constructed from a sequence of distinct infinite strings of 0 and 1 (see
Section 2.2 for details), and its compression is known as a _Patricia trie_ ;
see [29, Section 6.3] for the computer science background. We study in this
paper tries and Patricia tries defined by independent random strings where all
bits are independent. We denote the random trie defined by $n$ random strings
by $\Upsilon_{n}$, and the corresponding Patricia trie by
$\widehat{\Upsilon}_{n}$.

The _Binary Search Tree (BST)_ is another commonly studied random binary tree.
(See Section 2.3 for definition.) Just as tries and Patricia tries, it appears
naturally in computer science in connection with sorting and searching, see
e.g [29, Section 6.2.2]. Unlike tries, the compressed version is perhaps not
so interesting in that context, but we study here the different random binary
trees from a purely mathematical perspective, and we find it natural to study
also the _compressed Binary Search Tree_ , and compare it to other random full
binary trees. We denote the random BST with $n$ nodes by $\mathcal{B}_{n}$,
and its compression by $\widehat{\mathcal{B}}_{n}$.

In this paper we focus on fringe trees of the various random trees. Recall
that for a rooted tree $T$ and a node $v\in T$, the _fringe tree_ $T^{v}$ is
the subtree of $T$ consisting of $v$ and all its descendants; the fringe tree
$T^{v}$ is a rooted tree with root $v$, and if $T$ is a binary tree or a full
binary tree, then so is each of its fringe trees. If $T$ and $t$ are two
binary trees, let $N_{t}(T)$ be the number of fringe trees of $T$ that are
equal to $t$ (in the sense of isomorphic as binary trees), i.e.,

$\displaystyle N_{t}(T):=\bigl{\lvert}\\{v\in T:T^{v}=t\\}\bigr{\rvert}.$
(1.1)

Here $t$ will always be a fixed tree (think of it as small), while $T$ usually
will be a (big) random tree; then $N_{t}(T)$ is a random variable. We consider
also the random fringe tree $T^{*}$ defined as $T^{v}$ for a node $v\in T$
chosen uniformly at random. (If $T$ is random, we first condition on $T$ and
then choose a node $v$ in it.) Thus, for every fixed binary tree $t$ and a
non-random binary tree $T$,

$\displaystyle\operatorname{\mathbb{P}{}}(T^{*}=t)=\frac{N_{t}(T)}{|T|},$
(1.2)

for a random binary tree $T$, (1.2) holds conditionally on $T$, and thus

$\displaystyle\operatorname{\mathbb{P}{}}(T^{*}=t)=\operatorname{\mathbb{E}}{}\frac{N_{t}(T)}{|T|}.$
(1.3)

See [1] for a general study of fringe tree distributions, including explicit
results for several classes of random trees.

We consider asymptotics as the size of the random tree tends to infinity. When
$T$ is a random trie $\Upsilon_{n}$ or a binary search tree $\mathcal{B}_{n}$,
the asymptotic distribution of the random fringe tree $T^{*}$ is given already
by [1]. More precise result including asymptotic normality of the fringe tree
counts $N_{t}(T)$ are proved in [28] (tries) and [9], [10] (BST), see also e.g
[13], [23], and [20]. Our main results below use these results to show
corresponding results for Patricia tries and compressed binary search trees.
In particular, in both cases the counts $N_{t}(T)$ are asymptotically normal.

For Patricia tries $\widehat{\Upsilon}_{n}$, we find explicitly the
asymptotics of the mean and variance of $N_{t}(\widehat{\Upsilon}_{n})$, and
thus the asymptotic distribution of the random fringe tree
$\widehat{\Upsilon}_{n}^{*}$. For the compressed BST
$\widehat{\mathcal{B}}_{n}$, this seems more difficult. We show how to find
explicitly the asymptotics of the mean
$\operatorname{\mathbb{E}}{}N_{t}(\widehat{\mathcal{B}}_{n})$ and,
equivalently, the asymptotic distribution of the random fringe tree
$\widehat{\mathcal{B}}^{*}_{n}$, but this is done by a recursion and we cannot
give a general formula. We leave as an open problem to find a formula for the
asymptotic variance of $N_{t}(\widehat{\mathcal{B}}_{n})$ for the compressed
BST.

######  Remark 1.1.

A _cladogram_ is a full binary tree where we do not care about the
orientations, i.e, we do not distinguish between left and right. (Formally, we
may see a cladogram as an equivalence classe of full binary trees.) In
particular, the Patricia tries and compressed binary search trees studied here
may be regarded as random cladograms by forgetting all orientations. The
results below yield as corollaries corresponding results for fringe trees
(which now are random cladograms) of these; we omit the details. See also
Remark A.1.

A very different model of random cladograms is studied by Aldous [3, 4]; the
results obtained here may be compared to results for fringe trees in that
model [in preparation].  $\triangle$

######  Remark 1.2.

Related results of fringe trees in other classes of random trees have been
given by many authors, see for example [1], [5], [12], [15], [7], [8], [16],
[19], [20], [27], [21], [22], [28], [6], and the further references therein.
$\triangle$

##  2\. Preliminaries

###  2.1. Notation

For a rooted tree $T$, the set of leaves of $T$ is denoted ${\mathcal{L}}(T)$.
The leaves are also called _external nodes_ and the other nodes, i.e, those
with outdegree $>0$, are called _internal nodes_. The number of nodes of $T$
is denoted $|T|$, and the number of leaves (external nodes) by
$|T|_{\mathsf{e}}:=|{\mathcal{L}}(T)|$. Recall that in a binary tree $T$, the
number of nodes of outdegree 2 is $|T|_{\mathsf{e}}-1$, and thus the number of
nodes of outdegree 1 is $|T|-2|T|_{\mathsf{e}}+1$. Hence, if $T$ is a full
binary tree, then

$\displaystyle|T|=2|T|_{\mathsf{e}}-1.$ (2.1)

The _root degree_ $\rho(T)$ is the (out)degree of the root $o\in T$.

We let $\bullet$ denote the tree consisting of a root only, so
$|\bullet|=|\bullet|_{\mathsf{e}}=1$.

Let ${\mathfrak{T}}$ be the set of all binary trees, and
${\widehat{\mathfrak{T}}}$ the subset of all full binary trees, and
$\mathfrak{T}^{\prime}$ the set of all binary trees such that no leaf has a
parent of outdegree 1; thus
${\widehat{\mathfrak{T}}}\subset\mathfrak{T}^{\prime}\subset{\mathfrak{T}}$.
Furthermore, for any set $S\subseteq\\{0,1,2\\}$, let
$\mathfrak{T}^{S}:=\\{T\in{\mathfrak{T}}:\rho(T)\in S\\}$ be the set of all
binary trees with root degree in $S$. In particular,
$\mathfrak{T}^{\\{0\\}}=\\{\bullet\\}$.

If $t$ is a full binary tree, let $\widecheck{{\mathfrak{T}}}_{t}$ be the set
of all binary trees that can be obtained fron $t$ by subdividing the edges,
i.e, by replacing every edge by a path of $\ell\geq 1$ edges; each such path
thus contains $\ell-1$ new nodes of outdegree 1. Note that each new node has
its (only) child as either a left or a right child. Let further
$\widecheck{{\mathfrak{T}}}_{t}^{+}$ be the set of all binary trees that
compress to $t$; note that this is larger than
$\widecheck{{\mathfrak{T}}}_{t}$ since $\widecheck{{\mathfrak{T}}}_{t}^{+}$
allows also adding a path from the root to a new root, but
$\widecheck{{\mathfrak{T}}}_{t}$ does not; in fact,
$\widecheck{{\mathfrak{T}}}_{t}=\widecheck{{\mathfrak{T}}}_{t}^{+}\cap\mathfrak{T}^{\\{0,2\\}}$.
(If $t\neq\bullet$, then
$\widecheck{{\mathfrak{T}}}_{t}=\widecheck{{\mathfrak{T}}}_{t}^{+}\cap\mathfrak{T}^{\\{2\\}}$.)

If $v$ is a node in a binary tree $T$, then the _left depth_
$d_{\mathsf{L}}(v)$ is the number of edges that go from some node to its left
child in the path from the root to $v$. The _right depth_ $d_{\mathsf{R}}(v)$
is defined similarly. Note that $d_{\mathsf{L}}(v)+d_{\mathsf{R}}(v)=d(v)$,
the depth of $v$. When necessary, we write $d_{T}(v)$ for the depth in $T$.

We define the _left external path length_ $\mathsf{LPL}(T)$ and _right
external path length_ $\mathsf{RPL}(T)$ by

$\displaystyle\mathsf{LPL}(T)=\sum_{v\in{\mathcal{L}}(T)}d_{\mathsf{L}}(v),\qquad\mathsf{RPL}(T)=\sum_{v\in{\mathcal{L}}(T)}d_{\mathsf{R}}(v).$
(2.2)

Thus the sum $\mathsf{LPL}(T)+\mathsf{RPL}(T)$ equals the total external path
length $\sum_{v\in{\mathcal{L}}(T)}d(v)$.

The fringe tree $T^{v}$ and the fringe tree counts $N_{t}(T)$ are defined in
the introduction.

We use $\overset{\mathrm{d}}{\longrightarrow}$ and
$\overset{\mathrm{p}}{\longrightarrow}$ to denote convergence in distribution
and probability, respectively, of random variables. We further say that
_$X_{n}\overset{\mathrm{d}}{\longrightarrow}Y$ with all moments_ if
$X_{n}\overset{\mathrm{d}}{\longrightarrow}Y$ and also
$\operatorname{\mathbb{E}}{}X_{n}^{r}\to\operatorname{\mathbb{E}}{}Y^{r}$ for
every integer $r>0$. We let $o_{\mathrm{p}}(1)$ denote any sequence of random
variables $X_{n}$ such that $X_{n}\overset{\mathrm{p}}{\longrightarrow}0$.

$N(\mu,\sigma^{2})$ denotes the normal distribution with mean $\mu$ and
variance $\sigma^{2}\geq 0$. $\operatorname{Po}(\lambda)$ denotes the Poisson
distribution with parameter $\lambda\geq 0$. We thus have

$\displaystyle\operatorname{Po}(\lambda;n):=\operatorname{Po}(\lambda)(n)=\frac{\lambda^{n}}{n!}e^{-\lambda},\qquad
n=0,1,\dots$ (2.3)

We may sometimes abbreviate “uniformly random” to “random”. $\log$ denotes
natural logarithms. Unspecified limits are as ${n\to\infty}$.

In this paper we discuss results for the random fringe tree $T^{*}_{n}$ of a
sequence of random trees $T_{n}$; we state results both conditioned on the
tree $T_{n}$ and unconditioned, and we use the standard terminology and call
such results _quenched_ and _annealed_ , repectively.

###  2.2. Tries

A trie is a rooted tree constructed from a set of $n\geq 1$ distinct strings
$\Xi^{(1)},\Xi^{(2)},\dots,\allowbreak\Xi^{(n)}$ in some alphabet
$\mathcal{A}$; we consider here only the case $\mathcal{A}=\\{0,1\\}$, and
then the trie will be a binary tree. (See e.g [29, Section 6.3] and [11,
Section 1.4.4].) We assume for convenience that the strings are infinite; thus
$\Xi^{(i)}=\xi^{(i)}_{1}\xi^{(i)}_{2}\dotsm\in\\{0,1\\}^{\infty}$ for every
$i$. The trie is constructed recursively. If $n=0$, then the trie is the empty
tree $\emptyset$. Otherwise, we begin with a root, and put every string in the
root. If $n=1$, then we stop there, so the trie equals $\bullet$. Otherwise,
i.e, if $n\geq 2$, we pass all strings to new nodes; all strings beginning
with 0 (if any) are passed to a left child of the root and all strings
beginning with 1 (if any) are passed to a right child of the root. We continue
recursively, the next time partitioning the strings according to the second
letter, and so on, always looking at the first letter not yet inspected. At
the end there is a tree with $n$ leaves, each containing one string.
Equivalently, each string $\Xi^{(i)}$ defines an infinite path $\Gamma_{i}$
from the root in the infinite binary tree, by processing the letters in the
string in order and going to a left child for every 0 and a right child for
every 1. We then stop each path at first node that it does not share with any
other of the paths $\Gamma_{j}$; these nodes are the leaves of the trie, and
the trie is the union of the $n$ stopped paths. Note that in a trie, a parent
of a leaf must have outdegree 2, i.e, a trie belongs to the set
$\mathfrak{T}^{\prime}$.

We will consider the random trie $\Upsilon_{n}$ defined by $n$ random strings
$\Xi^{(1)},\dots,\Xi^{(n)}$ where we assume that the strings are independent,
and furthermore in each string the letters are independent and identically
distributed with distribution $\operatorname{Be}(p)$ for some $p\in(0,1)$,
i.e, each letter $\xi^{(i)}_{k}$ has
$\operatorname{\mathbb{P}{}}(\xi^{(i)}_{k}=1)=p$ and
$\operatorname{\mathbb{P}{}}(\xi^{(i)}_{k}=0)=q:=1-p$. We omit the parameter
$p$ from the notation, but it is implicit when we discuss tries; we use always
the notations $p$ and $q=1-p$ in the sense above.

It is well known that many results for tries show (typically small) periodic
oscillations instead of limits as ${n\to\infty}$, see e.g [29; 31; 14; 17; 25;
18; 24; 28]. More precisely, if $\log p/\log q$ is irrational, then such
oscillations do not occur, but if $\log p/\log q$ is rational they typically
do. We call the case when $\log p/\log q\in\mathbb{Q}$ _periodic_ ; otherwise
we have the _aperiodic_ case. In the periodic case, if $\log p/\log q$ equals
$a/b$ in lowest terms (with $a,b\in\mathbb{N}$), then define

$\displaystyle d=d_{p}:=\frac{-\log p}{a}=\frac{-\log q}{b}>0,$ (2.4)

the greatest common divisor of $-\log p$ and $-\log q$.

The Patricia trie $\widehat{\Upsilon}_{n}$ is obtained by compressing
$\Upsilon_{n}$. Note that the trie $\Upsilon_{n}$ and the Patricia tree
$\widehat{\Upsilon}_{n}$ both have exactly $n$ leaves:

$\displaystyle|\Upsilon_{n}|_{\mathsf{e}}=|\widehat{\Upsilon}_{n}|_{\mathsf{e}}=n.$
(2.5)

The Patricia tree $\widehat{\Upsilon}_{n}$ thus has $n-1$ internal nodes,
while the number of internal nodes in $\Upsilon_{n}$ is random.

###  2.3. Binary search trees

Binary search trees may be constructed in different (but equivalent) ways; we
will use the following, closely connected to the sorting algorithm _Quicksort_
(see e.g [29, Section 6.2.2] and [11, Section 1.4.1]): Consider a set of $n$
distinct items, which we may assume are real numbers $x_{1},\dots,x_{n}$. If
$n=0$, the BST $\mathcal{B}_{0}$ is the empty tree $\emptyset$, and if $n=1$,
$\mathcal{B}_{1}:=\bullet$. If $n\geq 2$, pick one of the $n$ items at random,
and call it the _pivot_. Compare all other elements to the pivot, and let $L$
be the set of all $x_{i}$ that are smaller than the pivot, and let $R$ be the
set of all items $x_{i}$ that are greater than the pivot. (Thus,
$|L|+|R|=n-1$.) The BST $\mathcal{B}_{n}$ is defined as the binary tree with
the root having left and right subtrees that are constructed recursively from
the sets $L$ and $R$, respectively. It is easily seen, by induction, that
$|\mathcal{B}_{n}|=n$; in fact, it is natural to label the root by the pivot,
and then during the recursion each node becomes labelled by exactly one of the
$n$ numbers $x_{i}$. Note that both
$|\mathcal{B}_{n}|_{\mathsf{e}}=|\widehat{\mathcal{B}}_{n}|_{\mathsf{e}}$ and
$|\widehat{\mathcal{B}}_{n}|$ are random. It is shown by Aldous [1, Example
3.3] and Devroye [9, Theorem 2], that, as ${n\to\infty}$,

$\displaystyle|\mathcal{B}_{n}|_{\mathsf{e}}/n=|\widehat{\mathcal{B}}_{n}|_{\mathsf{e}}/n\overset{\mathrm{p}}{\longrightarrow}1/3$
(2.6)

and thus, see (2.1),

$\displaystyle|\widehat{\mathcal{B}}_{n}|/n\overset{\mathrm{p}}{\longrightarrow}2/3.$
(2.7)

More precisely [9],

$\displaystyle\frac{|\mathcal{B}_{n}|_{\mathsf{e}}-n/3}{\sqrt{n}}=\frac{|\widehat{\mathcal{B}}_{n}|_{\mathsf{e}}-n/3}{\sqrt{n}}\overset{\mathrm{d}}{\longrightarrow}N(0,2/45)$
(2.8)

and thus
$\frac{\lvert\widehat{\mathcal{B}}_{n}\rvert-2n/3}{\sqrt{n}}\overset{\mathrm{d}}{\longrightarrow}N(0,8/45)$
by (2.1); see also [30] for expectations and e.g [11, Theorem 6.9] for a more
general result.

###  2.4. Fringe trees of compressed trees

Let $T$ be a binary tree and ${\widehat{T}}$ its compression. Note first that
the leaves of ${\widehat{T}}$ are precisely the leaves of $T$, while the roots
may differ. (In general, there may in $T$ be a path of nodes of outdegree 1
from the root of $T$ to the root of ${\widehat{T}}$.) Thus,
$|{\widehat{T}}|_{\mathsf{e}}=|T|_{\mathsf{e}}$.

Let $t$ be a full binary tree and consider the nodes $v\in{\widehat{T}}$ such
that ${\widehat{T}}^{v}=t$. We consider two cases separately:

  1. (i)

If $t=\bullet$, then: $v\in{\widehat{T}}$ and ${\widehat{T}}^{v}=t$ $\iff$ $v$
is a leaf in ${\widehat{T}}$ $\iff$ $v$ is a leaf in $T$
$\iff$ $v\in T$ and $T^{v}=t$.

  2. (ii)

If $|t|>1$, then the root of $t$ has outdegree 2, and:
$v\in{\widehat{T}}$ and ${\widehat{T}}^{v}=t$ $\iff$ $v$ has outdegree 2 in
$T$ and $t$ is the contraction of $T^{v}$.

Consequently, in both cases,

$\displaystyle v\in{\widehat{T}}\text{ and }{\widehat{T}}^{v}=t\iff v\in
T\text{ and }T^{v}\in\widecheck{{\mathfrak{T}}}_{t},$ (2.9)

where we recall that $\widecheck{{\mathfrak{T}}}_{t}$ is the set of all binary
trees that can be obtained fron $t$ by subdividing the edges.

Define the functional $\varphi$ on binary trees by

$\displaystyle\varphi(T):=\boldsymbol{1}\\{T\in\widecheck{{\mathfrak{T}}}_{t}\\},$
(2.10)

and define the corresponding additive functional

$\displaystyle\Phi(T):=\sum_{v\in T}\varphi(T^{v}).$ (2.11)

Then, by (2.9),

$\displaystyle
N_{t}({\widehat{T}})=\sum_{v\in{\widehat{T}}}\boldsymbol{1}\\{{\widehat{T}}^{v}=t\\}=\sum_{v\in
T}\boldsymbol{1}\\{T^{v}\in\widecheck{{\mathfrak{T}}}_{t}\\}=\sum_{v\in
T}\varphi(T^{v})=\Phi(T).$ (2.12)

###  2.5. Extended fringe trees

Let $T$ be a rooted tree. The fringe tree $T^{v}$ defined in the introduction
consists of a node $v$ and all its descendants. Aldous [1] introduces also the
_extended fringe tree_ by also going up from the chosen node $v$ to ancestors
and then taking descendants, thus including siblings, cousins, and so on; we
may formally define the extended fringe tree as the nested sequence of fringe
trees $(T^{v_{i}})_{i=0}^{d(v)}$ where $v_{i}$ is the $i$th ancestor of $v$.
(See [1, Section 4] for details.) It is shown in [1, Proposition 11] that if
the random fringe trees of some sequence of random trees $T_{n}$ converge in
distribution, then so do the random extended fringe trees. The limit then is
an infinite nested sequence of random trees $(T_{\infty}^{(i)})_{i\geq 0}$.

######  Remark 2.1.

Assume also the technical condition (satisfied for the random trees studied
here) that the depth of a random node in $T_{n}$ tends to infinity in
probability. Then the random limit sequence $(T_{\infty}^{(i)})_{i\geq 0}$ can
be combined to a random infinite tree, called _sin-tree_ , with a single
infinite path from $o$ consisting of the roots of the trees
$T_{\infty}^{(i)}$, see [1]. The results below can be translated to this, more
intuitive, description of the limit of the extended fringe tree, but we leave
that to the reader.  $\triangle$

We consider in the present paper the extended fringe tree
${T}^{**}=({T}^{**(i)})_{i}$ of a uniformly random _leaf_ in the tree $T$
(instead of a random node); this also converges in distribution when the
random fringe tree does, since it can be regarded as the random extended
fringe tree conditioned on the fringe tree being $\bullet$.

The distribution of this random extended fringe tree
${T}^{**}=({T}^{**(i)})_{i}$ can be described by the probabilities, for pairs
$(t,\ell)$ of a tree $t$ and a marked leaf $\ell\in t$, and any (deterministic
or random) tree $T$, letting $L$ be a uniformly random leaf in $T$,

$\displaystyle q(T;t,\ell):=\operatorname{\mathbb{P}{}}\bigl{(}\exists w\in
T:L\in T^{w}\text{ and }(T^{w},L)\text{ is isomorphic to }(t,\ell)\bigr{)}.$
(2.13)

In fact, it is easy to see that for any such pair $(t,\ell)$ and $i\geq 0$, if
$o$ is the root of ${T}^{**}$ (defined as the root of ${T}^{**(0)}$), then

$\displaystyle\operatorname{\mathbb{P}{}}\bigl{(}({T}^{**(i)},o)=(t,\ell)\bigr{)}=q(T;t,\ell)\boldsymbol{1}\\{i=d_{t}(\ell)\\}.$
(2.14)

We define also the simpler

$\displaystyle q(T;t):=\operatorname{\mathbb{P}{}}\bigl{(}\text{a random leaf
$v$ lies in some fringe tree $T^{w}$ isomorphic to $t$}\bigr{)}.$ (2.15)

Note that, if $|T|>1$, any leaf lies in several fringe trees of different
sizes; hence $\sum_{t}q(T;t)>1$ so $q(T;\cdot)$ is not a probability
distribution on trees. In fact, trivially $q(T;\bullet)=1$ for every tree $T$.

For a random tree $T$ we define also $q(T;t,\ell\mid T)$ and $q(T;t\mid T)$ by
(2.13) and (2.15) conditioned on $T$. Thus $q(T;t\mid T)$ is a functional of
$T$, and thus a random variable, while $q(T;t)$ is a number depending on the
distribution of $T$ only, and similarly for $q(T;t,\ell)$. We have, as always
for conditional expectations,

$\displaystyle q(T;t,\ell)=\operatorname{\mathbb{E}}{}q(T;t,\ell\mid T),\qquad
q(T;t)=\operatorname{\mathbb{E}}{}q(T;t\mid T).$ (2.16)

Let $t$ be a fixed tree with a marked leaf $\ell$, and let $T$ be a
(deterministic or random) tree. For every fringe tree $T^{w}$ that is
isomorphic to $t$, there is exactly one leaf $L$ in $T$ such that $L\in T^{w}$
and $(T^{w},L)=(t,\ell)$. Since all copies of $t$ in $T$ are disjoint, these
leaves $L$ are distinct for different fringe trees $T^{w}=t$, and thus (for a
random tree $T$)

$\displaystyle q(T;t,\ell\mid T)=\frac{N_{t}(T)}{|T|_{\mathsf{e}}}$ (2.17)

and hence

$\displaystyle
q(T;t,\ell)=\operatorname{\mathbb{E}}{}\frac{N_{t}(T)}{|T|_{\mathsf{e}}}.$
(2.18)

Consequently, recalling (2.14), the distribution of the random extended fringe
tree ${T}^{**}$ is determined by the fringe subtree counts $N_{t}(T)$.
Furthermore, again since the copies of $t$ in $T$ are disjoint, the number of
leaves that lie in some copy of $t$ equals $N_{t}(T)|t|_{\mathsf{e}}$, and
hence, for any (random) tree $T$,

$\displaystyle q(T;t\mid T)=\frac{N_{t}(T)|t|_{\mathsf{e}}}{|T|_{\mathsf{e}}}$
(2.19)

and

$\displaystyle
q(T;t)=|t|_{\mathsf{e}}\operatorname{\mathbb{E}}{}\frac{N_{t}(T)}{|T|_{\mathsf{e}}}.$
(2.20)

Consequently, for every leaf $\ell\in t$,

$\displaystyle q(T;t,\ell\mid T)=\frac{1}{|t|_{\mathsf{e}}}q(T;t\mid T),\qquad
q(T;t,\ell)=\frac{1}{|t|_{\mathsf{e}}}q(T,t).$ (2.21)

Hence, it suffices to study the simpler $q(T;t\mid T)$ and $q(T;t)$ without
marked leaves.

For a sequence of (deterministic or random) trees $T_{n}$, it follows from
(2.14) and (2.21) that the extended fringe trees
${T}^{**}_{n}=({T}^{**(i)}_{n})_{i}$ converge in distribution, to some
sequence of (random) trees ${T}^{**}_{\infty}=({T}^{**(i)}_{\infty})_{i\geq
0}$, if and only if $q(T_{n};t)$ converges for every fixed tree $t$, and in
this case the limit distribution is determined by the limits

$\displaystyle q({T}^{**}_{\infty};t):=\lim_{n\to\infty}q(T_{n};t).$ (2.22)

More precisely, if these limits exist, then it follows from (2.14) and (2.21)
that if $o$ is the root of ${T}^{**}_{\infty}$ (i.e., the root of
${T}^{**(0)}_{\infty}$), then for every tree $t$ and leaf $\ell\in t$ with
$d_{t}(\ell)=i$,

$\displaystyle\operatorname{\mathbb{P}{}}\bigl{(}({T}^{**(i)}_{\infty},o)=(t,\ell)\bigr{)}=\frac{1}{|t|_{\mathsf{e}}}\lim_{n\to\infty}q(T_{n};t)=\frac{1}{|t|_{\mathsf{e}}}q({T}^{**}_{\infty};t).$
(2.23)

Note also that for any (deterministic) tree $T$, (2.19) and (1.2) yield

$\displaystyle
q(T;t)=\frac{|t|_{\mathsf{e}}|T|\operatorname{\mathbb{P}{}}(T^{*}=t)}{|T|_{\mathsf{e}}}=|t|_{\mathsf{e}}\frac{|T|}{|T|_{\mathsf{e}}}\operatorname{\mathbb{P}{}}(T^{*}=t)=|t|_{\mathsf{e}}\frac{\operatorname{\mathbb{P}{}}(T^{*}=t)}{\operatorname{\mathbb{P}{}}(T^{*}=\bullet)}.$
(2.24)

This leads to the following version of the result by Aldous [1, Proposition
11] that, as said above, if a sequence of random fringe trees converge in
distribution, then so do the extended fringe trees. We also obtain a formula
for the limits (2.22).

######  Lemma 2.2.

Let $(T_{n})$ be a sequence of random trees such that
$\operatorname{\mathbb{P}{}}(T^{*}_{n}=t\mid
T_{n})\overset{\mathrm{p}}{\longrightarrow}\operatorname{\mathbb{P}{}}(T^{*}_{\infty}=t)$
for every fixed tree $t$ and some random tree $T^{*}_{\infty}$ (a quenched
limiting fringe tree). Then

$\displaystyle q(T_{n};t\mid
T_{n})\overset{\mathrm{p}}{\longrightarrow}q({T}^{**}_{\infty};t)=\kappa|t|_{\mathsf{e}}{\operatorname{\mathbb{P}{}}(T^{*}_{\infty}=t)},$
(2.25)

where (with the limit in probability, in general)

$\displaystyle\kappa:=\frac{1}{\operatorname{\mathbb{P}{}}(T^{*}_{\infty}=\bullet)}=\lim_{n\to\infty}\frac{|T_{n}|}{|T_{n}|_{\mathsf{e}}}.$
(2.26)

For full binary trees with
$|T_{n}|\overset{\mathrm{p}}{\longrightarrow}\infty$, we simply have
$\kappa=2$.

###### Proof.

We have by (2.24) and the assumption

$\displaystyle q(T_{n};t\mid
T_{n})=|t|_{\mathsf{e}}\frac{\operatorname{\mathbb{P}{}}(T^{*}_{n}=t\mid
T_{n})}{\operatorname{\mathbb{P}{}}(T^{*}_{n}=\bullet\mid
T_{n})}\overset{\mathrm{p}}{\longrightarrow}|t|_{\mathsf{e}}\frac{\operatorname{\mathbb{P}{}}(T^{*}_{\infty}=t)}{\operatorname{\mathbb{P}{}}(T^{*}_{\infty}=\bullet)},$
(2.27)

which can be written as (2.25)–(2.26).

For full binary trees with
$|T_{n}|\overset{\mathrm{p}}{\longrightarrow}\infty$, (2.1) yields $\kappa=2$.
∎

Results for extended fringe trees thus follow rather trivially from results
for fringe trees $T^{*}_{n}$, but we find it interesting to state also such
results explicitly below.

##  3\. Patricia tries

We fix a full binary tree $t$ and consider $N_{t}(\widehat{\Upsilon}_{n})$,
the number of fringe trees in the Patricia trie $\widehat{\Upsilon}_{n}$ that
equal $t$. Let $m:=|t|_{\mathsf{e}}$, the number of leaves in $t$. The case
$m=1$ is trivial with $t=\bullet$ and $N_{t}(\widehat{\Upsilon}_{n})=n$, so we
assume $m\geq 2$.

Asymptotic normality of $N_{t}(\widehat{\Upsilon}_{n})$ follows by (2.12) and
a straightforward application of results for tries in [28], see below for
details, although some work is required to calculate the asymptotic mean and
variance. Note that the argument below is very similar to the one in [28,
Section 4.2] for the number of all fringe trees in $\Upsilon_{n}$ with a given
number of leaves.

We first introduce some notation. Let

$\displaystyle\pi_{t}:=\operatorname{\mathbb{P}{}}(\Upsilon_{m}\in\widecheck{{\mathfrak{T}}}_{t}),$
(3.1)

(this will be calculated later) and

$\displaystyle H:=-p\log p-q\log q,$ (3.2)

the entropy of the bits in the random strings $\Xi^{(i)}$. Further, for
$\lambda>0$, let $\widetilde{\Upsilon}_{\lambda}$ be the random trie
constructed from a random number $N_{\lambda}\in\operatorname{Po}(\lambda)$
random strings; thus $\widetilde{\Upsilon}_{\lambda}$ has $N_{\lambda}$
leaves. The results in [28] use heavily some functions defined in general
(assuming $\varphi(\bullet)=0$ as in our case) by [28, (3.16)–(3.18)]:

$\displaystyle f_{\mathsf{E}}(\lambda)$
$\displaystyle:=\operatorname{\mathbb{E}}{}\varphi(\widetilde{\Upsilon}_{\lambda}),$
(3.3) $\displaystyle f_{\mathsf{V}}(\lambda)$
$\displaystyle:=2\operatorname{Cov}\bigl{(}\varphi(\widetilde{\Upsilon}_{\lambda}),\Phi(\widetilde{\Upsilon}_{\lambda})\bigr{)}-\operatorname{Var}\varphi(\widetilde{\Upsilon}_{\lambda}),$
(3.4) $\displaystyle f_{\mathsf{C}}(\lambda)$
$\displaystyle:=\operatorname{Cov}\bigl{(}\varphi(\widetilde{\Upsilon}_{\lambda}),N_{\lambda}\bigr{)},$
(3.5)

and their Mellin transforms defined by (for
$\mathsf{X}=\mathsf{E},\mathsf{V},\mathsf{C}$ and suitable $s$)

$\displaystyle
f_{\mathsf{X}}^{*}(s):=\int_{0}^{\infty}f_{\mathsf{X}}(\lambda)\lambda^{s-1}\,\mathrm{d}\lambda.$
(3.6)

For $\mathsf{X}=\mathsf{E},\mathsf{V},\mathsf{C}$ define also the function
$\psi_{\mathsf{X}}(x)$, $x\in\mathbb{R}$ by [28, (3.13)–(3.14)]:

  1. (i)

In the aperiodic case ($\log p/\log q\notin\mathbb{Q}$), $\psi_{\mathsf{X}}$
is constant: for all $x$,

$\displaystyle\psi_{\mathsf{X}}(x):=f_{\mathsf{X}}^{*}(-1).$ (3.7)

  2. (ii)

In the periodic case, $\psi_{\mathsf{X}}$ is a continuous $d$-periodic
function given by the Fourier series, recalling $d=d_{p}$ defined in (2.4),

$\psi_{\mathsf{X}}(x)=\sum_{k=-\infty}^{\infty}f_{\mathsf{X}}^{*}\Bigl{(}-1-\frac{2\pi
k}{d}\mathrm{i}\Bigr{)}e^{2\pi\mathrm{i}kx/d}.$ (3.8)

(The Fourier series converges absolutely in our case by (3.12)–(3.14) below,
or by [28, Theorem 3.1] and the formulas for $f_{X}(\lambda)$ below.)

######  Theorem 3.1.

Let $t$ be a full binary tree with $|t|_{\mathsf{e}}=m>1$. Then
$N_{t}(\widehat{\Upsilon}_{n})$ is asymptotically normal as ${n\to\infty}$:

$\displaystyle\frac{N_{t}(\widehat{\Upsilon}_{n})-\operatorname{\mathbb{E}}{}N_{t}(\widehat{\Upsilon}_{n})}{\sqrt{\operatorname{Var}N_{t}(\widehat{\Upsilon}_{n})}}$
$\displaystyle\overset{\mathrm{d}}{\longrightarrow}N(0,1),$ (3.9)

with convergence of all moments. We have
$\operatorname{Var}N_{t}(\widehat{\Upsilon}_{n})=\Theta(n)$ as ${n\to\infty}$,
and

$\displaystyle\operatorname{\mathbb{E}}{}N_{t}(\widehat{\Upsilon}_{n})$
$\displaystyle=nH^{-1}\psi_{\mathsf{E}}(\log n)+o(n),$ (3.10)
$\displaystyle\operatorname{Var}N_{t}(\widehat{\Upsilon}_{n})$
$\displaystyle=n\bigl{(}H^{-1}\psi_{\mathsf{V}}(\log
n)-H^{-2}\psi_{\mathsf{C}}(\log n)^{2}+o(1)\bigr{)},$ (3.11)

where $\psi_{\mathsf{X}}$ is given by (3.7)–(3.8) with (for
$\operatorname{Re}s>-m$)

$\displaystyle f_{\mathsf{E}}^{*}(s)$
$\displaystyle=\pi_{t}\frac{\Gamma(m+s)}{m!},$ (3.12) $\displaystyle
f_{\mathsf{V}}^{*}(s)$
$\displaystyle=\frac{\pi_{t}}{m!}\Gamma(m+s)-\frac{\pi_{t}^{2}}{m!^{2}}2^{-2m-s}\Gamma(2m+s)$
$\displaystyle\qquad-2\frac{\pi_{t}^{2}}{m!^{2}}\sum_{k=0}^{\infty}(-1)^{k}\frac{\Gamma(2m+s+k)}{k!}\cdot\frac{p^{m+k}+q^{m+k}}{1-(p^{m+k}+q^{m+k})},$
(3.13) $\displaystyle f_{\mathsf{C}}^{*}(s)$
$\displaystyle=-sf_{\mathsf{E}}^{*}(s)=-\pi_{t}\frac{s\Gamma(m+s)}{m!}.$
(3.14)

In the aperiodic case, (3.10)–(3.11) simplify to

$\displaystyle\operatorname{\mathbb{E}}{}N_{t}(\widehat{\Upsilon}_{n})/n$
$\displaystyle\to H^{-1}\frac{\pi_{t}}{m(m-1)},$ (3.15)
$\displaystyle\operatorname{Var}N_{t}(\widehat{\Upsilon}_{n})/n$
$\displaystyle\to
H^{-1}f_{\mathsf{V}}^{*}(-1)-\Bigl{(}H^{-1}\frac{\pi_{t}}{m(m-1)}\Bigr{)}^{2}.$
(3.16)

###### Proof.

By (2.12), we have $N_{t}(\widehat{\Upsilon}_{n})=\Phi(\Upsilon_{n})$; we
apply [28, Theorem 3.9] to $\Phi(\Upsilon_{n})$. We first verify the technical
condition there that we can write $\varphi=\varphi_{+}-\varphi_{-}$ with
bounded $\varphi_{\pm}$ such that the corresponding additive functionals
$\Phi_{\pm}$ are increasing, in the sense that
$\Phi_{\pm}(T_{1})\leq\Phi_{\pm}(T_{2})$ if $T_{1}$ is a subtree of $T_{2}$.
As in [28, Section 4.3], we let
$\varphi_{>m}(T):=\boldsymbol{1}\\{|T|_{\mathsf{e}}>m\\}$, and it is easily
seen that $\varphi_{+}:=\varphi+\varphi_{>m}$ and $\varphi_{-}:=\varphi_{>m}$
satisfy the condition. Hence [28, Theorem 3.9] applies. Furthermore,
$\varphi(\Upsilon_{n})=$ for $n>m$, and it is easy to see that there exists
$n$ such that $\operatorname{Var}\Phi(\Upsilon_{n})>0$ (i.e,
$\Phi(\Upsilon_{n})$ is not constant); we may for example take $n=m+1$ if
$m\geq 3$ and $n=4$ for $m=2$. Hence also [28, Lemma 3.14] applies, which
shows that
$\operatorname{Var}N_{t}(\widehat{\Upsilon}_{n})=\operatorname{Var}\Phi(\Upsilon_{n})=\Omega(n)$
as ${n\to\infty}$. Hence, (3.9) (with convergence of moments) follows by [28,
Theorem 3.9(iv)]. Furthermore, the moment convergence in [28, Theorem 3.9(ii)]
implies (3.11). In particular, $\operatorname{Var}\Phi(\Upsilon_{n})=O(n)$,
and thus $\operatorname{Var}\Phi(\Upsilon_{n})=\Theta(n)$. The asymtotics
(3.10) follows from [28, Theorem 3.9(v)].

It remains to find the Mellin transforms $f_{\mathsf{X}}^{*}$ (which yield
$\psi_{\mathsf{X}}(x)$ by (3.7)–(3.8)). First, since
$\Upsilon_{n}\in\widecheck{{\mathfrak{T}}}_{t}$ is possible only when
$n=|t|_{\mathsf{e}}=m$, it follows by (2.10) and (3.1) that

$\displaystyle
f_{\mathsf{E}}(\lambda):=\operatorname{\mathbb{E}}{}\varphi(\widetilde{\Upsilon}_{\lambda})=\operatorname{\mathbb{P}{}}(\widetilde{\Upsilon}_{\lambda}\in\widecheck{{\mathfrak{T}}}_{t})=\operatorname{\mathbb{P}{}}(N_{\lambda}=m)\pi_{t}=\operatorname{Po}(\lambda;m)\pi_{t}=\pi_{t}\frac{\lambda^{m}}{m!}e^{-\lambda}.$
(3.17)

This, or simpler [28, Lemma 3.16], yields the Mellin transform

$\displaystyle
f_{\mathsf{E}}^{*}(s):=\int_{0}^{\infty}f_{\mathsf{E}}(\lambda)\lambda^{s-1}\,\mathrm{d}\lambda=\frac{\Gamma(m+s)}{m!}\pi_{t},$
(3.18)

verifying (3.12). By [28, Lemma 3.6], we have
$f_{\mathsf{C}}^{*}(s)=-sf_{\mathsf{E}}^{*}(s)$, showing (3.14). (We also
obtain $f_{\mathsf{C}}(\lambda)=\lambda
f_{\mathsf{E}}^{\prime}(\lambda)=(m-\lambda)f_{\mathsf{E}}(\lambda)$.)

To find the more complicated $f_{\mathsf{V}}$, note first that if
$\varphi(T)=1$, i.e, $T\in\widecheck{{\mathfrak{T}}}_{t}$, then no fringe tree
$T^{v}$ except $T^{o}=T$ (where $o$ is the root) belongs to
$\widecheck{{\mathfrak{T}}}_{t}$. Hence, if $\varphi(T)=1$, then $\Phi(T)=1$,
and consequently,

$\displaystyle\operatorname{Cov}\bigl{(}\varphi(\widetilde{\Upsilon}_{\lambda}),\Phi(\widetilde{\Upsilon}_{\lambda})\bigr{)}=\operatorname{\mathbb{E}}{}\varphi(\widetilde{\Upsilon}_{\lambda})-\operatorname{\mathbb{E}}{}\varphi(\widetilde{\Upsilon}_{\lambda})\operatorname{\mathbb{E}}{}\Phi(\widetilde{\Upsilon}_{\lambda}).$
(3.19)

Similarly,
$\operatorname{Var}\varphi(\widetilde{\Upsilon}_{\lambda})=\operatorname{\mathbb{E}}{}\varphi(\widetilde{\Upsilon}_{\lambda})-(\operatorname{\mathbb{E}}{}\varphi(\widetilde{\Upsilon}_{\lambda}))^{2}$,
and thus (3.4) yields, using (3.19),

$\displaystyle
f_{\mathsf{V}}(\lambda)=\operatorname{\mathbb{E}}{}\varphi(\widetilde{\Upsilon}_{\lambda})-2\operatorname{\mathbb{E}}{}\varphi(\widetilde{\Upsilon}_{\lambda})\operatorname{\mathbb{E}}{}\Phi(\widetilde{\Upsilon}_{\lambda})+(\operatorname{\mathbb{E}}{}\varphi(\widetilde{\Upsilon}_{\lambda}))^{2}.$
(3.20)

Let $\mathcal{A}^{*}:=\bigcup_{n=0}^{\infty}\\{0,1\\}^{n}$ be the set of
finite strings of $\\{0,1\\}$. If
$\alpha=\alpha_{1}\dotsm\alpha_{n}\in\mathcal{A}^{*}$, define $P(\alpha)$ as
the probability that the random string $\Xi^{(1)}$ begins with $\alpha$, i.e,

$\displaystyle
P(\alpha):=\prod_{i=1}^{|\alpha|}q^{1-\alpha_{i}}p^{\alpha_{i}},$ (3.21)

where $|\alpha|\geq 0$ is the length of $\alpha$. We may regard the strings
$\alpha\in\mathcal{A}^{*}$ as the nodes in the infinite binary tree, and,
using again $\varphi(\bullet)=0$, it follows (see [28, (2.25)]) that, using
also (3.17),

$\displaystyle\operatorname{\mathbb{E}}{}\Phi(\widetilde{\Upsilon}_{\lambda})$
$\displaystyle=\sum_{\alpha\in\mathcal{A}^{*}}\operatorname{\mathbb{E}}{}\varphi\bigl{(}\widetilde{\Upsilon}_{P(\alpha)\lambda}\bigr{)}=\sum_{\alpha\in\mathcal{A}^{*}}f_{\mathsf{E}}\bigl{(}P(\alpha)\lambda\bigr{)}=\pi_{t}\sum_{\alpha\in\mathcal{A}^{*}}\operatorname{Po}\bigl{(}P(\alpha)\lambda;m\bigr{)}.$
(3.22)

Let $\sum_{\alpha}^{\prime}$ denote the sum over all
$\alpha\in\mathcal{A}^{*}$ with $|\alpha|\geq 1$, i.e, over all strings
$\alpha$ except the empty string. Then (3.20) and (3.22) yield, using (3.17)
again and (2.3),

$\displaystyle f_{\mathsf{V}}(\lambda)$
$\displaystyle=\pi_{t}\operatorname{Po}(\lambda;m)-2\pi_{t}^{2}\operatorname{Po}(\lambda;m)\sum_{\alpha\in\mathcal{A}^{*}}\operatorname{Po}\bigl{(}P(\alpha)\lambda;m\bigr{)}+\pi_{t}^{2}\operatorname{Po}(\lambda;m)^{2}$
$\displaystyle=\pi_{t}\frac{\lambda^{m}}{m!}e^{-\lambda}-2\frac{\pi_{t}^{2}}{m!^{2}}\sum_{\alpha\in\mathcal{A}^{*}}P(\alpha)^{m}\lambda^{2m}e^{-(1+P(\alpha))\lambda}+\pi_{t}^{2}\frac{\lambda^{2m}}{m!^{2}}e^{-2\lambda}$
$\displaystyle=\pi_{t}\frac{\lambda^{m}}{m!}e^{-\lambda}-2\frac{\pi_{t}^{2}}{m!^{2}}{\sum_{\alpha}}^{\prime}P(\alpha)^{m}\lambda^{2m}e^{-(1+P(\alpha))\lambda}-\pi_{t}^{2}\frac{\lambda^{2m}}{m!^{2}}e^{-2\lambda}.$
(3.23)

The Mellin transform is thus, for $\operatorname{Re}s>-m$, by a simple
calculation,

$\displaystyle f_{\mathsf{V}}^{*}(s)$
$\displaystyle=\frac{\pi_{t}}{m!}\Gamma(m+s)-2\frac{\pi_{t}^{2}}{m!^{2}}{\sum_{\alpha}}^{\prime}P(\alpha)^{m}(1+P(\alpha))^{-2m-s}\Gamma(2m+s)$
$\displaystyle\qquad-\frac{\pi_{t}^{2}}{m!^{2}}2^{-2m-s}\Gamma(2m+s).$ (3.24)

By a binomial expansion we have, with absolutely convergent sums, e.g by
(3.26) below,

$\displaystyle{\sum_{\alpha}}^{\prime}P(\alpha)^{m}(1+P(\alpha))^{-2m-s}$
$\displaystyle={\sum_{\alpha}}^{\prime}P(\alpha)^{m}\sum_{k=0}^{\infty}\frac{(-1)^{k}}{k!}\frac{\Gamma(2m+s+k)}{\Gamma(2m+s)}P(\alpha)^{k}$
$\displaystyle=\sum_{k=0}^{\infty}\frac{(-1)^{k}}{k!}\frac{\Gamma(2m+s+k)}{\Gamma(2m+s)}{\sum_{\alpha}}^{\prime}P(\alpha)^{m+k}.$
(3.25)

For any exponent $b$ and $\ell\geq 1$ we have from the definition (3.21),
letting $j$ be the number of 1s in $\alpha$,

$\displaystyle\sum_{\alpha:|\alpha|=\ell}P(\alpha)^{b}=\sum_{j=0}^{\ell}\binom{\ell}{j}\bigl{(}p^{j}q^{\ell-j}\bigr{)}^{b}=(p^{b}+q^{b})^{\ell}.$
(3.26)

Hence, summing over $\ell\geq 1$, we obtain from (3)

$\displaystyle{\sum_{\alpha}}^{\prime}P(\alpha)^{m}(1+P(\alpha))^{-2m-s}=\sum_{k=0}^{\infty}\frac{(-1)^{k}}{k!}\frac{\Gamma(2m+s+k)}{\Gamma(2m+s)}\frac{p^{m+k}+q^{m+k}}{1-(p^{m+k}+q^{m+k})}.$
(3.27)

Finally, we obtain (3.1) from (3) and (3.27).

In the aperiodic case, (3.7) holds, and thus (3.10)–(3.11) yield
(3.15)–(3.16), using (3.12) and (3.14). ∎

We have postponed calculating $\pi_{t}$, which appears in the formulas above.
We begin with an elementary (and certainly known) calculation of
$\operatorname{\mathbb{P}{}}(\Upsilon_{m}=t)$. Recall that a trie belongs to
set set $\mathfrak{T}^{\prime}$ of trees, and that
$|\Upsilon_{m}|_{\mathsf{e}}=m$. Hence, it suffices to consider the case
$t\in\mathfrak{T}^{\prime}$ and $|t|_{\mathsf{e}}=m$, since otherwise the
probability is 0.

######  Lemma 3.2.

Let $t$ be a binary tree with $t\in\mathfrak{T}^{\prime}$ and
$|t|_{\mathsf{e}}=m\geq 1$. The probability that the random trie
$\Upsilon_{m}$ equals $t$ is given by

$\displaystyle\operatorname{\mathbb{P}{}}(\Upsilon_{m}=t)=m!\,q^{\mathsf{LPL}(t)}p^{\mathsf{RPL}(t)}.$
(3.28)

###### Proof.

Each of the $m$ leaves $x_{i}$ of $t$ corresponds to a finite string
$A(x_{i})$ of $\\{0,1\\}$ which encodes the path from the root to $x_{i}$ by 0
for each left child and 1 for each right child. Since
$t\in\mathfrak{T}^{\prime}$, the random trie $\Upsilon_{m}$ constructed from
the strings $\Xi^{(1)},\dots,\Xi^{(m)}$ equals $t$ if and only if the strings
$A(x_{1}),\dots,A(x_{m})$ are initial segments of $\Xi^{(1)},\dots,\Xi^{(m)}$,
in some order. The string $A(x_{i})$ contains $d_{\mathsf{L}}(x_{i})$ 0s and
$d_{\mathsf{R}}(x_{i})$ 1s, and thus the probability that $\Xi^{(j)}$ begins
with $A(x_{i})$ is $q^{d_{\mathsf{L}}(x_{i})}p^{d_{\mathsf{R}}(x_{i})}$. Since
there are $m!$ possible permutations of the strings, we obtain

$\displaystyle\operatorname{\mathbb{P}{}}(\Upsilon_{m}=t)=m!\,\prod_{i=1}^{m}q^{d_{\mathsf{L}}(x_{i})}p^{d_{\mathsf{R}}(x_{i})}=m!\,q^{\mathsf{LPL}(t)}p^{\mathsf{RPL}(t)},$
(3.29)

showing (3.28). ∎

For a full binary tree $t$, recall from Section 2.4 that
$\widecheck{{\mathfrak{T}}}_{t}$ is the set of binary trees obtained by
subdividing the edges of $t$. Let

$\displaystyle\nu_{k}(t):=\bigl{\lvert}\\{v\in
t:|t^{v}|_{\mathsf{e}}=k\\}\bigr{\rvert},\qquad k\geq 1.$ (3.30)

######  Lemma 3.3.

Let $t$ be a full binary tree with $|t|_{\mathsf{e}}=m\geq 1$. Then,

$\displaystyle\pi_{t}:=\operatorname{\mathbb{P}{}}(\Upsilon_{m}\in\widecheck{{\mathfrak{T}}}_{t})=m!\,q^{\mathsf{LPL}(t)}p^{\mathsf{RPL}(t)}\prod_{k=2}^{m-1}\bigl{(}1-(q^{w(e)}+p^{w(e)})\bigr{)}^{-\nu_{k}(t)}.$
(3.31)

###### Proof.

By Lemma 3.2,

$\displaystyle\operatorname{\mathbb{P}{}}(\Upsilon_{m}\in\widecheck{{\mathfrak{T}}}_{t})=\operatorname{\mathbb{P}{}}(\Upsilon_{m}\in\widecheck{{\mathfrak{T}}}_{t}\cap\mathfrak{T}^{\prime})=\sum_{T\in\widecheck{{\mathfrak{T}}}_{t}\cap\mathfrak{T}^{\prime}}\operatorname{\mathbb{P}{}}(\Upsilon_{m}=T)=m!\,\sum_{T\in\widecheck{{\mathfrak{T}}}_{t}\cap\mathfrak{T}^{\prime}}q^{\mathsf{LPL}(T)}p^{\mathsf{RPL}(T)}.$
(3.32)

Let the _weight_ $w(e)$ of an edge $e$ in a tree $T$ be the number of leaves
$x$ such that $e$ is on the path from the root to $x$. If we insert $\ell\geq
0$ new nodes in a given edge $e$, of which $j$ get a left child and $k=\ell-j$
a right child, then $\mathsf{LPL}(T)$ and $\mathsf{RPL}(T)$ will increase by
$jw(e)$ and $kw(e)$, respectively, and the term
$q^{\mathsf{LPL}(T)}p^{\mathsf{RPL}(T)}$ will thus be multiplied by
$q^{jw(e)}p^{kw(e)}$. Summing over all $j$ and $k$ with a given $\ell=j+k$ we
obtain the factor, since the insertion may be done with $\binom{\ell}{j}$
orders of left and right,

$\displaystyle\sum_{j=0}^{\ell}\binom{\ell}{j}q^{jw(e)}p^{(\ell-j)w(e)}=\bigl{(}q^{w(e)}+p^{w(e)}\bigr{)}^{\ell}.$
(3.33)

And summing over all $\ell\geq 0$ gives the factor

$\displaystyle\sum_{\ell=0}^{\infty}\bigl{(}q^{w(e)}+p^{w(e)}\bigr{)}^{\ell}=\frac{1}{1-(q^{w(e)}+p^{w(e)})}.$
(3.34)

The edges of weight 1 are precisely the edges that lead to a leaf. Hence, we
are not allowed to insert any new nodes in any edge with weight 1, since that
would yield a tree not in $\mathfrak{T}^{\prime}$, but we may insert
arbitrarily many in all other edges. Thus, it follows from (3.32) that
$\operatorname{\mathbb{P}{}}(\Upsilon_{m}\in\widecheck{{\mathfrak{T}}}_{t})$
is obtained by multiplying $\operatorname{\mathbb{P}{}}(\Upsilon_{m}=t)$ in
(3.28) by the product of the factors in (3.34) for all edges $e$ with
$w(e)\geq 2$. Moreover, if $e=uv$ where $v$ is a child of $u$, then

$\displaystyle w(e)=|{\mathcal{L}}(T)\cap T^{v}|,$ (3.35)

the number of leaves in the fringe tree $T^{v}$, and for $k\leq m-1$, the
number of edges with weight $k$ thus equals $\nu_{k}(T)$. (This fails for
$k=m$, since in a full binary tree $T$ with $|T|_{\mathsf{e}}=m$, all edges
have weight $\leq m-1$ while $\nu_{m}(T)=1$.) Consequently, (3.31) follows. ∎

######  Remark 3.4.

We do not claim that the error term $o(n)$ in (3.10) is $o(\sqrt{n})$ so that
$\operatorname{\mathbb{E}}{}N_{t}(\widehat{\Upsilon}_{n})$ may be replaced by
$H^{-1}\psi_{\mathsf{E}}(\log n)$ in (3.9). It is known that in the
corresponding results for the size of a random trie, this is in general _not_
true, see [14] and [28, Appendix C]. We leave it as an open problem whether
the same may happen here too.  $\triangle$

######  Remark 3.5.

Theorem 3.1 extends to multivariate limits for several full binary trees
$t_{i}$ by the Cramér–Wold device, i.e, by considering linear combinations of
different $N_{t_{i}}(\widehat{\Upsilon}_{n})$, cf [28, Remark 3.10]. In
particular, for any set $U$ of full binary trees with the same number of
leaves $|t|_{\mathsf{e}}=m>1$ for $t\in U$ (and thus the same size
$|t|=2m+1$), all results in Theorem 3.1 hold also for
$N_{U}(\widehat{\Upsilon}_{n}):=\sum_{t\in U}N_{t}(\widehat{\Upsilon}_{n})$ if
we just replace $\pi_{t}$ by $\pi_{U}:=\sum_{t\in U}\pi_{t}$. (By the same
proof.) For example, this yields the asymptotic distribution of the number
$N_{m}(\widehat{\Upsilon}_{n})$ of all fringe trees with $m$ leaves; we then
replace $\pi_{t}$ by

$\displaystyle\pi_{m}:=\operatorname{\mathbb{P}{}}\Bigl{(}\Upsilon_{m}\in\bigcup_{|t|_{\mathsf{e}}=m}\widecheck{{\mathfrak{T}}}_{t}\Bigr{)}=1-p^{m}-q^{m},$
(3.36)

since $\bigcup_{|t|_{\mathsf{e}}=m}\widecheck{{\mathfrak{T}}}_{t}$ (where $t$
is a full binary tree) is the set of all tries with $m$ leaves and a root of
outdegree 2, and the probability that the root of $\Upsilon_{m}$ has outdegree
1 is $p^{m}+q^{m}$. In general, with trees $t_{i}$ of different sizes,
asymptotic covariances can be found by calculations similar to the ones above
for the variance; we omit the details.  $\triangle$

The asymptotic normality of $N_{t}(\widehat{\Upsilon}_{n})$ yields
corresponding results for the distributions of fringe trees and extended
fringe trees. We note first a simple corollary.

######  Corollary 3.6.

Let $t$ be a full binary tree with $|t|_{\mathsf{e}}=m>1$. Then

$\displaystyle
N_{t}(\widehat{\Upsilon}_{n})/n=\operatorname{\mathbb{E}}{}N_{t}(\widehat{\Upsilon}_{n})/n+o_{\mathrm{p}}(1)=H^{-1}\psi_{\mathsf{E}}(\log
n)+o_{\mathrm{p}}(1),$ (3.37)

with the periodic function $\psi_{\mathsf{E}}(t)$ as in Theorem 3.1. In
particular, in the aperiodic case,

$\displaystyle
N_{t}(\widehat{\Upsilon}_{n})/n\overset{\mathrm{p}}{\longrightarrow}\frac{\pi_{t}}{m(m-1)H}.$
(3.38)

###### Proof.

The first equality in (3.37) follows from
$\operatorname{Var}N_{t}(\widehat{\Upsilon}_{n})=O(n)$ by Chebyshev’s
inequality, and the second is (3.10).

In the aperiodic case, we use (3.15) instead of (3.10) and obtain (3.38). ∎

The size of the random trie $\Upsilon_{n}$ shows oscillations in the periodic
case, see e.g [29; 31; 14; 17; 25; 18; 24; 28]. However, the Patricia trie
$\widehat{\Upsilon}_{n}$ is a full binary tree with $n$ leaves, and thus has a
fixed size $|\widehat{\Upsilon}_{n}|=2n-1$. (This is special to the binary
case considered here.) Hence we obtain from (1.3) and Corollary 3.6
immediately the following for the random fringe tree. We state results both
conditioned on the tree $\widehat{\Upsilon}_{n}$ and unconditioned (i.e.,
results of quenched and annealed type, repectively.)

######  Corollary 3.7.

Let $t$ be a full binary tree with $|t|_{\mathsf{e}}=m>1$. Then

$\displaystyle\operatorname{\mathbb{P}{}}(\widehat{\Upsilon}_{n}^{*}=t\mid\widehat{\Upsilon}_{n})$
$\displaystyle=\frac{1}{2H}\psi_{\mathsf{E}}(\log n)+o_{\mathrm{p}}(1),$
(3.39)
$\displaystyle\operatorname{\mathbb{P}{}}(\widehat{\Upsilon}_{n}^{*}=t)$
$\displaystyle=\frac{1}{2H}\psi_{\mathsf{E}}(\log n)+o(1),$ (3.40)

with the periodic function $\psi_{\mathsf{E}}(t)$ as in Theorem 3.1. In
particular, in the aperiodic case,

$\displaystyle\operatorname{\mathbb{P}{}}(\widehat{\Upsilon}_{n}^{*}=t\mid\widehat{\Upsilon}_{n})$
$\displaystyle\overset{\mathrm{p}}{\longrightarrow}\frac{\pi_{t}}{2m(m-1)H},$
(3.41)
$\displaystyle\operatorname{\mathbb{P}{}}(\widehat{\Upsilon}_{n}^{*}=t)$
$\displaystyle\longrightarrow\frac{\pi_{t}}{2m(m-1)H}.$ (3.42)

Furthermore, if $|t|=1$, i.e, $t=\bullet$, then, for any $p$,

$\displaystyle\operatorname{\mathbb{P}{}}(\widehat{\Upsilon}_{n}^{*}=t\mid\widehat{\Upsilon}_{n})$
$\displaystyle=\operatorname{\mathbb{P}{}}(\widehat{\Upsilon}_{n}^{*}=t)=\frac{n}{2n-1}\to\frac{1}{2}.$
(3.43)

###### Proof.

The quenched versions (3.39) and (3.41) are the same as (3.37) and (3.38) by
(1.3) conditioned on $\widehat{\Upsilon}_{n}$, recalling
$|\widehat{\Upsilon}_{n}|=2n-1$. The annealed versions follow by taking
expectations; note that the error term $o_{\mathrm{p}}(1)$ in (3.39) is
bounded so dominated convergence applies and shows that its expectation is
$o(1)$.

Finally, (3.43) is trivial (but included for completeness). ∎

For the random extended fringe tree $\widehat{\Upsilon}_{n}^{**}$, we obtain
similarly, for the probabilities $q(\widehat{\Upsilon}_{n};t)$ defined in
Section 2.5.

######  Corollary 3.8.

Let $t$ be a full binary tree with $|t|_{\mathsf{e}}>1$. Then

$\displaystyle q(\widehat{\Upsilon}_{n};t\mid\widehat{\Upsilon}_{n})$
$\displaystyle=|t|_{\mathsf{e}}H^{-1}\psi_{\mathsf{E}}(\log
n)+o_{\mathrm{p}}(1),$ (3.44) $\displaystyle q(\widehat{\Upsilon}_{n};t)$
$\displaystyle=|t|_{\mathsf{e}}H^{-1}\psi_{\mathsf{E}}(\log n)+o(1),$ (3.45)

with the periodic function $\psi_{\mathsf{E}}(t)$ as in Theorem 3.1. In
particular, in the aperiodic case,

$\displaystyle q(\widehat{\Upsilon}_{n};t\mid\widehat{\Upsilon}_{n})$
$\displaystyle\overset{\mathrm{p}}{\longrightarrow}\frac{\pi_{t}}{(|t|_{\mathsf{e}}-1)H},$
(3.46) $\displaystyle q(\widehat{\Upsilon}_{n};t)$
$\displaystyle\longrightarrow\frac{\pi_{t}}{(|t|_{\mathsf{e}}-1)H}.$ (3.47)

For $|t|_{\mathsf{e}}=1$, $q(\widehat{\Upsilon}_{n})=1$ by definition.

###### Proof.

Follows as Corollary 3.7 from Corollary 3.6, now using (2.19)–(2.20) and
recalling $|\widehat{\Upsilon}_{n}|_{\mathsf{e}}=n$. ∎

######  Remark 3.9.

We have here only stated first order results for the distributions of fringe
trees and extended fringe trees. We similarly obtain from Theorem 3.1 also
asymptotic normality of these distributions in the quenched version, meaning
asymptotic normality of the conditional probabilities above.  $\triangle$

######  Remark 3.10.

Corollaries 3.7 and 3.8 show that in the periodic case there is oscillation
and no limit distribution, although suitable subsequences converge in
distribution. It is well known that for some related functionals for tries,
the oscillations are numerically very small; this is true here too when $m$ is
small, but not for large $m$. Consider the symmetric case $p=q=\frac{1}{2}$;
then $d_{p}=\log 2$. (In other periodic cases, $d_{p}$ is smaller and the
oscillations are substantially smaller than in the symmetric case, but they
still become large for large $m$.) In the Fourier series (3.8) for
$f_{\mathsf{E}}$, we have by (3.12) the constant term
$f_{\mathsf{E}}^{*}(-1)=\pi_{t}/m(m-1)$, and if we normalize by this term, for
the term $k=1$ we have

$\displaystyle\frac{f_{\mathsf{E}}^{*}(-1-\frac{2\pi}{\log
2}\mathrm{i})}{f_{\mathsf{E}}^{*}(-1)}=\frac{\Gamma(m-1-\frac{2\pi}{\log
2}\mathrm{i})}{\Gamma(m-1)}.$ (3.48)

For $m=2$, this ratio has absolute value $|\Gamma(1-\frac{2\pi}{\log
2}\mathrm{i})|\doteq 4.9\cdot 10^{-6}$, and higher Fourier coefficients are
much smaller. Hence, the oscillations are in this case hardly of practical
importance. However, the absolute value of the ratio increases as $m$
increases: for $m=3$ it is $\doteq 4.5\cdot 10^{-5}$, for $m=4$ it is $\doteq
2.1\cdot 10^{-4}$ and for $m=100$ it is $\doteq 0.66$; in fact, the absolute
value of the ratio converges to 1 as ${m\to\infty}$ (see [32, 5.11.12]), and
the same holds for every Fourier coefficient. Hence we cannot always ignore
the oscillations.

More precisely, still taking $p=q=\frac{1}{2}$, the normalized $(\log
2)$-periodic function
$\psi_{0}(x):=\psi_{\mathsf{E}}(x)/f_{\mathsf{E}}^{*}(-1)$ is non-negative by
(3.10) and has by (3.8) and (3.18) Fourier coefficients

$\displaystyle\widehat{\psi}_{0}(k)=\frac{f_{\mathsf{E}}^{*}(-1-k\frac{2\pi}{\log
2}\mathrm{i})}{f_{\mathsf{E}}^{*}(-1)}=\frac{\Gamma(m-1-\frac{2\pi k}{\log
2}\mathrm{i})}{\Gamma(m-1)}.$ (3.49)

Let $\\{x\\}:=x-\lfloor x\rfloor$ denote the fractional part of a real number
$x$, and suppose that $m\to\infty$ along a subsequence such that $\\{\lg
m\\}=\\{(\log m)/d\\}\to u\in[0,1]$. (Recall that $d=\log 2$.) It then follows
from (3.49) and [32, 5.11.12] that, for any $k\in\mathbb{Z}$,

$\displaystyle\widehat{\psi}_{0}(k)\sim m^{-(2\pi k/\log
2)\mathrm{i}}=e^{-2\pi k(\lg m)\mathrm{i}}\to e^{-2\pi
ku\mathrm{i}}=\widehat{\delta_{du}}(k),$ (3.50)

where $\delta_{du}$ is a point mass at $du$. Hence, by the continuity theorem,
the function $\psi_{0}(x)$ converges weakly (as a measure on the circle
$\mathbb{R}/d\mathbb{Z}$) to $\delta_{du}$, which roughly means that for large
$m$, $\psi_{0}(x)$ is concentrated at $x$ close to $du\approx d\\{\lg m\\}$.
Hence, still roughly, $\psi_{E}(\log n)$ in (3.10) is large when $\\{\lg
n\\}=\\{\log n/d\\}\approx\\{\lg m\\}$, but small otherwise. This should not
be surprising. For a large $n$, in the first generations of the construction
of the trie from $n$ strings in Section 2.2, by the law of large numbers
almost exatly half of the strings are passed to the left child and half to the
right child. Consequently, there will be many fringe trees in $\Upsilon_{n}$,
and thus in $\widehat{\Upsilon}_{n}$, of size $\approx 2^{-j}n$ for integers
$j$, but few for intermediate sizes, until we get down to small sizes $m$.
Thus, for a fixed large $m$, we expect many fringe trees of size $m$ when
$n/m$ is close to a power of 2, which is the same as $\\{\lg n\\}\approx\\{\lg
m\\}$.  $\triangle$

######  Remark 3.11.

If we consider the ratio between the probabilities for two given trees $t$ of
the same size, then there are no oscillations even in the periodic case, since
the oscillations in Corollaries 3.7 and 3.8 for the two trees cancel by (3.8)
and (3.12).  $\triangle$

##  4\. Compressed binary search trees

In this section we study fringe trees of the compressed BST
$\widehat{\mathcal{B}}_{n}$. Let $t$ be a full binary tree, and let as in
Section 2.4 $\widecheck{{\mathfrak{T}}}_{t}$ be the set of all binary trees
that can be obtained by inserting additional nodes of outdegree 1 in the
edges. As said in the introduction, Aldous [1] shows that the random fringe
trees $\mathcal{B}^{*}_{n}$ converge in distribution to some limiting random
fringe tree $\mathcal{B}^{*}_{\infty}$ as ${n\to\infty}$, and Devroye [9, 10]
show asymptotic normality of the subtree counts $N_{t}(\mathcal{B}_{n})$.
Furthermore, [1] shows that the distribution of the limiting random fringe
tree $\mathcal{B}^{*}_{\infty}$ equals the mixture
$\sum_{k=1}^{\infty}\frac{2}{(k+1)(k+2)}\textrm{Law}(\mathcal{B}_{k})$, i.e,
for any set ${\mathfrak{S}}\subseteq{\mathfrak{T}}$,

$\displaystyle\operatorname{\mathbb{P}{}}\bigl{(}\mathcal{B}^{*}_{\infty}\in{\mathfrak{S}}\bigr{)}=\sum_{k=1}^{\infty}\frac{2}{(k+1)(k+2)}\operatorname{\mathbb{P}{}}\bigl{(}\mathcal{B}_{k}\in{\mathfrak{S}}\bigr{)}.$
(4.1)

We use these results and (2.12) to obtain similar results for fringe trees of
the compressed BST $\widehat{\mathcal{B}}_{n}$.

######  Theorem 4.1.

Let $t$ be a full binary tree. Then $N_{t}(\widehat{\mathcal{B}}_{n})$ is
asymptotically normal: there exist constants $\beta_{t}>0$ and $\gamma_{t}>0$
such that, as ${n\to\infty}$,

$\displaystyle\frac{N_{t}(\widehat{\mathcal{B}}_{n})-n\beta_{t}}{\sqrt{n}}\overset{\mathrm{d}}{\longrightarrow}N(0,\gamma^{2}_{t}),$
(4.2)

with convergence of mean and variance. In particular,

$\displaystyle
N_{t}(\widehat{\mathcal{B}}_{n})/n\overset{\mathrm{p}}{\longrightarrow}\beta_{t}.$
(4.3)

Furthermore, there exists a limiting fringe tree distribution given by a
random full binary tree $\widehat{\mathcal{B}}^{*}_{\infty}$ such that for
every $t\in{\widehat{\mathfrak{T}}}$,

$\displaystyle\operatorname{\mathbb{P}{}}(\widehat{\mathcal{B}}^{*}_{\infty}=t)=\frac{3}{2}\beta_{t},$
(4.4)

and (quenched version)

$\displaystyle\operatorname{\mathbb{P}{}}(\widehat{\mathcal{B}}^{*}_{n}=t\mid\widehat{\mathcal{B}}_{n})$
$\displaystyle=\frac{N_{t}(\widehat{\mathcal{B}}_{n})}{|\widehat{\mathcal{B}}_{n}|}\overset{\mathrm{p}}{\longrightarrow}\operatorname{\mathbb{P}{}}(\widehat{\mathcal{B}}^{*}_{\infty}=t)$
(4.5) and (annealed version)
$\displaystyle\operatorname{\mathbb{P}{}}(\widehat{\mathcal{B}}^{*}_{n}=t)$
$\displaystyle=\operatorname{\mathbb{E}}{}\frac{N_{t}(\widehat{\mathcal{B}}_{n})}{|\widehat{\mathcal{B}}_{n}|}\to\operatorname{\mathbb{P}{}}(\widehat{\mathcal{B}}^{*}_{\infty}=t).$
(4.6)

We conjecture that also all higher moments converge in (4.2), but we have not
pursued this and leave it as an open problem.

###### Proof.

We use again (2.12); thus
$N_{t}(\widehat{\mathcal{B}}_{n})=\Phi(\mathcal{B}_{n})$ where $\Phi$ is
defined by (2.10)–(2.11). The asymptotic normality (4.2) (with convergence of
mean and variance) then follows from [20, Corollary 1.15]; see also [10] for
similar results. The convergence in probability (4.3) is an immediate
consequence.

Furthermore, [20, Corollary 1.15 and (1.24)] yield

$\displaystyle\beta_{t}=\sum_{k=1}^{\infty}\frac{2}{(k+1)(k+2)}\operatorname{\mathbb{E}}{}\varphi(\mathcal{B}_{k})=\sum_{k=1}^{\infty}\frac{2}{(k+1)(k+2)}\operatorname{\mathbb{P}{}}(\mathcal{B}_{k}\in\widecheck{{\mathfrak{T}}}_{t}).$
(4.7)

Alternatively, (4.3) and dominated convergence yield, together with (2.12),

$\displaystyle\beta_{t}$
$\displaystyle=\lim_{n\to\infty}\frac{\operatorname{\mathbb{E}}{}N_{t}(\widehat{\mathcal{B}}_{n})}{n}=\lim_{n\to\infty}\frac{1}{n}\sum_{v\in\mathcal{B}_{n}}\boldsymbol{1}\\{\mathcal{B}_{n}^{v}\in\widecheck{{\mathfrak{T}}}_{t}\\}=\lim_{n\to\infty}\operatorname{\mathbb{P}{}}\bigl{(}\mathcal{B}^{*}_{n}\in\widecheck{{\mathfrak{T}}}_{t}\bigr{)}$
$\displaystyle=\operatorname{\mathbb{P}{}}\bigl{(}\mathcal{B}^{*}_{\infty}\in\widecheck{{\mathfrak{T}}}_{t}\bigr{)},$
(4.8)

which agrees with (4.7) by (4.1). The union
$\bigcup_{t\in{\widehat{\mathfrak{T}}}}\widecheck{{\mathfrak{T}}}_{t}$ of the
sets $\widecheck{{\mathfrak{T}}}_{t}$ over all full binary trees $t$ is the
set $\mathfrak{T}^{\\{0,2\\}}$ of all binary trees where the root has degree 2
or 0. Hence, (4) implies

$\displaystyle\sum_{t\in{\widehat{\mathfrak{T}}}}\beta_{t}=\sum_{t\in{\widehat{\mathfrak{T}}}}\operatorname{\mathbb{P}{}}\bigl{(}\mathcal{B}^{*}_{\infty}\in\widecheck{{\mathfrak{T}}}_{t}\bigr{)}=\operatorname{\mathbb{P}{}}\bigl{(}\mathcal{B}^{*}_{\infty}\in\mathfrak{T}^{\\{0,2\\}}\bigr{)}=\lim_{n\to\infty}\operatorname{\mathbb{P}{}}\bigl{(}\mathcal{B}^{*}_{n}\in\mathfrak{T}^{\\{0,2\\}}\bigr{)}.$
(4.9)

If $v\in\mathcal{B}_{n}$, then the fringe tree
$\mathcal{B}_{n}^{v}\in\mathfrak{T}^{\\{0,2\\}}$ $\iff$ the degree
$d(v)\in\\{0,2\\}$ $\iff$ $v\in\widehat{\mathcal{B}}_{n}$. Hence, (4.9)
yields, using (2.7) and dominated convergence,

$\displaystyle\sum_{t\in{\widehat{\mathfrak{T}}}}\beta_{t}=\lim_{n\to\infty}\operatorname{\mathbb{E}}{}\frac{|\\{v\in\mathcal{B}_{n}:v\in\widehat{\mathcal{B}}_{n}\\}|}{n}=\lim_{n\to\infty}\operatorname{\mathbb{E}}{}\frac{|\widehat{\mathcal{B}}_{n}|}{n}=\frac{2}{3}.$
(4.10)

Consequently, $\sum_{t\in{\widehat{\mathfrak{T}}}}\frac{3}{2}\beta_{t}=1$, so
(4.4) defines a probability distribution on full binary trees.

Combining (4.3) and (2.7) we obtain

$\displaystyle\frac{N_{t}(\widehat{\mathcal{B}}_{n})}{|\widehat{\mathcal{B}}_{n}|}\overset{\mathrm{p}}{\longrightarrow}\frac{3}{2}\beta_{t}.$
(4.11)

The quenched and annealed convergence in distribution (4.5) and (4.6) then
follow from (1.2) and (1.3) (and dominated convergence again).

It remains to show that $\beta_{t}>0$ and $\gamma_{t}>0$. For $\beta_{t}$,
this is immediate from (4.7). For $\gamma_{t}$, let $m:=|t|_{\mathsf{e}}$ and
note first that we may assume $m\geq 2$, since for $t=\bullet$, we have
$N_{\bullet}(\widehat{\mathcal{B}}_{n})=|\widehat{\mathcal{B}}_{n}|_{\mathsf{e}}=|\mathcal{B}_{n}|_{\mathsf{e}}$,
and thus $\gamma^{2}_{\bullet}=2/45$ by (2.8). Fix a suitable $k\geq m$; we
may take $k=4$ if $m=2$ and $k=m$ if $m\geq 3$. Assume $n\geq 2k-1$. In the
construction of the binary search tree $\mathcal{B}_{n}$ in Section 2.3, stop
at every node that receives exactly $2k-1$ items. At each such node, peek into
the future to see whether the fringe tree at that node will be a full binary
tree (with $k$ leaves), or it will contain some node of outdegree 1; in the
latter case, continue the recursive constraction at this node too, but in the
first case, just mark the node and leave it. The result is a subtree of
$\mathcal{B}_{n}$ that we denote by $\mathcal{B}^{\prime}_{n}$; it has a
number $N^{\prime}_{k}$ of marked nodes with $2k-1$ items each, and we recover
$\mathcal{B}_{n}$ by replacing each marked node by a random full binary tree
with $k$ leaves (more precisely, a copy of $\mathcal{B}_{2k-1}$ conditioned on
being a full binary tree); denote these trees by
$T_{1},\dots,T_{N^{\prime}_{k}}$. Every fringe tree $\mathcal{B}_{n}^{v}$ that
belongs to $\widecheck{{\mathfrak{T}}}_{t}$, and thus has $m$ leaves, either
lies completely in $\mathcal{B}^{\prime}_{n}$ or in one of the
$N^{\prime}_{k}$ trees $T_{i}$; furthermore, any fringe tree of $T_{i}$ that
belongs to $\widecheck{{\mathfrak{T}}}_{t}$ has to be a copy of $t$. Thus we
have

$\displaystyle
N_{t}(\widehat{\mathcal{B}}_{n})=N^{\prime\prime}+\sum_{i=1}^{N^{\prime}_{k}}N_{t}(T_{i})$
(4.12)

where $N^{\prime\prime}$ is determined by $\mathcal{B}^{\prime}_{n}$.
Condition on $\mathcal{B}^{\prime}_{n}$ (which also determines
$N^{\prime}_{k}$). Then the trees $T_{i}$ are (conditionally) independent and
identically distributed, and, by our choice of $k$,
$0<\operatorname{\mathbb{P}{}}(N_{t}(T_{i})=1)<1$ so
$c:=\operatorname{Var}N_{t}(T_{i})>0$. Hence (4.12) implies that the
conditional variance

$\displaystyle\operatorname{Var}\bigl{[}N_{t}(\widehat{\mathcal{B}}_{n})\mid\mathcal{B}^{\prime}_{n}\bigr{]}=\sum_{i=1}^{N^{\prime}_{k}}\operatorname{Var}N_{t}(T_{i})=cN^{\prime}_{k}.$
(4.13)

The number $N^{\prime}_{k}$ equals the number of fringe trees of
$\mathcal{B}_{n}$ that are full binary trees of size $2k-1$; we let
${\widehat{\mathfrak{T}}}_{k}$ be the set of all such full binary trees. Thus

$\displaystyle
N^{\prime}_{k}/n=\operatorname{\mathbb{P}{}}\bigl{(}\mathcal{B}^{*}_{n}\in{\widehat{\mathfrak{T}}}_{k}\mid\mathcal{B}_{n}\bigr{)}.$
(4.14)

Hence we obtain from the known convergence
$\mathcal{B}^{*}_{n}\overset{\mathrm{d}}{\longrightarrow}\mathcal{B}^{*}_{\infty}$

$\displaystyle\operatorname{\mathbb{E}}{}N^{\prime}_{k}/n=\operatorname{\mathbb{E}}{}\operatorname{\mathbb{P}{}}\bigl{(}\mathcal{B}^{*}_{n}\in{\widehat{\mathfrak{T}}}_{k}\mid\mathcal{B}_{n}\bigr{)}=\operatorname{\mathbb{P}{}}\bigl{(}\mathcal{B}^{*}_{n}\in{\widehat{\mathfrak{T}}}_{k}\bigr{)}\to\operatorname{\mathbb{P}{}}\bigl{(}\mathcal{B}^{*}_{\infty}\in{\widehat{\mathfrak{T}}}_{k}\bigr{)}=:c^{\prime},$
(4.15)

where it follows from (4.1) that $c^{\prime}>0$. Recall also the law of total
variance: for any square-integrable random variable $X$ and random variable
(or $\sigma$-field) $Y$

$\displaystyle\operatorname{Var}X=\operatorname{\mathbb{E}}{}\operatorname{Var}[X\mid
Y]+\operatorname{Var}\operatorname{\mathbb{E}}{}[X\mid
Y]\geq\operatorname{\mathbb{E}}{}\operatorname{Var}[X\mid Y].$ (4.16)

Consequently, (4.13) and (4.15) yield

$\displaystyle\operatorname{Var}\bigl{[}N_{t}(\widehat{\mathcal{B}}_{n})\bigr{]}\geq\operatorname{\mathbb{E}}{}\operatorname{Var}\bigl{[}N_{t}(\widehat{\mathcal{B}}_{n})\mid\mathcal{B}^{\prime}_{n}\bigr{]}=c\operatorname{\mathbb{E}}{}N^{\prime}_{k}=cc^{\prime}n+o(n).$
(4.17)

The convergence of variance in (4.2) thus yields $\gamma^{2}_{t}\geq
cc^{\prime}>0$. ∎

######  Remark 4.2.

Theorem 4.1 extends to multivariate limits for several full binary trees by
the Cramér–Wold device; we omit the details.  $\triangle$

######  Remark 4.3.

The random BST can be constructed by a simple continuous-time branching
process, which yields a simple description of the limiting random fringe tree
$\mathcal{B}^{*}_{\infty}$ as this branching process stopped at an
exponentially distributed random time [1] (see also [21, Example 6.2]). In
principle, this leads to a description of the compressed BST and its limiting
fringe tree $\widehat{\mathcal{B}}^{*}_{\infty}$, but this becomes more
complicated and we have not been able to use it, for example to compute
$\beta_{t}$ and the probabilities in (4.4); we therefore do not give the
details. The rather complicated explicit values of $\beta_{t}$ given in
Appendix A for small $t$ also suggest that no really simple description of
$\widehat{\mathcal{B}}^{*}_{\infty}$ exists.  $\triangle$

For the random extended fringe tree $\widehat{\mathcal{B}}^{**}_{n}$ we obtain
for the probabilities $q(\widehat{\mathcal{B}}_{n};t)$ defined in Section 2.5:

######  Corollary 4.4.

Let $t$ be a full binary tree. Then

$\displaystyle q(\widehat{\mathcal{B}}_{n};t\mid\widehat{\mathcal{B}}_{n})$
$\displaystyle\overset{\mathrm{p}}{\longrightarrow}q(\widehat{\mathcal{B}}^{**}_{\infty};t)=3|t|_{\mathsf{e}}\beta_{t},$
(4.18) $\displaystyle q(\widehat{\mathcal{B}}_{n};t)$
$\displaystyle\longrightarrow q(\widehat{\mathcal{B}}^{**}_{\infty};t).$
(4.19)

###### Proof.

Immediate from (4.4)–(4.5) and Lemma 2.2. ∎

The numbers $\beta_{t}$ are given by (4.7), but since
$\widecheck{{\mathfrak{T}}}_{t}$ is an infinite set, this formula is of
limited use for explicit calculations. In the remainder of the section, we
give one way to find $\beta_{t}$ and thus the limiting fringe distribution
$\widehat{\mathcal{B}}^{*}_{\infty}$ more explicitly.

######  Problem 4.5.

It seems possible that similar but more complicated arguments might make it
possible to compute also the asymptotic variance $\gamma^{2}_{t}$, but we have
not pursued this, and we leave it as an open problem.

###  4.1. Computing $\beta_{t}$

We define a generating function for binary trees and sets of binary trees as
follows. For a binary tree $T$, let

$\displaystyle p_{T}$
$\displaystyle:=\operatorname{\mathbb{P}{}}(\mathcal{B}_{|T|}=T),$ (4.20)
$\displaystyle F_{T}(x)$ $\displaystyle:=p_{T}x^{|T|}.$ (4.21)

For any set ${{\mathfrak{T}}_{0}}$ of binary trees, let

$\displaystyle
F_{{{\mathfrak{T}}_{0}}}(x):=\sum_{T\in{{\mathfrak{T}}_{0}}}F_{T}(x).$ (4.22)

These generating functions will help us to compute fringe tree probabilities
by the following simple formula for the BST.

######  Lemma 4.6.

If ${{\mathfrak{T}}_{0}}$ is a set of binary trees, then

$\displaystyle\operatorname{\mathbb{P}{}}(\mathcal{B}^{*}_{\infty}\in{{\mathfrak{T}}_{0}})=2\int_{0}^{1}F_{{\mathfrak{T}}_{0}}(x)(1-x)\,\mathrm{d}x.$
(4.23)

###### Proof.

By (4.22) and linearity, it suffices to consider the case when
${{\mathfrak{T}}_{0}}=\\{T\\}$ for a single binary tree $T$. Let $k:=|T|$.
Then, by (4.1),

$\displaystyle\operatorname{\mathbb{P}{}}(\mathcal{B}^{*}_{\infty}=T)$
$\displaystyle=\frac{2}{(k+1)(k+2)}\operatorname{\mathbb{P}{}}(\mathcal{B}_{k}=T)=2p_{T}\int_{0}^{1}x^{k}(1-x)\,\mathrm{d}x$
$\displaystyle=2\int_{0}^{1}F_{T}(x)(1-x)\,\mathrm{d}x,$ (4.24)

which shows (4.23). ∎

Let $t$ be a full binary tree, and recall that
$\widecheck{{\mathfrak{T}}}_{t}^{+}$ is the set of all binary trees that
contract to $t$, and $\widecheck{{\mathfrak{T}}}_{t}$ the subset of all such
trees where the root has degree 2 or 0. In other words,
$\widecheck{{\mathfrak{T}}}_{t}$ is the set of all binary trees that can be
obtained from $t$ by replacing any edge by a path, and
$\widecheck{{\mathfrak{T}}}_{t}^{+}$ is the set of all binary trees that can
be obtained from these by adding a path of length $\ell\geq 0$ to the root.
Define the corresponding generating functions

$\displaystyle G_{t}(x)$
$\displaystyle:=F_{\widecheck{{\mathfrak{T}}}_{t}^{+}}(x),$ (4.25)
$\displaystyle H_{t}(x)$
$\displaystyle:=F_{\widecheck{{\mathfrak{T}}}_{t}}(x).$ (4.26)

We state a series of lemmas to help us compute these generating functions.

######  Lemma 4.7.

If $T$ is a path with $l\geq 1$ nodes, then

$\displaystyle F_{T}(x)=\frac{x^{\ell}}{\ell!}.$ (4.27)

###### Proof.

By the construction of the BST,

$\displaystyle
p_{T}=\operatorname{\mathbb{P}{}}(\mathcal{B}_{\ell}=T)=\frac{1}{\ell}\cdot\frac{1}{\ell-1}\dotsm\frac{1}{1}=\frac{1}{\ell!},$
(4.28)

since a given path $T$ is obtained by exactly one choice of pivot each time.
Hence, (4.27) follows by the definition (4.21). ∎

######  Lemma 4.8.

If ${{\mathfrak{T}}_{P}}$ is the set consisting of all paths with any number
$\ell\geq 1$ of nodes, then

$\displaystyle
F_{{\mathfrak{T}}_{P}}(x)=\tfrac{1}{2}\bigl{(}e^{2x}-1\bigr{)}.$ (4.29)

###### Proof.

There are $2^{\ell-1}$ different paths with $\ell$ nodes. Thus Lemma 4.7
yields, letting $P_{\ell}$ denote any path with $|P_{\ell}|=\ell$,

$\displaystyle
F_{{\mathfrak{T}}_{P}}(x)=\sum_{\ell=1}^{\infty}2^{\ell-1}F_{P_{\ell}}(x)=\frac{1}{2}\sum_{\ell=1}^{\infty}\frac{(2x)^{\ell}}{\ell!}=\frac{1}{2}\bigl{(}e^{2x}-1\bigr{)}.$
(4.30)

∎

######  Lemma 4.9.

Let $T$ be a binary tree and let $T_{1}$ be a tree obtained by adding a path
with $\ell\geq 1$ nodes to the root of $T$. Then

$\displaystyle
F_{T_{1}}(x)=\int_{0}^{x}F_{T}(y)\frac{(x-y)^{\ell-1}}{(\ell-1)!}\,\mathrm{d}y.$
(4.31)

###### Proof.

Let $|T|=k$; then $|T_{1}|=k+\ell$. In analogy with (4.28), the construction
of the BST yields

$\displaystyle p_{T_{1}}$
$\displaystyle=\operatorname{\mathbb{P}{}}(\mathcal{B}_{k+\ell}=T_{1})=\frac{1}{k+\ell}\cdot\frac{1}{k+\ell-1}\dotsm\frac{1}{k+1}\cdot\operatorname{\mathbb{P}{}}(\mathcal{B}_{k}=T)$
$\displaystyle=\frac{k!}{(k+\ell)!}p_{T},$ (4.32)

since $T_{1}$ is obtained by exactly one choice of pivot each of the first
$\ell$ times, and then by the same choices as for $T$. On the other hand, a
standard Beta integral yields

$\displaystyle\int_{0}^{x}F_{T}(y)(x-y)^{\ell-1}\,\mathrm{d}y$
$\displaystyle=p_{T}\int_{0}^{x}y^{k}(x-y)^{\ell-1}\,\mathrm{d}y=p_{T}x^{k+\ell}\int_{0}^{1}z^{k}(1-z)^{\ell-1}\,\mathrm{d}z$
$\displaystyle=p_{T}\frac{\Gamma(k+1)\Gamma(\ell)}{\Gamma(k+1+\ell)}x^{k+\ell}=p_{T}\frac{k!\,(\ell-1)!}{(k+\ell)!}x^{k+\ell}.$
(4.33)

By (4.1) and (4.21), this equals $(\ell-1)!\,x^{k+\ell}p_{T_{1}}$, and thus
(4.31) follows by the definition (4.21). ∎

######  Lemma 4.10.

Let ${{\mathfrak{T}}_{0}}$ be a set of binary trees and let
${\mathfrak{T}}_{1}$ be the set of trees obtained by adding a path with any
number $\ell\geq 1$ of nodes to the root of any tree
$T\in{{\mathfrak{T}}_{0}}$. Then

$\displaystyle
F_{{\mathfrak{T}}_{1}}(x)=2\int_{0}^{x}F_{{{\mathfrak{T}}_{0}}}(y)e^{2(x-y)}\,\mathrm{d}y.$
(4.34)

###### Proof.

For each $\ell$, there are $2^{\ell}$ different paths of length $\ell$ that
can be added (including the choice of edge from the end of the path to the
former root). Hence, by Lemma 4.9, summing over all $T\in{{\mathfrak{T}}_{0}}$
and all possible paths,

$\displaystyle
F_{{{\mathfrak{T}}_{0}}}(x)=\sum_{T\in{{\mathfrak{T}}_{0}}}\sum_{\ell\geq
1}2^{\ell}\int_{0}^{x}F_{T}(y)\frac{(x-y)^{\ell-1}}{(\ell-1)!}\,\mathrm{d}y=2\int_{0}^{x}F_{{{\mathfrak{T}}_{0}}}(y)e^{2(x-y)}\,\mathrm{d}y.$
(4.35)

∎

######  Lemma 4.11.

Let $T_{\mathsf{L}}$ and $T_{\mathsf{R}}$ be binary trees and let $T_{1}$ be a
tree obtained by taking a path with $\ell\geq 1$ nodes and adding
$T_{\mathsf{L}}$ and $T_{\mathsf{R}}$ as the left and right subtrees of the
last node in the path. Then

$\displaystyle
F_{T_{1}}(x)=\int_{0}^{x}F_{T_{\mathsf{L}}}(y)F_{T_{\mathsf{R}}}(y)\frac{(x-y)^{\ell-1}}{(\ell-1)!}\,\mathrm{d}y.$
(4.36)

###### Proof.

This is similar to the proof of Lemma 4.9. Let
$|T_{\mathsf{L}}|=k_{\mathsf{L}}$ and $|T_{\mathsf{R}}|=k_{\mathsf{R}}$; then
$|T_{1}|=k_{\mathsf{L}}+k_{\mathsf{R}}+\ell$. The same argument as for (4.1)
now yields

$\displaystyle p_{T_{1}}$
$\displaystyle=\operatorname{\mathbb{P}{}}(\mathcal{B}_{k_{\mathsf{L}}+k_{\mathsf{R}}+\ell}=T_{1})=\frac{1}{k_{\mathsf{L}}+k_{\mathsf{R}}+\ell}\dotsm\frac{1}{k_{\mathsf{L}}+k_{\mathsf{R}}+1}\cdot\operatorname{\mathbb{P}{}}(\mathcal{B}_{k_{\mathsf{L}}}=T_{\mathsf{L}})\cdot\operatorname{\mathbb{P}{}}(\mathcal{B}_{k_{\mathsf{R}}}=T_{\mathsf{R}})$
$\displaystyle=\frac{(k_{\mathsf{L}}+k_{\mathsf{R}})!}{(k_{\mathsf{L}}+k_{\mathsf{R}}+\ell)!}p_{T_{\mathsf{L}}}p_{T_{\mathsf{R}}},$
(4.37)

since if the first $\ell$ pivots have been chosen correctly to form the
desired path, with the last node having left and right subtrees of sizes
$k_{\mathsf{L}}$ and $k_{\mathsf{R}}$, respectively, then the shapes of those
subtrees are independent. The rest of the proof is as for Lemma 4.9 with only
notational changes. ∎

######  Lemma 4.12.

Let ${\mathfrak{T}}_{\mathsf{L}}$ and ${\mathfrak{T}}_{\mathsf{R}}$ be two
sets of binary trees and let ${\mathfrak{T}}_{1}$ be the set of trees obtained
by taking a path with any number $\ell\geq 1$ of nodes and adding two trees
$T_{\mathsf{L}}\in{\mathfrak{T}}_{\mathsf{L}}$ and
$T_{\mathsf{R}}\in{\mathfrak{T}}_{\mathsf{R}}$ as the left and right subtrees
of the last node in the path. Then

$\displaystyle
F_{{\mathfrak{T}}_{1}}(x)=\int_{0}^{x}F_{{\mathfrak{T}}_{\mathsf{L}}}(y)F_{{\mathfrak{T}}_{\mathsf{R}}}(y)e^{2(x-y)}\,\mathrm{d}y.$
(4.38)

###### Proof.

By Lemma 4.11 and summing over $T_{\mathsf{L}}\in{\mathfrak{T}}_{\mathsf{L}}$,
$T_{\mathsf{R}}\in{\mathfrak{T}}_{\mathsf{R}}$, and $\ell\geq 1$, just as in
the proof of Lemma 4.10; note that for a given $\ell$, now there are
$2^{\ell-1}$ paths. ∎

Finally, we obtain our formula for $\beta_{t}$, using the functions $G_{t}(x)$
for which we provide a recursion.

######  Theorem 4.13.

Let $t$ be a full binary tree.

  1. (a)

The generating function $G_{t}(x)$ can be computed recursively as follows.

    1. (i)

If $t=\bullet$, then

$\displaystyle G_{\bullet}(x)=\frac{1}{2}(e^{2x}-1).$ (4.39)

    2. (ii)

If $|t|>1$, and the root of $t$ has left and right subtrees $t_{\mathsf{L}}$
and $t_{\mathsf{R}}$, then

$\displaystyle
G_{t}(x)=\int_{0}^{x}G_{t_{\mathsf{L}}}(y)G_{t_{\mathsf{R}}}(y)e^{2(x-y)}\,\mathrm{d}y.$
(4.40)

  2. (b)

Then $\beta_{t}$ is given by:

    1. (i)

If $|t|=1$, i.e, $t=\bullet$, then $\beta_{t}=1/3$.

    2. (ii)

If $|t|>1$, and the root of $t$ has left and right subtrees $t_{\mathsf{L}}$
and $t_{\mathsf{R}}$, then

$\displaystyle\beta_{t}=\int_{0}^{1}(1-x)^{2}G_{t_{\mathsf{L}}}(x)G_{t_{\mathsf{R}}}(x)\,\mathrm{d}x.$
(4.41)

###### Proof.

(a): The recursion (4.39)–(4.40) is an immediate consequence of the definition
(4.25) and Lemmas 4.8 and 4.12.

(b)(i): If $t=\bullet$, then
$N_{t}(\widehat{\mathcal{B}}_{n})=|\widehat{\mathcal{B}}_{n}|_{\mathsf{e}}$,
and thus (2.6) and (4.3) show $\beta_{t}=1/3$.

(b)(ii): Lemma 4.11 with $\ell=1$ shows, by summing over all
$T_{\mathsf{L}}\in\widecheck{{\mathfrak{T}}}_{t_{\mathsf{L}}}^{+}$ and
$T_{\mathsf{R}}\in\widecheck{{\mathfrak{T}}}_{t_{\mathsf{R}}}^{+}$, and
recalling (4.26),

$\displaystyle
H_{t}(x)=F_{\widecheck{{\mathfrak{T}}}_{t}}(x)=\int_{0}^{x}G_{t_{\mathsf{L}}}(y)G_{t_{\mathsf{R}}}(y)\,\mathrm{d}y.$
(4.42)

Hence, (4) and Lemma 4.6 yield

$\displaystyle\beta_{t}$
$\displaystyle=\operatorname{\mathbb{P}{}}(\mathcal{B}^{*}_{\infty}\in\widecheck{{\mathfrak{T}}}_{t})=2\int_{0}^{1}H_{t}(x)(1-x)\,\mathrm{d}x=2\iint_{0\leq
y\leq x\leq
1}(1-x)G_{t_{\mathsf{L}}}(y)G_{t_{\mathsf{R}}}(y)\,\mathrm{d}y\,\mathrm{d}x$
$\displaystyle=\int_{0}^{1}(1-y)^{2}G_{t_{\mathsf{L}}}(y)G_{t_{\mathsf{R}}}(y)\,\mathrm{d}y,$
(4.43)

which proves (4.41). (Alternatively, one can use integration by parts in
(4.1).) ∎

######  Remark 4.14.

Note that (4.40) and (4.41) hold for $t=\bullet$ too if we define
$G_{\emptyset}:=1$.

Furthermore, (4.41), (4.40), and an integration by parts yield the alternative
formula

$\displaystyle\beta_{t}$ $\displaystyle=\int_{0}^{1}(1-x)^{2}e^{2x}\cdot
G_{t_{\mathsf{L}}}(x)G_{t_{\mathsf{R}}}(x)e^{-2x}\,\mathrm{d}x=-\int_{0}^{1}\Bigl{(}(1-x)^{2}e^{2x}\Bigr{)}^{\prime}\cdot\Bigl{(}e^{-2x}G_{t}(x)\Bigr{)}\,\mathrm{d}x$
$\displaystyle=\int_{0}^{1}2x(1-x)e^{2x}\cdot
e^{-2x}G_{t}(x)\,\mathrm{d}x=\int_{0}^{1}2x(1-x)G_{t}(x)\,\mathrm{d}x.$ (4.44)

This is perhaps more elegant than (4.41), but (4.41) seems better for
calculations.  $\triangle$

##  Appendix A Examples

We give here some examples of exact and numerical values for the limits of
$\operatorname{\mathbb{P}{}}(T_{n}^{*}=t)$ and $q(T_{n};t)$ that describe the
distribution of random fringe trees and extended fringe trees when $T_{n}$ is
a random Patricia trie $\widehat{\Upsilon}_{n}$ or a compressed binary search
tree $\widehat{\mathcal{B}}_{n}$. We consider only the smallest fringe trees
$t$, with $|t|_{\mathsf{e}}\leq 4$. Since we consider only full binary trees
$T_{n}$, we assume that $t$ is a full binary tree; moreover, the case
$|t|_{\mathsf{e}}=1$ is trivial, since then for any sequence $T_{n}$ of full
binary trees

$\displaystyle\operatorname{\mathbb{P}{}}(T^{*}_{n}=\bullet\mid
T_{n})=\frac{|T_{n}|_{\mathsf{e}}}{|T_{n}|}=\frac{|T_{n}|_{\mathsf{e}}}{2|T_{n}|_{\mathsf{e}}-1}\to\frac{1}{2}$
(A.1)

provided $|T_{n}|_{\mathsf{e}}\to\infty$. Hence we consider the small trees in
Figure 1 with the notations given there, and their mirror images which we may
ignore since they give the same result, with $p$ and $q$ exchanged for
$\widehat{\Upsilon}_{n}$. For simplicity, we state only the annealed versions
of the results; note that the (stronger) quenched results too hold by the
results above. Also for simplicity, for Patricia tries, we do not show the
oscillations in that appear in the periodic case (in particular in the
symmetric case $p=q=\frac{1}{2}$); we give only the constant terms coming from
the constant term $f_{\mathsf{E}}^{*}(-1)$ in (3.8) and ignore the oscillating
terms there (which is the same as averaging $\psi_{\mathsf{E}}$ over a
period). We denote this by $\approx$ below; note that in the aperiodic case,
$\approx$ thus means $\to$. We use freely notation from the previous sections.

######  Remark A.1.

If we ignore orientations and regard the random trees as cladograms, see
Remark 1.1, and for Patricia tries consider only the symmetric case
$p=\frac{1}{2}$, then we do not have to consider mirror images, and also
$t_{4b}$ disappears; instead we should multiply the results below for $t_{3}$
by 2, and for $t_{4a}$ by 4 (the numbers of possible orientations).
$\triangle$

###  A.1. The uniform full binary tree

For comparison, we give also the corresponding values for the uniform random
full binary tree with $n$ leaves, here denoted ${\mathcal{U}}_{n}$. (Note that
this random tree is quite different from $\widehat{\Upsilon}_{n}$ and
$\widehat{\mathcal{B}}_{n}$; for example, as is well known, typically
${\mathcal{U}}_{n}$ has height of order $\sqrt{n}$, while
$\widehat{\Upsilon}_{n}$ and $\widehat{\mathcal{B}}_{n}$ have heights of order
$\log$n.)

The random full binary tree ${\mathcal{U}}_{n}$ can be regarded as a
conditioned Galton–Watson tree with critical offspring distribution
$\operatorname{\mathbb{P}{}}(\xi=0)=\operatorname{\mathbb{P}{}}(\xi=2)=\frac{1}{2}$,
see e.g [2], and thus it follows by Aldous [1, Lemma 9] (see also [27]) that
the asymptotic fringe tree distribution is the corresponding (unconditioned)
Galton–Watson tree, which in this case simply means that for every full binary
tree $t$,

$\displaystyle\operatorname{\mathbb{P}{}}({\mathcal{U}}^{*}_{n}=t)\to
2^{-|t|}=2^{1-2|t|_{\mathsf{e}}}.$ (A.2)

We have also the quenched version [26, Theorem 7.12]
$\operatorname{\mathbb{P}{}}({\mathcal{U}}^{*}_{n}=t\mid{\mathcal{U}}_{n})\to
2^{-|t|}$, and thus Lemma 2.2 yields

$\displaystyle
q({\mathcal{U}}_{n};t)\to|t|_{\mathsf{e}}2^{1-|t|}=|t|_{\mathsf{e}}2^{2-2|t|_{\mathsf{e}}}.$
(A.3)

(0,0)(1,1)(2,0) $t_{2}$(6,0)(8,2)(9,1)(10,0) (8,0)(9,1)
$t_{3}$(14,0)(17,3)(18,2)(19,1)(20,0) (16,0)(18,2) (18,0)(19,1)
$t_{4a}$(24,0)(27,3)(28,2)(30,0) (26,0)(27,1)(28,2) (28,0)(27,1)
$t_{4b}$(34,0)(35,1)(37,3)(39,1)(40,0) (36,0)(35,1) (38,0)(39,1) $t_{4c}$
Figure 1. Some small full binary trees.

###  A.2. The examples

We consider the trees $t_{2},\dots,t_{4c}$ in Figure 1 one by one; for each of
them we consider the different random fringe trees studied above.

######  Example A.2.

$\mathbf{t_{2}}$ : For the Patricia trie $\widehat{\Upsilon}_{n}$, note first
that we have $|t_{2}|_{\mathsf{e}}=2$,
$\mathsf{LPL}(t_{2})=\mathsf{RPL}(t_{2})=1$, $\nu_{1}(t_{2})=2$,
$\nu_{2}(t_{2})=1$, and $\nu_{k}(t_{2})=0$, $k>2$. Hence, Lemma 3.3 yields

$\displaystyle\pi_{t_{2}}=2pq.$ (A.4)

(Which perhaps is more easily seen directly.) Corollaries 3.7 and 3.8 then
yield

$\displaystyle\operatorname{\mathbb{P}{}}(\widehat{\Upsilon}_{n}^{*}=t_{2})$
$\displaystyle\approx\frac{pq}{2H},$ (A.5) $\displaystyle
q(\widehat{\Upsilon}_{n};t_{2})$ $\displaystyle\approx\frac{2pq}{H}.$ (A.6)

In particular, in the symmetric case $p=\frac{1}{2}$, when $H=\log 2$,

$\displaystyle\operatorname{\mathbb{P}{}}(\widehat{\Upsilon}_{n}^{*}=t_{2})$
$\displaystyle\approx\frac{1}{8\log 2}\doteq 0.1803,$ (A.7) $\displaystyle
q(\widehat{\Upsilon}_{n};t_{2})$ $\displaystyle\approx\frac{1}{2\log 2}\doteq
0.7213.$ (A.8)

For the compressed BST $\widehat{\mathcal{B}}_{n}$, Theorem 4.13 yields
$G_{t_{2}}(x)=\frac{1}{8}e^{4x}-\frac{1}{2}xe^{2x}-\frac{1}{8}$ and

$\displaystyle\beta_{t_{2}}=\tfrac{1}{128}e^{4}-\tfrac{1}{8}e^{2}+\tfrac{233}{384}\doteq
0.1097,$ (A.9)

Hence, Theorem 4.1 and Lemma 2.2 yield

$\displaystyle\operatorname{\mathbb{P}{}}(\widehat{\mathcal{B}}^{*}_{n}=t_{2})$
$\displaystyle\to\tfrac{3}{2}\beta_{t_{2}}=\tfrac{3}{256}e^{4}-\tfrac{3}{16}e^{2}+\tfrac{233}{256}\doteq
0.1645.$ (A.10) $\displaystyle q(\widehat{\mathcal{B}}_{n};t_{2})$
$\displaystyle\to
6\beta_{t_{2}}=\tfrac{3}{64}e^{4}-\tfrac{3}{4}e^{2}+\tfrac{233}{64}\doteq
0.6581.$ (A.11)

For the uniformly random full binary tree ${\mathcal{U}}_{n}$, (A.2)–(A.3)
yield

$\displaystyle\operatorname{\mathbb{P}{}}({\mathcal{U}}^{*}_{n}=t_{2})$
$\displaystyle\to\frac{1}{8}=0.125,$ (A.12) $\displaystyle
q({\mathcal{U}}_{n};t_{2})$ $\displaystyle\to\frac{1}{2}=0.5.$ (A.13)

$\triangle$

######  Example A.3.

$\mathbf{t_{3}}$ : For $\widehat{\Upsilon}_{n}$, we have
$|t_{3}|_{\mathsf{e}}=3$, $\mathsf{LPL}(t_{3})=2$, $\mathsf{RPL}(t_{3})=3$,
and $\nu_{1}(t_{3})=3$, $\nu_{2}(t_{3})=1$, $\nu_{3}(t_{3})=1$. Hence, Lemma
3.3 yields

$\displaystyle\pi_{t_{3}}=\frac{6p^{3}q^{2}}{1-p^{2}-q^{2}}=\frac{6p^{3}q^{2}}{2pq}=3p^{2}q.$
(A.14)

Corollaries 3.7 and 3.8 then yield

$\displaystyle\operatorname{\mathbb{P}{}}(\widehat{\Upsilon}_{n}^{*}=t_{3})$
$\displaystyle\approx\frac{p^{2}q}{4H},$ (A.15) $\displaystyle
q(\widehat{\Upsilon}_{n};t_{3})$ $\displaystyle\approx\frac{3p^{2}q}{2H}.$
(A.16)

In particular, in the symmetric case $p=\frac{1}{2}$, when $H=\log 2$,

$\displaystyle\operatorname{\mathbb{P}{}}(\widehat{\Upsilon}_{n}^{*}=t_{3})$
$\displaystyle\approx\frac{1}{32\log 2}\doteq 0.0451,$ (A.17) $\displaystyle
q(\widehat{\Upsilon}_{n};t_{3})$ $\displaystyle\approx\frac{3}{16\log 2}\doteq
0.2705.$ (A.18)

For $\widehat{\mathcal{B}}_{n}$, Theorem 4.13 yields

$\displaystyle\beta_{t_{3}}=\frac{1}{1728}e^{6}-\frac{1}{256}e^{4}-\frac{3}{64}e^{2}+\frac{2447}{6912}\doteq
0.0279.$ (A.19)

Hence, Theorem 4.1 and Lemma 2.2 yield

$\displaystyle\operatorname{\mathbb{P}{}}(\widehat{\mathcal{B}}^{*}_{n}=t_{3})$
$\displaystyle\to\frac{3}{2}\beta_{t_{3}}=\frac{1}{1152}e^{6}-\frac{3}{512}e^{4}-\frac{9}{128}e^{2}+\frac{2447}{4608}\doteq
0.0418,$ (A.20) $\displaystyle q(\widehat{\mathcal{B}}_{n};t_{3})$
$\displaystyle\to
9\beta_{t_{3}}=\frac{1}{192}e^{6}-\frac{9}{256}e^{4}-\frac{27}{64}e^{2}+\frac{2447}{768}\doteq
0.2507.$ (A.21)

For ${\mathcal{U}}_{n}$, (A.2)–(A.3) yield

$\displaystyle\operatorname{\mathbb{P}{}}({\mathcal{U}}^{*}_{n}=t_{3})$
$\displaystyle\to\frac{1}{32}=0.03125,$ (A.22) $\displaystyle
q({\mathcal{U}}_{n};t_{3})$ $\displaystyle\to\frac{3}{16}=0.1875.$ (A.23)

$\triangle$

######  Example A.4.

$\mathbf{t_{4a}}$ : For $\widehat{\Upsilon}_{n}$, we have
$|t_{4a}|_{\mathsf{e}}=4$, $\mathsf{LPL}(t_{4a})=3$, $\mathsf{RPL}(t_{4a})=6$,
and $\nu_{1}(t_{4a})=4$, $\nu_{2}(t_{4a})=1$, $\nu_{3}(t_{4a})=1$,
$\nu_{4}(t_{4a})=1$. Hence, Lemma 3.3 yields

$\displaystyle\pi_{t_{4a}}=\frac{24p^{6}q^{3}}{(1-p^{2}-q^{2})(1-p^{3}-q^{3})}=\frac{24p^{6}q^{3}}{2pq\cdot
3pq}=4p^{4}q.$ (A.24)

Corollaries 3.7 and 3.8 then yield

$\displaystyle\operatorname{\mathbb{P}{}}(\widehat{\Upsilon}_{n}^{*}=t_{4a})$
$\displaystyle\approx\frac{p^{4}q}{6H},$ (A.25) $\displaystyle
q(\widehat{\Upsilon}_{n};t_{4a})$ $\displaystyle\approx\frac{4p^{4}q}{3H}.$
(A.26)

In particular, in the symmetric case $p=\frac{1}{2}$, when $H=\log 2$,

$\displaystyle\operatorname{\mathbb{P}{}}(\widehat{\Upsilon}_{n}^{*}=t_{4a})$
$\displaystyle\approx\frac{1}{192\log 2}\doteq 0.0075,$ (A.27) $\displaystyle
q(\widehat{\Upsilon}_{n};t_{4a})$ $\displaystyle\approx\frac{1}{24\log
2}\doteq 0.0601.$ (A.28)

For $\widehat{\mathcal{B}}_{n}$, Theorem 4.13 yields

$\displaystyle\beta_{t_{4a}}=\frac{1}{32768}e^{8}-\frac{1}{4608}e^{6}-\frac{11}{512}e^{2}+\frac{47503}{294912}\doteq
0.0057.$ (A.29)

Hence, Theorem 4.1 and Lemma 2.2 yield

$\displaystyle\operatorname{\mathbb{P}{}}(\widehat{\mathcal{B}}^{*}_{n}=t_{4a})$
$\displaystyle\to\frac{3}{2}\beta_{t_{4a}}=\frac{3}{65536}e^{8}-\frac{1}{3072}e^{6}-\frac{33}{1024}e^{2}+\frac{47503}{196608}\doteq
0.0086,$ (A.30) $\displaystyle q(\widehat{\mathcal{B}}_{n};t_{4a})$
$\displaystyle\to
12\beta_{t_{4a}}=\frac{3}{8192}e^{8}-\frac{1}{384}e^{6}-\frac{33}{128}e^{2}+\frac{47503}{24576}\doteq
0.0690.$ (A.31)

For ${\mathcal{U}}_{n}$, (A.2)–(A.3) yield

$\displaystyle\operatorname{\mathbb{P}{}}({\mathcal{U}}^{*}_{n}=t_{4a})$
$\displaystyle\to\frac{1}{128}\doteq 0.0078,$ (A.32) $\displaystyle
q({\mathcal{U}}_{n};t_{4a})$ $\displaystyle\to\frac{1}{16}=0.0625.$ (A.33)

$\triangle$

######  Example A.5.

$\mathbf{t_{4b}}$ : For $\widehat{\Upsilon}_{n}$, we have
$|t_{4b}|_{\mathsf{e}}=4$, $\mathsf{LPL}(t_{4b})=4$, $\mathsf{RPL}(t_{4b})=5$,
and $\nu_{1}(t_{4b})=4$, $\nu_{2}(t_{4b})=1$, $\nu_{3}(t_{4b})=1$,
$\nu_{4}(t_{4b})=1$. Hence, Lemma 3.3 yields

$\displaystyle\pi_{t_{4b}}=\frac{24p^{5}q^{4}}{(1-p^{2}-q^{2})(1-p^{3}-q^{3})}=\frac{24p^{5}q^{4}}{2pq\cdot
3pq}=4p^{3}q^{2}.$ (A.34)

Corollaries 3.7 and 3.8 then yield

$\displaystyle\operatorname{\mathbb{P}{}}(\widehat{\Upsilon}_{n}^{*}=t_{4b})$
$\displaystyle\approx\frac{p^{3}q^{2}}{6H},$ (A.35) $\displaystyle
q(\widehat{\Upsilon}_{n};t_{4b})$
$\displaystyle\approx\frac{4p^{3}q^{2}}{3H}.$ (A.36)

All other results are by symmetry the same as for $t_{4b}$.  $\triangle$

######  Example A.6.

$\mathbf{t_{4c}}$ : For $\widehat{\Upsilon}_{n}$, we have
$|t_{4c}|_{\mathsf{e}}=4$, $\mathsf{LPL}(t_{4c})=\mathsf{RPL}(t_{4c})=4$, and
$\nu_{1}(t_{4c})=4$, $\nu_{2}(t_{4c})=2$, $\nu_{3}(t_{4c})=0$,
$\nu_{4}(t_{4c})=1$. Hence, Lemma 3.3 yields

$\displaystyle\pi_{t_{4c}}=\frac{24p^{4}q^{4}}{(1-p^{2}-q^{2})^{2}}=\frac{24p^{4}q^{4}}{(2pq)^{2}}=6p^{2}q^{2}.$
(A.37)

Corollaries 3.7 and 3.8 then yield

$\displaystyle\operatorname{\mathbb{P}{}}(\widehat{\Upsilon}_{n}^{*}=t_{4c})$
$\displaystyle\approx\frac{p^{2}q^{2}}{4H},$ (A.38) $\displaystyle
q(\widehat{\Upsilon}_{n};t_{4c})$ $\displaystyle\approx\frac{2p^{2}q^{2}}{H}.$
(A.39)

In particular, in the symmetric case $p=\frac{1}{2}$, when $H=\log 2$,

$\displaystyle\operatorname{\mathbb{P}{}}(\widehat{\Upsilon}_{n}^{*}=t_{4c})$
$\displaystyle\approx\frac{1}{64\log 2}\doteq 0.0225,$ (A.40) $\displaystyle
q(\widehat{\Upsilon}_{n};t_{4c})$ $\displaystyle\approx\frac{1}{8\log 2}\doteq
0.1803.$ (A.41)

For $\widehat{\mathcal{B}}_{n}$, Theorem 4.13 yields

$\displaystyle\beta_{t_{4c}}=\frac{1}{16384}e^{8}-\frac{1}{1728}e^{6}+\frac{1}{1024}e^{4}-\frac{1}{64}e^{2}+\frac{54973}{442368}\doteq
0.0106.$ (A.42)

Hence, Theorem 4.1 and Lemma 2.2 yield

$\displaystyle\operatorname{\mathbb{P}{}}(\widehat{\mathcal{B}}^{*}_{n}=t_{4c})$
$\displaystyle\to\frac{3}{2}\beta_{t_{4c}}=\frac{3}{32768}e^{8}-\frac{1}{1152}e^{6}+\frac{3}{2048}e^{4}-\frac{3}{128}e^{2}+\frac{54973}{294912}\doteq
0.0159,$ (A.43) $\displaystyle q(\widehat{\mathcal{B}}_{n};t_{4c})$
$\displaystyle\to
12\beta_{t_{4c}}=\frac{3}{4096}e^{8}-\frac{1}{144}e^{6}+\frac{3}{256}e^{4}-\frac{3}{16}e^{2}+\frac{54973}{36864}\doteq
0.1273.$ (A.44)

For ${\mathcal{U}}_{n}$, (A.2)–(A.3) yield (just as for $t_{4a}$)

$\displaystyle\operatorname{\mathbb{P}{}}({\mathcal{U}}^{*}_{n}=t_{4c})\to\frac{1}{128}\doteq
0.0078,$ (A.45) $\displaystyle
q({\mathcal{U}}_{n};t_{4c})\to\frac{1}{16}=0.0625.$ (A.46)

$\triangle$

We summarize the numerical values above in Tables 1 and 2. In particular, note
the large differences in the relative importance of $t_{4a}$ and $t_{4c}$ for
the three random full binary trees considered here: the asymptotic ratio
between the probabilities for $t_{4c}$ and $t_{4a}$ are 3 for symmetric
Patricia tries (the oscillations cancel, see Remark 3.11), $1.846\dots$ for
compressed BST, and 1 for uniform full binary trees.

| $t_{2}$ | $t_{3}$ | $t_{4a}$ | $t_{4c}$
---|---|---|---|---
Patricia trie $\widehat{\Upsilon}_{n}$ ($p=q=\frac{1}{2}$) | 0.1803 | 0.0451 | 0.0075 | 0.0225
Compressed BST $\widehat{\mathcal{B}}_{n}$ | 0.1645 | 0.0418 | 0.0086 | 0.0159
Uniform full binary tree ${\mathcal{U}}_{n}$ | 0.125 | 0.0312 | 0.0078 | 0.0078
Table 1. Limits or approximations of $\operatorname{\mathbb{P}{}}(T^{*}_{n}=t)$ for three random full binary trees. | $t_{2}$ | $t_{3}$ | $t_{4a}$ | $t_{4c}$
---|---|---|---|---
Patricia trie $\widehat{\Upsilon}_{n}$ ($p=q=\frac{1}{2}$) | 0.7213 | 0.2705 | 0.0601 | 0.1803
Compressed BST $\widehat{\mathcal{B}}_{n}$ | 0.6581 | 0.2507 | 0.0690 | 0.1273
Uniform full binary tree ${\mathcal{U}}_{n}$ | 0.5 | 0.1875 | 0.0625 | 0.0625
Table 2. Limits or approximations of $q(T_{n};t)$ for three random full binary
trees.

## References

  * Aldous [1991] David Aldous. Asymptotic fringe distributions for general families of random trees. _Ann. Appl. Probab._ 1 (1991), no. 2, 228–266.
  * Aldous [1991] D. Aldous, The continuum random tree II: an overview. _Stochastic Analysis (Durham, 1990)_ , 23–70, London Math. Soc. Lecture Note Ser. 167, Cambridge Univ. Press, Cambridge, 1991.
  * Aldous [1996] David Aldous. Probability distributions on cladograms. In _Random discrete structures (Minneapolis, MN, 1993)_ , IMA Vol. Math. Appl. 76, pp. 1–18. Springer, New York, 1996\.
  * Aldous [2023] David Aldous. The critical beta-splitting random tree model II: Overview and open problems. Preprint, 2023. arxiv.org/abs/2303.02529.
  * Bennies and Kersting [2000] Jürgen Bennies & Götz Kersting. A random walk approach to Galton–Watson trees. _J. Theoret. Probab._ 13 (2000), no. 3, 777–803.
  * [6] Gabriel Berzunza Ojeda, Cecilia Holmgren & Svante Janson. Fringe trees for random trees with given vertex degrees. arXiv:2312.04243
  * Chang and Fuchs [2010] Huilan Chang & Michael Fuchs. Limit theorems for patterns in phylogenetic trees. _J. Math. Biol._ 60 (2010), 481–512.
  * Dennert and Grübel [2010] Florian Dennert & Rudolf Grübel. On the subtree size profile of binary search trees. _Combin. Probab. Comput._ 19 (2010), no. 4, 561–578.
  * Devroye [1991] Luc Devroye. Limit laws for local counters in random binary search trees. _Random Structures Algorithms_ 2 (1991), no. 3, 303–315.
  * Devroye [2002/3] Luc Devroye. Limit laws for sums of functions of subtrees of random binary search trees. _SIAM J. Comput._ 32 (2002/03), no. 1, 152–171.
  * Drmota [2009] Michael Drmota. _Random Trees_. Springer-Verlag, Vienna, 2009.
  * Feng, Mahmoud and Panholzer [2008] Qunqiang Feng, Hosam M. Mahmoud & Alois Panholzer. Phase changes in subtree varieties in random recursive and binary search trees. _SIAM J. Discrete Math._ 22 (2008), no. 1, 160–184.
  * Flajolet, Gourdon and Martínez [1997] Philippe Flajolet, Xavier Gourdon & Conrado Martínez. Patterns in random binary search trees. _Random Structures Algorithms_ 11 (1997), no. 3, 223–244.
  * Flajolet, Roux and Vallée [2010] Philippe Flajolet, Mathieu Roux & Brigitte Vallée. Digital trees and memoryless sources: from arithmetics to analysis. _Discrete Math. Theor. Comput. Sci. Proc._ , AM (2010), 233–260.
  * Fuchs [2008] Michael Fuchs. Subtree sizes in recursive trees and binary search trees: Berry–Esseen bounds and Poisson approximations. _Combin. Probab. Comput._ 17 (2008), no. 5, 661–680.
  * Fuchs [2012] Michael Fuchs. Limit theorems for subtree size profiles of increasing trees. _Combin. Probab. Comput._ 21 (2012), no. 3, 412–441.
  * [17] Michael Fuchs, Hsien-Kuei Hwang & Vytas Zacharovas. Asymptotic variance of random symmetric digital search trees. _Discrete Math. Theor. Comput. Sci._ 12 (2010), no. 2, 103–165.
  * [18] Michael Fuchs, Hsien-Kuei Hwang & Vytas Zacharovas. An analytic approach to the asymptotic variance of trie statistics and related structures. _Theoret. Comput. Sci._ 527 (2014), 1–36.
  * [19] Mohan Gopaladesikan, Hosam Mahmoud & Mark Daniel Ward. Asymptotic joint normality of counts of uncorrelated motifs in recursive trees. _Methodol. Comput. Appl. Probab._ 16 (2014), no. 4, 863–884.
  * [20] Cecilia Holmgren & Svante Janson. Limit laws for functions of fringe trees for binary search trees and recursive trees. _Electronic J. Probability_ 20 (2015), no. 4, 1–51.
  * Holmgren and Janson [2017] Cecilia Holmgren & Svante Janson. Fringe trees, Crump–Mode–Jagers branching processes and $m$-ary search trees. _Probab. Surv._ 14 (2017), 53–154.
  * [22] Cecilia Holmgren, Svante Janson & Matas Šileikis. Multivariate normal limit laws for the numbers of fringe subtrees in $m$-ary search trees and preferential attachment trees. _Electron. J. Combin._ 24 (2017), no. 2, Paper 2.51, 49 pp.
  * [23] Hsien-Kuei Hwang & Ralph Neininger. Phase change of limit laws in the quicksort recurrence under varying toll functions. _SIAM J. Comput._ 31 (2002), no. 6, 1687–1722.
  * [24] Philippe Jacquet & Wojciech Szpankowski. _Analytic Pattern Matching_. Cambridge Univ. Press, Cambridge, UK, 2015
  * [25] Svante Janson. Renewal theory in analysis of tries and strings. _Theoretical Computer Science_ 416 (2012), 33–54.
  * Janson [2012] Svante Janson. Simply generated trees, conditioned Galton–Watson trees, random allocations and condensation. _Probability Surveys_ 9 (2012), 103–252.
  * Janson [2016] Svante Janson. Asymptotic normality of fringe subtrees and additive functionals in conditioned Galton-Watson trees. _Random Structures Algorithms_ 48 (2016), no. 1, 57–101.
  * [28] Svante Janson. Central limit theorems for additive functionals and fringe trees in tries. _Electron. J. Probab._ 27 (2022), Paper No. 47, 63 pp.
  * Knuth [1998] Donald E. Knuth. _The Art of Computer Programming. Vol. 3: Sorting and Searching_. 2nd ed., Addison-Wesley, Reading, Mass., 1998.
  * [30] Hosam M. Mahmoud. The expected distribution of degrees in random binary search trees. _Comput. J._ 29 (1986), no. 1, 36–37.
  * Mahmoud [1992] Hosam Mahmoud. _Evolution of Random Search Trees_ , Wiley, New York, 1992.
  * [32] _NIST Handbook of Mathematical Functions_. Edited by Frank W. J. Olver, Daniel W. Lozier, Ronald F. Boisvert & Charles W. Clark. Cambridge Univ. Press, 2010.
Also available as _NIST Digital Library of Mathematical Functions_ ,
http://dlmf.nist.gov/