Conditioning Galton–Watson Trees on Large Maximal Outdegree

Abstract

We propose a new way to condition random trees, that is, conditioning random trees to have large maximal outdegree. Under this conditioning, we show that conditioned critical Galton–Watson trees converge locally to size-biased trees with a unique infinite spine. For the subcritical case, we obtain the local convergence to size-biased trees with a unique infinite node. We also study the tail of the maximal outdegree of subcritical Galton–Watson trees, which is essential for the proof of the local convergence.

1 Introduction

In the seminal paper [9], Kesten studied the local convergence of critical or subcritical Galton–Watson trees (GW trees) conditioned to have large height. The local limits are certain size-biased trees with a unique infinite spine, which we call Kesten’s trees throughout this paper. Since then, several other conditionings have also been considered: large total progeny and large number of leaves. In particular, Jonnsson and Stefánsson [8] noticed that some subcritical GW trees conditioned to have large total progeny do not converge locally to Kesten’s trees. They proved that instead those large conditioned trees converge locally to certain size-biased trees with a unique infinite node, which we call condensation trees. Janson [7] completed this result by proving that any subcritical GW tree conditioned to have large total progeny converges locally to a condensation tree, if not to a Kesten’s tree. Recently, Abraham and Delmas [1, 2] provided a convenient framework for the local convergence of conditioned GW trees, and then they studied, in particular, the local convergence of GW trees under the conditioning of large number of individuals with outdegree in a given set, which generalizes the conditionings of large total progeny and large number of leaves. Specifically, in [1] they provided a framework for the local convergence of finite random trees to Kesten’s trees, and in [2], they provided a framework for the local convergence of finite random trees to condensation trees.

In this paper, we consider a new conditioning of random trees, that is, we condition GW trees to have large maximal outdegree and use the convenient framework in [1, 2] to study the local convergence of large conditioned trees. The maximal outdegree of a discrete tree is the maximum of the numbers of offsprings of all nodes in the tree, see (1) for the precise definition. We say that a probability distribution $p=(p_0,p_1,p_2,\ldots )$ on nonnegative integers is $bounded$ if the set $\{n; p_n > 0\}$ is bounded, and $unbounded$ otherwise. For any critical and unbounded distribution p, we show in Theorem 4.1 the local convergence of the GW tree with the offspring distribution p conditioned to have large maximal outdegree, to the Kesten’s tree with the offspring distribution p. For any subcritical and unbounded distribution p, we show in Theorem 4.2 the local convergence of the conditioned GW tree with the offspring distribution p, to the condensation tree with the offspring distribution p. Note that our results are complete: for a bounded distribution p, the corresponding GW tree cannot have very large maximal outdegree; for a supercritical distribution p, the situation is essentially trivial, by the well-known decomposition of supercritical GW trees (see e.g. Theorem 3 on page 52 in [4]). We also study in Proposition 3.2 the tail of the maximal outdegree of subcritical GW trees and prove that the tail of the offspring distribution p and the tail of the maximal outdegree of the corresponding GW tree are asymptotically equivalent up to a certain factor. This result is essential for the proof of the local convergence in the subcritical case.

This paper is organized as follows. In Sect. 2, we recall several notations of trees, the local convergence of random trees, and a characterization of condensation trees. In Sect. 3, we study the tail of the maximal outdegree of subcritical GW trees. Finally Sect. 4 is devoted to our main results, Theorem 4.1 for the critical case and Theorem 4.2 for the subcritical case.

2 Preliminaries

This section is extracted from [1, 2]. For more details and proofs, refer to [1, 2]. We denote by ${\mathbb N}= \{1,2,\ldots \}$ the set of positive integers and by ${\mathbb Z}_+ = \{0,1,2,\ldots \}$ the set of nonnegative integers.

2.1 Notations of Discrete Trees

Denote by

$$\begin{aligned} \mathcal {U}=\bigcup _{n\ge 0}{\mathbb N}^n \end{aligned}$$

the set of finite sequences of positive integers with the convention ${\mathbb N}^0=\{\emptyset \}$. 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 the set:

