Local convergence of critical Galton–Watson trees

Abstract

We study the local convergence of critical Galton–Watson trees under various conditionings. We give a sufficient condition, which serves to cover all previous known results, for the convergence in distribution of a conditioned Galton–Watson tree to Kesten’s tree. We also propose a new proof to give the limit in distribution of a critical Galton–Watson tree, with finite support, conditioned on having a large width.

1. Introduction

In [6], 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 [2], 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 [1] 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 [5]; therefore, using [5, 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 [2]. Considering the conditioning event $\{L(\tau) = n\}$ was partially solved in [5].

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, [5] 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 [2].

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 [7] 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 [3].

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:

1. (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})$ ;

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

(1) \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 [6], the random tree $\tau^{*}$ can be viewed as the tree $\tau$ conditioned on nonextinction. Following [3], for $\mathbf{t} \in \mathbb{T}_{0}$ and $x \in \mathcal{L}_0(\mathbf{t})$ ,

(2) \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 [2, 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})$ ,

(3) \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

(4) \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 [2, 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 [4, 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 [5, Theorem 2.1].

Remark 5. As a conclusion, Theorem 1 serves to cover all the situations encountered in [3] (which are known as identity, additivity, and monotonicity), which allows us to give a simple and short proof of [3, 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 [2, 6], $(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 [1]:

    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.