[1]Vladislav Kargin

[1]Department of Mathematics and Statistics, Binghamton University, 4400
Vestal Pkwy East, Binghamton, 13902, NY, USA

# Scaling limits of slim and fat trees

<EMAIL_ADDRESS>*

###### Abstract

We consider Galton–Watson trees conditioned on both the total number of
vertices $n$ and the number of leaves $k$. The focus is on the case in which
both $k$ and $n$ grow to infinity and $k=\alpha n+O(1)$, with
$\alpha\in(0,1)$. Assuming the exponential decay of the offspring
distribution, we show that the rescaled random tree converges in distribution
to Aldous’ Continuum Random Tree with respect to the Gromov–Hausdorff
topology. The scaling depends on a parameter $\sigma^{\ast}$ which we
calculate explicitly. Additionally, we compute the limit for the degree
sequences of these random trees.

###### keywords:

Random tree, Galton–Watson tree, Continuum random tree, Scaling limit, Contour
process

###### pacs:

[

MSC Classification]Primary 60J80, Secondary 60C05 05C05

##  1 Introduction

In this paper, we investigate the Galton–Watson (“GW”) trees conditioned both
on the total number of vertices and on the number of leaves, when the total
number of vertices is large and the number of leaves is far from its expected
value. For a situation with small number of leaves, we can expect long
leafless branches, while in the situation when a tree has a large number of
leaves, the branches are short and bushy, and this is why we call these trees
“slim” and “fat,” respectively.

The general setup is as follows. Let $L$ be a non-negative, integer-valued
random variable with the probability mass function $\mathbb{P}(L=i)=w_{i}$,
$i=0,1,2,\ldots$, which is assumed to satisfy the following conditions:

$\mathbb{E}L=1,\text{ and for some $a>0$, }\mathbb{E}e^{aL}<\infty.$ (1)

We also assume that the distribution of $L$ is not trivial: $w_{1}\neq 1$.

A random tree $T$ is the family tree of a Galton–Watson process with one
individual in generation 0 and with offspring of each individual distributed
independently as the random variable $L$. We use ordered trees so that the
information on the birth order of family tree branches is known. For a formal
description, see Sect. 3 in the paper of Le Gall and Le Jan [23].

The probability space $\Omega$ is the space of all ordered rooted trees with
the probability distribution $\mathcal{P}$ induced by the distribution of
random variable $L$. We write $\Omega_{n}\subset\Omega$ for trees with $n$
vertices and $\Omega_{k,n}\subset\Omega_{n}$ for trees with $k$ leaves and $n$
vertices. We say that _$(k,n)\in PP(w)$_ for an offspring distribution
$w=(w_{0},w_{1},\ldots)$ if the set of trees $\Omega_{k,n}$ has positive
probability. In this case, both $\Omega_{n}$ and $\Omega_{k,n}$ are endowed
with conditional probability laws $\mathcal{P}_{n}$ and $\mathcal{P}_{k,n}$
induced from law $\mathcal{P}$ on $\Omega$.

Note that a probability distribution $(w_{j})_{j=0}^{\infty}$ can be replaced
by an equivalent probability distribution $(\tilde{w}_{j})_{j=0}^{\infty}$
without changing the measure on $\Omega_{n}$ (see Sect. 4 in Janson [16]). In
particular, by Remark 4.3 in [16], any equivalent probability distribution is
determined by its expectation, and possible expectations are in $(0,\nu]$,
where $\nu$ is a certain parameter. It is easy to check by using the
definition of $\nu$ (see formulas (3.8) - (3.10) in [16]) that if
$(w_{j})_{j=0}^{\infty}$ has an exponentially declining tail then $\nu\geq 1$.
Therefore, for every such $(w_{j})_{j=0}^{\infty}$ we can always find an
equivalent probability distribution $(\tilde{w}_{j})_{j=0}^{\infty}$ so that
its expectation is $1$. In particular, the condition $\mathbb{E}L=1$ in (1)
does not impose an additional restriction on measure of trees in $\Omega_{n}$
and $\Omega_{k,n}$ but is used only to fix a specific equivalent weight
distribution.

We consider the case when the number of leaves $k$ approximately proportional
to the number of vertices $n$, more specifically, $k=\alpha n+O(1)$, where
$\alpha\in(0,1)$. Recall that if the offspring distribution
$\\{w_{i}\\}_{i=0}^{\infty}$ has finite variance, then the expected number of
leaves for a tree in $\Omega_{n}$ is $\sim w_{0}n$ (see Theorem II.5.1 in
[17]). We are mainly interested in the case when $\alpha\neq w_{0}$.

###  1.1 Main Results

In Theorem 1.1, we will show that as $n\to\infty$, a rescaled tree in
$\Omega_{k,n}$ converges in the Gromov–Hausdorff topology to a random metric
space called the Continuum Random Tree (“CRT”). This space was first
introduced by Aldous in [1], [2], [3] and for details of the definition, we
refer the reader to Sect. 2 in Le Gall’s survey [22]. In order to formulate
the result precisely, we introduce some additional notation in the next
subsection.

####  1.1.1 $\alpha$-Shifted Offspring Distribution

Let $\theta(t):=\sum_{i=0}^{\infty}w_{i}t^{i}$, where $\\{w_{i}\\}$ is the
offspring distribution, and let $\rho$ denote the radius of convergence for
this series. By assumption (1), $\sum_{i=0}^{\infty}w_{i}=1$ and
$\sum_{i=1}^{\infty}iw_{i}=1.$ Therefore, $\theta(1)=1$ and
$\theta^{\prime}(1)=1$. In particular, $1\leq\rho\leq\infty$. The assumption
$w_{1}\neq 1$ implies additionally that $w_{0}\neq 0$.

Define

$\widehat{\psi}(t):=\frac{t\theta^{\prime}(t)}{\theta(t)-w_{0}}.$ (2)

(Janson in [16] uses $\psi(t)$ to denote
$\frac{t\theta^{\prime}(t)}{\theta(t)}$.) In Lemma 2.1, we show that
$\widehat{\psi}(t)$ is increasing on the interval $[0,\rho)$. Hence, we can
define

$\widehat{\nu}:=\lim_{t\uparrow\rho}\widehat{\psi}(t)\in[1/(1-w_{0}),\infty].$
(3)

($\widehat{\nu}\geq 1/(1-w_{0})$ because $\widehat{\psi}(1)=1/(1-w_{0})$ and
$\rho\geq 1$.)

######  Definition 1.

Let $\alpha\in(0,1)$, and let $w_{i}^{\ast}$ be a probability mass
distribution with unit mean, such that $w_{0}^{\ast}=\alpha$ and
$w_{j}^{\ast}=Cw_{j}(t^{\ast})^{j-1}$ for all $j>0$ and for some $C>0$ and
$t^{\ast}>0$. We call $w_{0}^{\ast},w_{1}^{\ast},\ldots$, the _$\alpha$
-shifted offspring distribution_. Let $L^{\ast}$ denote a random variable that
have the distribution $\mathbb{P}(L^{\ast}=j)=w_{j}^{\ast}$ for
$j=0,1,2,\ldots$.

In other words, in the $\alpha$-shifted distribution, $w_{0}^{\ast}$ is set to
$\alpha$ and the remaining weights are exponentially re-weighted in such a way
that the result is still a probability mass distribution with unit mean. It is
easy to check that $C$ and $t^{\ast}$ can be determined from the following
equations,

$(1-\alpha)t^{\ast}\theta^{\prime}(t^{\ast})=\theta(t^{\ast})-w_{0},\text{ and
}C=\frac{1}{\theta^{\prime}(t^{\ast})}.$ (4)

In Lemma 2.2, we show that these equations are solvable if
$\alpha<1-1/\widehat{\nu}$. (In particular, they are always solvable for
$\alpha\leq w_{0}$. Intuitively, $\alpha>1-1/\widehat{\nu}$ corresponds to the
situation when the number of leaves is not sustainable by the structure of the
offspring distribution.)

In Lemma 2.3, we show that the variance of the $\alpha$-shifted distribution
$w_{j}^{\ast}$ is

$(\sigma^{\ast})^{2}=\frac{t^{\ast}\theta^{\prime\prime}(t^{\ast})}{\theta^{\prime}(t^{\ast})}.$
(5)

####  1.1.2 Rescaled Convergence in the Gromov–Hausdorff Metric

Let us consider trees in $\Omega_{k,n}$ as metric spaces with a marked point
(‘root’) by using the usual graph theoretic distance between vertices and
extending it to the edges linearly. We will denote the distance between points
$u$ and $v$ as $d(u,v)$.

Recall the definition of the Gromov–Hausdorff metric. If $(E,\delta)$ is a
metric space, then the Hausdorff distance between compact subsets of $E$ is
defined as follows:

$\displaystyle\delta_{\textrm{Haus}}(K,K^{\prime})=\inf\\{\alpha>0:K\subset
U_{\alpha}(K^{\prime})\text{ and }K^{\prime}\subset U_{\alpha}(K)\\},$

where $U_{\alpha}(K):=\\{x\in E:\delta(x,K)\leq\alpha\\}$. Then, if $T$ and
$T^{\prime}$ are two rooted compact metric spaces, with roots $\rho$ and
$\rho^{\prime}$, the Gromov–Hausdorff distance is defined as

$\displaystyle
d_{GH}(T,T^{\prime})=\inf\Big{\\{}\delta_{\textrm{Haus}}\big{(}\phi(T),\phi^{\prime}(T^{\prime})\big{)}\vee\delta\big{(}\phi(\rho),\phi^{\prime}(\rho^{\prime})\big{)}\Big{\\}},$

where the infimum is over all choices of a metric space $(E,\delta)$ and all
isometric embeddings $\phi:T\to E$ and $\phi^{\prime}:T^{\prime}\to E$. Two
rooted compact metric spaces $T_{1}$, $T_{2}$ are equivalent if there is a
root-preserving isometry between these two spaces and obviously
$d_{GH}(T,T^{\prime})$ depends only on the equivalence classes of $T$ and
$T^{\prime}$. It is a fact that $d_{GH}(T,T^{\prime})$ defines a metric on the
set of equivalence classes of rooted compact metric spaces. (For the unrooted
case, see Theorem 7.3.30 in Burago et al. [6]. The proof for the rooted case
can be obtained after some adjustments.) Moreover, the set of isometry classes
of real trees equipped with the Gromov–Hausdorff metric a complete and
separable metric space. See Theorem 1 in a paper of Evans et al. [12].

Recall that we say that $(k,n)\in PP(w)$ for an offspring distribution
$w=(w_{0},w_{1},\ldots)$ if the set of trees with $n$ vertices and $k$ leaves
has a positive probability under the probability law $\mathcal{P}$ induced by
this offspring distribution. We have the following convergence result.

######  Theorem 1.1.

Let the offspring distribution $w=(w_{j})_{j=0,1,\ldots}$ satisfy Condition
(1), and assume that $\big{(}(k_{i},n_{i})\big{)}_{i=1}^{\infty}$ is a
sequence in $PP(w)$ such that $n_{i}\to\infty$ and $k_{i}=\alpha n_{i}+O(1)$
where $\alpha\in(0,1-1/\widehat{\nu})$. Let $T_{n_{i}}$ be a tree chosen in
$\Omega_{k_{i},n_{i}}$ according to the probability law
$\mathcal{P}_{k_{i},n_{i}}$. Then,

$\displaystyle\frac{1}{\sqrt{n_{i}}}T_{n_{i}}\to\frac{2}{\sigma^{\ast}}\mathcal{T},$

where $\mathcal{T}$ is the Aldous continuum random tree and the convergence is
in distribution with respect to the Gromov–Hausdorff topology on the space of
compact metric spaces.

####  1.1.3 Convergence of Contour Processes

Theorem 1.1 follows from a stronger result that asserts the convergence of the
rescaled contour process associated with the tree $T_{n}\in\Omega_{k,n}$ to a
Brownian excursion. For details of this implication, see the proof of Theorem
2.5 in Le Gall’s survey [22]. The key fact is Lemma 2.4 in [22], which states
that if $T$ and $T^{\prime}$ are two real trees with contour functions $C(x)$
and $C^{\prime}(x)$ then $d_{GH}(T,T^{\prime})\leq 2\|g-g^{\prime}\|$, where
$\|g-g^{\prime}\|$ stands for the uniform norm of $g-g^{\prime}$.

Before stating the stronger result, let us define the contour and related
processes for an ordered rooted tree. While we need only the contour process
to formulate the result, the other processes will be useful in the proof.

Let $T$ be an ordered tree with $n$ vertices.

Figure 1: The contour, Łukasiewicz, and height processes for a tree on 8
vertices. The red points $\big{(}m(l),H_{n}(l)\big{)}$ are an embedding of the
height process in the contour process (see Definition 2).

_The depth-first search (DFS)_ : The sequence $f_{i}$, with $i=0,\ldots,2n-2,$
is a sequence of vertices, defined as follows: (i) $f_{0}=root$; (ii) given
$f_{i}=v,$ choose, if possible, the left-most child $w$ of $v$ that has not
already been visited and set $f_{i+1}=w$. If this is not possible, let
$f_{i+1}$ be the parent of $v$, (iii) the sequence ends when $f_{2n-2}=root$
and all vertices has been visited at least once.

_The contour process_ $C_{n}(i)$, $i=0,\ldots,2n-2,$ is defined as follows:

$C_{n}(i)=d(root,f_{i})=\text{height of }f_{i},\text{ the i-th vertex in the
DFS}.$ (6)

Between the integer points, the path $C_{n}(t)$ is defined by linear
interpolation. See Fig. 1 for an illustration.

We also define _the Łukasiewicz path process_ $S_{n}(i)$, for $i=0,\ldots,n$.
(In the paper of Marckert and Mokkadem [24], this process is called the Depth
First Queue Process (DFQP); we follow the terminology in the book of Flajolet
and Sedgewick [14].) Assume that the vertices in a planar tree are denoted
$v_{j}$, $j=0,\ldots,n-1$, in the order of their appearance in the Depth First
Search (and without repetition, unlike $f_{i}$). Let $\xi_{i}$,
$i=1,\ldots,n$, be the number of children of vertex $v_{i-1}$. Then,
$S_{n}(0)=0$, and

$S_{n}(j)=\sum_{i=1}^{j}(\xi_{i}-1),\text{ for }1\leq j\leq n.$ (7)

Similar to the contour process, we extend the Łukasiewicz process to the
intervals between integers by linearity. For illustration, see Fig. 1.

A Łukasiewicz path, by definition, is a piecewise continuous map from
$[0,n]\to\mathbb{R}$ that has the following properties: its increments
$S_{n}(j+1)-S_{n}(j)\in\\{-1,0,1,\ldots\\}$ for all integer $0\leq j\leq n-1$;
it is non-negative, $S_{n}(j)\geq 0$, for every $0\leq j\leq n-1$;
$S_{n}(0)=0$, and $S_{n}(n)=-1$. The construction (7) maps an ordered rooted
tree with $n$ vertices to a Łukasiewicz path. In fact, every Łukasiewicz path
can be obtained in this way, and therefore this construction gives a bijective
map from the set of ordered trees $\Omega_{n}$ to the set of Łukasiewicz paths
on interval $[0,n]$.

Finally, we define the _height process_ $H_{n}(i)$, $i=0,\ldots,n-1$, as

$H_{n}(i)=d(root,v_{i})=\text{height of }v_{i}.$ (8)

Now let us formulate the key result. In the theorem below, the convergence of
stochastic processes is the weak convergence with respect to the space of
continuous functions on $[0,1]$ with the topology induced by the uniform norm:
$\|f\|_{\infty}=\sup_{t\in[0,1]}f(t)$.

######  Theorem 1.2.

Let the offspring distribution $w=(w_{j})_{j=0,1,\ldots}$ satisfy Condition
(1), and assume that $\big{(}(k_{i},n_{i})\big{)}_{i=1}^{\infty}$ is a
sequence in $PP(w)$ such that $n_{i}\to\infty$ and $k_{i}=\alpha n_{i}+O(1)$
where $\alpha\in(0,1-1/\widehat{\nu})$. Let $T_{n_{i}}$ be a tree chosen in
$\Omega_{k_{i},n_{i}}$ according to the probability law
$\mathcal{P}_{k_{i},n_{i}}$ and let $C_{n_{i}}$ be the contour process for
this tree. Then, as $n_{i}\to\infty$,

