1. Introduction
In [Reference Kesten6], Kesten proved that a critical or subcritical Galton–Watson (GW) tree conditioned on reaching at least height h converges in distribution (for the local topology on trees) as h goes to infinity toward the so-called sized-biased tree (that we call here Kesten’s tree and whose distribution is described in Section 2.3). Since then, several different conditionings have been studied, in particular conditioning on extinction after a large time, on large total population size, and on a large number of leaves. In [Reference Abraham and Delmas2], Abraham and Delmas provided a criterion for local convergence of finite random trees to Kesten’s tree, then gave short and elementary proofs of essentially all previous related results and some new ones. Later [Reference Abraham, Bouaziz and Delmas1] proved that a critical Galton–Watson tree conditioned on having a large number of marked vertices converges in distribution to Kesten’s tree and applied this result to give the limit in distribution of a critical Galton–Watson tree conditioned on having a large number of protected nodes.
Let
$L(\mathbf{t})$
be the width of the tree
$\mathbf{t}$
. Note that this functional L is clearly monotone in the sense of [Reference He5]; therefore, using [Reference He5, Theorem 2.1], we immediately get that a critical GW tree
$\tau$
conditioned on
$\{L(\tau)>n\}$
converges in distribution toward Kesten’s tree as n goes to infinity. In this paper, we propose another proof by somewhat generalizing this monotonicity property. Notice that the functional L does not satisfy additivity in [Reference Abraham and Delmas2]. Considering the conditioning event
$\{L(\tau) = n\}$
was partially solved in [Reference He5].
Let
$p = (p(0),p(1),\ldots)$
be a probability distribution on the set of nonnegative integers. We say that p has finite support if the set
$\{n \in \mathbb{N},\ p(n) > 0\}$
is finite; p is called nonsingular if
$p(0) + p(1) < 1$
. For any nonsingular and critical distribution p with finite support, [Reference He5] provides a positive answer to this question; more precisely, proving that a critical GW tree
$\tau$
conditioned on
$\{L(\tau) = n\}$
converges in distribution toward Kesten’s tree as n goes to infinity.
The main objective of this paper is to provide another proof. On the technical level, our proofs are extremely short and elementary, thanks in particular to the convenient framework in [Reference Abraham and Delmas2].
The paper is then organized as follows: In Section 2, we recall briefly the framework we use for discrete trees and define the Galton–Watson tree
$\tau$
and Kesten’s tree
$\tau^{*}$
associated with offspring distribution p. In Section 3, we state and prove our general result on local convergence of conditioned critical and subcritical Galton–Watson trees and we apply it to the conditioning on large width, in the critical case, in Corollary 3.6, which is one of the main objectives of this paper.
In Section 4, we study the conditioning on large width of a critical Galton–Watson tree with finite support, where we give an elementary and short proof. Finally, we generalize this result by considering a type of conditioning which has never been treated before.
2. Technical background on GW trees
2.1. The set of discrete trees
We denote by
$\mathbb{N} = \{0,1,2,\ldots\}$
the set of nonnegative integers and by
$\mathbb{N}^{*} = \{1,2,\ldots\}$
the set of positive integers. We recall Neveu’s formalism [Reference Neveu7] for ordered rooted trees. Let
$\mathcal{U} = \bigcup_{n\geq 0} (\mathbb{N}^{*})^{n}$
be the set of finite sequences of positive integers with the convention
$(\mathbb{N}^{*})^{0} = \{\emptyset\}$
. For
$u\in \mathcal{U}$
, its length or generation
$|u| \in \mathbb{N}$
is defined by
$u \in(\mathbb{N}^{*})^{|u|}$
. If u and v are two sequences of
$\mathcal{U}$
, we denote by uv the concatenation of the two sequences, with the convention that
$uv = u$
if
$v = \emptyset$
and
$uv = v$
if
$u = \emptyset$
. The set of ancestors of u is
$\textrm{An}(u) = \{v \in \mathcal{U};$
there exists
$w \in \mathcal{U}$
such that
$u = vw\}$
. The most recent common ancestor of a subset s of
$\mathcal{U}$
, denoted by R(s), is the unique element u of
$\cap_{u \in s} \textrm{An}(u)$
with maximal length
$|u|$
. For two distinct elements u and v of
$\mathcal{U}$
, we denote by
$u<v$
the lexicographic order on
$\mathcal{U}$
, i.e.
$u<v$
if
$u \in \textrm{An}(v)$
and
$u \neq v$
, or if
$u=wiu'$
and
$v=wjv'$
for some
$i,j \in \mathbb{N}^{*}$
with
$i<j$
. We write
$u \leq v$
if
$u=v$
or
$u<v$
.
A tree
$\mathbf{t}$
is a subset of
$\mathcal{U}$
that satisfies:
-
•
$\emptyset \in \mathbf{t}$
; -
• if
$u \in \mathbf{t}$
, then
$\textrm{An}(u) \subset \mathbf{t}$
; -
• for every
$u \in \mathbf{t}$
, there exists
$k_{u}(\mathbf{t}) \in \mathbb{N}$
such that, for every
$i \in \mathbb{N}^*$
,
$ui \in \mathbf{t}$
if and only if
$1 \leq i \leq k_{u}(\mathbf{t})$
.
The vertex
$\emptyset$
is called the root of
$\mathbf{t}$
. The integer
$k_{u}(\mathbf{t})$
represents the number of offspring of the vertex
$u \in \mathbf{t}$
, and we call it the outdegree of the node u in the tree
$\mathbf{t}$
. The maximal outdegree
$M(\mathbf{t})$
of a tree
$\mathbf{t}$
is defined by
$M(\mathbf{t}) = \sup\{k_{u}(\mathbf{t}),\, u \in \mathbf{t} \}$
. The set of children of a vertex
$u \in \mathbf{t}$
is given by
$C_u(\mathbf{t}) = \{ui ;\, 1 \leq i \leq k_u(\mathbf{t})\}$
. By convention, we set
$k_u(\mathbf{t}) = -1$
if
$u \not \in \mathbf{t}$
.
A vertex
$u \in \mathbf{t}$
is called a leaf if
$k_{u}(\mathbf{t}) = 0$
. We denote by
$\mathcal{L}_0(\mathbf{t})$
the set of leaves of
$\mathbf{t}$
. A vertex
$u \in \mathbf{t}$
is called a protected node if
$C_u(\mathbf{t}) \neq \emptyset$
and
$C_u(\mathbf{t}) \bigcap \mathcal{L}_{0}(\mathbf{t}) = \emptyset$
, i.e. u is not a leaf and none of its children are leaves.
For a tree
$\mathbf{t}$
, we denote by
$\mathcal{Z}_{n}(\mathbf{t}) = \textrm{Card}(\{u \in \mathbf{t}, \vert u \vert = n \})$
the size of the nth generation of
$\mathbf{t}$
, and the height of
$\mathbf{t}$
is defined by
$H(\mathbf{t}) = \sup \{|u|,\, u \in \mathbf{t} \}$
and can be infinite. We define the width
$L(\mathbf{t})$
of
$\mathbf{t}$
as
$L(\mathbf{t}) = \sup_{k \geq 0} \mathcal{Z}_{k}(\mathbf{t})$
.
We denote by
$\mathbb{T}$
the set of trees, by
$\mathbb{T}_{0} = \{\mathbf{t} \in \mathbb{T};\,\textrm{Card}(\mathbf{t}) < +\infty\}$
the subset of finite trees, and by
$\mathbb{T}_{1} = \{\mathbf{t} \in \mathbb{T};\,\lim_{n \rightarrow + \infty}|M(\{u \in \mathbf{t};\, |u| = n\})| = + \infty\}$
the subset of trees with a unique infinite spine.
For
$h \in \mathbb{N}$
, the restriction function
$r_{h}$
from
$\mathbb{T}$
to
$\mathbb{T}$
is defined by
$r_{h}(\mathbf{t}) = \{u \in \mathbf{t},\, \vert u \vert \leq h \}$
. We endow the set
$\mathbb{T}$
with the ultrametric distance
\[d(\mathbf{t},\mathbf{t}') = 2^{- \sup \{h \in \mathbb{N}, r_{h}(\mathbf{t}) = r_{h}(\mathbf{t}')\}}. \]
A sequence
$(\mathbf{t}_n,\, n \in \mathbb{N})$
of trees converges to a tree
$\mathbf{t}$
with respect to the distance d if and only if, for every
$h \in \mathbb{N}$
,
$r_{h}(\mathbf{t}_{n}) = r_{h}(\mathbf{t})$
for n large enough.
Let
$(T_{n},\, n \in \mathbb{N})$
and T be
$\mathbb{T}$
-valued random variables. We denote by
$\textrm{dist}(T)$
the distribution of the random variable T, and write
$\lim_{n \rightarrow + \infty} \textrm{dist}(T_{n}) = \textrm{dist}(T)$
for the convergence in distribution of the sequence
$(T_{n},\, n \in \mathbb{N})$
to T.
If
$\mathbf{t},\mathbf{t}' \in \mathbb{T}$
and
$x \in \mathcal{L}_{0}(\mathbf{t})$
we denote by
$\mathbf{t} \circledast_x \mathbf{t}' = \{u \in \mathbf{t}\} \cup \{xv;\, v \in \mathbf{t}'\}$
the tree obtained by grafting the tree
$\mathbf{t}'$
on the leaf x of the tree
$\mathbf{t}$
. For every
$\mathbf{t} \in \mathbb{T}$
and every
$x \in \mathcal{L}_0(\mathbf{t})$
, we shall consider the set of trees obtained by grafting a tree on the leaf x of
$\mathbf{t}$
:
$\mathbb{T}(\mathbf{t},x) = \{\mathbf{t} \circledast_x \mathbf{t}';\, \mathbf{t}' \in \mathbb{T}\}$
.
For convergence in distribution in the set
$\mathbb{T}_{0} \cup \mathbb{T}_{1}$
, we recall the following key characterization in [Reference Abraham and Delmas3].
Lemma 1.
Let
$(T_{n})_{n \in \mathbb{N}}$
and T be random trees taking values in the set
$\mathbb{T}_{0} \cup \mathbb{T}_{1}$
. Then the sequence
$(T_{n})_{n \in \mathbb{N}}$
converges in distribution to T if and only if:
-
(i) for every finite tree
$\mathbf{t} \in \mathbb{T}_{0}$
,
$\lim_{n \rightarrow + \infty} \mathbb{P}(T_{n} = \mathbf{t}) = \mathbb{P}(T = \mathbf{t})$
;
-
(ii) for every finite tree
$\mathbf{t} \in \mathbb{T}_{0}$
and every leaf x of
$\mathbf{t}$
,
\[ \liminf_{n \rightarrow + \infty} \mathbb{P}(T_{n} \in \mathbb{T}(\mathbf{t},x)) \geq \mathbb{P}(T \in \mathbb{T}(\mathbf{t},x)). \]
2.2. Galton–Watson trees
Let
$p = (p(n),\, n \in \mathbb{N})$
be a probability distribution on
$\mathbb{N}$
. We assume that
\begin{equation}p(0)>0, \qquad p(0)+p(1)<1, \qquad \mu \;:\!=\; \sum_{n=0}^{+\infty} n p(n) < +\infty.\end{equation}
A
$\mathbb{T}$
-valued random variable
$\tau$
is a GW tree with offspring distribution p if the distribution of
$k_{\emptyset}(\tau)$
is p and it enjoys the branching property: for
$n \in \mathbb{N}^{*}$
, conditionally on
$\{k_{\emptyset}(\tau) = n \}$
, the subtrees
$(S_{1}(\tau),\ldots,S_{n}(\tau))$
are independent and distributed as the original tree
$\tau$
.
The GW tree and the offspring distribution are called critical (resp. subcritical, supercritical) if
$\mu =1$
(resp.
$\mu <1,\ \mu >1$
). In the critical and subcritical cases, we have that, almost surely (a.s.),
$\tau$
belongs to
$\mathbb{T}_{0}$
.
2.3. Kesten’s tree
Let p be an offspring distribution satisfying (1) with
$\mu \leq 1$
(i.e. the associated GW process is critical or subcritical). We denote by
$ p^{*}=(p^{*}(n)=np(n)/\mu,\, n\in \mathbb{N})$
the corresponding size-biased distribution.
We define an infinite random tree
$\tau ^{*}$
(the size-biased tree that we call Kesten’s tree in this paper) whose distribution is described in the following:
There exists a unique infinite sequence
$(v_{k},\, k \in \mathbb{N}^{*})$
of positive integers such that, for every
$h \in\mathbb{N}$
,
$v_{1}\cdots v_{h} \in \tau^{*}$
, with the convention that
$v_{1}\cdots v_{h}=\emptyset$
if
$h=0$
. The joint distribution of
$(v_{k},\, k \in \mathbb{N}^{*})$
and
$\tau^{*}$
is determined recursively as follows. For each
$h \in \mathbb{N}$
, conditionally given
$(v_{1},\ldots,v_{h})$
and
$\{u\in \tau^*;\, |u|\leq h\}$
the tree
$\tau^*$
up to level h, we have:
-
• The number of children
$(k_{u}(\tau^{*}),\, u \in \tau^{*},\, |u|=h)$
are independent and distributed according to p if
$u\neq v_{1}\cdots v_{h}$
and according to
$p^{*}$
if
$u = v_{1}\ldots v_{h}$
. -
• Given
$\{u\in \tau^*;\, |u|\leq h+1\}$
and
$(v_1, \ldots, v_h)$
, the integer
$v_{h+1}$
is uniformly distributed on the set of integers
$\{1,\ldots,k_{v_{1}\cdots v_{h}}(\tau^{*})\}$
.
Remark 1. Notice that, by construction, a.s.
$\tau^{*} \in \mathbb{T}_{1}$
. And, following Kesten [Reference Kesten6], the random tree
$\tau^{*}$
can be viewed as the tree
$\tau$
conditioned on nonextinction. Following [Reference Abraham and Delmas3], for
$\mathbf{t} \in \mathbb{T}_{0}$
and
$x \in \mathcal{L}_0(\mathbf{t})$
,
\begin{equation} \mathbb{P}(\tau^{*} \in \mathbb{T}(\mathbf{t},x)) = \frac{\mathbb{P}(\tau = \mathbf{t})}{\mu^{\vert x \vert}p(0)} = \mu^{- \vert x \vert} \mathbb{P}(\tau \in \mathbb{T}(\mathbf{t},x)). \end{equation}
In the particular case of a critical offspring distribution (
$\mu = 1$
) we get, for all
$\mathbf{t} \in \mathbb{T}_{0}$
and
$x \in \mathcal{L}_0(\mathbf{t})$
,
$\mathbb{P}(\tau^{*} \in \mathbb{T}(\mathbf{t},x)) = \mathbb{P}(\tau \in \mathbb{T}(\mathbf{t},x))$
.
3. Main result
Let A be an integer-valued function defined on
$\mathbb{T}$
which is finite on
$\mathbb{T}_{0}$
, and let
$n_{0} \in \mathbb{N} \cup \{+ \infty \}$
be given. We define, for all
$n \in \mathbb{N}^{*}$
, the subset of trees
$\mathbb{A}_{n} = \{\mathbf{t} \in \mathbb{T};\, A(\mathbf{t}) \in [n,n + n_{0})\}$
. Common values of
$n_{0}$
that will be considered are 1 and
$+ \infty$
.
The following theorem states a general result concerning the local convergence of critical and subcritical GW trees
$\tau$
conditioned on
$\mathbb{A}_{n}$
toward Kesten’s tree; its proof is in fact a straighforward adaptation of the proof of [Reference Abraham and Delmas2, Theorem 3.1].
We denote by
$\textrm{dist}(\tau \mid \tau \in \mathbb{A}_{n})$
the conditional law of
$\tau$
given
$\{\tau \in \mathbb{A}_{n}\}$
.
Theorem 1.
Assume that (1) holds,
$\mu \leq 1$
, and that
$\mathbb{P}(\tau\in\mathbb{A}_{n}) > 0$
for n large enough. Then, if, for all
$\mathbf{t} \in \mathbb{T}_{0}$
and
$x \in \mathcal{L}_{0}(\mathbf{t})$
,
\begin{equation} \liminf_{n \rightarrow + \infty} \dfrac{\mathbb{P}(\mathbf{t}\circledast_x\tau\in\mathbb{A}_{n})}{\mathbb{P}(\tau\in\mathbb{A}_{n})} \geq \dfrac{1}{\mu^{\vert x \vert}} \end{equation}
as
$n \rightarrow + \infty$
, we have
$\textrm{dist}(\tau \mid \tau \in \mathbb{A}_{n}) \rightarrow \textrm{dist}(\tau^{*})$
.
Proof. Since
$\mu \leq 1$
, we have, a.s.,
$\tau \in \mathbb{T}_{0}$
and
$\tau^{*} \in \mathbb{T}_{1}$
. So we can use Lemma 1 to prove this convergence.
We have, for every
$\mathbf{t} \in \mathbb{T}_{0}$
,
$x \in \mathcal{L}_0(\mathbf{t})$
, and
$\mathbf{t}' \in \mathbb{T}_{0}$
,
\[ \mathbb{P}(\tau = \mathbf{t} \circledast_x \mathbf{t}') = \dfrac{\mathbb{P}(\tau = \mathbf{t}) \mathbb{P}(\tau = \mathbf{t}')}{p(0)}. \]
Let
$\mathbf{t} \in \mathbb{T}_{0}$
and
$x \in \mathcal{L}_0(\mathbf{t})$
. For such n we get
\begin{align*} \mathbb{P}(\tau \in \mathbb{T}(\mathbf{t},x) \mid \tau \in \mathbb{A}_{n}) & = \dfrac{1}{\mathbb{P}(\tau \in \mathbb{A}_{n})} \sum_{\mathbf{t}' \in \mathbb{T}_{0}} \mathbb{P}(\tau = \mathbf{t} \circledast_x \mathbf{t}') \mathbf{1}_{\{\mathbf{t} \circledast_x \mathbf{t}' \in \mathbb{A}_{n}\}} \\ & = \dfrac{\mathbb{P}(\tau = \mathbf{t})}{p(0) \mathbb{P}(\tau \in \mathbb{A}_{n})} \sum_{\mathbf{t}' \in \mathbb{T}_{0}} \mathbb{P}(\tau = \mathbf{t}') \mathbf{1}_{\{A(\mathbf{t} \circledast_x \mathbf{t}') \in \mathbb{A}_{n}\}}. \end{align*}
So, we obtain that
\[ \mathbb{P}(\tau \in \mathbb{T}(\mathbf{t},x) \mid \tau \in \mathbb{A}_{n}) = \dfrac{\mathbb{P}(\tau = \mathbf{t})}{p(0)} \dfrac{\mathbb{P}(\mathbf{t} \circledast_x \tau \in \mathbb{A}_{n})}{\mathbb{P}(\tau \in \mathbb{A}_{n})}. \]
Using (2), we deduce that
\begin{equation*} \mathbb{P}(\tau \in \mathbb{T}(\mathbf{t},x) \mid \tau \in \mathbb{A}_{n}) = \mu^{\vert x \vert} \mathbb{P}(\tau^{*} \in \mathbb{T}(\mathbf{t},x)) \dfrac{\mathbb{P}(\mathbf{t} \circledast_x \tau \in \mathbb{A}_{n})}{\mathbb{P}(\tau \in \mathbb{A}_{n})}. \end{equation*}
Then, using (3), we deduce that
\begin{equation} \liminf_{n \rightarrow + \infty}\mathbb{P}(\tau \in \mathbb{T}(\mathbf{t},x) \mid \tau \in \mathbb{A}_{n}) \geq \mathbb{P}(\tau^{*} \in \mathbb{T}(\mathbf{t},x)). \end{equation}
Furthermore, for all
$\mathbf{t} \in \mathbb{T}_{0}$
and all
$n > A(\mathbf{t})$
,
\begin{equation*} \mathbb{P}(\tau = \mathbf{t},\,\tau \in \mathbb{A}_{n}) = \mathbb{P}(\tau = \mathbf{t},\mathbf{t} \in \mathbb{A}_{n}) \leq \mathbf{1}_{\{\mathbf{t} \in \mathbb{A}_{n}\}} = 0, \end{equation*}
and thus
$ \lim_{n \rightarrow + \infty} \mathbb{P}(\tau = \mathbf{t} \mid \tau \in \mathbb{A}_{n}) = \mathbb{P}(\tau^{*} = \mathbf{t}) = 0 $
. Finally, by Lemma 1, we have proved this result.
We have several remarks related to Theorem 1.
Remark 2. Despite this proof being very similar to that of [Reference Abraham and Delmas2, Theorem 3.1], it is quite clear that the condition therein is a particular case of our condition.
Remark 3. We apply Theorem 1 to the conditioning on the maximal outdegree. Let
$\tau$
be a critical Galton–Watson tree; we have, for every
$\mathbf{t} \in \mathbb{T}_{0}$
,
$x \in \mathcal{L}_0(\mathbf{t})$
,
\[ \mathbb{P}(M(\mathbf{t} \circledast_x \tau) = n) = \mathbb{P}(M(\tau) = n) \]
for n large enough. This yields a short and elementary proof of [Reference He4, Theorem 4.1]. In general, assume that p is critical; A satisfies the identity property that, for all
$\mathbf{t} \in \mathbb{T}_{0}$
and every leaf
$x \in \mathcal{L}_{0}(\mathbf{t})$
, there exists
$n_{0} \in \mathbb{N}^{*}$
such that, for all
$\mathbf{t}' \in \mathbb{T}_{0}$
satisfying
$A(\mathbf{t} \circledast_x \mathbf{t}') \geq n_{0}$
,
$A(\mathbf{t} \circledast_x \mathbf{t}') = A(\mathbf{t}')$
; and assume that
$\mathbb{P}(A(\tau) = n) > 0$
for any n. Then, by Theorem 1, as
$n \rightarrow + \infty$
,
$\textrm{dist}(\tau \mid A(\tau) = n) \rightarrow \textrm{dist}(\tau^{*})$
and, as
$n \rightarrow + \infty$
,
$\textrm{dist}(\tau \mid A(\tau) \geq n) \rightarrow \textrm{dist}(\tau^{*})$
.
Remark 4. Assume that p is critical. If A satisfies the monotonicity property that
$A(\mathbf{t} \circledast_x \mathbf{t}') \geq A(\mathbf{t}')$
for any
$\mathbf{t},\mathbf{t}' \in \mathbb{T}_{0}$
and
$x \in \mathcal{L}_{0}(\mathbf{t})$
, and if
$\mathbb{P}(A(\tau)\geq n) > 0$
for any integer n (consider
$n_{0} = + \infty$
), then, using Theorem 1, as
$n \rightarrow + \infty$
,
$\textrm{dist}(\tau \mid A(\tau) \geq n) \rightarrow \textrm{dist}(\tau^{*})$
, which provides another short proof of [Reference He5, Theorem 2.1].
Remark 5. As a conclusion, Theorem 1 serves to cover all the situations encountered in [Reference Abraham and Delmas3] (which are known as identity, additivity, and monotonicity), which allows us to give a simple and short proof of [Reference Abraham and Delmas3, Theorems 2.2.1 and 2.2.4].
As direct application, we can recover several specific conditionings in the critical case:
-
• Conditioning on extinction after large time [Reference Abraham and Delmas2, Reference Kesten6],
$(A = H)$
:
as
$n \rightarrow + \infty$
,
$\textrm{dist}(\tau \mid H(\tau) \geq n) \rightarrow \textrm{dist}(\tau^{*})$
.
-
• Conditioning on the total population size,
$(A = \textrm{Card})$
:
As
$n \rightarrow + \infty$
,
$\textrm{dist}(\tau \mid \textrm{Card}(\tau) \geq n) \rightarrow \textrm{dist}(\tau^{*})$
.
-
• Conditioning on the number of individuals having a given number of children:
Let
$\mathcal{A}$
be a nonempty subset of
$\mathbb{N}$
. For a tree
$\mathbf{t}$
, we denote by
$\mathbb{L}_{\mathcal{A}}(\mathbf{t})$
the total number of nodes in the tree
$\mathbf{t}$
with outdegree in
$\mathcal{A}$
. Assume that
$\sum_{k \in \mathcal{A}} p(k) > 0$
. Then, as
$n \rightarrow + \infty$
,
$\textrm{dist}(\tau \mid \mathbb{L}_{\mathcal{A}}(\tau) \geq n) \rightarrow \textrm{dist}(\tau^{*})$
.-
• Conditioning on the number of protected nodes [Reference Abraham, Bouaziz and Delmas1]:
Let
$A(\mathbf{t})$
be the number of protected nodes in the tree
$\mathbf{t}$
. Then, as
$n \rightarrow + \infty$
,
$\textrm{dist}(\tau \mid A(\tau) \geq n) \rightarrow \textrm{dist}(\tau^{*})$
.
-
Notice that most of the applications only work in the critical case.
One of our original motivations for this result was the local convergence under conditioning on large width, so now we apply Theorem 1 to this specific conditioning. Recall that the width
$L(\mathbf{t})$
of a tree
$\mathbf{t}$
is defined to be
$L(\mathbf{t}) = \sup_{k \geq 0} \mathcal{Z}_{k}(\mathbf{t})$
. Since
$p_{0} + p_{1} < 1$
, we have
$\mathbb{P}(L(\tau) \geq n) > 0$
for any n. Then Theorem 1 immediately gives the local convergence of critical GW trees to Kesten’s tree under the conditioning of large width.
Corollary 1.
Assume that p is critical. Then, as
$n \rightarrow + \infty$
,
$\textrm{dist}(\tau \mid L(\tau) \geq n) \rightarrow \textrm{dist}(\tau^{*})$
.
4. Conditioning on the largest generation, critical case
Theorem 2.
Let
$\tau$
be a critical GW tree with offspring distribution p satisfying (1) with finite support, and let
$\tau^{*}$
be a Kesten tree associated to p. Let
$\tau_{n}$
be a random tree distributed according to
$\tau$
conditionally on
$\{L(\tau) = n \}$
. Then, as
$n \rightarrow + \infty$
,
$\textrm{dist}(\tau_{n}) \rightarrow \textrm{dist}(\tau^{*})$
, where the limit is understood along the infinite subsequence
$\{n \in \mathbb{N}\colon \mathbb{P}(L(\tau) = n) > 0 \}$
.
Proof. We consider
$A(\mathbf{t}) = L(\mathbf{t})$
with
$n_{0} = 1$
, i.e.
$\mathbb{A}_{n} = \{ \mathbf{t} \in \mathbb{T};\, L(\mathbf{t}) = n \}$
. Since
$p(0) + p(1) < 1$
, the set
$\{n \in \mathbb{N}\colon \mathbb{P}( L(\tau) = n ) > 0 \}$
is infinite. Let
$\mathbf{t} \in \mathbb{T}_{0}$
,
$x \in \mathcal{L}_0(\mathbf{t})$
. We consider
$K = \sup \{n \in \mathbb{N}, p(n) > 0 \} < + \infty$
, the supremum of the support of p. We have, for all
$\vert x \vert \leq s \leq H(\mathbf{t})$
and all
$n \geq L(\mathbf{t}) + K^{H(\mathbf{t}) - \vert x \vert} + 1$
,
\[ \mathcal{Z}_{s}(\mathbf{t}) + \mathcal{Z}_{s - \vert x \vert}(\tau) \leq L(\mathbf{t}) + K^{s - \vert x \vert} < n. \]
We deduce that L satisfies the property identity, i.e.
$L(\mathbf{t} \ast_{x} \tau) = n \Leftrightarrow L(\tau) = n$
for n large enough. According to Theorem 1, we deduce the convergence and hence end the proof.
We can generalize these results concerning the width in the following way: let
$\mathcal{A}$
be a nonempty subset of
$\mathbb{N}$
such that
$\sum_{k \in \mathcal{A}} p(k) > 0$
. For a tree
$\mathbf{t}$
and s a nonnegative integer, we write as
$\mathcal{L}^{(s)}_{\mathcal{A}}(\mathbf{t}) = \{ u \in \mathbf{t};\,\vert u \vert = s \mbox{ and } k_{u}(\mathbf{t}) \in \mathcal{A}\}$
the set of individuals, in generation s, whose number of children belongs to
$\mathcal{A}$
, and
$\mathbb{L}^{(s)}_{\mathcal{A}}(\mathbf{t})$
as its cardinal. We consider
$\mathcal{S}_{\mathcal{A}}(\mathbf{t}) = \sup_{s \geq 0} \mathbb{L}^{(s)}_{\mathcal{A}}(\mathbf{t})$
.
In the case
$\mathcal{A} = \{0\}$
,
$\mathbb{L}^{(s)}_{\mathcal{A}}(\mathbf{t})$
represents the number of leaves in generation s of
$\mathbf{t}$
, and
$\mathcal{S}_{\mathcal{A}}(\mathbf{t})$
the maximum number of leaves in the same generation. We can also have
$ \mathbb{L}^{(s)}_{\mathcal{A}}(\mathbf{t}) = \mathcal{Z}_{s}(\mathbf{t})$
, and so
$\mathcal{S}_{\mathcal{A}}(\mathbf{t}) = L(\mathbf{t})$
the largest generation by taking
$\mathcal{A} = \mathbb{N}$
.
Since
$p(0) + p(1) < 1$
and
$\sum_{k \in \mathcal{A}} p(k) > 0$
, the set
$\{n \in \mathbb{N}\colon \mathbb{P}(\mathcal{S}_{\mathcal{A}}(\tau) = n ) > 0 \}$
is infinite.
Since, for all
$\mathbf{t} \in \mathbb{T}_{0}$
,
$x \in \mathcal{L}_0(\mathbf{t})$
, and all
$\vert x \vert \leq s \leq H(\mathbf{t})$
,
\[ \mathbb{L}^{(s)}_{\mathcal{A}}(\mathbf{t}) + \mathbb{L}^{(s - \vert x \vert)}_{\mathcal{A}}(\tau) \leq L(\mathbf{t}) + K^{s - \vert x \vert} < n \]
for n large enough, the same work as in the previous proof allows us to prove the following theorem.
Theorem 3.
Let
$\tau$
be a critical GW tree with offspring distribution p satisfying (1) with finite support and such that
$\sum_{k \in \mathcal{A}} p(k) > 0$
. Let
$\tau^{*}$
be a Kesten tree associated to p. Then, as
$n \rightarrow + \infty$
,
$\textrm{dist}(\tau \mid \mathcal{S}_{\mathcal{A}}(\tau) = n ) \rightarrow \textrm{dist}(\tau^{*})$
, where the limit is understood along the infinite subsequence
$\{n \in \mathbb{N}\colon \mathbb{P}(\mathcal{S}_{\mathcal{A}}(\tau) = n ) > 0 \}$
and
$\textrm{dist}(\tau \mid \mathcal{S}_{\mathcal{A}}(\tau) \geq n ) \rightarrow \textrm{dist}(\tau^{*}) $
.
Note that this type of conditioning has never been treated before.
Acknowledgements
Sincere thanks to the anonymous referees for their comments and suggestions, which considerably improved the presentation of this paper.
Funding information
There are no funding bodies to thank relating to the creation of this article.
Competing interests
There were no competing interests to declare which arose during the preparation or publication process of this article.