$$\begin{aligned} A_u = \{v \in \mathcal {U}; \text{ there } \text{ exists } w \in \mathcal {U}, w \ne \emptyset , \text{ such } \text{ that } u = vw\}. \end{aligned}$$

A tree ${\mathbf {t}}$ is a subset of $\mathcal {U}$ that satisfies:

• $\emptyset \in {\mathbf {t}}$.

• If $u\in {\mathbf {t}}$, then $A_u\subset {\mathbf {t}}$.

• For every $u\in {\mathbf {t}}$, there exists $k_u({\mathbf {t}}) \in {\mathbb Z}_+ \cup \{\infty \}$ such that, for every positive integer $i, ui \in {\mathbf {t}}$ if and only if $1 \le i \le k_u({\mathbf {t}})$.

The node $\emptyset$ is called the root of ${\mathbf {t}}$. The integer $k_u({\mathbf {t}})$ represents the number of offsprings of the node u in the tree ${\mathbf {t}}$, and we call it the outdegree of the node u in the tree ${\mathbf {t}}$. We say the node $u \in {\mathbf {t}}$ is a leaf if $k_u({\mathbf {t}}) = 0$ and it is infinite if $k_u({\mathbf {t}}) = \infty$. The set of leaves of the tree ${\mathbf {t}}$ is denoted by $\mathcal {L}({\mathbf {t}}) = \{u \in {\mathbf {t}}; k_u({\mathbf {t}}) = 0\}$. The maximal outdegree $M({\mathbf {t}})$ of a tree ${\mathbf {t}}$ is defined by

$$\begin{aligned} M({\mathbf {t}})=\sup \{k_u({\mathbf {t}});u\in {\mathbf {t}}\}. \end{aligned}$$

(1)

For $u \in {\mathbf {t}}$, we denote the sub-tree of ${\mathbf {t}}$ “above” u by $\mathcal {S}_u(\mathbf {t})$. For $u \in {\mathbf {t}}\setminus \mathcal {L}({\mathbf {t}})$, denote the forest “above” u by $\mathcal {F}_u(\mathbf {t})$. Note that $u\in \mathcal {S}_u(\mathbf {t})$ and $u\notin \mathcal {F}_u(\mathbf {t})$. For $u \in {\mathbf {t}}\setminus \{\emptyset \}$, we also define the sub-tree $\mathcal {S}^u(\mathbf {t})$ of ${\mathbf {t}}$ “below” u as $\mathcal {S}^u(\mathbf {t}) = \{v \in \mathbf {t}, u \notin A_v\}$. We denote by ${\mathbb {T}}_\infty$ the set of trees, by ${\mathbb {T}}$ the subset of trees with no infinite node, by ${\mathbb {T}}_0$ the subset of finite trees, by ${\mathbb {T}}_1$ the subset of trees with a unique infinite spine but no infinite node, and by ${\mathbb {T}}_2$ the subset of trees with a unique infinite node but no infinite spine. For precise definitions of all these notations in this paragraph, refer to [1, 2].

2.2 Local Convergence of Random Trees

For the general framework of local convergence of discrete trees, refer to [1, 2].

If $v =(v_1,\ldots , v_n) \in \mathcal {U}$ with $n > 0$, and $k \in {\mathbb Z}_+$, we define the shift of v by k as $\theta (v, k) = (v_1+k, v_2,\ldots , v_n)$. If ${\mathbf {t}}\in {\mathbb {T}}_0$, $x \in {\mathbf {t}}$, and ${\mathbf {t}}' \in {\mathbb {T}}_\infty$, we denote by

$$\begin{aligned} {\mathbf {t}}\circledast (x,{\mathbf {t}}') = {\mathbf {t}}\cup \{x\theta (v, k_x({\mathbf {t}})); v\in {\mathbf {t}}'\backslash \{\emptyset \}\} \end{aligned}$$

(2)