$\displaystyle\bigg{(}\frac{C_{n_{i}}(2n_{i}t)}{\sqrt{n_{i}}}\bigg{)}_{t\in(0,1)}\xrightarrow{\text{weakly}}\frac{2}{\sigma^{\ast}}e(t),$

where $e(t)$ is a standard Brownian excursion, and $\sigma^{\ast}$ is as
defined in (5).

This theorem implies convergence results for continuous functionals on trees,
in particular, the following result about the height of trees.

######  Corollary 1.3.

Let $h_{n_{i}}$ be the height of a random tree
$T_{n_{i}}\in\Omega_{k_{i},n_{i}}$, and suppose that the assumptions of
Theorem 1.2 are satisfied. Then, the distribution of
$\sigma^{\ast}h_{n_{i}}/(2\sqrt{n_{i}})$ converges to the distribution of the
maximum of a standard Brownian excursion.

###### Proof.

The height of tree $T_{n_{i}}$ corresponds to the maximum of the tree’s
contour process. The maximum is a continuous functional on functions in
$C[0,1]$ with the uniform metric. Therefore, by Theorem 1.2, the distribution
of the maximum for the re-scaled contour process $C_{n}$ converges to the
distribution of the maximum of a standard Brownian excursion.

∎

####  1.1.4 Convergence of the Degree Sequence

Now, let $n_{j}(T)$ denote the number of vertices of out-degree $j$ in tree
$T$. (Recall that the out-degree of a vertex in a rooted tree is the number of
edges that lead away from the root. For Galton–Watson trees it is the number
of children of an individual represented by the vertex.) We say that the
sequence $(n_{0}(T),n_{1}(T),\ldots)$ is the _degree sequence_ of tree $T$. A
probability measure on trees $\Omega_{k,n}$ induces a probability measure on
degree sequences. By definition, $n_{0}(T)=k$ for a tree $T\in\Omega_{k,n}$.
In addition, $\sum_{i=0}^{\infty}n_{i}(T)=n$, where $n$ is the number of
vertices in $T$, and therefore, $\\{\frac{n_{i}(T)}{n}\\}_{i=0}^{\infty}$ is a
random probability measure.

######  Theorem 1.4.

Let the offspring distribution $w=(w_{j})_{j=0,1,\ldots}$ satisfy Condition
(1), and assume that $(T_{n}\in\Omega_{k,n})$ is a sequence of random trees
with $k\to\infty$, $n\to\infty$, and $(k,n)\in PP(w)$. Suppose that $k=\alpha
n+O(1)$ as $n\to\infty$, and $\alpha\in(0,1-1/\widehat{\nu})$. Then, almost
surely, $\frac{n_{j}(T_{n})}{n}\to w_{j}^{\ast}$ for $j=0,1,2,\ldots$, where
$\\{w_{j}^{\ast}\\}$ is the $\alpha$-shifted offspring distribution.

####  1.1.5 Examples

Here are some explicitly calculated $\alpha$-shifted distributions together
with the parameter $(\sigma^{\ast})^{2}$.

######  Example 1 (GW trees with geometric distribution).

Consider GW trees with the geometric offspring distribution
$w_{j}=2^{-(j+1)}$, $j=0,1,\ldots$ conditioned to have $n$ vertices. This
distribution is an exponential rescaling of the weight sequence $w_{j}=1$,
where $j=0,1,\ldots$, and therefore these trees have the uniform distribution
on $\Omega_{n}$. (This is Example 10.1 in Janson [16].) For this distribution,
we calculate $\theta(t)=(2-t)^{-1}$ and $\widehat{\nu}=+\infty$. Therefore,
equations in (4) are solvable for every $\alpha\in(0,1)$. The solution is
$t^{\ast}=2\alpha$ and $C=4(1-\alpha)^{2}$. This implies $w_{0}^{\ast}=\alpha$
and $w_{j}^{\ast}=\alpha^{j-1}(1-\alpha)^{2}$ for $j=1,2,\ldots$. The variance
is $(\sigma^{\ast})^{2}=2\alpha/(1-\alpha)$. Note that as $\alpha$ (i.e., the
limiting ratio of the number of leaves to the number of vertices) increases,
the variance parameter of the $\alpha$-shifted offspring distribution,
$(\sigma^{\ast})^{2}$, also increases. In particular, we should expect that
the height of the random tree in $\Omega_{k,n}$ decreases. (A tree with many
leaves is “fat” and “short”.)

######  Example 2 (Unary-Binary GW trees).

Consider unary-binary GW trees with weight sequence $w_{0}=p$, $w_{1}=1-2p$,
$w_{2}=p$, and $w_{i}=0$ for all other $i$, where $0<p<1/2$. In this case,
$\widehat{\nu}=2$ and equations (4) are solvable for every
$\alpha\in(0,\frac{1}{2})$. (It is not possible to solve these equations for
$\alpha>1/2$ because the number of leaves and the number of vertices are
related by the inequality $n\geq 2k-1$ in the unary-binary trees, with the
equality reached for binary trees.) The setup of this example includes
Examples 10.4 and 10.5 in Janson [16]. After $\alpha$-shifting we get
$w_{0}^{\ast}=w_{2}^{\ast}=\alpha$, $w_{1}^{\ast}=1-2\alpha$, with variance
$(\sigma^{\ast})^{2}=2\alpha$. We can see that, as $\alpha$ increases, the
variance also increases, as in the previous example. However, in this case
$\alpha$ is bounded from above, therefore variance of the offspring
distribution is bounded from above, and the tree cannot be made arbitrarily
short.

####  1.1.6 Algorithm for Generating Trees in $\Omega_{k,n}$

The proof of Theorems 1.2 and 1.4 is based on a new algorithm that generates
trees in $\Omega_{k,n}$ with weight sequence $w_{1},w_{2},\ldots$. In order to
explain the algorithm, we introduce a useful map between ordered trees and
balls-in-boxes allocations. The general idea of the algorithm is to generate a
suitable random allocation and then recover a random tree from this
allocation.

First, we define a map $\sigma$ that sends an ordered tree on $n$ vertices to
the sequence of the vertex offspring sizes. In this sequence the vertices are
ordered by the DFS, but the repeats of the vertices are omitted:

$\sigma:T\to\sigma(T)=(\xi_{1},\ldots,\xi_{n}).$ (9)

For example in Fig. 1, $\sigma(T)=(3,0,1,0,2,1,0,0)$.

This sequence can be identified with an allocation of $n-1$ balls
(corresponding to edges) in $n$ boxes (corresponding to vertices). The set of
all possible allocations is denoted $B_{n-1,n}$. The map $\sigma:\Omega_{n}\to
B_{n-1,n}$ is injective but not surjective.

By using the cycle lemma111The cycle lemma appears first in a paper of
Dvoretzky and Motzkin [11] and re-appears in different forms in many other
papers. See Dershowitz and Zacks [7] and Note I.47 on p.75-76 of the book by
Flajolet and Sedgewick [14] for an overview of the literature. The lemma is
closely related to Vervaat’s transform for the Brownian Bridge (see [31]) and
is often called the discrete Vervaat transform (see Pitman [28], Exercise 1 in
Sect. 5.1). , one can establish the following result.

######  Lemma 1.5 (Corollary 15.4 in [16]).

If $(y_{1},\ldots,y_{n})\in B_{n-1,n}$, then exactly one of the $n$ cyclic
shifts of $(y_{1},\ldots,y_{n})$ is the out-degree sequence $\sigma(T)$ of a
tree $T\in\Omega_{n}$.

Figure 2: An example of the cycle shift that sends a random walk bridge to a
Łukasiewicz path.

The relevant cyclic shift can be identified as follows. First note that the
sequence $y_{1},\ldots,y_{n}$ corresponds to a path $W_{0}=0$,
$W_{j}=\sum_{i=1}^{j}(y_{i}-1)$, $j=1,\ldots,n$, and that for this path
$W_{n}=-1$. Let $m=\min_{0\leq j\leq n}W_{j}$, and let $\widehat{j}$ be the
first time when the path achieves this minimum. Then the relevant cyclic shift
of $W_{j}$ is the path for the random walk with the steps given by
$(y_{\widehat{j}+1}-1,\ldots,y_{n}-1,y_{1}-1,\ldots y_{\widehat{j}}-1)$. It is
easy to see that the resulting path is a Łukasiewicz path and, therefore, it
corresponds to a tree $T\in\Omega_{n}$.

A cyclic shift is illustrated in Fig. 2.

Now we define an algorithm for the generation of trees in $\Omega_{k,n}$.
Define the probability mass function $\widehat{w}_{j}^{\ast}$ as follows:

$\widehat{w}_{0}^{\ast}:=0;\,\widehat{w}_{j}^{\ast}:=\frac{w_{j}^{\ast}}{1-\alpha},\text{
for }j=1,2,\ldots,$ (10)

where $w_{j}^{\ast}$ is the $\alpha$-shifted distribution from Definition
1.222In the proofs of our theorems the parameter $\alpha$ is given to us and
satisfy the assumption that $k=\alpha n+O(1)$ as $n\to\infty$. If $\alpha$ is
not known and the task is simply to generate the tree with $k$ leaves and $n$
vertices, then one can take $\alpha=k/n$.

Let the random sequence $\xi^{\prime}_{1},\ldots,\xi^{\prime}_{n-k}$ have the
following distribution

$\mathbb{P}(\xi^{\prime}_{1}=j_{1};\ldots;\xi^{\prime}_{n-k}=j_{n-k})=\begin{cases}\frac{1}{Z}\prod_{i=1}^{n-k}\widehat{w}_{j_{i}}^{\ast},&\text{if
}\sum_{i=1}^{n-k}j_{i}=n-1,\\\ 0,&\text{otherwise.}\end{cases}$ (11)

where $Z$ is a normalizing constant. In other words,
$\xi^{\prime}_{1},\ldots,\xi^{\prime}_{n-k}$ has the distribution of i.i.d.
random variables with distribution $\widehat{w}_{j}^{\ast}$, conditioned to
have the sum $n-1$.

## Algorithm A

  1. 1.

Generate a sample of $\xi^{\prime}_{1},\ldots,\xi^{\prime}_{n-k}$ with
distribution as in (11).

  2. 2.

Add $k$ zeros to the sequence $\xi^{\prime}_{i}$ and let
$\xi^{\prime\prime}=(\xi^{\prime\prime}_{i})_{i\leq n}$ be a uniform
permutation of the resulting sequence.

  3. 3.

Apply the (unique) cyclic shift to the resulting sequence
$(\xi^{\prime\prime}_{i})_{i\leq n}$ so that the result is in the image of the
map $\sigma$ defined in (9). Let the result be denoted
$\xi_{1},\ldots,\xi_{n}$.

  4. 4.

Obtain a tree $T\in\Omega_{k,n}$ as $\sigma^{-1}(\xi_{1},\ldots,\xi_{n})$.

It is assumed that the first step of this algorithm is implemented efficiently
as described in Devroye [8].

######  Theorem 1.6.

Let the offspring distribution $w=(w_{j})_{j=0,1,\ldots}$ satisfy Condition
(1). Suppose that $\alpha\in(0,1-1/\widehat{\nu})$ and $(k,n)\in PP(w)$. Then,
algorithm A produces a tree $T\in\Omega_{k,n}$ with the probability
distribution $\mathcal{P}_{k,n}$ corresponding to weights
$w_{0},w_{1},\ldots.$ If $k=\alpha n+O(1)$, then the expected running time of
the algorithm is $O(n)$, as $n\to\infty$.

Note that the essential corollary of this theorem is that for a random tree
$T\in\Omega_{k,n}$ with the law $\mathcal{P}_{k,n}$, the distribution of
$\sigma(T)$ equals the distribution of the random sequence
$(\xi_{1},\ldots,\xi_{n})$ produced by the algorithm. This gives us the
ability to study the Łukasiewicz and related processes for the random trees in
$\Omega_{k,n}$.

We will first prove Theorem 1.6. After this theorem is proved, the general
strategy is as follows. We use the fact that the sequence
$\big{(}\xi^{\prime\prime}_{i}\big{)}_{i=1}^{n}$ from Algorithm A is
exchangeable and apply tools from Billingsley [4] to show that the partial
sums of this sequence converge (after rescaling) to the Brownian bridge. Then,
properties of the discrete Vervaat’s transform ensure that the partial sums of
$\big{(}\xi_{i}\big{)}_{i=1}^{n}$ converge after rescaling to a Brownian
excursion. Then, we adapt tools from Marckert and Mokkadem [24] in order to
show that this convergence implies the re-scaled convergence of the height and
the contour processes to a Brownian excursion. The adaptation is necessary,
because the sequence of i.i.d. random variables underlying
$\big{(}\xi_{i}\big{)}_{i=1}^{n}$ is conditioned not only on the sum being
equal to $-1$ but also on the number of increments $-1$ being equal to $k$.
The changes to the argument are straightforward but we give the argument in
full detail for the convenience of interested reader.

Together, this gives a proof of Theorem 1.2 and, consequently, of Theorem 1.1.

For the proof of Theorem 1.4, we again start with results of Theorem 1.6. In
this case, we note that it is enough to show that $n_{\xi^{\prime}}(i)$, the
number of occurrences of increment $i$ in the sequence
$\big{(}\xi^{\prime}_{i}\big{)}_{i=1}^{n-k}$, after normalization by
$(n-k)^{-1}$ converges almost surely to $\widehat{w}^{\ast}_{i}$. In order to
show this, we use an idea from a paper of Broutin and Marckert[5]. Roughly
speaking, the idea is that under certain conditions the events which are rare
under a random walk with i.i.d. increments $\hat{\zeta}_{j}$, remain rare,
even if a condition is imposed on the random walk (for example, if the
variables $\hat{\zeta}_{j}$ are required to add up to a specific constant). By
using this trick, we can extend the almost sure convergence for
$n_{\hat{\zeta}}(i)$, where $(\hat{\zeta}_{j})_{j=1}^{n-k}$ are i.i.d., to the
almost sure convergence of $n_{\xi^{\prime}}(i)$. This allows us to prove
Theorem 1.4

The rest of the paper is organized as follows. In Sect. 1.2 we describe the
relation of our results to previous work. In Sect. 2, we give detailed proofs.
In Sect. 3, we discuss some remaining problems. Appendix is devoted to the
proof of an auxiliary local limit theorem.

###  1.2 Relation to Previous Work

Excellent reviews of the vast literature about the asymptotic behavior of
finite random trees can be found in a book [14] by Flajolet and Sedgewick, and
in review articles [22] by Le Gall and [16] by Janson.

From early on, it was observed that different families of random trees often
have some similar macroscopic properties. For example, the tree height
distribution has the same functional form for many tree families, although the
distribution parameters could depend on the specific choice of the family.

In a sequence of papers, [1], [2], [3], Aldous provided an explanation for
this phenomenon by showing that certain sequences of finite random trees
converge under rescaling in the Gromov–Hausdorff topology to universal objects
that he called the _continuum random trees (CRTs)_. In particular, he showed
that Galton–Watson trees with a finite-variance offspring distribution
converge under rescaling to a special CRT, which he called the _Brownian CRT_.
(We will sometime refer to this limit as the Aldous CRT.) The tree is
characterized by the property that its contour process is the Brownian
excursion. Aldous’ proof of this result is based on graph theoretical
arguments which showed that all such Galton–Watson trees converge under
rescaling to the same limit independent of the specific offspring
distribution. Then proof was concluded by an investigation of a particular
case of GW trees with geometric offspring distribution.

Marckert and Mokkadem in [24] gave a different proof of this result under the
condition that the offspring distribution has exponentially declining tails.
In their proof, they establish the convergence (under rescaling) of the
Łukasiewicz process to the Brownian excursion and then, show that the paths of
the height process must be uniformly close to the paths of the Łukasiewicz
process. For this implication, they use a relation of Galton–Watson trees to
queues and an explicit formula for the height process in terms of the
Łukasiewicz process. Then one can handle the height process by using methods
from the classic theory about ladder heights (Feller [13], Chapter XII).
Finally, the rescaled convergence of the height process implies the rescaled
convergence of the contour process.

Duquesne in [9] extends Aldous’ result to Galton–Watson trees that may have
infinite variance. He relies heavily on the machinery developed in papers of
Duquesne and Le Gall [10] and of Le Gall and Le Jan [23]. While their approach
is similar to the approach of Marckert and Mokkadem in [24], however, in the
case of infinite variance the Łukasiewicz process converges under rescaling to
an excursion of a Lévy process, and it is not immediately clear what is the
candidate for the rescaled limit of the associated height process. The authors
of these papers defined a height process for the Lévy process and then, showed
that the height process of the GW trees converges under rescaling to this
continuous-time height process. In this way, they showed that Galton–Watson
trees with infinite variance offspring distribution converge under rescaling
to _Lévy CRTs_ , encoded by these height processes. (There are several such
CRTs, depending on the parameter of the Lévy process.)

An alternative proof of Duquesne’s theorem was given by Kortchemski in [19].
The proof is still based on the results in Duquesne and Le Gall [10]. However,
Kortchemski uses the fact that the probability measure of events conditioned
on the size of a GW tree equal to $n$ is absolutely continuous with respect to
the probability measure of the events conditioned on the size of the tree
being at least $n$, and this type of conditioning was already handled in Sect.
2.5 of [10]. A similar absolute continuity relation can be obtained for the
continuous limit objects, and Kortchemski concludes the proof by showing the
uniform convergence of the Radon–Nikodym densities.

By a similar method, in [18], Kortchemski proved that if one conditions a
Galton–Watson tree on the number of leaves, instead of the total number of
vertices, then one still has the convergence under rescaling to the Brownian
CRT or a Lévy CRT. The key additional ingredient in the proof is the fact that
a GW tree with $k$ leaves has $k/w_{0}$ total vertices with high probability.
He also proved an extension of this result to the case when one conditions the
GW tree on the number of vertices that have degrees in a given non-empty set
of integers.

The applicability of these universality results has been significantly
enlarged in [15] by Haas and Miermont. They considered a big class of trees
with Markov branching property. In random trees with this property, the
subtrees above some given height are independent with a law that depends only
on the tree size, and the size is measured either as the number of leaves or
vertices. Their result is that these trees converge under rescaling to
universal random objects, called self-similar fragmentation trees.

In particular, Haas and Miermont show in [15] that the convergence under
rescaling holds in the case when the Galton–Watson trees are conditioned
either on the total progeny, or on the number of leaves (but not both). In
[29], Rizzolo used the method of [15] to show the convergence under rescaling
of the Galton–Watson trees conditioned on the number of vertices that have
degrees in a specified set. The proof of these results is based on the theory
of fragmentation processes, and this gives a completely different approach to
results by Aldous, Duquesne, Le Gall, Le Jan, and Kortchemski.

In this paper, we use the approach based on random walks and their continuous-
time limits and not on fragmentations processes.

The difference of this paper from earlier studies described above is that we
focus on the situation when a Galton–Watson random tree is conditioned on both
the number of total progeny and the number of leaves. In particular, we
consider a situation in which these two requirements are at odds with each
other. In a sense, the obtained results are about an atypical event since they
are concerned with the structure of trees under an additional condition super-
imposed on the usual conditional Galton–Watson tree.

A similar approach is taken in papers [20] by Labarbe and Marckert, and [5] by
Broutin and Marckert. The paper [20] considers Bernoulli random walks (that
is, walks with increments in $\\{-1,+1\\}$) and associated processes, –
bridges, meanders and excursions, – conditioned on a given number of peaks. A
well-known bijection maps the contour process of an ordered tree to a
Bernoulli excursion, and the results in [20] imply the convergence of
uniformly distributed ordered trees with a given number of leaves to the
Aldous continuum random tree (see Sect. 1.1 in their paper).333In addition,
the paper [20] studies the counting process for leaves under DFS exploration
of the tree. For extension of these results to GW trees, see a recent paper of
Thévenin [30]. This is a particular case of our Theorem 1.1 for the case when
weights $w_{j}$ are geometric, $w_{j}=2^{-j-1}$.

For ordered trees with non-uniform distributions, the contour process is still
an (interpolated) excursion with increments $\\{-1,+1\\}$ but its distribution
is more complicated and its rescaled convergence is difficult to establish
directly. So, instead of the contour process, we use the Łukasiewicz process,
that has a more tractable distribution, in order to prove the rescaled
convergence to the Brownian excursion. Then, we infer that this implies the
convergence for the contour process as well, by applying the techniques
developed by Marckert and Mokkadem in [24]. This allows us to derive the
convergence under re-scaling for a broader class of random trees than that
considered in the paper of Labarbe and Marckert [20].

From the technical viewpoint, the methods by which we obtain the re-scaled
convergence of the Łukasiewicz process to the Brownian excursion, also differ
from methods in [20]. In particular, in [20] the authors use combinatorics to
explicitly evaluate the number of simple walk paths with a given number of
peaks between two lattice points. Then, they use the Stirling formula and
obtain the finite-dimensional distributions of the limit by calculating the
asymptotics of these explicit expressions. The combinatorics at the heart of
this approach becomes significantly harder for paths with a more general set
of increments, and we choose to use a different approach.

For tightness, [20] uses a combinatorial trick that maps simple walks with
increments $\pm 1$ to walks with $\\{0,1\\}$ increments in a non-trivial
fashion: peaks and valleys of the original walk path correspond to increment
$1$, and the other points between steps of the original path to increment $0$.
This map is injective and converts conditioning on the number of peaks to
conditioning on the final point of the walk, which is easier to handle. Then,
it is noted that a formula for the inverse map involves summation of
independent geometric random variables, and this fact is used in order to show
that the tightness also holds for the original random walk. Additional
conditioning on the final point of the original random walk (needed for
bridges and excursions) is handled by using the explicit formulas for the
number of paths with a given number of peaks.

This argument is hard to generalize to walks with more general increments (and
so to Łukasiewicz walks) because of the absence of the required combinatorial
trick.

Instead, we use the connection of discrete walks with the balls-in-boxes
model, as described by Kolchin [17] and Janson [16], and with exchangeable
random variables. This allows us to apply the results in Billingsley’s book
[4] that establish the re-scaled convergence for partial sums of a certain
class of exchangeable random variables.

In a paper of Broutin and Marckert, [5], the entire degree sequence of a tree
is specified.444See also an application of this approach to random forests in
Lei [21], and an extension in a paper of Ojeda et al. [25] where different
assumptions about the degree sequence are used. More precisely, let
$d_{i}(\tau)$ denote the number of vertices of out-degree $i$ in the tree
$\tau$, and let $\vec{d}(\tau)=\\{d_{i}(\tau)\\}_{i=0}^{\infty}$ be the degree
sequence of $\tau$. Also, let $|\vec{d}|=\sum_{i=0}^{\infty}d_{i}$ and
$\Delta(\vec{d})=\max\\{d_{i}\\}$ be the size and the maximum degree of the
tree. Assume that $\vec{d}^{(1)},\vec{d}^{(2)},\ldots$ be a sequence of degree
sequences so that $|\vec{d}^{(j)}|\to\infty$,
$\Delta(\vec{d}^{(j)})=o(\sqrt{|\vec{d}^{(j)}|})$, and the measure
$\vec{d}^{(j)}/|\vec{d}^{(j)}|$ converges to a probability measure
$\mu_{0},\mu_{1},\ldots$ that has finite second moment.

Take the uniform measure on the set of trees with degree sequence
$\vec{d}^{(j)}$ and let the correspondent random tree be denoted $T_{j}$.
Broutin and Marckert showed that the sequence of trees $T_{j}$ converges under
rescaling to the Brownian CRT in the Gromov–Hausdorff topology. The proof is
based on the approach of Marckert and Mokkadem [24] and it is similar to our
approach. In particular, their proof of the convergence of Łukasiewicz process
uses Billingsley’s theorem 24.1 in [4]. In their main theorem, the conditions
for applicability of Billingsley’s theorem hold by assumption on
$\Delta(\vec{d}^{(j)})$.

The results of [5] could be used to prove our main result, Theorem 1.1,
provided one can show that as $n$ grows, the degree sequences of the trees in
$\Omega_{n,k}$ (after normalization) converge in probability to the
$\alpha$-shifted distribution and that they satisfy the condition that
$\Delta\vec{d}^{(j)}=o\Big{(}\sqrt{|\vec{d}^{(j)}|}\Big{)}$.

In this paper we choose a different, more direct approach to the proof of the
main result. However, Theorem 1.4 contains the main ingredient of the
different approach. Namely, in this theorem we show that as $n\to\infty$, the
(normalized) degree sequence of a tree in $\Omega_{n,k}$ almost surely
converges to the $\alpha$-shifted distribution.

##  2 Proofs

###  2.1 Preliminary Results

We start with proving some results about the existence of the $\alpha$-shifted
distribution and about its variance.

######  Lemma 2.1.

The function $\widehat{\psi}(t)$ in (2) is an increasing continuous function
on $(0,\rho)$.

###### Proof.

Let $\widehat{\theta}(t)=\theta(t)-w_{0}=\sum_{i=1}^{\infty}w_{i}t^{i}$, and
let

$\displaystyle p_{i}(t)=\frac{w_{i}t^{i}}{\widehat{\theta}(t)}\text{ for
}i=1,2,\ldots,$

for $t\in(0,\rho)$, and zero otherwise. Then, for every $t\in(0,\rho)$,
$p_{i}(t)$ is a probability mass function (pmf) of a discrete random variable
$X_{t}$.

By definition,
$\widehat{\psi}(t)=t\theta^{\prime}(t)/\widehat{\theta}(t)=t\widehat{\theta}^{\prime}(t)/\widehat{\theta}(t)$.
Then we calculate:

$\displaystyle t\widehat{\psi}^{\prime}(t)$
$\displaystyle=\frac{t\widehat{\theta}^{\prime}(t)}{\widehat{\theta}(t)}+\frac{t^{2}\widehat{\theta}^{\prime\prime}(t)}{\widehat{\theta}(t)}-\frac{t^{2}\widehat{\theta}^{\prime}(t)^{2}}{\widehat{\theta}(t)^{2}}$
$\displaystyle=\sum_{i=1}^{\infty}ip_{i}(t)+\sum_{i=1}^{\infty}i(i-1)p_{i}(t)-\Big{(}\sum_{i=1}^{\infty}ip_{i}(t)\Big{)}^{2}$
$\displaystyle=\mathbb{E}(X_{t}^{2})-(\mathbb{E}X_{t})^{2}=\mathbb{V}\mathrm{ar}(X_{t})>0.$

∎

######  Lemma 2.2.

Let $w_{0},w_{1},\ldots$ be a probability distribution with unit mean and
finite variance. If $\alpha<1-1/\widehat{\nu}$ with $\widehat{\nu}$ as defined
in (3), then there exist $C>0$ and $t^{\ast}>0$ that solve problem (4).

###### Proof.

We can write (4) as $C=1/\theta^{\prime}(t^{\ast})$ and

$\widehat{\psi}(t^{\ast})=\frac{1}{1-\alpha}.$ (12)

By Lemma 2.1, the function $\widehat{\psi}(t)$ is continuous and increasing on
the interval $(0,\rho)$, and we have: $\lim_{t\to 0}\widehat{\psi}(t)=1$,
$\lim_{t\to\rho}\widehat{\psi}(t)=\widehat{\nu}$. So if
$(1-\alpha)^{-1}<\widehat{\nu}$, then the equation (12) has a solution
$t^{\ast}\in(0,\rho)$ by the intermediate value theorem, and we can set
$C=1/\theta^{\prime}(t^{\ast})$ since $\theta^{\prime}(t^{\ast})$ is well-
defined and non-zero for $t\in(0,\rho)$. ∎

######  Lemma 2.3.

The variance of the $\alpha$-shifted distribution $\\{w_{j}^{\ast}\\}$,
$j=0,1,\ldots$, is

$(\sigma^{\ast})^{2}=\frac{t^{\ast}\theta^{\prime\prime}(t^{\ast})}{\theta^{\prime}(t^{\ast})},$
(13)

where $t^{\ast}$ is the solution of equations (4).

###### Proof.

The generating function for the distribution $\\{w_{j}^{\ast}\\}$ is

$\displaystyle\theta^{\ast}(t)$
$\displaystyle:=\sum_{j=0}^{\infty}w^{\ast}_{j}t^{j}=\alpha+Cw_{1}t+Cw_{2}t^{\ast}t^{2}+\ldots$
$\displaystyle=\alpha+\frac{C}{t^{\ast}}\big{(}\theta(t^{\ast}t)-w_{0}\big{)}.$

Then the mean is $(\theta^{\ast})^{\prime}(1)=C\theta^{\prime}(t^{\ast})=1$ by
(4). For probability distributions with unit mean, the variance equals the
second derivative of the generating function evaluated at $t=1$. So we get
that the variance is

$\displaystyle(\theta^{\ast})^{\prime\prime}(1)=Ct^{\ast}\theta^{\prime\prime}(t^{\ast})=\frac{t^{\ast}\theta^{\prime\prime}(t^{\ast})}{\theta^{\prime}(t^{\ast})}.$

∎

###  2.2 Proofs of Main Results

In this section we prove Theorems 1.6, 1.2 and 1.4, about the generation
algorithm, the convergence of the contour process, and the most likely type of
the degree profile, respectively.

First, we establish some useful notation and give additional details about the
relation of Galton–Watson trees and balls-in-boxes allocations.

Let $w_{k}$, $k=0,1,\ldots$ be a probability mass function with unit mean. It
induces distributions on trees in $\Omega_{n}$, as conditioned Galton–Watson
trees, and on allocations of the balls-in-boxes model $B_{n-1,n}$. [The
probability of an allocation $(y_{1},\ldots y_{n})$ is
$\propto\prod_{i=1}^{n}w_{y_{i}}$.] For the injective map $\sigma$ from (9),
the push-forward probability distribution on $\sigma(\Omega_{n})$ equals the
distribution on $B_{n-1,n}$ conditioned to the image of the map $\sigma$.

The following result illustrates the relation between random trees and the
balls-in-boxes model.

For a balls-in-boxes allocation $y=(y_{1},\ldots,y_{n})$, let $N_{s}(y)$ be
the number of those $y_{i}$ in allocation $y$ that are equal to $s$. The
_occupation profile_ of an allocation $y$ is the sequence
$\big{(}N_{s}(y)\big{)}_{s=0}^{\infty}$. In particular, $N_{0}(y)$ denotes the
number of empty boxes in an allocation.

Note that a cyclic shift does not change the probability of an allocation and
does not change numbers $N_{s}(y)$. This fact and the cyclic shift lemma (see
Lemma 1.5) imply the following result. Recall that $n_{s}(T)$ denote the
number of vertices of out-degree $s$ in a random tree $T\in\Omega$. Then, the
joint distribution of the degree sequence
$\big{(}n_{s}(T)\big{)}_{s=0}^{\infty}$ coincides with the joint distribution
of the occupation profile $\big{(}N_{s}(y)\big{)}_{s=0}^{\infty}$ for a random
allocation $y$ in $B_{n-1,n}$.

######  Lemma 2.4 (Lemma II.2.2 in [17]).

If the set $\Omega_{n}$ is not empty, then

$\displaystyle\mathbb{P}(n_{s}(T)=n_{s};\,s=0,\ldots,n-1)=\mathbb{P}(N_{s}(y)=n_{s};\,s=0,\ldots,n-1).$

Now we turn to the proofs of Theorems.

###### Proof of Theorem 1.6.

Since $\sigma$ is a one-to-one correspondence, for the first claim of the
theorem it is enough to show that the distribution of the random sequence
$(\xi_{1},\ldots,\xi_{n})$ produced in the third step of the algorithm equals
to the distribution of $\sigma(T)$ for $T\in\Omega_{k,n}$ distributed
according to $\mathcal{P}_{k,n}$.

Let $v_{i}$, $i=0,\ldots,n-1$, be the vertices of an ordered rooted tree
$T\in\Omega_{k,n}$ listed in the DFS order. The probability of the tree is

$\displaystyle p(T)\propto\prod_{i=0}^{n-1}w_{d(v_{i})}.$