the tree obtained by grafting the tree ${\mathbf {t}}'$ at x on “the right” of the tree ${\mathbf {t}}$, with the convention that ${\mathbf {t}}\circledast (x,{\mathbf {t}}') = {\mathbf {t}}$ if ${\mathbf {t}}' = \{\emptyset \}$ is the tree reduced to its root. For ${\mathbf {t}}\in {\mathbb {T}}_0$, $x\in {\mathbf {t}}$, and $k \in {\mathbb Z}_+$, we consider

$$\begin{aligned} {\mathbb {T}}_+({\mathbf {t}}, x, k) = \{{\mathbf {s}}\in {\mathbb {T}}_\infty ;\, {\mathbf {s}}={\mathbf {t}}\circledast (x,{\mathbf {t}}'),{\mathbf {t}}' \in {\mathbb {T}}_\infty , k_x({\mathbf {s}}) \ge k\}, \end{aligned}$$

(3)

the set of trees obtained by grafting a tree at x on “the right” of ${\mathbf {t}}$, such that x has at least k offsprings. We recall Lemma 2.2 in [2], which is a very useful characterization of convergence in distribution in ${\mathbb {T}}_0\cup {\mathbb {T}}_2$.

Lemma 2.1

Let $(T_n, n \in {\mathbb N})$ and T be ${\mathbb {T}}_\infty$-valued random variables which belong a.s. to ${\mathbb {T}}_0\cup {\mathbb {T}}_2$. The sequence $(T_n, n \in \mathbb {N})$ converges in distribution to T if and only if for every $\mathbf {t} \in {\mathbb {T}}_0$ and every $x \in {\mathbf {t}}$ and $k\in {\mathbb Z}_+$, we have

$$\begin{aligned} \lim _{n\rightarrow \infty }{\mathbb P}(T_n \in {\mathbb {T}}_+(\mathbf {t},x,k)) = {\mathbb P}(T \in {\mathbb {T}}_+(\mathbf {t},x,k))\quad and \quad \lim _{n\rightarrow \infty }{\mathbb P}(T_n =\mathbf {t}) = {\mathbb P}(T =\mathbf {t}). \end{aligned}$$

2.3 GW Trees

Let $p=(p_0,p_1,p_2,\ldots )$ be a probability distribution on the set of the nonnegative integers. We denote by $\mu _p$ the expectation of p and assume that $0<\mu _p<\infty$.

A ${\mathbb {T}}$-valued random variable $\tau$ is a Galton–Watson (GW) tree with the offspring distribution p if the distribution of $k_\emptyset (\tau )$ is p and for $n\in {\mathbb N}$, conditionally on $\{k_\emptyset (\tau )=n\}$, the sub-trees $(\mathcal {S}_1(\tau ), \mathcal {S}_2(\tau ),\ldots , \mathcal {S}_n(\tau ))$ are independent and distributed as the original tree $\tau$. In particular, the restriction of the distribution of $\tau$ on the set ${\mathbb {T}}_0$ is given by:

$$\begin{aligned} \forall {\mathbf {t}}\in {\mathbb {T}}_0,\quad {\mathbb P}(\tau = {\mathbf {t}}) =\prod _{u\in {\mathbf {t}}} p_{k_u({\mathbf {t}})}. \end{aligned}$$

(4)

The GW tree is called critical (resp. subcritical, supercritical) if $\mu _p = 1$ (resp. $\mu _p < 1$, $\mu _p >1$). We exclude the trivial case $p_1=1$. Then in the critical and subcritical case, a.s. the GW tree $\tau$ belongs to ${\mathbb {T}}_0$.

Let ${\mathbb P}_k$ be the distribution of the forest $\tau ^{(k)} = (\tau _1,\ldots ,\tau _k)$ of k i.i.d. GW trees with the offspring distribution p. Recall from (1) the definition of the maximal outdegree. We set

$$\begin{aligned} M(\tau ^{(k)})=\sup _{1\le j \le k} M(\tau _j). \end{aligned}$$

(5)

When there is no confusion, we shall write $\tau$ for $\tau ^{(k)}$, and $M(\tau )$ for $M(\tau ^{(k)})$.

2.4 Kesten’s Trees and Condensation Trees

We recall from Section 1 in [2] the following unified definition of Kesten’s trees in the critical case and condensation trees in the subcritical case, which first appeared in Section 5 of [7]. Let p be a critical or subcritical offspring distribution. Let $\tau ^*(p)$ denote the random tree which is defined by:

• (i) There are two types of nodes: normal and special.

• (ii) The root is special.

• (iii) Normal nodes have the offspring distribution p.

• (iv) Special nodes have the biased offspring distribution $p'$ on ${\mathbb Z}_+\cup \{\infty \}$ defined by:

  $$\begin{aligned} p'_k = {\left\{ \begin{array}{ll} kp_k &{} \text {if } k \in {\mathbb Z}_+,\\ 1-\mu _p &{} \text {if } k = \infty . \end{array}\right. } \end{aligned}$$

• (v) The offsprings of all the nodes are independent of each others.

• (vi) All the offsprings of a normal node are normal.

• (vii) When a special node gets a finite number of offsprings, one of them is selected uniformly at random and is special while the others are normal.

• (viii) When a special node gets an infinite number of offsprings, all of them are normal.

Notice that:

• If p is critical, then a.s. $\tau ^*(p)$ has exactly one infinite spine and all its nodes have finite outdegrees. We call $\tau ^*(p)$ a Kesten’s tree.

• If p is subcritical, then a.s. $\tau ^*(p)$ has exactly one node of infinite outdegree and no infinite spine. We call $\tau ^*(p)$ a condensation tree.

For ${\mathbf {t}}\in {\mathbb {T}}_0$, $x \in {\mathbf {t}}$, we set:

$$\begin{aligned} D(\mathbf {t}, x) =\frac{\mathbb {P}(\tau = \mathcal {S}^x(\mathbf {t}))}{p_0}\mathbb {P}_{k_x(\mathbf {t})}(\tau = \mathcal {F}_x(\mathbf {t})). \end{aligned}$$

For $z\in {\mathbb R}$, we set $z_+ = \max (z, 0)$. Let X be a random variable with the distribution p. By (4) and the definition of condensation trees given above, one can prove the following characterization of condensation trees, which is Lemma 3.1 in [2]:

Lemma 2.2

Suppose that p is subcritical. Then the distribution of $\tau ^*(p)$ is also characterized by: a.s. $\tau ^*(p)\in {\mathbb {T}}_2$ and for ${\mathbf {t}}\in {\mathbb {T}}_0,\ x \in {\mathbf {t}},\ k \in {\mathbb Z}_+$,

$$\begin{aligned} {\mathbb P}(\tau ^*(p) \in {\mathbb {T}}_+({\mathbf {t}},x,k)) = D({\mathbf {t}}, x)\left( 1-\mu _p+{\mathbb E}\left[ (X - k_x({\mathbf {t}}))_+\mathbf {1}_{\{X\ge k\}}\right] \right) . \end{aligned}$$

3 The Tail of the Maximal Outdegree

We begin with a simple result on the probability distribution of the maximal outdegree. Write $q=(q_0,q_1,q_2,\ldots )$ for the probability distribution of $M(\tau )$. Recall from (1) that $M(\tau )$ is the maximal outdegree of the GW tree $\tau$.

Lemma 3.1

If $p_0>0$, then $q_n>0$ if and only if $p_n>0$ for any nonnegative integer n.

Proof

First of all if $p_n=0$, of course $q_n=0$. If $p_0>0$, then $q_0=\mathbb {P}\left[ M(\tau ) =0 \right] =p_0>0$. If $p_0>0$ and $p_n>0$ for $n\ge 1$, then $\mathbb {P}\left[ M(\tau ) =n \right] \ge p_n (p_0)^n>0$, where $p_n (p_0)^n$ is the probability of the tree such that the root has n offsprings and these n offsprings are all leaves. $\square$

Use F(n) to denote the cumulative distribution function of p, and $\bar{F}(n)=1-F(n)$ the tail function. Similarly use H(n) to denote the cumulative distribution function of $M(\tau )$, and $\bar{H}(n)=1-H(n)$ the tail function. The following is the main result of this section.

Proposition 3.2

Suppose that the offspring distribution $p=(p_0,p_1,p_2,\ldots )$ is subcritical and unbounded, then $\lim _{n\rightarrow \infty }H^n(n)=1$ and

$$\begin{aligned} \lim _{n\rightarrow \infty }\frac{\bar{F}(n)}{\bar{H}(n)}=\lim _{n\rightarrow \infty }\frac{p_n}{q_n}=1-\mu _p, \end{aligned}$$

where the second limit is understood along the infinite subsequence $\{n; p_n > 0\}$.

Proof

By considering the outdegree of the root, we get

$$\begin{aligned} H(n)=\sum _{m\le n}p_m H^m(n). \end{aligned}$$

(6)

By comparing (6) at the values n and $n-1$, we see

$$\begin{aligned} q_n= & {} \sum _{1\le m\le n-1} p_m [H^m(n)-H^m(n-1)] +p_n H^n(n)\\= & {} \sum _{1\le m\le n-1} q_n p_m \sum _{1\le i\le m}[H^{m-i}(n)H^{i-1}(n-1)] +p_n H^n(n), \end{aligned}$$

or equivalently,

$$\begin{aligned} q_n\left( 1-\sum _{1\le m\le n-1} p_m \sum _{1\le i\le m}[H^{m-i}(n)H^{i-1}(n-1)]\right) =p_n H^n(n). \end{aligned}$$

(7)

From (7), we get the obvious inequality $q_n(1-\mu _p)\le p_n$. So $M(\tau )$ has finite expectation, then by a well-known result $\bar{H}(n) = o\, (1/n)$, and consequently

$$\begin{aligned} \lim _{n\rightarrow \infty }H^n(n)=1. \end{aligned}$$

(8)

From the obvious fact that for fixed m,

$$\begin{aligned} \sum _{1\le i\le m}H^{m-i}(n)H^{i-1}(n-1)\le m \quad \text {and} \quad \lim _{n\rightarrow \infty }\sum _{1\le i\le m}H^{m-i}(n)H^{i-1}(n-1)=m, \end{aligned}$$

we get

$$\begin{aligned} \lim _{n\rightarrow \infty }\left( 1-\sum _{1\le m\le n-1} p_m \sum _{1\le i\le m}[H^{m-i}(n)H^{i-1}(n-1)]\right) =1-\mu _p. \end{aligned}$$

(9)

For a subcritical offspring distribution p, clearly $p_0>0$, so $q_n>0$ if and only if $p_n>0$ by Lemma 3.1. By combining (7), (8), and (9), we get

$$\begin{aligned} \lim _{n\rightarrow \infty }\frac{\bar{F}(n)}{\bar{H}(n)}=\lim _{n\rightarrow \infty }\frac{p_n}{q_n}=1-\mu _p, \end{aligned}$$

where the second limit is understood along the infinite subsequence $\{n; p_n > 0\}$, and the first equality is automatic from the second one. $\square$

We end this section with two remarks related to Proposition 3.2.

Remark 3.3

Bertoin [5, 6] studied the scaling limit and tail of the maximal outdegree of critical GW trees with regularly varying offspring tails. In Section 1 of [5] (in the first paragraph on page 577) the maximal outdegree of subcritical GW trees was mentioned, and combined with a classical result due to Gnedenko (see e.g. Proposition 1.11 in [10]), it is easy to see that [5] contains the tail part $\bar{F}(n)/\bar{H}(n)$ of our Proposition 3.2 in the case of regularly varying offspring tails. Our Proposition 3.2 deals with all subcritical and unbounded offspring distributions and gives both the probability part $p_n/q_n$ and the tail part. Note that it is impossible to achieve this generality by using extreme value theory, since some offspring distributions do not belong to the domain of attraction of any extreme value distribution, e.g. the geometric offspring distribution (see e.g. [3]).

Remark 3.4

It is interesting to compare our Proposition 3.2 with Corollary 1 in [5] and Lemma 1 in [6]. In the critical and infinite variance case considered in Corollary 1 of [5], $\bar{H}(n)/\bar{F}(n)\rightarrow \infty$ as $n\rightarrow \infty$, and $M(\tau )$ has infinite expectation. In the critical and finite variance case considered in Lemma 1 of [6], $\bar{H}(n)/\bar{F}(n)\rightarrow \infty$ as $n\rightarrow \infty$ again, and $M(\tau )$ may have finite or infinite expectation, depending on $\bar{F}(n)$. In the subcritical case, our Proposition 3.2 shows that the two tails are asymptotically equivalent up to a certain factor, and $M(\tau )$ has finite expectation.

4 The Main Results

We first deal with the critical case, which is much simpler than the subcritical case. Recall from (2) the definition of $\mathbf {t} \circledast (x,\mathbf {t}')$. Note that for a tree ${\mathbf {t}}\circledast (x,{\mathbf {t}}')$ with ${\mathbf {t}}\in {\mathbb {T}}_0$, $x \in \mathcal {L}({\mathbf {t}})$, and ${\mathbf {t}}' \in {\mathbb {T}}_0$, when $n > M({\mathbf {t}})$, we get $M({\mathbf {t}}\circledast (x,{\mathbf {t}}')) = n$ if and only if $M({\mathbf {t}}') = n$. Then an immediate adaptation of the proof of Theorem 3.1 in [1] (corresponding to the degenerate case $D = 0$ of (3.1) in [1]) combined with our Lemma 3.1 gives the following theorem. Note that for an unbounded and critical or subcritical offspring distribution p, clearly $p_0>0$, so $q_n>0$ if and only if $p_n>0$ by Lemma 3.1.

Theorem 4.1

Suppose that the offspring distribution $p=(p_0,p_1,p_2,\ldots )$ is critical and unbounded. Then for the GW tree $\tau$ with the offspring distribution p, we have as $n\rightarrow \infty$,

$$\begin{aligned} \text{ dist } (\tau |M(\tau )=n)\rightarrow \text {dist }(\tau ^*(p)), \end{aligned}$$

where the limit is understood along the infinite subsequence $\{n; p_n > 0\}$, and as $n\rightarrow \infty$,

$$\begin{aligned} \text {dist }(\tau |M(\tau )>n)\rightarrow \text {dist }(\tau ^*(p)). \end{aligned}$$

The subcritical case is more involved.

Theorem 4.2

Suppose that the offspring distribution $p=(p_0,p_1,p_2,\ldots )$ is subcritical and unbounded. Then for the GW tree $\tau$ with the offspring distribution p, we have as $n\rightarrow \infty$,

$$\begin{aligned} \text {dist }(\tau |M(\tau )=n)\rightarrow \text {dist }(\tau ^*(p)), \end{aligned}$$

where the limit is understood along the infinite subsequence $\{n; p_n > 0\}$, and as $n\rightarrow \infty$,

$$\begin{aligned} \text {dist }(\tau |M(\tau )>n)\rightarrow \text {dist }(\tau ^*(p)). \end{aligned}$$

Proof

We can write ${\mathbb P}(\cdot |M(\tau )>n)$ as a linear combination of $\{{\mathbb P}(\cdot |M(\tau )=m);m>n\}$, so we only need to prove the first convergence. Since p is subcritical, we have a.s. $\tau \in {\mathbb {T}}_0$ and $\tau ^*(p)\in {\mathbb {T}}_2$. So we will use Lemma 2.1 to prove the convergence.

Recall from (2), (3), and (5), the definitions of ${\mathbf {t}}\circledast (x,{\mathbf {t}}')$, ${\mathbb {T}}_+(\mathbf {t},x,k)$, and the maximal outdegree of a forest. For a tree ${\mathbf {s}}\in {\mathbb {T}}_+({\mathbf {t}},x,k)$, when $n>M({\mathbf {t}})$ it is clear that $M(\mathbf {s})=n$ if and only if $k_x(\mathbf {s})=n$ and the attached forest has the maximal outdegree at most n, or $k_x(\mathbf {s})<n$ and the attached forest has the maximal outdegree exactly n. Then similar to the proof of Lemma 2.2, for ${\mathbf {t}}\in {\mathbb {T}}_0$, $x\in {\mathbf {t}}$, $k\in {\mathbb Z}_+$, $n>M({\mathbf {t}})$, and $\ell = k_x({\mathbf {t}})$, we have

$$\begin{aligned}&{\mathbb P}(\tau \in {\mathbb {T}}_+({\mathbf {t}},x,k),M(\tau )=n) \\&\quad =\sum _{{\mathbf {s}}\in {\mathbb {T}}_+({\mathbf {t}},x,k)} {\mathbb P}(\tau ={\mathbf {s}})\mathbf {1}_{\{M({\mathbf {s}})=n\}}\\&\quad = D({\mathbf {t}},x)\left( p_n{\mathbb P}_{n-\ell }(M(\tau )\le n)+\sum _{j\ge \max (\ell +1,k)}^{n-1} p_j{\mathbb P}_{j-\ell }(M(\tau )=n)\right) . \end{aligned}$$

(10)

Recall the notations $q_n$ and H(n) introduced in Sect. 3. By Proposition 3.2, we have

$$\begin{aligned} \lim _{n\rightarrow \infty } {\mathbb P}_{n-\ell }(M(\tau )\le n)=\lim _{n\rightarrow \infty }H^{n-\ell }(n)=1, \end{aligned}$$

and

$$\begin{aligned} \lim _{n\rightarrow \infty }\frac{p_n}{{\mathbb P}(M(\tau )= n)}=\lim _{n\rightarrow \infty }\frac{p_n}{q_n}=1-\mu _p. \end{aligned}$$

So

$$\begin{aligned} \lim _{n\rightarrow \infty }\frac{p_n{\mathbb P}_{n-\ell }(M(\tau )\le n)}{{\mathbb P}(M(\tau )= n)}=1-\mu _p. \end{aligned}$$

(11)

Since

$$\begin{aligned} {\mathbb P}_m(M(\tau )=n)= & {} {\mathbb P}_m(M(\tau )\le n)-{\mathbb P}_m(M(\tau )\le n-1)\\= & {} H^m(n)-H^m(n-1) \\= & {} q_n\sum _{1\le i\le m}[H^{m-i}(n)H^{i-1}(n-1)],\\\end{aligned}$$

we see

$$\begin{aligned} \frac{{\mathbb P}_m(M(\tau )=n)}{{\mathbb P}(M(\tau )= n)}\le m \quad \text{ and }\quad \lim _{n\rightarrow \infty }\frac{{\mathbb P}_m(M(\tau )=n)}{{\mathbb P}(M(\tau )= n)}=m. \end{aligned}$$

So

$$\begin{aligned} \lim _{n\rightarrow \infty }\frac{\sum _{j\ge \max (\ell +1,k)}^{n-1} p_j{\mathbb P}_{j-\ell }(M(\tau )=n)}{{\mathbb P}(M(\tau )= n)}=\sum _{j\ge \max (\ell +1,k)}(j-\ell ) p_j. \end{aligned}$$

(12)

Combining (10), (11), and (12) together, we have as $n\rightarrow \infty$,

$$\begin{aligned} {\mathbb P}(\tau \in {\mathbb {T}}_+(\mathbf {t},x,k)|M(\tau )=n)= & {} \frac{{\mathbb P}({\mathbb {T}}_+(\mathbf {t},x,k),M(\tau )=n)}{{\mathbb P}(M(\tau )=n)} \\\rightarrow & {} D({\mathbf {t}},x) \left( 1-\mu _p+\sum _{j\ge \max (\ell +1,k)}(j-\ell ) p_j\right) \\= & {} {\mathbb P}(\tau ^*(p) \in {\mathbb {T}}_+(\mathbf {t},x,k)), \\\end{aligned}$$

where we used Lemma 2.2 for the last equality. Finally for any ${\mathbf {t}}\in {\mathbb {T}}_0$, when $n > M({\mathbf {t}})$, clearly

$$\begin{aligned} {\mathbb P}(\tau = {\mathbf {t}}\big | M(\tau )=n) = 0= {\mathbb P}(\tau ^*(p) = {\mathbf {t}}). \end{aligned}$$

By Lemma 2.1, we have proved the local convergence. $\square$