The probability of an allocation $y=\sigma(T)=(y_{1},\ldots,y_{n})\in
B(n-1,n)$ is

$p(y)\propto\prod_{j=1}^{n}w_{y_{j}},$ (14)

and the allocations are different for different $T$ by the injectivity of map
$\sigma$. If $\tau_{i}$ denotes a shift of allocation $y$ by $i$ positions
then for all $y$ in the image of $\sigma$, the allocations $\tau_{i}(y)$ are
different for $i=0,\ldots,n-1$ by the Cyclic Lemma 1.5 and their union covers
the set

$\displaystyle B_{k}(n-1,n)=\\{y:y\in B(n-1,n),\,N_{0}(y)=k\\}.$

Hence the distribution (14) on the allocations in $\sigma(\Omega_{k,n})$ can
be obtained provided that one can generate allocations in $B_{k}(n-1,n)$ with
distribution

$\displaystyle p_{k}(y)$ $\displaystyle\propto\prod_{i=1}^{n}w_{y_{j}}\propto
w_{0}^{k}\prod_{j=1}^{\infty}w_{j}^{N_{j}(y)}$ (15)

(The difference of (14) and (15) is that the latter is over all allocations in
$B_{k}(n-1,n)$ while the former is only over the allocations in
$\sigma(\Omega_{k,n})\subset B_{k}(n-1,n)$. )

The distribution (15) coincides with the distribution of random variables
$\xi_{1},\ldots,\xi_{n}$ which are i.i.d random variables
$\zeta_{1},\ldots,\zeta_{n}$ with distribution $w_{0},w_{1},\ldots$
conditional that $\sum_{i=1}^{n}\zeta_{i}=n-1$ and that $k$ of variables
$\zeta_{i}$ take value $0$.

By exchangeability of random variables $(\xi_{1},\ldots,\xi_{n})$, all
locations for those random variables $\xi_{i}$ that take value $0$ are equally
probable. Conditional on the choice of these locations, the remaining
variables, which we denote
$\xi^{\prime}=(\xi^{\prime}_{1},\ldots,\xi^{\prime}_{n-k})$, have the joint
distribution

$\displaystyle
p(\xi^{\prime})\propto\prod_{j=1}^{\infty}w_{j}^{N_{j}(\xi^{\prime})}\text{
for }\xi^{\prime}:\sum_{i=1}^{n-k}\xi^{\prime}_{i}=n-1.$

Note that the distribution of $\xi^{\prime}_{1},\ldots,\xi^{\prime}_{n-k}$ is
the same as the probability distribution of an i.i.d sequence
$\zeta^{\prime}_{1},\ldots,\zeta^{\prime}_{n-k}$, with $\zeta^{\prime}_{1}$
having the distribution $\widehat{w}_{0}=0,\widehat{w}_{i}=w_{i}/(1-w_{0})$
conditional that $\sum_{i=1}^{n-k}\zeta^{\prime}_{i}=n-1$. By exponential re-
weighting, which is possible by Condition (1), this distribution equals the
probability distribution of an i.i.d sequence
$\hat{\zeta}_{1},\ldots,\hat{\zeta}_{n-k}$ with $\hat{\zeta}_{1}$ having
distribution
$\widehat{w}_{0}^{\ast}=0,\hat{w}_{i}^{\ast}=w_{i}^{\ast}/(1-\alpha)$ and
conditioned to have the sum $\sum_{i=1}^{n-k}\hat{\zeta}_{i}=n-1$. In other
words, the random variables $(\xi^{\prime}_{1},\ldots,\xi^{\prime}_{n-k})$
have the distribution given in (11). This proves the first part of the theorem
and shows the validity of the algorithm: once we generated random variables
$(\xi^{\prime}_{1},\ldots,\xi^{\prime}_{n-k})$, we reverse the steps of the
above argument to generate the corresponding random tree.

In remains to estimate the speed of the algorithm. The main step is to
generate $(\xi^{\prime}_{1},\ldots,\xi^{\prime}_{n-k})$, or, which is the
same, a sequence $(\hat{\zeta}_{1},\ldots,\hat{\zeta}_{n-k})$ Note that for
$\hat{\zeta}_{i}$ we have $\mathbb{E}S_{\hat{\zeta}}(n-k)=(n-k)/(1-\alpha)\sim
n$.)

A fast method for generating such sequences was developed by Devroye [8]. In
application to our situation, the method is as follows.

  1. 1.

Generate a multinomial random vector $(N_{1},N_{2},\ldots,)$ with parameters
$(n-k,\widehat{w}_{1}^{\ast},\widehat{w}_{2}^{\ast},\ldots)$. Repeat this step
until a sample is obtained such that

$\displaystyle\sum_{j=0}^{\infty}jN_{j}=n-1.$

  2. 2.

Form an array of length $n-k$ with $N_{j}$ values $j$ and randomly permute it.
The result is the desired sequence
$\xi^{\prime}_{1},\ldots,\xi^{\prime}_{n-k}$.

Let us analyze the running time of this algorithm.

By Theorem 1 in [8], there is a method to generate the required multinomial
vector in expected time $\tau_{n}=o(n^{1/2})$ provided that the sequence
$\widehat{w}_{i}^{\ast}$ has finite variance. (In fact, for a compactly
supported distribution, this time is $O(1)$.)

The distribution of the sum $\sum_{j=0}^{\infty}jN_{j}$ is the same as the
distribution of the sum of an i.i.d. sequence
$\hat{\zeta}_{1},\ldots,\hat{\zeta}_{n-k}$ where each r.v. has pmf
$\\{\widehat{w}_{i}^{\ast}\\}$. The expectation of the pmf
$\\{\widehat{w}_{i}^{\ast}\\}$ is $1/(1-\alpha)$ by its definition (10),
hence, the expectation of the sum is $(n-k)/(1-\alpha)=n$. By using the local
central limit theorem (valid under the assumption that the variance of pmf
$\widehat{w}_{i}^{\ast}$ is finite), the probability that
$\sum_{i=1}^{n-k}\hat{\zeta}_{i}=n-1$ is bounded from below by
$\Omega(1/\sqrt{n})$. Therefore, the expected time that we draw a sample
$N_{j}$ such that $\sum_{j=0}^{\infty}jN_{j}=n-1$ is $\tau_{n}\sqrt{n}=o(n)$.

The time for other operations (adding zeros and random shuffling) is linear in
$n$. ∎

###### Proof of Theorem 1.2.

The proof consists of several steps. In the first step, we will show that the
Łukasiewicz path of a random tree in $\Omega_{k,n}$ converges to a Brownian
excursion. This will be accomplished in Lemmas 2.7 and 2.8 by analyzing random
sequences produced by Algorithm A.

In the second step of the proof, we are going to show that the Łukasiewicz
path of a random tree from $\Omega_{k,n}$ is close to the height process of
the tree. This result is formulated in Lemma 2.10.

In the third step, we will show that with high probability the height process
is close to the contour process. See Lemma 2.11.

The final step is to bring all these results together and show that the
contour process for a tree in $\Omega_{k,n}$ converges to the Brownian
excursion.

In all lemmas in this section (Lemmas 2.5 \- 2.13), we assume that the
assumptions of Theorem 1.2 are satisfied. That is, condition (1) holds, and
the sequence of pairs $(k,n)$ is such that $(k,n)\in PP(w)$ and, as
$n\to\infty$, $k=\alpha n+O(1)$, where $\alpha\in(0,1-1/\widehat{\nu})$.

Step 1: Łukasiewicz path converges to Brownian excursion.

Let $\xi^{\prime\prime}_{1},\ldots,\xi^{\prime\prime}_{n}$ be the sequence of
random variables produced by Step 2 of Algorithm A. Some properties of these
random variables are proved in Lemmas 2.5 and 2.6. Then, we prove the
convergence of Łukasiewicz path to Brownian excursion in Lemmas 2.7 and 2.8.

######  Lemma 2.5.

As $n\to\infty$, we have:

  1. (a)

For each integer $s\geq 0$,
$\mathbb{E}((\xi^{\prime\prime}_{1})^{s})\to\mathbb{E}((L^{\ast})^{s})$, where
$L_{\ast}$ is a random variable with distribution $w_{j}^{\ast}$. In
particular,
$\mathbb{V}\mathrm{ar}(\xi^{\prime\prime}_{1})\to(\sigma^{\ast})^{2}$;

  2. (b)

For each integer pair $s,t\geq 0$,
$\mathrm{Cov}\Big{(}(\xi^{\prime\prime}_{1})^{s},(\xi^{\prime\prime}_{2})^{t}\Big{)}\to
0$.

  3. (c)

For every $\beta>0$, there exists a $\gamma>0$ such that

$\displaystyle\mathbb{P}(\max_{j}|\xi^{\prime\prime}_{j}|>n^{\beta})\leq
e^{-\gamma n^{\beta}}.$

###### Proof.

(a) First, consider variables $\xi^{\prime}_{i}$. They have the distribution:

$\displaystyle\mathbb{P}\Big{(}\xi^{\prime}_{1}=j_{1},\ldots,\xi^{\prime}_{n-k}=j_{n-k}\Big{)}=\mathbb{P}\Big{(}\hat{\zeta}_{1}=j_{1},\ldots,\hat{\zeta}_{n-k}=j_{n-k}\Big{|}S_{\hat{\zeta}}(n-k)=n-1\Big{)},$

where $\hat{\zeta}_{1},\ldots,\hat{\zeta}_{n-k}$ are i.i.d. random variables
with distribution
$\mathbb{P}(\hat{\zeta}_{1}=j)=\widehat{w}^{\ast}_{j}=w^{\ast}_{j}/(1-\alpha)$,
if $j\geq 1$, and $0$ if $j=0$. Here $S_{\hat{\zeta}}(p)$ denotes
$\sum_{i=1}^{p}\hat{\zeta}_{i}$. Therefore,

$\displaystyle\mathbb{P}(\xi^{\prime}_{1}=j)$
$\displaystyle=\mathbb{P}\Big{(}\hat{\zeta}_{1}=j\Big{|}S_{\hat{\zeta}}(n-k)=n-1\Big{)}=\frac{\mathbb{P}\Big{(}\hat{\zeta}_{1}=j,\sum_{i=2}^{n-k}\hat{\zeta}_{i}=n-1-j\Big{)}}{\mathbb{P}\Big{(}S_{\hat{\zeta}}(n-k)=n-1\Big{)}}$
$\displaystyle=\mathbb{P}(\hat{\zeta}_{1}=j)\frac{\mathbb{P}\Big{(}S_{\hat{\zeta}}(n-k-1)=n-1-j\Big{)}}{\mathbb{P}\Big{(}S_{\hat{\zeta}}(n-k)=n-1\Big{)}}.$

The distribution of the random variable $\xi^{\prime\prime}_{1}$ can be
obtained as a mix distribution: $\xi^{\prime\prime}_{1}=0$ with probability
$(k/n)$ and $\xi^{\prime\prime}_{1}=\xi^{\prime}$ with probability $(1-k/n)$,
where $\xi^{\prime}$ has the same distribution as $\xi^{\prime}_{1}$. Also,
the distribution $L^{\ast}$ is a mix of the trivial distribution with
probability $\alpha$ and the distribution of $\hat{\zeta}$ with probability
$(1-\alpha)$. So, for $j>0$,

$\displaystyle\mathbb{P}(\xi^{\prime\prime}_{1}=j)$
$\displaystyle=(1-k/n)\mathbb{P}(\xi^{\prime}_{1}=j),$
$\displaystyle\mathbb{P}(L^{\ast}=j)$
$\displaystyle=(1-\alpha)\mathbb{P}(\hat{\zeta}_{1}=j),$

and therefore,

$\displaystyle\mathbb{P}(\xi^{\prime\prime}_{1}=j)=\mathbb{P}(L^{\ast}=j)\frac{1-k/n}{1-\alpha}\frac{\mathbb{P}\Big{(}S_{\hat{\zeta}}(n-k-1)=n-1-j\Big{)}}{\mathbb{P}\Big{(}S_{\hat{\zeta}}(n-k)=n-1\Big{)}}.$

Next, both $k$ and $n$ grow to infinity in such a way that
$k/n\to\alpha\in(0,1)$, hence
$\mathbb{E}S_{\hat{\zeta}}(n-k)=(n-k)\mathbb{E}\hat{\zeta}_{1}=n(1-k/n)/(1-\alpha)=n+o(1)$
and similarly $\mathbb{E}S_{\hat{\zeta}}(n-k-1)=n+o(1)$. We apply the local
limit law (Theorem I.4.2 in Kolchin [17]) and find that for any
$\varepsilon>0$ we can find $n(\varepsilon)$ such that for all
$n>n(\varepsilon)$ and all $j<n^{1/4}$,

$\displaystyle\bigg{|}\frac{1-k/n}{1-\alpha}\frac{\mathbb{P}\Big{(}S_{\hat{\zeta}}(n-k-1)=n-1-j\Big{)}}{\mathbb{P}\Big{(}S_{\hat{\zeta}}(n-k)=n-1\Big{)}}-1\bigg{|}<\varepsilon.$

In addition, this ratio of probabilities is bounded uniformly in $j$ and $n$.

Then, for arbitrary $\varepsilon>0$ and $n>n(\varepsilon)$, and for some
$c>0$.

$\displaystyle\bigg{|}\mathbb{E}\Big{[}(\xi^{\prime\prime}_{1})^{s}\Big{]}-\mathbb{E}\Big{[}(L^{\ast})^{s}\Big{]}\bigg{|}=\varepsilon\sum_{j=0}^{\lfloor
n^{1/4}\rfloor}j^{s}\,\mathbb{P}(L^{\ast}=j)+c\sum_{j={\lfloor
n^{1/4}\rfloor}+1}^{\infty}j^{s}\,\mathbb{P}(L^{\ast}=j).$

By assumption, the probability distribution of $L$ has exponentially declining
tails, which implies that $L^{\ast}$ has exponentially declining tails, so the
last term is bounded by

$\displaystyle c\sum_{j={\lfloor n^{1/4}\rfloor}+1}^{\infty}j^{s}\,e^{-aj}\to
0,$

as $n\to\infty$, and we conclude that all moments of random variable
$\xi^{\prime\prime}_{1}$ converge to the corresponding moments of $L^{\ast}$,
as $n\to\infty$. In particular,
$\mathbb{V}\mathrm{ar}(\xi^{\prime\prime}_{1})\to(\sigma^{\ast})^{2}$.

(b) By a similar argument, we can write for $j_{1}>0,j_{2}>0$,

$\displaystyle\mathbb{P}(\xi^{\prime\prime}_{1}=j_{1},\xi^{\prime\prime}_{2}=j_{2})$
$\displaystyle=\mathbb{P}(L_{1}^{\ast}=j_{1},L_{2}^{\ast}=j_{2})\Big{(}\frac{1-k/n}{1-\alpha}\Big{)}^{2}$
$\displaystyle\times\frac{\mathbb{P}\Big{(}S_{\hat{\zeta}}(n-k-2)=n-1-j_{1}-j_{2}\Big{)}}{\mathbb{P}\Big{(}S_{\hat{\zeta}}(n-k)=n-1\Big{)}},$

where $L_{1}^{\ast}$, $L_{2}^{\ast}$ are two independent random variables that
have the $\alpha$-shifted distribution. By using the local limit law, we find
that the ratio of probabilities approaches $1$ as $n\to\infty$, uniformly for
$j_{1}<n^{1/4},j_{2}<n^{1/4}$. In addition, this ratio is bounded uniformly in
$n,j_{1},j_{2}$. Together with assumption (1), this ensures that
$\mathbb{E}\Big{(}(\xi^{\prime\prime}_{1})^{s}(\xi^{\prime\prime}_{2})^{t}\Big{)}\to\mathbb{E}\Big{(}(L^{\ast}_{1})^{s}(L^{\ast}_{2})^{t}\Big{)}$
as $n\to\infty$, for all integer $s\geq 0,t\geq 0$. In particular, this
implies that
$\mathrm{Cov}\Big{(}(\xi^{\prime\prime}_{1})^{s},(\xi^{\prime\prime}_{2})^{t}\Big{)}\to
0$, as $n\to\infty$.

(c) We have

$\displaystyle\mathbb{P}$ $\displaystyle(\max_{i}\xi^{\prime}_{i}\leq
n^{\beta})=\mathbb{P}\Big{(}\xi^{\prime}_{1}\leq
n^{\beta},\ldots,\xi^{\prime}_{n-k}\leq n^{\beta}\Big{)}$
$\displaystyle=\mathbb{P}\Big{(}\hat{\zeta}_{1}\leq
n^{\beta},\ldots,\hat{\zeta}_{n-k}\leq
n^{\beta}\Big{|}S_{\hat{\zeta}}(n-k)=n-1\Big{)}$
$\displaystyle=\Big{[}\mathbb{P}(\hat{\zeta}_{1}\leq
n^{\beta})\Big{]}^{n-k}\frac{\mathbb{P}\Big{(}S_{\hat{\zeta}}(n-k)=n-1)\Big{|}\hat{\zeta}_{1}\leq
n^{\beta},\ldots,\hat{\zeta}_{n-k}\leq
n^{\beta}\Big{)}}{\mathbb{P}(S_{\hat{\zeta}}(n-k)=n-1)}.$

Define truncated random variables $\hat{\zeta}_{i}^{(n)}$, $i=1,\ldots,n-k$ as
i.i.d random variables with distribution

$\displaystyle\mathbb{P}(\hat{\zeta}_{1}^{(n)}=j)=\mathbb{P}\Big{(}\hat{\zeta}_{1}=j\Big{|}\hat{\zeta}_{1}\leq
n^{\beta}\Big{)}.$

Then we can write:

$\mathbb{P}(\max_{i}\xi^{\prime}_{i}\leq
n^{\beta})=\Big{[}\mathbb{P}(\hat{\zeta}_{1}\leq
n^{\beta})\Big{]}^{n-k}\frac{\mathbb{P}\Big{(}S_{\hat{\zeta}^{(n)}}(n-k)=n-1)\Big{)}}{\mathbb{P}\Big{(}S_{\hat{\zeta}}(n-k)=n-1\Big{)}}.$
(16)

By the assumption on the offspring probabilities, $\widehat{\zeta}_{1}$ has
exponentially declining tails and therefore, for some $a>0$, we can write:

$\displaystyle(n-k)\log\mathbb{P}(\hat{\zeta}_{1}\leq
n^{\beta})\geq(n-k)\log(1-e^{-an^{\beta}})\geq-2ne^{-an^{\beta}},$

where the last inequality follows because by a choice of $a$ we can ensure
$e^{-an^{\beta}}<3/4$ and we have $\log(1-x)\geq-2x$ for $0\leq x\leq 3/4$.
Then,

$\displaystyle\Big{[}\mathbb{P}(\hat{\zeta}_{1}\leq n^{\beta})\Big{]}^{n-k}$
$\displaystyle\geq e^{-2ne^{-an^{\beta}}}\geq 1-2ne^{-an^{\beta}}.$

This implies that for sufficiently small $\gamma>0$,
$\big{[}\mathbb{P}(\hat{\zeta}_{1}\leq n^{\beta})\big{]}^{n-k}\geq
1-e^{-\gamma n^{\beta}}$.

To estimate the denominator in the ratio of probabilities in (16), we can use
the local limit theorem (Theorem I.4.2 in Kolchin [17]). For the numerator,
this theorem is not applicable directly, since the distribution of random
variables $\hat{\zeta}_{i}^{(n)}$ is changing with $n$. However, it can be
adapted to this more general setting along the lines in the proof of Theorem
I.4.2 in Kolchin. (We provide the proof of the modified local limit theorem in
“Appendix”.) Then, we find that, for $r>0$,

$\displaystyle\frac{\mathbb{P}\Big{(}S_{\hat{\zeta}^{(n)}}(n-k)=n-1)\Big{)}}{\mathbb{P}\Big{(}S_{\hat{\zeta}}(n-k)=n-1\Big{)}}\to
1$

as $n\to\infty$. It follows that for some smaller $\gamma>0$,
$\mathbb{P}(\max_{i}\xi^{\prime}_{i}\leq n^{\beta})\geq 1-e^{-\gamma
n^{\beta}}$. In a similar fashion we can show that
$\mathbb{P}(\min_{i}\xi^{\prime}_{i}\geq-n^{\beta})\geq 1-e^{-\gamma
n^{\beta}}$. The sequence
$\xi^{\prime\prime}_{(1)},\ldots,\xi^{\prime\prime}_{(n)}$ is different from
the sequence $\xi^{\prime}_{(1)},\ldots,\xi^{\prime}_{(n-k)}$ only by addition
of $k$ zeros. It follows that some $\gamma>0$,
$\mathbb{P}(\max_{i}|\xi^{\prime\prime}_{i}|\leq n^{\beta})\geq 1-e^{-\gamma
n^{\beta}}$, which implies the claim of the lemma.

∎

######  Lemma 2.6.

As $n\to\infty$,

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\Big{(}\xi^{\prime\prime}_{i}-1+\frac{1}{n}\Big{)}^{2}\stackrel{{\scriptstyle\scriptscriptstyle\mathbb{P}}}{{\longrightarrow}}(\sigma^{\ast})^{2}.$

###### Proof.

We have $\mathbb{E}\xi^{\prime\prime}_{i}=1-1/n$ and
$\mathbb{E}\big{[}(\xi^{\prime\prime}_{i}-1+\frac{1}{n})^{2}\big{]}\to(\sigma^{\ast})^{2}$
by Lemma 2.5(a). Then,

$\displaystyle\mathbb{V}\mathrm{ar}$
$\displaystyle\Big{(}\frac{1}{n}\sum_{i=1}^{n}\big{(}\xi^{\prime\prime}_{i}-1+\frac{1}{n}\big{)}^{2}\Big{)}=\frac{1}{n^{2}}\Big{[}\sum_{i=1}^{n}\mathbb{V}\mathrm{ar}\Big{(}\big{(}\xi^{\prime\prime}_{i}-1+\frac{1}{n}\big{)}^{2}\Big{)}$
$\displaystyle+2\sum_{i<j}\mathrm{Cov}\Big{(}\big{(}\xi^{\prime\prime}_{i}-1+\frac{1}{n}\big{)}^{2},\big{(}\xi^{\prime\prime}_{j}-1+\frac{1}{n}\big{)}^{2}\Big{)}\Big{]}$
$\displaystyle=\frac{1}{n^{2}}\Big{[}n\mathbb{V}\mathrm{ar}\Big{(}\big{(}\xi^{\prime\prime}_{1}-1+\frac{1}{n}\big{)}^{2}\Big{)}+n(n-1)\mathrm{Cov}\Big{(}\big{(}\xi^{\prime\prime}_{1}-1+\frac{1}{n}\big{)}^{2},\big{(}\xi^{\prime\prime}_{2}-1+\frac{1}{n}\big{)}^{2}\Big{)}\Big{]}$
$\displaystyle\to 0,$

by Lemma 2.5(a) and (b). By Chebyshev’s inequality, this implies the statement
of the lemma. ∎

Let $S^{\prime\prime}_{n}(0)=0$ and

$\displaystyle
S^{\prime\prime}_{n}(j)=\sum_{i=1}^{j}\xi^{\prime\prime}_{i},\text{ where
}j=1,\ldots,n,$

and extend $S^{\prime\prime}_{n}(t)$ to all $t\in[0,n]$ by linear
interpolation.

In the lemmas below, the convergence of stochastic processes is the weak
convergence with respect to the space of continuous functions on $[0,1]$ with
the topology induced by the uniform norm:
$\|f\|_{\infty}=\sup_{t\in[0,1]}f(t)$.

######  Lemma 2.7.

As $n\to\infty$

$\displaystyle\frac{S^{\prime\prime}_{n}(tn)-tn}{\sigma^{\ast}\sqrt{n}}\Big{|}_{t\in[0,1]}\xrightarrow{weakly}b(t)\Big{|}_{t\in[0,1]},$

where $b(t)$ is the standard Brownian bridge on the interval $[0,1]$, and
$\sigma^{\ast}$ is as defined in (5).

###### Proof.

Define $x_{j}=(\xi^{\prime\prime}_{j}-1+1/n)/(\sqrt{n}\sigma^{\ast})$ and
$X_{n}(t)=\sum_{j=1}^{[tn]}x_{j}$, with $X_{n}(t)=0$ for $0\leq t<1/n$. Then,
$\sum_{j=1}^{n}x_{j}=0$ and
$\sum_{j=1}^{n}x_{j}^{2}\stackrel{{\scriptstyle\scriptscriptstyle\mathbb{P}}}{{\longrightarrow}}1$
by Lemma 2.6. In addition, by Lemma 2.5(c),
$\max_{j}|x_{j}|\stackrel{{\scriptstyle\scriptscriptstyle\mathbb{P}}}{{\longrightarrow}}0$.
This means that the assumptions of Theorem 24.2 in Billingsley’s book [4] are
satisfied, and we have $X_{n}(t)\xrightarrow{weakly}b(t)$. This implies the
claim of the lemma. ∎

Next, we consider the application of Step 3 in Algorithm A. By Theorem 1.6,
this step produces the Łukasiewicz path of a random tree in $\Omega_{k,n}$.

######  Lemma 2.8.

As $n\to\infty$, the normalized Łukasiewicz path
$S_{n}(tn)/(\sigma^{\ast}\sqrt{n})$ of a random tree from $\Omega_{k,n}$
weakly converges to a standard Brownian excursion $e(t)$.

###### Proof.

Let
$b^{\prime\prime}_{n}(t)=(S^{\prime\prime}_{n}(tn)-tn)/(\sigma^{\ast}\sqrt{n})$.
By the previous lemma, $b^{\prime\prime}_{n}(t)$ converges to $b(t)$ in
distribution. According to Vervaat’s Theorem (Theorem 1 in [31]), the location
of the absolute minimum of Brownian bridge $b(t)$ is unique with probability
$1$, and, if this time is denoted $\tau_{m}$, the process
$b(t+\tau_{m})-b(\tau_{m})$ is distributed as a Brownian excursion $e(t)$.
(Here, the addition in the argument is modulo $1$.)

Since $b^{\prime\prime}_{n}(t)$ converges to the Brownian bridge $b(t)$ in
distribution, we can couple the random variables $b^{\prime\prime}_{n}(t)$ and
$b(t)$, so that the time at which $b^{\prime\prime}_{n}(t)$ achieves its first
minimum, $\tau^{\prime\prime}_{m}$, converges in probability to $\tau_{m}$.
Then,

$\displaystyle
b^{\prime\prime}_{n}(t+\tau^{\prime\prime}_{m})-b^{\prime\prime}_{n}(\tau^{\prime\prime}_{m})\Big{|}_{t\in[0,1]}\xrightarrow{dist}b(t+\tau_{m})-b(\tau_{m})\Big{|}_{t\in[0,1]},$

which is distributed as a Brownian excursion by Vervaat’s theorem.

If we write $S_{n}(j)=\sum_{i=1}^{j}(\widehat{\xi}^{\prime\prime}_{i}-1)$,
where $(\widehat{\xi}^{\prime\prime}_{i})$ is the sequence
$(\xi^{\prime\prime}_{i})$ after the cyclic shift, then the process
$b^{\prime\prime}_{n}(t+\tau^{\prime\prime}_{m})-b^{\prime\prime}_{n}(\tau^{\prime\prime}_{m})$
is equal to $S_{n}(t)/(\sigma^{\ast}\sqrt{n})$. By Theorem 1.6, $S_{n}(t)$ is
distributed as the Łukasiewicz path of a random tree from $\Omega_{k,n}$.

Hence, we have shown that the normalized Łukasiewicz path
$S_{n}(tn)/(\sigma^{\ast}\sqrt{n})$ of a random tree from $\Omega_{k,n}$
converges to a standard Brownian excursion $e(t)$. ∎

Step 2: Łukasiewicz path is close to the height process.

The height process for an ordered tree is defined in (8). In Lemma 1 of
Marckert and Mokkadem[24], it was shown that if $S_{n}(j)$ is the Łukasiewicz
path of an ordered tree, then the height process $H_{n}(l)$, $l=0,\ldots,n-1$,
can be written as follows:

$H_{n}(l)=\\#\Big{\\{}i:0\leq i\leq l-1,S_{n}(i)=\min_{i\leq k\leq
l}\big{\\{}S_{n}(k)\big{\\}}\Big{\\}}$ (17)

In words, $H_{n}(l)$ is the number of (weak) right minima of $S_{n}$ on the
interval $[0,l]$ (not counting the trivial right minimum at $i=l$).

For example, in Fig. 1, $H_{8}(3)=2$, and this corresponds to the right minima
at $i=0$ and $i=2$ of the Łukasiewicz path $S_{8}(i)$ on interval $[0,3]$.

Now, let $W_{n}(j)$, $j=0,\ldots,n$, be a path of a random walk with
independent increments $x_{i}$ that can take values $s=-1,0,1,\ldots$ with the
following probabilities:

$\mathbb{P}(x_{i}=s)=w^{\ast}_{s+1},$ (18)

where $\\{w^{\ast}_{k}\\}_{k\geq 0}$ is the $\alpha$-shifted weight
distribution from Definition 1 . For a path of this random walk, we can also
define the number of weak right minima on the interval $[0,l]$,
$l=0,\ldots,n-1$:

$RM_{n}(l)=\\#\Big{\\{}i:0\leq i\leq l-1,W_{n}(i)=\min_{i\leq k\leq
l}\big{\\{}W_{n}(k)\big{\\}}\Big{\\}}$ (19)

The key result about the process $RM_{n}(l)$ was proved in [24].

######  Lemma 2.9 (Corollary 5 in [24]).

Let $W_{n}(j)$, $j=0,\ldots,n$, be a path of a random walk with independent
increments that have the law as in (18), and let $RM_{n}(l)$ be as defined in
(19). Then, for some $\gamma>0$ and $\nu>0$, we have

$\mathbb{P}\bigg{(}\sup_{0\leq l<n}\Big{|}W_{n}(l)-\min_{0\leq i\leq
l}W_{n}(i)-RM_{n}(l)\frac{(\sigma^{\ast})^{2}}{2}\Big{|}\geq
n^{1/4+\nu}\bigg{)}\leq e^{-\gamma n^{\nu}}.$ (20)

Note that if $W_{n}(j)$ happens to be an excursion, then $\min_{0\leq i\leq
l}W_{n}(i)=0$ and in this case Lemma 2.9 says that $RM_{n}(l)$ after scaling
by $(\sigma^{\ast})^{2}/2$ is close to the excursion $W_{n}(l)$.

The proof of this result in [24] is based on a reduction of the problem to a
problem about ladder heights of a random walk, for which appropriate tools are
available in Feller’s book ([13], Chapter XII).

By using this result, we can complete the second step of the proof.

######  Lemma 2.10.

Let $S_{n}(l)$ and $H_{n}(l)$ be the Łukasiewicz and the height processes for
a random tree in $\Omega_{k,n}$. For any $\nu>0$, there exists constants
$\gamma>0$ and $N>0$ such that for all $n\geq N$ and $(n,k)\in PP(w)$,

$\mathbb{P}\bigg{(}\sup_{0\leq
l<n}\Big{|}S_{n}(l)-\frac{(\sigma^{\ast})^{2}}{2}H_{n}(l)\Big{|}\geq
n^{1/4+\nu}\bigg{)}\leq e^{-\gamma n^{\nu}}.$ (21)

###### Proof.

From (17) and (19), it can be seen that the probability of the event in (21)
equals the probability of the event in (20), denoted as $\mathfrak{A}_{n}$,
conditional on the event $\mathfrak{B}_{n}$ that $W_{n}(i)$, $i=0,\ldots,n$ is
an excursion with exactly $k$ steps equal to $-1$. We have

$\displaystyle\mathbb{P}(\mathfrak{A}_{n}|\mathfrak{B}_{n})\leq\frac{\mathbb{P}(\mathfrak{A}_{n})}{\mathbb{P}(\mathfrak{B}_{n})}\leq\frac{e^{-\gamma
n^{\nu}}}{\mathbb{P}(\mathfrak{B}_{n})}.$

It follows that it is enough to show that $\mathbb{P}(\mathfrak{B}_{n})$ is
sufficiently large. Let us introduce two other events: $\mathfrak{C}_{n}$ is
the event that $W_{n}(i)$ has exactly $k$ steps equal to $-1$ and
$\mathfrak{E}_{n}$ is the event that $W_{n}(i)$ is an excursion. Then
$\mathfrak{B}_{n}=\mathfrak{C}_{n}\cap\mathfrak{E}_{n}$ and

$\displaystyle\mathbb{P}(\mathfrak{B}_{n})=\mathbb{P}(\mathfrak{E}_{n}|\mathfrak{C}_{n})\mathbb{P}(\mathfrak{C}_{n}).$

The probability of the increment $-1$ in the random walk $W_{n}$ equals to
$w^{\ast}_{0}=\alpha$, so by the local central limit theorem the probability
of the event $\mathfrak{C}_{n}$ is asymptotically equal to $a/\sqrt{n}$ with
$a>0$.

In order to calculate $\mathbb{P}(\mathfrak{E}_{n}|\mathfrak{C}_{n})$ we note
that the distribution of the increments conditional that they are non-negative
is given by

$\displaystyle\mathbb{P}(x_{j}=s|x_{j}\geq
0)=\frac{w^{\ast}_{s+1}}{1-\alpha},\text{ for }s=0,1,2,\ldots$

The conditional expectation of the increment equals

$\displaystyle\mathbb{E}(x_{j}|x_{j}\geq 0)$
$\displaystyle=\frac{1}{1-\alpha}\sum_{s=0}^{\infty}sw^{\ast}_{s+1}=\frac{1}{1-\alpha}\sum_{k=1}^{\infty}(k-1)w^{\ast}_{k}$
$\displaystyle=\frac{1}{1-\alpha}\Big{(}\sum_{k=1}^{\infty}kw^{\ast}_{k}-\sum_{k=1}^{\infty}w^{\ast}_{k}\Big{)}=\frac{1}{1-\alpha}\Big{(}1-(1-\alpha)\Big{)}$
$\displaystyle=\frac{\alpha}{1-\alpha}.$

Then the expectation of the sum $W_{n}(n)$ conditional that exactly $k$ of the
increments are equal to $-1$ is

$\displaystyle\mathbb{E}(W_{n}(n)|\mathfrak{C}_{n})$
$\displaystyle=-k+\mathbb{E}(x_{j}|x_{j}\geq 0)(n-k)$ $\displaystyle=-\alpha
n+\frac{\alpha}{1-\alpha}(1-\alpha)n+O(1)=O(1).$

Again, by using the local central limit theorem, we find that the probability
that $W_{n}$ is a random walk bridge, conditional on the event
$\mathfrak{C}_{n}$, is asymptotically equal to $b/\sqrt{n}$ with $b>0$. Then,
all $n$ cyclic shifts of this random walk bridge have the same probability by
exchangeability of the increments and exactly one of these shifts is an
excursion by the cyclic lemma. Hence, conditional on $\mathfrak{C}_{n}$, the
random walk $W_{n}$ is an excursion with probability $\sim b/n^{3/2}$.
Altogether we conclude that

$\displaystyle\mathbb{P}(\mathfrak{B}_{n})\sim\frac{ab}{n^{5/2}},$

with $ab>0$. Hence,

$\displaystyle\mathbb{P}(\mathfrak{A}_{n}|\mathfrak{B}_{n})\leq\frac{1}{ab}n^{5/2}e^{-\gamma
n^{\nu}}\leq e^{-\gamma^{\prime}n^{\nu}},$

for a suitably chosen $\gamma^{\prime}$ and this completes the proof of the
lemma. ∎

Step 3. The height process is close to the contour process.

Here we introduce a couple of purely combinatorial results from Marckert and
Mokkadem[24] that relate the height and contour processes.

######  Definition 2.

Let $T\in\Omega_{n}$ be a rooted planar tree on $n$ vertices. For every
$l=0,\ldots,n-1$, define $m(l)$ as the first time when the Depth First Search
reaches the vertex $v_{l}$.

It is clear that the sequence $\Big{(}m(l)\Big{)}_{l=0}^{n-1}$ is strictly
increasing.

In the example in Fig. 1, we have:

l | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7
---|---|---|---|---|---|---|---|---
m(l) | 0 | 1 | 3 | 4 | 7 | 8 | 9 | 12

By definition of the contour process $C_{n}(t)$, it is easy to see that for
all $l$, the points $\big{(}m(l),H_{n}(l)\big{)}$ are located on the graph of
the contour process. Note also that for all $k\in\big{[}m(l),m(l+1)\big{)}$,

$H_{n}(l+1)-1\leq C_{n}(k)\leq H_{n}(l).$ (22)

(see Lemma 3 in [24]). Intuitively, $\big{(}m(l),H_{n}(l)\big{)}$ interpolate
the contour process, and $l\mapsto m(l)$ can be thought as a time change that
connects the contour process to the height process. See the illustration in
Fig. 1.

Another important combinatorial result proved in [24] is that for every
$l\in\\{0,\ldots,n-1\\}$,

$m(l)=2l-H_{n}(l).$ (23)

Since for large $l$, we can expect that $H_{n}(l)$ has the order $\sqrt{l}$
with large probability, this identity suggests that the time change function
$m(l)\sim 2l$ with large probability, and that the deviations of $m(l)$ from
$2l$ are of order $\sqrt{l}$.

Now, let us define $\tau(nt)$ as the integer such that

$\lfloor
2nt\rfloor\in\Big{[}m\big{(}\tau(nt)\big{)},m\big{(}\tau(nt)+1\big{)}\Big{)}.$
(24)

(Intuitively, this function plays the role of the inverse of $m(l)$ scaled by
$2$.)

Then we have the following result.

######  Lemma 2.11.

For all $a>0$ and $\nu>0$, there exists such $\gamma>0$ that

$\displaystyle\mathbb{P}\Big{(}\sup_{t\in[0,1]}\Big{|}H_{n}\big{(}\tau(nt)\big{)}-C_{n}(2nt)\Big{|}\geq
an^{1/4+\nu}\Big{)}\leq e^{-\gamma n^{\nu}}$

###### Proof.

By (22), we have

$\displaystyle\mathbb{P}\Big{(}\sup_{t\in[0,1]}\Big{|}H_{n}\big{(}\tau(nt)\big{)}-C_{n}(2nt)\Big{|}\geq
an^{1/4+\nu}\Big{)}$
$\displaystyle\leq\mathbb{P}\Big{(}\sup_{l\in\\{0,\ldots,n-2\\}}\Big{|}H_{n}\big{(}l\big{)}-H_{n}\big{(}l+1\big{)}+1\Big{|}\geq
an^{1/4+\nu}\Big{)}$
$\displaystyle\leq\mathbb{P}\Big{(}\sup_{l\in\\{0,\ldots,n-2\\}}\Big{|}H_{n}\big{(}l\big{)}-\frac{2}{(\sigma^{\ast})^{2}}S_{n}(l)\Big{|}\geq\frac{a}{3}n^{1/4+\nu}\Big{)}$
$\displaystyle+\mathbb{P}\Big{(}\sup_{l\in\\{0,\ldots,n-2\\}}\Big{|}H_{n}\big{(}l+1\big{)}-1-\frac{2}{(\sigma^{\ast})^{2}}S_{n}(l+1)\Big{|}\geq\frac{a}{3}n^{1/4+\nu}\Big{)},$
$\displaystyle+\mathbb{P}\Big{(}\sup_{l\in\\{0,\ldots,n-2\\}}\frac{2}{(\sigma^{\ast})^{2}}\Big{|}S_{n}\big{(}l+1\big{)}-S_{n}(l)\Big{|}\geq\frac{a}{3}n^{1/4+\nu}\Big{)},$

and by Lemmas 2.5(c) and 2.10, the sum of these three probabilities can be
bounded by $e^{-\gamma n^{\nu}}$ with a suitable $\gamma>0$. ∎

By using Lemmas 2.10 and 2.11, we can relate the Łukasiewicz process
$S(\tau(nt))$ and the contour process $C_{n}(nt)$. To move further, we need to
estimate the difference between $\tau(nt)$ and $nt$.

######  Lemma 2.12.

Let $\tau(nt)$ be as in (24) for the random time $m(l)$ defined for a random
tree in $\Omega_{k,n}$. Then,

$\displaystyle\mathbb{P}\Big{(}\sup_{t\in[0,1]}\big{|}\tau(nt)-nt\big{|}>n^{1/2+\nu}\Big{)}\leq
e^{-\gamma n^{\nu}}.$

###### Proof.

By the triangle inequality, we have

$\displaystyle\sup_{t\in[0,1]}\big{|}2\tau(nt)-2nt\big{|}\leq\sup_{t\in[0,1]}\big{|}2\tau(nt)-m(\tau(nt))\big{|}+\sup_{t\in[0,1]}\big{|}m(\tau(nt))-2nt\big{|}.$

By applying Equation (23) with $l=\tau(nt)$, we find that the first term is
bounded by $\sup_{t}H_{n}\big{(}\tau(nt)\big{)}$. For the second term, we note
that by definition of $\tau(nt)$, it is bounded by

$\displaystyle\sup_{t\in[0,1]}\Big{|}m\big{(}\tau(nt)+1\big{)}-m\big{(}\tau(nt)\big{)}\Big{|}$
$\displaystyle=\sup_{l\in\\{0,\ldots,n-1\\}}\big{|}m(l+1)-m(l)\big{|}$
$\displaystyle\leq\sup_{l\in\\{0,\ldots,n-1\\}}H_{n}(l).$

Altogether, we have

$\displaystyle\sup_{t\in[0,1]}\big{|}2\tau(nt)-2nt\big{|}\leq
2\sup_{l\in\\{0,\ldots,n-1\\}}H_{n}(l).$

By (17), $H_{n}(l)$ is the number of right minima for $S_{n}$ on the interval
$[0,l]$. It was shown in Lemma 5 in [24], that the number of right minima for
the random walk $W_{n}$ satisfies the bound

$\displaystyle\mathbb{P}\Big{(}\sup_{l\in\\{0,\ldots,n-1\\}}RM_{n}(l)\geq
n^{1/2+\nu}\Big{)}\leq e^{-\gamma n^{\nu}}$

for a $\gamma>0$. An inequality of this form also holds for the number of
right minima of $S_{n}$ by a conditioning argument similar to the argument
that we used in the proof of Lemma 2.10.

So we have, for some $\gamma>0$,

$\displaystyle\mathbb{P}\Big{(}\sup_{t\in[0,1]}\big{|}\tau(nt)-nt\big{|}\leq
n^{1/2+\nu}\Big{)}\geq\mathbb{P}\Big{(}2\sup_{l\in\\{0,\ldots,n-1\\}}H_{n}(l)\leq
n^{1/2+\nu}\Big{)}\geq 1-e^{-\gamma n^{\nu}}$

and

$\displaystyle\mathbb{P}\Big{(}\sup_{t\in[0,1]}\big{|}\tau(nt)-nt\big{|}>n^{1/2+\nu}\Big{)}\leq
e^{-\gamma n^{\nu}}$

∎

######  Lemma 2.13.

Let $S_{n}(t)$ and $C_{n}(t)$ be the Łukasiewicz and the contour processes for
a tree $T\in\Omega_{k,n}$. Then, for every $\nu>0$, there exist two positive
constants, $\gamma>0$ and $N>0$, such that for all $n\geq N$,

$\displaystyle\mathbb{P}\bigg{[}\sup_{t\in[0,1]}\Big{|}S_{n}(nt)-\frac{\sigma^{2}}{2}C_{n}(2nt)\Big{|}\geq
n^{1/4+\nu}\bigg{]}\leq e^{-\gamma n^{\nu}}.$

###### Proof.

We have

$\displaystyle\mathbb{P}\Big{(}\sup_{t\in[0,1]}\big{|}S_{n}(nt)-\frac{\sigma^{2}}{2}C_{n}(2nt)\big{|}\geq
n^{1/4+\nu}\Big{)}\leq A+B+C+D,$

where

$\displaystyle
A=\mathbb{P}\bigg{(}\sup_{t\in[0,1]}\Big{|}S_{n}(nt)-S_{n}\big{(}\tau(nt)\big{)}\Big{|}\geq\frac{1}{3}n^{1/4+\nu},\sup_{t}\big{|}\tau(nt)-nt\big{|}<n^{1/2+\nu}\bigg{)},$
$\displaystyle
B=\mathbb{P}\bigg{(}\sup_{t\in[0,1]}\Big{|}S_{n}\big{(}\tau(nt)\big{)}-\frac{\sigma^{2}}{2}H_{n}\big{(}\tau(nt)\big{)}\Big{|}\geq\frac{1}{3}n^{1/4+\nu}\bigg{)},$
$\displaystyle
C=\mathbb{P}\bigg{(}\frac{\sigma^{2}}{2}\sup_{t\in[0,1]}\Big{|}H_{n}\big{(}\tau(nt)\big{)}-C_{n}(2nt)\Big{|}\geq\frac{1}{3}n^{1/4+\nu}\bigg{)},$
$\displaystyle
D=\mathbb{P}\Big{(}\sup_{t\in[0,1]}\big{|}\tau(nt)-nt\big{|}>n^{1/2+\nu}\Big{)}.$

The quantities $B$, $C$, and $D$ can be estimated using Lemmas 2.10, 2.11, and
2.12, respectively. For quantity $A$, note that we can estimate a similar
quantity for unconditional random walk $W_{n}$:

$\displaystyle\mathbb{P}\bigg{(}\sup_{t\in[0,1]}\Big{|}W_{n}(nt)-W_{n}\big{(}\tau(nt)\big{)}\Big{|}\geq\frac{1}{3}n^{1/4+\nu},\sup_{t}\big{|}\tau(nt)-nt\big{|}<n^{1/2+\nu}\bigg{)}$
$\displaystyle\leq\mathbb{P}\Big{(}\sup_{k\leq n^{1/2+\nu}}\sup_{0\leq j\leq
n-k}\big{|}W_{n}(j)-W_{n}(j+k)\big{|}\geq\frac{1}{3}n^{1/4+\nu}\Big{)}$
$\displaystyle\leq\sum_{j=1}^{n}\mathbb{P}\Big{(}\sup_{k\leq
n^{1/2+\nu}}\big{|}W_{n}(k)\big{|}\geq\frac{1}{3}n^{1/4+\nu}\Big{)}\leq
e^{-\gamma n^{\nu}}.$

The last step holds by Theorem III.15 from Petrov’s book [26] (see also
Appendix in [24]), and here we use the assumption that
$\mathbb{E}e^{aL}<\infty$ for some $a>0$.

This estimate remains valid for the process $S_{n}$ instead of $W_{n}$,
perhaps with a different $\gamma>0$, by a conditioning argument similar to the
argument that was used in the proof of Lemma 2.10. Therefore, we can find such
$\gamma>0$, that $A+B+C+D\leq e^{-\gamma n^{\nu}}$. ∎

Now we can conclude the proof of Theorem 1.2. In Lemma 2.8 we proved that the
normalized Łukasiewicz path $S_{n}(tn)/(\sigma^{\ast}\sqrt{n})$ of a random
tree from $\Omega_{k,n}$ converges to a standard Brownian excursion $e(t)$.
Then Lemma 2.13 implies that the process $\sigma^{\ast}C_{n}(2tn)/(2\sqrt{n})$
also converges to the excursion $e(t)$. This concludes the proof.

∎

For the proof of Theorem 1.4, we need a lemma, which allows us to compare the
probabilities of various events for unconditional random walks and
corresponding random bridges. As in the proof of Theorem 1.6, let
$\hat{\zeta}_{1},\ldots,\hat{\zeta}_{n-k}$ be an i.i.d sequence with
$\hat{\zeta}_{1}$ having distribution
$\widehat{w}_{0}^{\ast}=0,\hat{w}_{i}^{\ast}=w_{i}^{\ast}/(1-\alpha)$,
$i=1,\ldots$. Let

$\displaystyle m:={\lfloor(n-k)/2\rfloor},$

and let $\mathcal{F}_{n}^{(1/2)}$ denote the sigma-algebra generated by random
variables $\hat{\zeta}_{1},\ldots,\hat{\zeta}_{m}$.

######  Lemma 2.14.

Suppose $(n,k_{n})\in PP(w)$, $k_{n}=\alpha n+O(1)$, and the distribution
$\\{w_{i}\\}$ has finite variance. For every event
$\mathfrak{B}\in\mathcal{F}_{n}^{(1/2)}$,

$\displaystyle\mathbb{P}(\mathfrak{B}|\hat{\zeta}_{1}+\ldots+\hat{\zeta}_{n-k}=n-1)\leq
c\mathbb{P}(\mathfrak{B}),$

where $c$ is a positive constant that depends on $\\{w_{i}\\}$ but not on $n$.

###### Proof.

For the joint probability, we have

$\displaystyle\mathbb{P}(\mathfrak{B},S_{\hat{\zeta}}(n-k)=n-1)$
$\displaystyle=\sum_{x=0}^{\infty}\mathbb{P}\Big{(}\mathfrak{B},S_{\hat{\zeta}}(m)=x\Big{)}$
$\displaystyle\times\mathbb{P}\Big{(}S_{\hat{\zeta}}(n-k-m)=n-1-x)\Big{)}$

Hence, for the conditional probability,

$\displaystyle\mathbb{P}(\mathfrak{B}|S_{\hat{\zeta}}(n-k)=n-1)$
$\displaystyle=\sum_{x=0}^{\infty}\mathbb{P}\Big{(}\mathfrak{B},S_{\hat{\zeta}}(m)=x\Big{)}$
$\displaystyle\times\frac{\mathbb{P}\Big{(}S_{\hat{\zeta}}(n-k-m)=n-1-x)\Big{)}}{\mathbb{P}(S_{\hat{\zeta}}(n-k)=n-1)}.$

By using the local limit law (Theorem I.4.2 in Kolchin [17]) we have
$\mathbb{P}(S_{\hat{\zeta}}(n-k)=n-1)\geq c_{1}/\sqrt{n}$ for some $c_{1}>0$.
By Theorem 2.21 on p.76 in Petrov [27],
$\sup_{x}\mathbb{P}\Big{(}S_{\hat{\zeta}}(n-k-m)=n-1-x)\Big{)}\leq
c_{2}/\sqrt{n}$ for some $c_{2}>0$. Altogether, we get

$\displaystyle\mathbb{P}(\mathfrak{B}|S_{\hat{\zeta}}(n-k)=n-1)\leq\frac{c_{2}}{c_{1}}\sum_{x=0}^{\infty}\mathbb{P}\Big{(}\mathfrak{B},S_{\hat{\zeta}}(m)=x\Big{)}=\frac{c_{2}}{c_{1}}\mathbb{P}(\mathfrak{B}).$

∎

###### Proof of Theorem 1.4.

Let

$\displaystyle n_{\xi}(i)$ $\displaystyle=\Big{|}\\{j:\xi_{j}=i,1\leq j\leq
n\\}\Big{|},$ $\displaystyle n_{\xi^{\prime}}(i)$
$\displaystyle=\Big{|}\\{j:\xi^{\prime}_{j}=i,1\leq j\leq n-k\\}\Big{|},$
$\displaystyle n_{\hat{\zeta}}(i)$
$\displaystyle=\Big{|}\\{j:\hat{\zeta}_{j}=i,1\leq j\leq n-k\\}\Big{|},$

where sequences $(\xi_{j}),(\xi^{\prime}_{j})$ and $(\hat{\zeta}_{j})$ are as
defined in the definition of Algorithm A and in the proof of Theorem 1.6. By
Theorem 1.6, the random variable $n_{i}(T)$ has the same distribution as
$n_{\xi}(i)$. For $i=0$, we have $n_{\xi}(0)=k$ and $k/(n-1)\to\alpha$ by
assumption, so $n_{0}(T)/(n-1)\to\alpha=w_{0}^{\ast}$. For $i>0$, we can see
from the algorithm that it is enough to show that
$n_{\xi^{\prime}}(i)/(n-k)\to\widehat{w}_{i}^{\ast}=w_{i}^{\ast}/(1-\alpha)$
almost surely.

Let us define additionally,

$\displaystyle n_{\hat{\zeta}}^{(1/2)}(i)$
$\displaystyle=\Big{|}\Big{\\{}j:\hat{\zeta}_{j}=i,1\leq
j\leq\frac{n-k}{2}\Big{\\}}\Big{|},$ $\displaystyle
n_{\xi^{\prime}}^{(1/2)}(i)$
$\displaystyle=\Big{|}\Big{\\{}j:\xi^{\prime}_{j}=i,1\leq
j\leq\frac{n-k}{2}\Big{\\}}\Big{|}.$

As before, for shortness of formulas, we define
$m:=\lfloor\frac{n-k}{2}\rfloor$.

Then,

$\displaystyle\frac{n_{\hat{\zeta}}^{(1/2)}(i)}{m}=\frac{1}{m}\sum_{j=1}^{m}\mathbbm{1}[\hat{\zeta}_{j}=i],$

which implies
$\mathbb{E}\Big{(}\frac{n_{\hat{\zeta}}^{(1/2)}(i)}{m}\Big{)}=\widehat{w}_{i}^{\ast}$.
Then, by using the independence of random variables $\hat{\zeta}_{j}$,

$\displaystyle\mathbb{E}\Big{|}\frac{n_{\hat{\zeta}}^{(1/2)}(i)}{m}-\widehat{w}_{i}^{\ast}\Big{|}^{4}=\frac{1}{m^{4}}\mathbb{E}\Big{(}\sum_{j=1}^{m}(\mathbbm{1}[\hat{\zeta}_{j}=i]-\widehat{w}_{j}^{\ast})\Big{)}^{4}=O(m^{-2}).$

Then, by Markov’s inequality:

$\displaystyle\mathbb{P}\bigg{[}\Big{|}\frac{n_{\hat{\zeta}}^{(1/2)}(i)}{m}-\widehat{w}_{i}^{\ast}\Big{|}>\varepsilon\bigg{]}=O\Big{(}\frac{1}{\varepsilon^{4}m^{2}}\Big{)}$

By using Lemma 2.14, we infer that this estimate holds also for the
conditioned variables $\xi^{\prime}_{j}$:

$\mathbb{P}\bigg{[}\Big{|}\frac{n_{\xi^{\prime}}^{(1/2)}(i)}{m}-\widehat{w}_{i}^{\ast}\Big{|}>\varepsilon\bigg{]}=O\Big{(}\frac{1}{\varepsilon^{4}m^{2}}\Big{)}.$
(25)

Let

$\displaystyle
n_{\xi^{\prime}}^{(2/2)}(i)=\Big{|}\Big{\\{}j:\xi^{\prime}_{j}=i,m<j\leq
n-k\Big{\\}}\Big{|}.$

Since $\\{\xi^{\prime}_{j}\\}_{j=1}^{n}$ is an exchangeable sequence, we have

$\mathbb{P}\bigg{[}\Big{|}\frac{n_{\xi^{\prime}}^{(2/2)}(i)}{m}-\widehat{w}_{i}^{\ast}\Big{|}>\varepsilon\bigg{]}=O\Big{(}\frac{1}{\varepsilon^{4}m^{2}}\Big{)}.$
(26)

Together, Eqs. (25) and (26) imply that

$\mathbb{P}\bigg{[}\Big{|}\frac{n_{\xi^{\prime}}(i)}{n-k}-\widehat{w}_{i}^{\ast}\Big{|}>\varepsilon\bigg{]}=O\Big{(}\frac{1}{\varepsilon^{4}((n-k)^{2}}\Big{)}.$
(27)

So, by Borel–Cantelli lemma, as $n\to\infty$,

$\displaystyle\frac{n_{\xi^{\prime}}(i)}{n-k}\to\widehat{w}_{i}^{\ast},$

almost surely. This implies the statement of the theorem.

∎

##  3 Conclusion and Remaining Questions

In this paper, we investigated the scaling limit of Galton–Watson trees
conditioned on a fixed number of vertices $n$ and leaves $k$. We considered
the case when both $k$ and $n$ grow to infinity and $k=\alpha n+O(1)$, with
$\alpha\in(0,1-1/\hat{\nu})$. The offspring distribution is assumed to have
the exponentially declining tails ($\mathbb{E}e^{aL}<\infty$ for some $a>0$).

In this case, we found that the limit under rescaling is the Aldous continuum
random tree, and calculated the relevant parameter. We also showed that the
height of a tree in $\Omega_{k,n}$ converges under rescaling to the
distribution of the maximum of the Brownian excursion. Finally, we showed that
the normalized degree sequence of the tree converges almost surely to the
$\alpha$-shifted distribution.

Some other questions remain open. First, what happens when the assumption of
exponentially declining tails is relaxed? Similar to a comment in Marckert and
Mokkadem[24], we can argue that some number of finite moments and the
assumption $\mathbb{E}L=1$ should be sufficient to ensure that our convergence
results stay intact. However, the infinite variance of the offspring
distribution or power tails with $\mathbb{E}L<1$ will likely lead to
considerably different results.

Another question is what happens in the intermediate regime when both $k$ and
$n$ grow but $k/n\sim n^{-\beta}$ or $\big{(}k/n-(1-\widehat{\nu})\big{)}\sim
n^{-\beta}$ with $0<\beta<1$. The first case is when the tree has very small
but still growing number of leaves. The second case is about the regime when
the number of leaves in the tree is close to the maximal capacity that the
offspring distribution can sustain. The results in the paper of Labarbe and
Marckert [20] about Bernoulli random walks suggest that even in this case the
limit is Aldous’ Brownian continuum random tree, although the scaling factor
may be different from $n^{1/2}$.

Besides the scaling limit in the Gromov–Hausdorff topology, it could also be
interesting to study the characteristics of the conditioned trees in these
situations, such as their limiting degree sequences.

Acknowledgements This work was supported by Simons Foundation through the
program “Mathematics and Physical Sciences–Travel Support for Mathematicians”,
Award ID 523587.

The author is indebted to an anonymous referee for a very careful report with
many constructive comments that helped to improve this article.

Data availability Data sharing is not applicable to this article as no
datasets were generated or analyzed during the current study.

## Declarations

Conflict of interest The author declares that he has no conflict of interest.

##  Appendix A Proof of a Local Limit Theorem

First, recall some basic definitions. A random variable $X$ has a _lattice
distribution_ if, with probability 1, it takes values in a set $\\{a+kh\\}$
where $k\in\mathbb{Z}$ and $a$ and $h>0$ are fixed numbers. Number $h$ is
called a _step_ of the distribution. A step $h$ is called the maximal step if
there is no $a_{1}$ and $h_{1}>h$ so that all values of $X$ are in the set
$\\{a_{1}+kh_{1}\\}$.

For every integer random variable $\xi$, we use $\xi^{(A)}$ to denote a
truncated version of $\xi$; that is, $\xi^{(A)}$ has the distribution

$\displaystyle\mathbb{P}(\xi^{(A)}=j)=\mathbb{P}(\xi=j|\xi\leq A).$

######  Theorem A.1.

Let $\xi_{1},\xi_{2},\ldots$ be a sequence of i.i.d non-negative integer
random variables. Assume that for some $\alpha>0$,
$\mathbb{E}e^{\alpha\xi_{1}}<\infty$, and let $\mathbb{E}\xi_{1}=a$,
$\mathbb{V}\mathrm{ar}(\xi_{1})=\sigma^{2}$. Suppose that the maximal step of
the distribution of $\xi_{1}$ equals $1$. Let $A_{1},A_{2},\ldots$ be a
sequence of positive numbers such that $A_{N}=\Omega(N^{\varepsilon})$ for
some $\varepsilon>0$. Then as $N\to\infty$ and uniformly over integer $n$,

$\displaystyle\sigma\sqrt{N}\mathbb{P}(\xi_{1}^{(A_{N})}+\ldots+\xi_{N}^{(A_{N})}=n)-\frac{1}{\sqrt{2\pi}}e^{-\frac{(n-aN)^{2}}{2\sigma^{2}N}}\to
0.$

Before starting the proof of the theorem, let us derive several useful lemmas.

######  Lemma A.2.

Suppose an integer-valued random variable $\xi\geq 0$ has maximal step $1$
Then there exists an $A_{0}$ such that for all $A>A_{0}$, $\xi^{(A)}$ has
maximal step $1$.

###### Proof.

Let $x_{0}<x_{1}<\ldots$ be the values of $\xi$ and let $Y\in\mathbb{Z}^{+}$
be the set of differences $x_{i}-x_{i-1}$ for all $i=1,2,\ldots$. Then, the
maximal step $h=\gcd(Y)$. Indeed, if $h$ is a step then all elements in $Y$
are divisible by $h$, so $h$ is a divisor of $\gcd(Y)$. Conversely, every
$x_{j}$ can be written as $x_{0}+\sum_{i=1}(x_{i}-x_{i-1})$ and therefore
belongs to the set $x_{0}+k\gcd(Y)$, so $\gcd(Y)$ is a step.

By our assumption $gcd(Y)=1$. Order elements of $Y$ as $y_{1},y_{2},\ldots$.
Then for some finite $k$, $gcd(y_{1},\ldots,y_{k})=1$. Take an $m$ such that
all $y_{i}$ with $1\leq i\leq k$ belong to the set of differences
$x_{j}-x_{j-1}$ with $1\leq j\leq m$. Take $A_{0}=x_{m}$. Then for every
random variable $\xi^{(A)}$ with $A\geq A_{0}=x_{m}$, the corresponding set of
differences $Y^{(A)}$ contains all numbers $y_{1},\ldots,y_{k}$ and therefore
$gcd(Y^{(A)})=1$. This implies that the maximal step of $\xi^{(A)}$ equals 1.
∎

Now let $\xi_{i}$, $A_{N}$, $\xi_{i}^{(A_{N})}$ be as assumed in the statement
of Theorem A.1. In addition, let $a_{N}:=\mathbb{E}\xi_{1}^{(A_{N})}$,
$\sigma^{2}_{N}:=\mathbb{V}\mathrm{ar}(\xi_{1}^{(A_{N})})$,
$m_{3}:=\mathbb{E}(|\xi_{1}-a|^{3})$, and
$m_{3,N}:=\mathbb{E}(|\xi_{1}^{(A_{N})}-a_{N}|^{3})$.

######  Lemma A.3.

Under assumptions on $\xi_{i}$, $A_{N}$, as in Theorem A.1, for $N\to\infty$,
we have:

  1. (a)

$(a_{N}-a)N^{r}\to 0$, for every $r>0$,

  2. (b)

$\sigma_{N}-\sigma\to 0$,

  3. (c)

$m_{3,N}-m_{3}\to 0$.

###### Proof.

Recall that for $A_{N}\to\infty$, and $\alpha>0$,

$\displaystyle\int_{A_{N}}^{\infty}xe^{-\alpha x}dx=O(A_{N}e^{-\alpha
A_{N}}).$

Then,

$\displaystyle N^{r}\mathbb{E}|\xi_{1}-\xi_{1}1(X\leq
A_{N})|=N^{r}\sum_{j>A_{N}}jP(\xi_{1}=j)=N^{r}O\Big{(}\sum_{j>A_{N}}je^{-\alpha
j}\Big{)},$

and by comparison with the integral we find that

$N^{r}\mathbb{E}|\xi_{1}-\xi_{1}1(X\leq A_{N})|=O(N^{r}A_{N}e^{-\alpha
A_{N}})\to 0,$ (28)

as $N\to\infty$, under assumption that $A_{N}=\Omega(N^{\varepsilon})$.

Then,

$\displaystyle N^{r}\mathbb{E}|\xi_{1}1(X\leq A_{N})-\xi_{1}^{(A_{N})}|$
$\displaystyle=N^{r}\sum_{j\leq
A_{N}}j\mathbb{P}(\xi=j)\Big{|}1-\frac{1}{\sum_{j\leq
A_{N}}\mathbb{P}(\xi=j)}\Big{|}$ (29)
$\displaystyle=N^{r}O\Big{(}\sum_{j>A_{N}}\mathbb{P}(\xi=j)\Big{)}=N^{r}O(e^{-\alpha
N})\to 0,$

as $N\to\infty$.

From (28) and (29) by the triangle inequality we find that

$\displaystyle N^{r}\mathbb{E}|\xi_{1}-\xi_{1}^{(A_{N})}|\to 0,$

which implies the first claim of the lemma. Clearly, the second and the third
claims can be proved by similar arguments. ∎

Finally, we need an estimate on characteristic functions. Let $f_{N}(t)$ be a
characteristic function of $\xi_{1}^{(A_{N})}$ and let

$\tilde{f}_{N}(t)=f_{N}(t)e^{-ia_{N}t}$ (30)

be the characteristic function of the centered r.v. $\xi_{1}^{(A_{N})}-a_{N}$.

######  Lemma A.4.

Under assumptions on sequences $(\xi_{i})_{i=1}^{\infty}$,
$(A_{N})_{N=1}^{\infty}$, as in Theorem A.1, we have:

  1. (a)

$\tilde{f}_{N}(t)=1-\frac{\sigma_{N}^{2}t^{2}}{2}+O(|t|^{3}),$ with the
constant in $O$ term not depending on $N$.

  2. (b)

there exists an $\varepsilon>0$ and $N_{0}$, such that if $|t|<\varepsilon$
and $N>N_{0}$, then

$\displaystyle|\tilde{f}_{N}(t)|\leq e^{-\sigma^{2}t^{2}/4}.$

###### Proof.

By using Taylor’s formula with remainder, we write:

$\displaystyle\Big{|}\tilde{f}_{N}(t)-\big{(}1-\frac{\sigma_{N}^{2}t^{2}}{2}\big{)}\Big{|}\leq\frac{m_{3,N}|t|^{3}}{6},$

which implies the first claim of the lemma in view of Lemma A.3(c). In
addition, we have

$\Big{|}\tilde{f}_{N}(t)-\big{(}1-\frac{\sigma^{2}t^{2}}{2}\big{)}\Big{|}\leq\frac{|\sigma_{N}^{2}-\sigma^{2}|t^{2}}{2}+\frac{|m_{3,N}-m_{3}||t|^{3}}{6}+\frac{m_{3}|t|^{3}}{6},$
(31)

By using Lemma A.3(b) and (c), we can find $N_{0}$ and $\varepsilon>0$ such
that for $|t|<\varepsilon$ and $N>N_{0}$ the right-hand side of (31) is
smaller than $\frac{\sigma^{2}t^{2}}{4}$, and that
$\frac{\sigma^{2}t^{2}}{2}<1.$ Then,

$\displaystyle|\tilde{f}_{N}(t)|$
$\displaystyle=\Big{|}\tilde{f}_{N}(t)-\big{(}1-\frac{\sigma^{2}t^{2}}{2}\big{)}+\big{(}1-\frac{\sigma^{2}t^{2}}{2}\big{)}\Big{|}$
$\displaystyle\leq\frac{\sigma^{2}t^{2}}{4}+(1-\frac{\sigma^{2}t^{2}}{2}\big{)}\leq
1-\frac{\sigma^{2}t^{2}}{4}\leq e^{-\sigma^{2}t^{2}/4}.$

∎

Now we begin the proof of Theorem A.1. Let

$\displaystyle
P_{N}(n)=\mathbb{P}(\xi_{1}^{(A_{N})}+\ldots+\xi_{N}^{(A_{N})}=n).$

Since the characteristic function of $\xi_{1}^{(A_{N})}$ is $f_{N}(t)$, the
characteristic function of $S_{N}=\xi_{1}^{(A_{N})}+\ldots+\xi_{N}^{(A_{N})}$
equals

$\displaystyle[f_{N}(t)]^{N}=\sum_{n=-\infty}^{\infty}P_{N}(n)e^{itn}.$

By inversion formula,

$\displaystyle
P_{N}(n)=\frac{1}{2\pi}\int_{-\pi}^{\pi}e^{-itn}[f_{N}(t)]^{N}\,dt.$

By using formula (30), parameterization $n=aN+z\sigma\sqrt{N}$, and the change
of variable $x=t\sigma\sqrt{N}$, we rewrite this expression as

$\displaystyle P_{N}(n)$
$\displaystyle=\frac{1}{2\pi}\int_{-\pi}^{\pi}e^{-it(a-a_{N})N}e^{-itz\sigma\sqrt{N}}[\tilde{f}_{N}(t)]^{N}\,dt$
$\displaystyle=\frac{1}{2\pi}\int_{-\pi\sigma\sqrt{N}}^{\pi\sigma\sqrt{N}}e^{-ix\frac{(a-a_{N})}{\sigma}\sqrt{N}}e^{-ixz}\Big{[}\tilde{f}_{N}\big{(}\frac{x}{\sigma\sqrt{N}}\big{)}\Big{]}^{N}\,\frac{dx}{\sigma\sqrt{N}}$

Since, by inversion formula,

$\displaystyle\frac{1}{\sqrt{2\pi}}e^{-z^{2}/2}=\frac{1}{2\pi}\int_{-\infty}^{\infty}e^{-ixz-x^{2}/2}\,dx,$

we can write the difference

$\displaystyle
R_{N}=2\pi\Big{(}\sigma\sqrt{N}P_{N}(n)-\frac{1}{\sqrt{2\pi}}e^{-z^{2}/2}\Big{)},$

as a sum of four integrals:

$\displaystyle I_{1}$
$\displaystyle=\int_{-A}^{A}e^{-ixz}\Big{(}e^{-ix\frac{(a-a_{N})}{\sigma}\sqrt{N}}\Big{[}\tilde{f}_{N}\big{(}\frac{x}{\sigma\sqrt{N}}\big{)}\Big{]}^{N}-e^{-x^{2}/2}\Big{)}\,dx,$
$\displaystyle I_{2}$ $\displaystyle=-\int_{|x|\geq A}e^{-ixz-x^{2}/2}\,dx,$
$\displaystyle I_{3}$
$\displaystyle=\int_{A\leq|x|\leq\varepsilon\sigma\sqrt{N}}e^{-ixz}\Big{(}e^{-ix\frac{(a-a_{N})}{\sigma}\sqrt{N}}\Big{[}\tilde{f}_{N}\big{(}\frac{x}{\sigma\sqrt{N}}\big{)}\Big{]}^{N}\Big{)}\,dx,$
$\displaystyle I_{4}$
$\displaystyle=\int_{\varepsilon\sigma\sqrt{N}\leq|x|\leq\pi\sigma\sqrt{N}}e^{-ixz}\Big{(}e^{-ix\frac{(a-a_{N})}{\sigma}\sqrt{N}}\Big{[}\tilde{f}_{N}\big{(}\frac{x}{\sigma\sqrt{N}}\big{)}\Big{]}^{N}\Big{)}\,dx,$

where $A$ and $\varepsilon$ will be chosen later.

In order to show that $R_{N}\to 0$ for $N\to\infty$, we take an arbitrary
$\delta>0$ and show that by a choice of sufficiently large $N$ the difference
can be made smaller than $\delta$.

Since $|I_{2}|\leq\int_{|x|\geq A}e^{-x^{2}/2}\,dx$, it can be made
arbitrarily small by a choice of a sufficiently large $A$.

Next, we can choose a sufficiently small $\varepsilon$ such that for all
$N\geq N_{0}$, Lemma A.4(b) applies and for
$|x|\leq\varepsilon\sigma\sqrt{N}$,

$\displaystyle\Big{|}\tilde{f}_{N}\big{(}\frac{x}{\sigma\sqrt{N}}\big{)}\Big{|}\leq\exp\Big{(}-\frac{\sigma^{2}}{4}\big{(}\frac{x}{\sigma\sqrt{N}}\big{)}^{2}\Big{)}=e^{-x^{2}/(4N)}.$

Then, we can estimate $I_{3}$:

$\displaystyle|I_{3}|\leq\int_{A\leq|x|\leq\varepsilon\sigma\sqrt{N}}\Big{|}\tilde{f}_{N}\big{(}\frac{x}{\sigma\sqrt{N}}\big{)}\Big{|}^{N}\,dx\leq\int_{A\leq|x|}e^{-x^{2}/4}\,dx,$

which can be made arbitrarily small by a choice of a sufficiently large $A$.

Fix $A$ and $\varepsilon$ so that $|I_{2}|<\delta/4$ and $|I_{3}|<\delta/4$
for $N>N_{0}$.

Next, we address $I_{1}$. Let

$\displaystyle
g_{N}(x):=\Big{[}e^{-i\frac{a-a_{N}}{\sigma\sqrt{N}}x}\tilde{f}_{N}\big{(}\frac{x}{\sigma\sqrt{N}}\big{)}\Big{]}^{N},$

and note that this is the characteristic function of
$(S_{N}-aN)/(\sigma\sqrt{N})$. We claim that the distribution of this random
variable converges to the normal distribution with parameters $(0,1)$. Indeed,
by using Lemma A.4(a) and Lemmas A.3(a) and (b), we find that for a fixed $x$
and $N\to\infty$,

$\displaystyle\log g_{N}(x)$
$\displaystyle=N\Big{[}-i\frac{a-a_{N}}{\sigma\sqrt{N}}x+\log\Big{(}\tilde{f}_{N}\big{(}\frac{x}{\sigma\sqrt{N}}\big{)}\Big{)}\Big{]}$
$\displaystyle=-i\frac{a-a_{N}}{\sigma}\sqrt{N}x+N\log\Big{(}1-\frac{\sigma_{N}^{2}x^{2}}{2\sigma^{2}N}+o\big{(}\frac{1}{N})\Big{)}$
$\displaystyle=-\frac{x^{2}}{2}+o(1),$

which implies that $g_{N}(x)\to e^{-x^{2}/2}$ for every fixed $x$, and
therefore, the distribution of $(S_{n}-aN)/(\sigma\sqrt{N})$ converges weakly
to the standard normal distribution. Now, we invoke the fact that the weak
convergence of probability measures implies the uniform convergence of
characteristic functions on every finite interval. This implies that for every
$A$, integral $I_{1}$ converges to zero as $N\to\infty$.

It remains to estimate integral $I_{4}$. We have

$\displaystyle|I_{4}|\leq\int_{\varepsilon\leq\frac{|x|}{\sigma\sqrt{N}}\leq\pi}\Big{|}\tilde{f}_{N}\big{(}\frac{x}{\sigma\sqrt{N}}\big{)}\Big{|}^{N}\,dx=\sigma\sqrt{N}\int_{\varepsilon\leq|t|\leq\pi}\big{|}f_{N}(t)|^{N}\,dt.$

By Lemma A.2, the maximal step of $\xi_{1}^{(A_{N})}$ equals $1$ for all
sufficiently large $N$, which implies that

$\displaystyle\max_{\varepsilon\leq|t|\leq\pi}|f_{N}(t)|=q<1.$

Therefore, $|I_{4}|\leq\sigma\sqrt{N}2\pi q^{N}$ and $I_{4}\to 0$ as
$N\to\infty$.

The estimates of integrals $I_{1}$ and $I_{4}$ show that there exists $N_{1}$
such that $|I_{1}|\leq\delta/4$ and $|I_{4}|\leq\delta/4$ for $N>N_{1}$.
Hence, the difference $R_{N}$ for $N\to\infty$ approaches $0$ uniformly over
integer $n$.

## References

  * [1] David Aldous.  The continuum random tree I.  Annals of Probability, 19(1):1 – 28, 1991.
  * [2] David Aldous.  The continuum random tree II: an overview.  In M. T. Barlow and N. H. Bingham, editors, Proceedings of the Durham Symposium on Stochastic Analysis, 1990, pages 23 – 70. Cambridge University Press, 1991.
  * [3] David Aldous.  The continuum random tree III.  Annals of Probability, 21(1):248–289, 1993.
  * [4] Patrick Billingsley.  Convergence of Probability Measures.  John Wiley and Sons, Inc., first edition, 1968.
  * [5] N. Broutin and J. F. Marckert.  Asymptotic of trees with a prescribed degree sequence.  Random Structures and Algorithms, 44:290–316, 2014.
  * [6] Dmitri Burago, Yuri Burago, and Sergei Ivanov.  A Course in Metric Geometry, volume 33 of Graduate Studies in Mathematics.  American Mathematical Society, 2001.
  * [7] Nachum Dershowitz and Shmuel Zacks.  The cycle lemma and some applications.  European Journal of Combinatorics, 11:35–40, 1990.
  * [8] Luc Devroye.  Simulating size-constrained Galton–Watson trees.  SIAM J. of Computing, 41(1):1 – 11, 2012.
  * [9] Thomas Duquesne.  A limit theorem for the contour process of conditioned Galton–Watson trees.  Annals of Probability, 31(2):996–1027, 2003.
  * [10] Thomas Duquesne and Jean-François Le Gall.  Random trees, Lévy processes and spatial branching processes.  Astérisque, 281, 2002.
  * [11] A. Dvoretzky and Th. Motzkin.  A problem of arrangements.  Duke Mathematical Journal, 14:305–313, 1947.
  * [12] Steven N. Evans, Jim Pitman, and Anita Winter.  Rayleigh processes, real trees, and root growth with re-grafting.  Probability Theory and Related Fields, 134:81–126, 2006.
  * [13] William Feller.  An Introduction to Probability Theory and Its Applications, volume 2.  John Wiley and Sons, 2 edition, 1971.
  * [14] Philippe Flajolet and Robert Sedgewick.  Analytic Combinatorics.  Cambridge University Press, 2009.
  * [15] Bénédicte Haas and Grégory Miermont.  Scaling limits of Markov branching trees with applications to Galton–Watson and random unordered trees.  Annals of Probability, 40(6):2589–2666, 2012.
  * [16] Svante Janson.  Simply generated trees, conditioned Galton–Watson trees, random allocations and condensation.  Probability Surveys, 9:103–252, 2012.
  * [17] V. F. Kolchin.  Random Mappings.  (English translation: Optimization Software, New York, 1986). Nauka, Moscow, russian edition, 1984.
  * [18] Igor Kortchemski.  Invariance principles for Galton–Watson trees conditioned on the number of leaves.  Stochastic Processes and Their Applications, 122:3126–3172, 2012\.
  * [19] Igor Kortchemski.  A simple proof of Duquesne’s theorem on contour processes of conditioned Galton–Watson trees.  In C. Donati-Martin, editor, Seminaire de Probabilities XLV, volume 2078 of Lecture Notes in Mathematics, pages 537 – 558. Springer International Publishing, 2013.
  * [20] Jean-Maxime Labarbe and Jean-François Marckert.  Asymptotics of Bernoulli random walks, bridges, excursions and meanders with a given number of peaks.  Electronic Journal of Probability, 12:229–261, 2007.
  * [21] Tao Lei.  Scaling limit of random forests with prescribed degree sequences.  Bernoulli, 25:2409–2438, 2019.
  * [22] Jean-François Le Gall.  Random trees and applications.  Probability Surveys, 2:245–311, 2005.
  * [23] Jean-François Le Gall and Yves Le Jan.  Branching processes in Lévy processes: the exploration process.  Annals of Probability, 26:213–252, 1998.
  * [24] Jean-François Marckert and Abdelkader Mokkadem.  The depth-first processes of Galton–Watson trees converge to the same Brownian excursion.  Annals of Probability, 31(3):1655–1678, 2003.
  * [25] Gabriel Berzunza Ojeda, Cecilia Holmgren, and Paul Thévenin.  Convergence of trees with a given degree sequence and of their associated laminations.  https://arxiv.org/abs/2111.07748, 2021.
  * [26] V. V. Petrov.  Sums of independent random variables.  Springer Berlin Heidelberg New York, 1975.
  * [27] V. V. Petrov.  Limit theorems of probability theory, volume 4 of Oxford Studies in Probability.  The Clarendon Press, Oxford, 1995.
  * [28] Jim Pitman.  Combinatorial Stochastic Processes, volume 1875 of Lecture Notes in Mathematics.  Springer, 2002.
  * [29] Douglas Rizzolo.  Scaling limits of Markov branching trees and Galton–Watson trees conditioned on the number of vertices with out-degree in a given set.  Annales de l’Institut Henri Poincaré. Probabilités et Statistiques, 51(512 - 532), 2015.
  * [30] Paul Thévenin.  Vertices with fixed outdegrees in large Galton–Watson trees.  Electronic Journal of Probability, 25:1–25, 2020.
  * [31] Wim Vervaat.  A relation between Brownian bridge and Brownian excursion.  Annals of Probability, 7(1):143 – 149, 1979.