\documentclass[a4paper,12pt]{article}
\usepackage{amssymb}
\usepackage{latexsym}
\topmargin=-0.5cm
\oddsidemargin=0cm
\evensidemargin=0cm
\textwidth=16.5cm
\textheight=22cm
\pagestyle{plain}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\newtheorem{prop}{Proposition}
\newtheorem{thm}{Theorem}
\newtheorem{rem}{Remark}
\newtheorem{cor}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\title{On the number of vertices with a given degree \\
in a Galton-Watson tree}
\author{Nariyuki MINAMI \\
Institute of Mathematics, Unversity of Tsukuba, \\
Tsukuba-shi, Ibaraki 305-8571, Japan. \\
e-mail: minami@math.tsukuba.ac.jp}
\date{}
\maketitle
\begin{abstract}
Let $Y_k(\omega)$ ($k\geq0$) be the number of vertices of a
Galton-Watson tree $\omega$ having $k$ children, so that
$Z(\omega):=\sum_{k\geq0}Y_k(\omega)$ is the total progeny of
$\omega$. In this paper, we shall prove various statistical properties
of $Z$ and $Y_k$. We first show, under a mild condition, an asymptotic
expansion of $P(Z=n)$ as $n\to\infty$, improving the theorem
of Otter (1949). Next, we show that
${\cal Y}_k(\omega):=\sum_{j=0}^kY_j(\omega)$ is the total progeny of a
new Galton-Watson tree which is hidden in the original tree $\omega$.
We then proceed to study the joint probability distribution of
$Z$ and $\{Y_k\}_k$, and show that as $n\to\infty$,
$\{Y_k/n\}_k$ is asymptotically Gaussian under the conditional
distribution $P(\cdot\vert Z=n)$.
\end{abstract}
%\keywords{Galton-Watson trees; total progeny; Lagrange inversion;
%central limit theorem}
%\ams{60J80}{60C05;05A15;60F05}
\section{Introduction}
Let $\Pi=\{p_n\}_{n=0}^{\infty}$ be a probability distribution on non-negative
integers and let $\{X_n\}_{n=0}^{\infty}$ ($X_0=0$) be the Galton-Watson
process (or the discrete time branching process) with the offspring
distribution $\Pi$. Various long time behaviors of the integer valued
Markov chain $\{X_n\}$ form the main subject matter of classical treatises
of Galton-Watson processes (e.g. \cite{Ha}, \cite{A-N},
\cite{J}, \cite{S}). There, the random
tree structure which is obvious in the intuitive description of the process
is rather implicit, or even entirely omitted from the exposition.
In this paper, we are interested in the typical shape of the random tree,
which we shall call the Galton-Watson tree, obtained as the \lq\lq trajectory
\rq\rq of the branching mechanism which gives rise to the process $\{X_n\}$.
Namely a Galton-Watson tree is the random graph each of whose vertices gives
birth to a random number of children, according to the probability
distribution
$\Pi$ , and independently of each other. Two vertices are adjacent if and
only if one is the parent of the other. Let $Z$ be the total number of
vertices, or the total progeny, of the Galton-Watson tree and let $Y_k$
be the number of vertices
having $k$ children. Motivated by the classical pioneering work by Otter
(\cite{O}),
which does not yet seem to have been fully appreciated, we shall investigate
in some detail the asymptotic behavior of the probability distribution of
$Z$, and of ${\cal Y}_k:=\sum_{j=0}^kY_j$, $k=0,1,2,\ldots$, the number of
vertices having at most $k$ children. It will be seen
that ${\cal Y}_k$ is the total progeny of a Galton-Watson tree
which is hidden in the original tree. We shall also prove a central limit
theorem for the distribution of $(Y_0,Y_1,\ldots)$ conditioned on $Z$.
As a corollary of this theorem, the central limit theorem due to Mahmoud
for vertices of
uniform binary tree (\cite{Ma})
will be reproduced. Our proofs are based on the
analysis of generating functions, and we rely entirely upon the Lagrange
inversion formula in obtaining explicit formulas for various probabilities,
and upon the classical saddle point method in obtaining their asymptotic
expressions.
In order to prepare a solid basis for our work, it is necessary to give a
precise description of \lq\lq trees\rq\rq and to introduce a suitable
$\sigma$-field ${\cal F}$ as well as a probability measure $P$ on the space
$\Omega$ of such trees. In this work we follow the convenient and elegant
construction of the probability space $(\Omega,{\cal F},P)$ due to Neveu
(\cite{N}). (It should be remarked, however, that an alternative construction
of the probability space of a Galton-Watson tree had already been given
by
Otter himself \cite{O}, which turns out to be equivalent to that of Neveu
(see \cite{K-M}),
and which even has some advantage when one considers $\Omega$ as a
topological space.)
Now let $U$ be the totality of finite sequences
$u=j_1j_2\cdots j_n$ of strictly positive integers. We can write
$U=\bigcup_{n\geq0}\mathbf{N}^n$, where $\mathbf{N}=\{1,2,\ldots\}$ and
$\mathbf{N}^0=\{\phi\}$, $\phi$ standing for the empty sequence. A tree
$\omega$ is by definition a subset of $U$ satisfying the following three
conditions: (a) $\phi\in\omega$; (b) if $uj\in\omega$ , then $u\in\omega$;
(c) for each $u\in\omega$, there is a non-negative integer $\nu_u(\omega)$
such that $uj\in\omega\Leftrightarrow1\leq j\leq\nu_u(\omega)$.
Here, for two sequences $u=j_1j_2\cdots j_n$ and $v=k_1k_2\cdots k_p$,
we write $uv$ for their conjunction: $uv=j_1j_2\cdots j_nk_1k_2\cdots k_p$.
In particular, $uj=j_1j_2\cdots j_nj$ for $j\in\mathbf{N}$.
%For convenience, let us agree to set $u0=u\phi=u$.
Thus $\omega$ is a graph with
vertices $u\in\omega$ and edges of the form $(u,uj)$. Condition (a)
says that $\omega$ always contain the special vertex $\phi$, the root of
$\omega$, while condition (b) expresses the essential feature of a tree.
Condition (c) says that our $\omega$ is what is called the ordered
tree in combinatorics. The integer $\nu_u(\omega)$ is the number of
children of the
vertex $u\in\omega$, and we follow Otter in calling it the \lq\lq type\rq\rq
of the vertex $u$. For notational convenience, we shall sometimes write
$\nu_{\omega}(u)$ instead of $\nu_u(\omega)$.
For each $u\in U$, let $\Omega_u=\{\omega\in\Omega\ \vert\ \omega\ni u\}$ be
the set of trees containing $u$ as their common
vertex, and let ${\cal F}$ be the
$\sigma$-field generated by the family $\{\Omega_u\ \vert\ u\in U\}$.
For $n=1,2,\ldots$, we let ${\cal F}_n$ be the $\sigma$-field generated by
$\Omega_u$'s with $\vert u\vert\leq n$, $\vert u\vert$ being the length
of the sequence $u$. For each $u\in U$, we also define the translation
$T_u:\Omega_u\mapsto\Omega$ by $T_u(\omega)=\{v\in U\vert uv\in\omega\}$.
Now let
$(\Omega^{\ast},{\cal F}^{\ast},P^{\ast})=\prod_{u\in U}(\mathbf{Z}_+,\Pi)$
be the product over $U$ of the
discrete probability space $(\mathbf{Z}_+,\Pi)$, the $\sigma$-field
${\cal F}^{\ast}$ being
generated by the coordinate maps $\nu^{\ast}_u$, $u\in U$, and let the
measurable map $\psi:(\Omega^{\ast},{\cal F}^{\ast})\mapsto(\Omega,{\cal F})$
be defined by
$$\psi(\omega^{\ast})=\{u=j_1\cdots j_p\ \vert\ j_{k+1}\leq
\nu^{\ast}_{j_1\cdots j_k}(\omega^{\ast})\ ,\ 0\leq k
0$, in which case we have
$Z<\infty$ with positive probability. We also assume $p_0+p_1<1$ in order to
avoid the trivial case, which can be treated separately if necessary.
The outline of the present paper is as follows. In \S2, we consider
the asymptotic behavior of $P(Z=n)$ as $n\to\infty$. Under a certain condition
on the generating function of $\Pi$, we shall show that $P(Z=n)$ has
an asymptotic expansion as $n\to\infty$. If we take its main term, we can
reproduce Otter's result (Theorem 4 of \cite{O}).
We also give some partial results when the above
mentioned condition fails to hold. In \S3,
we show that ${\cal Y}_k(\omega)$ can be viewed as the total progeny
of a random tree structure, which we shall call an abstract Galton-Watson
tree, which is hidden in the original tree $\omega$. We then
investigate the asymptotic
behavior of $P({\cal Y}_k=n)$ as $n\to\infty$, for $k=0,1,2,\ldots$. In
\S4, we give some explicit formulas for the joint distribution of
$Y_k$, $k\geq0$ conditioned on the event $\{Z=n\}$. We then consider its
limiting behavior as $n\to\infty$ in \S5,
and prove a central limit theorem for $Y_k$'s.
\section{Asymptotic results for $P(Z=n)$}
\subsection{Preliminaries}
Let $f(z)=\sum_{n=0}^{\infty}p_nz^n$ be the generating function of the
offspring
distribution $\Pi=\{p_n\}_{n=0}^{\infty}$, and let $\rho\geq1$ be its radius
of convergence. As announced in the introduction, we assume $p_0>0$ and
$p_0+p_1<1$, so that $f(0)>0$ and $f(z)$ is strictly convex on $[0,\rho)$.
Let further ${\cal P}(z)=\sum_{n=1}^{\infty}P(Z=n)z^n=\mathbf{E}[z^Z]$
be the generating function of the total progeny $Z$.
Note that we have $Z\geq1$ since a tree $\omega$ always contains
the root $\phi$. From the relation
\begin{equation}
Z(\omega)=1+\sum_{j=1}^{\nu_{\phi}(\omega)}\sum_{u\in U}1_{\Omega_{ju}}(\omega)
=1+\sum_{j=1}^{\nu_{\phi}(\omega)}Z\circ T_j(\omega)
\label{eqn:2-1}
\end{equation}
and the conditional independence given ${\cal F}_1$
of $Z\circ T_j$, $j=1,\ldots,\nu_{\phi}(\omega)$, we obtain
\begin{eqnarray*}
{\cal P}(z)&=&\sum_{k=0}^{\infty}P(\nu_{\phi}=k)\mathbf{E}
\left[z^{1+Z\circ T_1+\cdots+Z\circ T_k}\ \vert\ \nu_{\phi}=k\right] \\
&=&z\sum_{k=0}^{\infty}p_k(\mathbf{E}[z^Z])^k=zf({\cal P}(z))\ .
\end{eqnarray*}
Thus $w={\cal P}(z)$ satisfies the functional equation $w=zf(w)$. Since
we are assuming $f(0)\ne0$, we can apply Lagrange inversion formula (see
e.g. \cite{Ho}), to show that $P(Z=n)$, which is the $n$-th coefficient
of the power series ${\cal P}(z)$, is given by
\begin{equation}
P(Z=n)=\frac1n\mbox{Res}\left[\left(\frac{f(z)}{z}\right)^n\right]
=\frac1{2\pi in}\oint\left(\frac{f(z)}{z}\right)^ndz\ ,
\label{eqn:2-3}
\end{equation}
where $\oint$ denotes the contour integration along a circle surrounding the
origin. (\ref{eqn:2-3}) shows that $P(Z=n)$ is the coefficient of $z^{n-1}$
of the power series $f(z)^n$ divided by $n$. But $f(z)^n$ is the generating
function of the $n$-th convolution power $\Pi^{\ast n}$ of $\Pi$, hence
$nP(Z=n)$ is equal to
the probability that the first generation of our Galton-Watson process
consists of $n-1$ individuals when there are $n$ individuals at the 0-th
generation. In other words, if we let $\{q(n,m)\}_{n,m\geq0}$ the transition
probability of the Galton-Watson process with the offspring distribution
$\Pi$, then we have
\begin{equation}
P(Z=n)=\frac1n q(n,n-1)\ .
\label{eqn:2-4}
\end{equation}
By a purely probabilistic argument, Dwass \cite{D} (see also \cite{J})
obtained this seemingly
non-trivial relation. The basic functional equation
${\cal P}(z)=zf({\cal P}(z))$ seems to date back to the work of Hawkins and
Ulam (see the footnote on page 32 of \cite{Ha}), and was independently
re-discovered by Good (\cite{G}) and Otter (\cite{O}), the latter having
noted the formula
(\ref{eqn:2-3}) at the same time. This was also re-discovered by
Boyd (\cite{B}), who used it to give an alternative proof of
the relation (\ref{eqn:2-4}).
The class of distributions on natural numbers which are obtained as
distributions of the total progeny of Galton-Watson trees coincides the
class of \lq\lq Lagrange distributions\rq\rq treated systematically by
Consul and Shenton (\cite{Co}). Good (\cite{G2}) generalized the Lagrange
inversion formula to multi-variable functions, and discussed its relation to
multi-type branching processes. See also \cite{G3}.
\bigskip
Now let $\alpha$ ($\alpha\geq1$) be the radius of convergence of the power
series ${\cal P}(z)$ and let $a={\cal P}(\alpha-)$.
Then we have the following relations.
\begin{prop} Under the condition $p_0>0$ and $p_0+p_1<1$, we have
\begin{description}
\item[(i)] $a\leq\rho$;
\item[(ii)] $\alpha$ and $a$ are finite;
\item[(iii)] $f(a)/a=1/\alpha$;
\item[(iv)] $f'(a)\leq1/\alpha$;
\item[(v)] $f'(a)=1/\alpha$ if $a<\rho$;
\item[(vi)] if, conversely, $f'(\zeta)=f(\zeta)/\zeta$ for some
$0<\zeta<\rho$, then $a<\rho$ and $\zeta=a$.
\end{description}
\end{prop}
\noindent{\it Proof.}
All the statements except (vi) are proved in
Lemma 4 and Theorem 3 of \cite{O}.
To show (vi), suppose $a=\rho$, in which case $\rho$ is finite.
Then as $z$ increases from $0$ to
$\alpha$, ${\cal P}(z)$ strictly increases from $0$ to $\rho$. Hence
there exists a $z_0\in(0,\alpha)$ such that $\zeta={\cal P}(z_0)$.
If we put $z=z_0$ in the formula $zf({\cal P}(z))={\cal P}(z)$ and
in $zf'({\cal P}(z)){\cal P}'(z)+f({\cal P}(z))={\cal P}'(z)$
which is obtained by differentiating the former with respect to $z$,
then by $f'(\zeta)=f(\zeta)/\zeta$, we get ${\cal P}'(z_0)+f(\zeta)
={\cal P}'(z_0)$, whence $f(\zeta)=0$. But this is a contradiction because
$f(z)$ is increasing and $f(0)=p_0>0$. Thus we must have $a<\rho$, and
by (iii) and (v), $f'(z)=f(z)/z$ is satisfied also at $z=a$. But since
$(zf'(z)-f(z))'=zf^{\prime\prime}(z)>0$ on $(0,\rho)$, such $z$ is unique,
so that $\zeta=a$.
From now on,
we shall refer the condition of the statement (vi) as {\em Condition A}.
Since $(zf'(z)-f(z))\vert_{z=0}=-p_0<0$, it is obviously equivalent to
the condition
\begin{equation}
\lim_{z\uparrow\rho}(zf'(z)-f(z))>0\ .
\label{eqn:2-5}
\end{equation}
It is also easy to see that Condition A holds if and only if
the function $f(z)/z$ attains
a unique minimum in $(0,\rho)$, which is equal to $f(a)/a$.
When, on the other hand, Condition A fails, we have $\rho=a<\infty$, and
$f(z)/z$ is decreasing on $(0,a]$. Hence the number $a$ is always
characterized by the relation
\begin{equation}
\frac{f(a)}a=\inf_{00$. Then $P(Z=n)=0$ if $n\not\equiv1$ {\rm (mod $d$)}.
\medskip
\noindent
(ii) It holds that
$$\limsup_{n\to\infty}P(Z=n)^{1/n}=f(a)/a\ ,$$
where $a$ is given by (\ref{eqn:2-6}).
\label{prop:2}
\end{prop}
\noindent{\it Proof.}
(i) This is a part of Theorem 4 of \cite{O}. Here we
give an alternative proof, to emphasize that it has nothing to do with
Condition A.
In the expansion
$$\left(\frac{f(z)}z\right)^n=\sum_{j_1,j_2,\ldots,j_n\geq0}
p_{j_1}p_{j_2}\cdots p_{j_n}z^{j_1+j_2+\cdots+j_n-n}\ ,$$
we have $p_{j_1}p_{j_2}\cdots p_{j_n}>0$ only when all of $j_1,j_2,\ldots,j_n$
are integer multiple of $d$. Hence if $n\not\equiv1$ (mod $d$), then we
have
$$j_1+j_2+\cdots+j_n-n\ne -1$$
for any of such $j_1,j_2,\ldots,j_n$, so that the residue at the origin of
$(f(z)/z)^n$ vanishes and so does $P(Z=n)$ by (\ref{eqn:2-3}). This proves
(i). The assertion (ii) is obvious from the Cauchy-Hadamard formula for
the radius of convergence of power series and from (iii) of Proposition 1.
Note that we have $00$, and the expansion
$$\psi(\theta)=\log\frac{f(a)}{a}-K\theta^2+\sum_{k=3}^{\infty}B_k\theta^k
\ ,$$
where we have let $\psi^{\prime\prime}(0)=-2K$.
In fact, if we let $\rho_k:=p_ka^k/f(a)$, then
$\Pi_a:=\{\rho_k\}_{k\geq0}$ is a probability distribution on
$\mathbf{Z}_+$ whose characteristic function is $f(ae^{i\theta})/f(a)$.
Hence if $\kappa_k$ is the $k$-th cumulant of the distribution
$\Pi_a$, then we have the relation $B_k=i^k\kappa_k/k!$.
It is easy to show
$\vert f(ae^{i\theta})\vert0$. Thus we arrive at
\begin{eqnarray}
P(Z=n)
&=&\frac{ad}{2\pi n}\left(\frac{f(a)}{a}\right)^n\left[
\sum_{\ell+m\leq A}c_{\ell m}n^{\ell}\int_{-\infty}^{\infty}
\exp(-nK\theta^2)\theta^{3\ell+m}d\theta+
{\cal O}(n^{-1-A/2})\right] \nonumber\\
&=&\frac{ad}{2\pi}\left(\frac{f(a)}{a}\right)^n
\left[\sum_{\ell+m\leq A}\gamma_{\ell m}K^{-\frac{3\ell+m+1}{2}}
n^{-1-\frac{\ell+m+1}2}+{\cal O}(n^{-2-\frac{A}2})\right]\ ,
\label{eqn:2-11}
\end{eqnarray}
where $\gamma_{\ell m}=0$ if $\ell+m$ is odd, and
$\gamma_{\ell m}=\Gamma((3\ell+m+1)/2)c_{\ell m}$
if $\ell+m$ is even. If we take $A=2k-1$, $k=1,2,\ldots$, then the error
term becomes ${\cal O}(n^{-k-3/2})$, while the final term in the sum is
a constant multiple of
$n^{-k-1/2}$. The validity of (\ref{eqn:2-11}) for
all $A>0$ thus implies that we have the asymptotic expansion
$$P(Z=n)\sim\frac{ad}{2\pi}\sum_{k=1}^{\infty}\left(\sum_{\ell+m=2(k-1)}
\gamma_{\ell m}K^{-\frac{3\ell+m+1}2}\right)\left(\frac{f(a)}{a}\right)^n
n^{-k-\frac12}$$
as $n\to\infty$. The coefficient for $k=1$ is
$$\frac{ad}{2\pi}\gamma_{00}K^{-1/2}=\frac{ad}{2\pi}
c_{00}\Gamma\left(\frac12\right)\left(
\frac{a^2f^{\prime\prime}(a)}{2f(a)}\right)^{-\frac12}=
d\sqrt{\frac{f(a)}{2\pi f^{\prime\prime}(a)}}\ .$$
\bigskip
\begin{lemma} If $00\}$. Since we have,
for any $k\in{\cal A}$, the inequality
$$\vert f(re^{i\theta})\vert\leq\vert p_0+p_kr^ke^{ik\theta}\vert+
\sum_{n\ne0,k}p_nr^n\ ,$$
where
$$\vert p_0+p_kr^ke^{ik\theta}\vert^2=
p_0^2+p_k^2r^{2k}+2p_0p_kr^k\cos k\theta\ ,$$
all we have to do is to verify that $\cos k\theta<1$ for som $k\in{\cal A}$.
When ${\cal A}=\{d\}$, this is obvious from the assumption on $\theta$.
When ${\cal A}$ contains at least two numbers, take distinct $k,k'\in{\cal A}$
such that $g.c.d.(k,k')=d$. Then there are integers $m$ and $m'$ such that
$mk+m'k'=d$. Now if we had $\cos k\theta=\cos k'\theta=1$, then
$k\theta=2\pi\ell$ and $k'\theta=2\pi\ell'$ for som integers $\ell$ and
$\ell'$. Hence we would have $\theta d=\theta(mk+m'k')\in2\pi\mathbf{Z}$,
contradicting the assumption on $\theta$. Thus either $\cos k\theta<1$
or $\cos k'\theta<1$.
\subsection{Some partial results when Condition A fails}
When Condition A fails to hold, we have in view of Proposition 1,
$\rho=a<\infty$, and
$f(\rho)=f(a)=a/\alpha<\infty$. Also we have $f'(\rho)=f'(a)\leq1/\alpha
<\infty$, namely $f'(\rho)\leq f(\rho)/\rho$. On the other hand,
$f(\rho)/\rho=f(a)/a\leq1/\alpha\leq1$ because of $\alpha\geq1$. In
particular, $f(z)=f(x+iy)$ is of $C^1$ with respect to $(x,y)$
on the closed disk $\{\vert z\vert\leq\rho\}$,
hence we can take the circle $\{\vert z\vert=\rho\}$ as the
contour of integration in (\ref{eqn:2-3}), so that
$$P(Z=n)=\frac{\rho d}{2\pi n}\int_{-\pi/d}^{\pi/d}\exp(n\psi(\theta))
e^{i\theta}d\theta\ ,$$
where we let $\psi(\theta)=\log\{f(\rho e^{-i\theta}/\rho e^{i\theta})\}$.
We shall consider two cases separately.
\subsubsection{The case $f'(\rho)=f(\rho)/\rho$.}
In this case, we shall assume $f^{(4)}(\rho)<\infty$.
As before, we have
$\psi'(0)=0$ and
$$-2K:=\psi^{\prime\prime}(0)=\rho^2f^{\prime\prime}(\rho)/
f(\rho)<0\ ,$$
so that
\begin{equation}
\psi(\theta)=\psi(0)-K\theta^2+i\beta\theta^3+\phi(\theta)\ ,
\label{eqn:2-3-1}
\end{equation}
where $i\beta=\psi^{(3)}(0)/3!$ with a real $\beta$ and
$\phi(\theta)={\cal O}(\theta^4)$ as $\theta\to0$.
Moreover, $\psi(0)=\log(f(\rho)/\rho)$ is the maximum value of
$\mathbf{Re}\psi(\theta)$. Now we can proceed as in \S 2.2, to obtain
\begin{eqnarray*}
P(Z=n)&=&\frac{\rho d}{2\pi n}\left\{\int_{-\delta}^{\delta}
\exp(n\psi(\theta))e^{i\theta}d\theta+{\cal O}(\Delta_{\delta}^n)\right\} \\
&=&\frac{\rho d}{2\pi n}\left\{\int_{-\tau_n}^{\tau_n}
\exp(n\psi(\theta))e^{i\theta}d\theta+
{\cal O}\left(\left(\frac{f(\rho)}{\rho}\right)^n\int_{\tau_n}^{\delta}
e^{-\eta n\theta^2}d\theta\right)
+{\cal O}(\Delta_{\delta}^n)\right\}\ ,
\end{eqnarray*}
where $\delta$, $\Delta_{\delta}$,
$\tau_n$ and $\eta$ have the same meaning as before.
Since
$$\int_{\tau_n}^{\delta}e^{-\eta n\theta^2}d\theta=
{\cal O}(n^{-2/3}e^{-\eta n^{1/3}})\ ,$$
it absorbs the error term ${\cal O}(\Delta_{\delta}^n)$. Hence taking
(\ref{eqn:2-3-1}) and $\tau_n=n^{-1/3}$ into account, we can write
\begin{eqnarray*}
P(Z=n)&=&\frac{\rho d}{2\pi n}\left(\frac{f(\rho)}{\rho}\right)^n
\left\{\int_{-\tau_n}^{\tau_n}
\exp\left(-Kn\theta^2+i\beta n\theta^3+n\phi(\theta)\right)
e^{i\theta}d\theta+
{\cal O}(n^{-2/3}e^{-\eta n^{1/3}})\right\} \\
&=&\frac{\rho d}{2\pi n}\left(\frac{f(\rho)}{\rho}\right)^n
\left\{\int_{-\tau_n}^{\tau_n}
\exp\left(-Kn\theta^2+i\beta n\theta^3\right)
e^{i\theta}d\theta \right. \\
&\qquad&\left.+{\cal O}\left(\int_0^{\tau_n}e^{-Kn\theta^2}
n\phi(\theta)d\theta\right)+{\cal O}\left(n^{-2/3}e^{-\eta n^{1/3}}\right)
\right\}\ .
\end{eqnarray*}
From $\phi(\theta)={\cal O}(\theta^4)$, we obtain the estimate
$$\int_0^{\tau_n}e^{-Kn\theta^2}n\phi(\theta)d\theta=
{\cal O}(n^{-3/2})\ .$$
On the other hand,
\begin{eqnarray*}
& &\int_{-\tau_n}^{\tau_n}
\exp\left(-Kn\theta^2+i\beta n\theta^3+i\theta\right)d\theta \\
&=&\int_{-\tau_n}^{\tau_n}e^{-Kn\theta^2}\cos(\beta n\theta^3+\theta)
d\theta \\
&=&\int_{-\tau_n}^{\tau_n}e^{-K n\theta^2}d\theta+
{\cal O}\left(\int_{-\tau_n}^{\tau_n}e^{-Kn\theta^2}
(n^2\theta^6+\theta^2)d\theta\right) \\
&=&\frac1{\sqrt{n}}\int_{-\infty}^{\infty}e^{-K z^2}dz
+{\cal O}(n^{-3/2})\ ,
\end{eqnarray*}
thus
$$P(Z=n)=\sqrt{\frac{f(\rho)}{2\pi f^{\prime\prime}(\rho)}}
\left(\frac{f(\rho)}{\rho}\right)^n n^{-3/2}(1+{\cal O}(n^{-1}))\ .$$
\subsubsection{The case $f'(\rho)0$ and
$$\psi^{\prime\prime}(0)=\frac{\rho f'(\rho)}{f(\rho)^2}
(\rho f'(\rho)-f(\rho))-\rho^2\frac{f^{\prime\prime}(\rho)}{f(\rho)}<0\ .$$
Thus letting $-2K=\psi^{\prime\prime}(0)$, we can write
\begin{equation}
\psi(\theta)=\psi(0)-i\beta\theta-K\theta^2+\phi(\theta)\ ,
\label{eqn:2-3-3}
\end{equation}
with $\phi$ a $C^k$ function satisfying $\phi(\theta)={\cal O}(\theta^3)$
and $\phi(0)=\phi'(0)=\phi^{\prime\prime}(0)=0$.
We now estimate, with the same notation as before,
\begin{eqnarray*}
P(Z=n)
&=&\frac{\rho d}{2\pi n}\left\{\int_{-\tau_n}^{\tau_n}
\exp(n\psi(\theta))e^{i\theta}d\theta+
{\cal O}\left(\left(\frac{f(\rho)}{\rho}\right)^nn^{-2/3}
e^{-\eta n^{1/3}}\right)
\right\}\ .
\end{eqnarray*}
If we let
$$J_n:=\int_{-\tau_n}^{\tau_n}\exp(n\psi(\theta))e^{i\theta}d\theta\ ,$$
then
$$J_n=\left(\frac{f(\rho)}{\rho}\right)^n\frac1{\sqrt{n}}
\int_{-n^{1/6}}^{n^{1/6}}e^{-i\beta\sqrt{n}z}F_n(z)dz\ ,$$
where
$$F_n(z):=\exp\left[-Kz^2+n\phi\left(\frac{z}{\sqrt{n}}\right)+
i\frac{z}{\sqrt{n}}\right]\ .$$
Now it is easy to see that we can find constants $A,C>0$ which are independent
of $n$ so that for $j=0,1,\ldots,k$ and $\vert z\vert\leq n^{1/6}$, we have
$$\left\vert \frac{d^j}{dz^j}F_n(z)
\right\vert\leq Ae^{-cz^2}\ .$$
Integrating by parts $k$ times, we obtain
\begin{eqnarray*}
J_n&=&\left(\frac{f(\rho)}{\rho}\right)^n\frac1{\sqrt{n}}\left\{
\sum_{j=1}^k(-1)^{j-1}\left[\frac{e^{-i\beta\sqrt{n}z}}{(-i\beta\sqrt{n})^j}
\frac{d^{j-1}}{dz^{j-1}}F_n(z)\right]_{z=-n^{1/6}}^{z=n^{1/6}}\right. \\
& &\qquad\qquad\left. +(-1)^k\int_{-n^{1/6}}^{n^{1/6}}
\frac{e^{-i\beta\sqrt{n}z}}{(-i\beta\sqrt{n})^k}
\frac{d^k}{dz^k}F_n(z)dz\right\} \\
&=&\left(\frac{f(\rho)}{\rho}\right)^n\frac1{\sqrt{n}}\times
{\cal O}(n^{-k/2})\ ,
\end{eqnarray*}
and consequently
$$P(Z=n)={\cal O}\left(\left(\frac{f(\rho)}{\rho}\right)^n
n^{-\frac32-\frac k2}\right)\ ,$$
as $n\to\infty$.
\bigskip
For illustration, consider the case $\rho=1$, so that $f(\rho)/\rho=1$.
The condition $f'(\rho)0$ and $0<\gamma<1$, then $f^{(k)}(1)<
\infty$ for all $k\geq3$, and consequently $P(Z=n)$ decays faster than
any power of $n$. But still one has
$$\limsup_{n\to\infty}P(Z=n)^{1/n}=1$$
by Proposition \ref{prop:2}.
\section{The distribution of ${\cal Y}_k$}
\subsection{${\cal Y}_k$ as the total progeny of a hidden Galton-Watson tree}
In this section, we consider ${\cal Y}_k(\omega):=\sum_{j=0}^kY_j(\omega)$,
the number of those vertices of the Galton-Watson tree $\omega$ having at most
$k$ children, ${\cal Y}_0(\omega)$ being in particular the number of
\lq\lq leaves \rq\rq of $\omega$.
Let
$$Q(z)=Q_k(z):=\mathbf{E}[1_{\{{\cal Y}_k<\infty\}}z^{{\cal Y}_k}]
=\sum_{n=1}^{\infty}P({\cal Y}_k=n)z^n$$
be the generating function of the distribution of ${\cal Y}_k$. (Note
that by our assumption $p_0>0$, we have $P(Y_0>0)=1$. Thus
$P({\cal Y}_k=0)=0$ for all $k\geq0$.)
Since we have
$${\cal Y}_k(\omega)=1_{\{\nu_{\phi}\leq k\}}(\omega)+
\sum_{j=1}^{\nu_{\phi}(\omega)}
({\cal Y}_k\circ T_j)(\omega)\ ,$$
we can proceed, just as in \S2.1,
\begin{eqnarray*}
Q(z)&=&\mathbf{E}\left[z^{1_{\{\nu_{\phi}\leq k\}}}
\prod_{j=1}^{\nu_{\phi}}\left(1_{\{{\cal Y}_k<\infty\}}\circ T_j\right)
\left(z^{{\cal Y}_k}\circ T_j\right) \right] \\
&=&\mathbf{E}\left[z^{1_{\{\nu_{\phi}\leq k\}}}
\mathbf{E}\left[\left.\prod_{j=1}^{\nu_{\phi}}\left(
1_{\{{\cal Y}_k<\infty\}}z^{{\cal Y}_k}
\circ T_j\right)\ \right\vert{\cal F}_1\right]
\right] \\
&=&\mathbf{E}\left[z^{1_{\{\nu_{\phi}\leq k\}}}
\prod_{j=1}^{\nu_{\phi}}\mathbf{E}\left[1_{\{{\cal Y}_k<\infty\}}
z^{{\cal Y}_k}\right] \right] \\
&=&z\mathbf{E}\left[1_{\{\nu_{\phi}\leq k\}}Q(z)^{\nu_{\phi}}\right]+
\mathbf{E}\left[1_{\{\nu> k\}}Q(z)^{\nu_{\phi}} \right] \\
&=&z\sum_{j=0}^{k}p_jQ(z)^j+f(Q(z))-\sum_{j=0}^kp_jQ(z)^j\ .
\end{eqnarray*}
Thus $w=Q(z)$ solves the equation
$$z\sum_{j=0}^kp_jw^j=w-f(w)+\sum_{j=0}^kp_jw^j\ ,$$
or
$$z=\frac{w}{g_k(w)}\ ,$$
where we have set
$$g_k(w)=\frac{w\sum_{j=0}^kp_jw^j}{w-f(w)+\sum_{j=0}^kp_jw^j}\ .$$
For later use, let us further define
\begin{equation}
h_k(w)=\sum_{j=0}^kp_jw^j\quad\mbox{and}\quad\varphi_k(w)=\sum_{j>k}p_j
w^{j-1}\ .
\label{eqn:13}
\end{equation}
Then
\begin{equation}
g_k(w)=\frac{h_k(w)}{1-\varphi_k(w)}\ .
\label{eqn:14}
\end{equation}
We shall now prove that $g_k(w)$ is the generating function of a probability
distribution $\Pi^{(k)}:=\{p_n^{(k)}\}_{n=0}^{\infty}$ which satisfies our
basic assumption, namely $p^{(k)}_0>0$ and $p^{(k)}_0+p^{(k)}_1<1$.
To this end, let us write
\begin{eqnarray*}
g_k(w)&=&h_k(w)\sum_{n=0}^{\infty}\varphi_k(w)^n \\
&=&\left(\frac{h_k(w)}{h_k(1)}\right)h_k(1)\sum_{n=0}^{\infty}
\varphi_k(1)^n\left(\frac{\varphi_k(w)}{\varphi_k(1)}\right)^n\ .
\end{eqnarray*}
If we set
$$H(w):=\frac{h_k(w)}{h_k(1)}\ ;$$
$$G(\zeta):=h_k(1)\sum_{n=0}^{\infty}\varphi_k(1)^n\zeta^n\ ;$$
$$\psi(w):=\frac{\varphi_k(w)}{\varphi_k(1)}\ ,$$
then $H$, $G$, $\psi$ are generating functions respectively of
$$P(\nu_{\phi}\in\bullet\ \vert\ \nu_{\phi}\leq k)\ ;$$
$$\mbox{the geometric distribution with parameter}\ \varphi_k(1)
=P(\nu_{\phi}>k)\ ;$$
and
$$P(\nu_{\phi}-1\in\bullet\ \vert\ \nu_{\phi}>k)\ .$$
Consequently, if $X$, $N$, $S_1,S_2,\ldots$ are independent integer-valued
random variables, and if $X$ [resp. $N$, $S_j$] has $H$ [resp. $G$, $\psi$]
as its generating function, then $g_k(w)=G(\psi(w))H(w)$ is the generating
function of the random variable
$$\sum_{j=1}^NS_j+X\ .$$
Obviously $g_k(0)=p_0$ for $k\geq1$ and $=p_0/(1-p_1)$ for $k=0$, whence
$p^{(k)}_0=g_k(0)>0$. By
$$g_k'(w)=\frac{h'_k(w)(1-\varphi_k(w))+h_k(w)\varphi'_k(w)}
{(1-\varphi_k(w))^2}$$
and by $\varphi_k(1)+h_k(1)=1$, we get
$$g_k'(1)=\frac{h'_k(1)+\varphi_k'(1)}{h_k(1)}=1+\frac{f'(1)-1}{h_k(1)}\ .$$
This shows that $g'_k(1)<1$ [resp. $=1$ or $>1$] if and only if $f'(1)<1$
[resp. $=1$ or $>1$]. On the other hand, we have
$$g'_k(0)=\left\{
\begin{array}{rl}
p_0p_2/(1-p_1)^2\quad(k=0) \\
p_1+p_0p_2\quad(k=1) \\
p_1\quad(k>1)
\end{array}
\right.\ .$$
Hence for $k>1$, $p^{(k)}_0+p^{(k)}_1=g_k(0)+g'_k(0)=p_0+p_1<1$ by the
assumption. Similarly for $k=1$,
$$g_1(0)+g'_1(0)=p_0+p_1+p_0p_2<1\ .$$
To consider the case $k=0$, let $q_2=\sum_{n\geq2}p_n>0$. Then
\begin{eqnarray*}
p_0(1-p_1+p_2)&=&(1-p_1-q_2)(1-p_1+p_2) \\
&\leq&(1-p_1-q_2)(1-p_1+q_2) \\
&=&(1-p_1)^2-q_2^2<(1-p_1)^2\ ,
\end{eqnarray*}
and hence
$$g_0(0)+g'_0(0)=\frac{p_0}{1-p_1}+\frac{p_0p_2}{(1-p_1)^2}=
\frac{p_0(1-p_1+p_2)}{(1-p_1)^2}<1\ .$$
Finally, if $t>0$ satisfies $f(t)=t$, then $h_k(t)+t\varphi_k(t)=t$ for any
$k\geq0$, namely
$$g_k(t)=\frac{h_k(t)}{1-\varphi_k(t)}=t\ .$$
These considerations can be summerized in the following theorem:
\begin{thm}
For any $k\geq0$, the distribution of ${\cal Y}_k$ is equal to that of the
total progeny of the Galton-Watson tree with the offspring distribution
$\Pi^{(k)}=\{p^{(k)}_n\}_{n=0}^{\infty}$. As the original
$\Pi=\{p_n\}_{n=0}^{\infty}$, $\Pi^{(k)}$ satisfies the condition
$p^{(k)}_0>0$, $p^{(k)}_0+p^{(k)}_1<1$. The new Galton-Watson tree is
sub-critical [resp. critical or super-critical] if and only if the original
one is so. Moreover the extinction probabilities of both Galton-Watson trees,
which are solutions respectively of $f(t)=t$ and $g_k(t)=t$, coincide.
\label{thm:2}
\end{thm}
\begin{cor}
$P(Z=\infty\ ,\ {\cal Y}_k<\infty)=0$ for any $k\geq0$.
\end{cor}
\noindent{\it Proof.}
Obviously $\{Z<\infty\}\subset\{{\cal Y}_k<\infty\}$. But the probability
of both events, being the extinction probability of the old or the
new Galton-Watson tree respectively, are equal.
\bigskip
We have thus shown the existence of a Galton-Watson tree whose total
progeny has the same distribution as ${\cal Y}_k$. This would be sufficient
for most applications, but it is natural to ask if the new Galton-Watson
tree can be constructed as a functional of the original tree $\omega$,
so that its total progeny {\em coincides} with ${\cal Y}_k(\omega)$.
We shall now show that this is actually the case, but before doing so,
we need to prepare an abstract notion of Galton-Watson tree. To begin with,
let us generalize the notion of tree itself.
\begin{definition}
Let $G=(V,E)$ be a directed graph, where $V$ is a finite or countable
vertex set and $E\subset V\times V$. We shall call $G$ an abstract
tree if the following five conditions hold:
\begin{description}
\item[1)] For any $u\in V$, $(u,u)\notin E$. Namely $G$ has no loops.
\item[2)] There is a special vertex $u_0\in V$ such that $(u,u_0)\notin
E$ for all $u\in V$. We call $u_0$ the \lq\lq root \rq\rq of $G$.
\item[3)] For any $v\in V\setminus\{u_0\}$, there is one and only one
$u\in V$ such that $(u,v)\in E$. In particular, $G$ is an oriented graph.
\item[4)] The (non-directed) graph $G^s=(V,E^s)$ obtained by letting
$E^s:=\{\{u,v\}:\ (u,v)\in E\ \mbox{or}\ (v,u)\in E\}$ is connected.
\item[5)] For any $u\in V$, the set $W_G(u)=\{v\in V:\ (u,v)\in E\}$
is finite and totally ordered.
\end{description}
\end{definition}
\bigskip
Let us first show that an abstract tree $G=(V,E)$ is isomorphic to a tree
$\omega\in\Omega$ in the sense of Neveu (and equivalently of Otter).
From 4), we see that for
an arbitrary $u\in V$, there is a path connecting $u_0$ and $u$ in the graph
$G^s$. Let $u_0u_1\ldots u_{n-1}u_n$, where we let $u_n=u$, be such a path
which has minimum length. By 1), we have $u_{i-1}\ne u_i$ for $i=1,\ldots,n$,
and by 2), we must have $(u_0,u_1)\in E$. Let $k$ be the maximum of those
$j=1,\ldots,n$ for which $(u_{i-1},u_i)\in E$ for all $i0$ implies $P(\cap_{n=1}^{\infty}\Omega_{u1_n})=0$ for each
$u\in U$, where we denote $1_n=11\ldots1$, the sequence consisting of
$n$ times repetition of $1$. Hence if we let
$\tilde{\Omega}=\cap_{u\in U}\cup_{n=1}^{\infty}(\Omega_{u1_n})^c$,
then we have $\tilde{\Omega}\in{\cal F}$ and $P(\tilde{\Omega})=1$.
Restricting ${\cal F}$ and $P$ to $\tilde{\Omega}$, we obtain a new
probability space $(\tilde{\Omega},\tilde{{\cal F}},\tilde{P})$.
For $k\geq0$ and for each $\omega\in\tilde{\Omega}$, set
$$V_k(\omega)=\{u\in U;\ u\in\omega\ \mbox{and}\
\nu_{\omega}(u)\leq k\}\subset U\ .$$
Then ${\cal Y}_k(\omega)=\sharp V_k(\omega)$. We are now going to show
that by suitably defining the adjacency relation on $V_k(\omega)$,
this can be turned into an abstract Galton-Watson tree whose offspring
distribution is $\Pi^{(k)}$. To make the idea transparent,
avoiding the notational complication, we shall give the full detail
of its construction only for $k=0$, in which case $V_0(\omega)$ is the
set of endpoints, or \lq\lq leaves \rq\rq of $\omega$, and give a brief
sketch for the general case $k\geq1$.
To begin with, let us make $V_0(\omega)$ into an abstract tree, which
we shall denote $G_0(\omega)$, in the following way. Since
$\omega\in\tilde{\Omega}$, we have
$$n_0(\omega):=\max\{p\geq0;\ 1_p\in\omega\}<\infty\ .$$
We denote $u_0(\omega)=1_{n_0(\omega)}$, and this will play the role
of the root of $G_0(\omega)$. Now if $n_0(\omega)=0$ or
$\nu_{\omega}(1_p)=1$ for all $p1$
for some $0\leq p1$ for some
$0\leq j0$ in (\ref{eqn:3-1-2}), then by the same procedure we can further
find the parent of $u$ and so on. Thus starting from a vertex
$v\in V_0(\omega)$ of the form (\ref{eqn:3-1-2}), we can find
$u_N,\ u_{N-1},\ldots,u_1$, so that $(u_{i-1},u_i)\in E_0(\omega)$
for $i=1,\ldots,N+1$, where we set $u_{N+1}=v$. Since this is true
for all $v\in V_0(\omega)$, we see that 4) holds, too. Finally for
each $u\in V_0(\omega)$, let $W_{\omega}(u)\subset V_0(\omega)$ be
the totality of its children. If $u$ is of the form (\ref{eqn:3-1-1}),
i.e. $u=\tilde{u}1_m$, then from the consideration above, we have
\begin{equation}
\sharp W_{\omega}(u)=\sum_{i=0}^m\left(\nu_{\omega}(\tilde{u}1_i)-1
\right)_+<\infty\ .
\label{eqn:3-1-3}
\end{equation}
Moreover we can arrange members in $W_{\omega}(u)$ in the natural
lexicographic order, under which $W_{\omega}(u)$ is totally ordered.
Namely given two typical vertices $v=\tilde{u}1_ib1_{\ell}$ and
$v=\tilde{u}1_{i'}b'1_{\ell'}$ of $W_{\omega}(u)$, we define $v0\}$ is the totality of the
\lq\lq inner points \rq\rq of the tree $t$. Subsets of $\Omega$ of this form
were called \lq\lq neighborhoods \rq\rq by Otter \cite{O}. By the
equivalence of two construction of the probability space for Galton-
Watson trees respectively due to Otter and Neveu (see \cite{K-M}),
it is enough to verify
\begin{equation}
P([t;\Lambda])=\left(\prod_{u\in{\cal I}(t)}p_{\nu_u(t)}\right)
\left(\prod_{e\in G_0(t)}p_{\lambda_e}\right)\ .
\label{eqn:3-1-6}
\end{equation}
Given $t$ and $\Lambda=(\lambda_e;e\in G_0(t))$ as above, let
$\Lambda_j=(\lambda_e;e\in G_0(T_jt))$ for $j=1,2,\ldots,\nu_{\phi}(t)$,
which altogether form a partition of
$\Lambda$. Then it is easily seen that
$$[t;\Lambda]=\{\omega\in\Omega;\ \nu_{\phi}(\omega)=\nu_{\phi}(t)\}
\cap\bigcap_{j=1}^{\nu_{\phi}(t)}
T_j^{-1}([T_jt;\Lambda_j])$$
holds. Thus from the assumption,
\begin{eqnarray*}
P([t;\Lambda])&=&P(\nu_{\phi}=\nu_{\phi}(t))
P\left(\left.\bigcap_{j=1}^{\nu_{\phi}(t)}T_j^{-1}([T_jt;\Lambda_j])
\right\vert\ \nu_{\phi}=\nu_{\phi}(t)\right) \\
&=&p_{\nu_{\phi}(t)}\prod_{j=1}^{\nu_{\phi}(t)}P([T_jt;\Lambda_j])\ .
\end{eqnarray*}
Repeating this argument to rewrite $P([T_jt;\Lambda_j])$ and so on,
we arrive at (\ref{eqn:3-1-6}).
Let us apply this criterion to our measure $Q$. From (\ref{eqn:3-1-3}) and
(\ref{eqn:3-1-5}), we see
$$Q(\nu_{\phi}=k)=\sum_{n=0}^{\infty}
\sum_{k_0+\cdots k_{n-1}=k,k_i\geq0}P(\nu_{\omega}(1_i)=1+k_i,\ 0\leq i0)\ ,
\end{eqnarray*}
and hence
$$Q(\nu_{\phi}=k)=
\sum_{n=0}^{\infty}p_0(1-p_0)^n\sum_{k_0+\cdots k_{n-1}=k}
\ \prod_{i=0}^{n-1}P(\nu_{\phi}-1=k_i\vert\ \nu_{\phi}>0)
=p_{k}^{(0)}\ ,$$
verifying the first part of the criterion. Next for $k\geq1$ and
$B_1,\ldots,B_k\in{\cal F}$, we write
\begin{eqnarray*}
& &Q\left(\{\nu_{\phi}=k\}\cap\bigcap_{i=1}^kT_i^{-1}(B_i)\right) \\
&=&P\left(\{\nu_{\phi}\circ\tau\circ G_0=k\}\cap
\bigcap_{i=1}^k(T_i\circ\tau\circ G_0)^{-1}(B_i)\right) \\
&=&\sum_{n=1}^{\infty}\sum_{k_0+\cdots k_{n-1}=k}
P\left(C_{n,k_0,\ldots,k_{n-1}}\cap\bigcap_{\ell=0}^k\bigcap_{a=2}^{1+k_i}
(T_{1_{\ell}a})^{-1}\left((\tau\circ G_0)^{-1}(B_{\ell,a})\right)\right)\ ,
\end{eqnarray*}
where we have written $B_{\ell,a}$ instead of $B_j$ when
$j=k_0+\cdots+k_{\ell-1}+(a-1)$ holds. By the same reasoning as above, we have
\begin{eqnarray*}
& &P\left(C_{n,k_0,\ldots,k_{n-1}}\cap\bigcap_{\ell=0}^{n-1}
\bigcap_{a=2}^{1+k_i}(T_{1_{\ell}a})^{-1}\left((\tau\circ G_0)^{-1}
(B_{\ell,a})\right)\right) \\
&=&P^{\ast}\left(\{\nu_{1_i}^{\ast}=1+k_i,0\leq ik$ for $ik\}$$ if
$\nu_{\omega}(1_{\ell}b)>k$;
\item[type II:] when $\nu_{\omega}(1_{n_0(\omega)})>0$, then
vertices of the form $v=1_{n_0(\omega)}a1_{m}$ are children of
$u_0(\omega)$, where $1\leq a\leq\nu_{\omega}(1_{n_0(\omega)})$
and $m=0$ if $\nu_{\omega}(1_{n_0(\omega)}a)\leq k$,
while
$$m=1+\max\{i\geq0;\nu_{\omega}(1_{n_0(\omega)}a1_i)>k\}$$
if $\nu_{\omega}(1_{n_0(\omega)}a)>k$.
\end{description}
The parent-child relationship between general vertices in
$V_k(\omega)$ is defined similarly, which gives $V_k(\omega)$ a structure
of an abstract tree $G_k(\omega)$. It is actually an abstract Galton-Watson
tree whose offspring distribution is the distribution of the independent
sum of the random numbers of two types of children, namely $\Pi^{(k)}$.
\bigskip
For illustration, consider again the tree $\omega$ drawn in Figure 1, for
which ${\cal Y}_1(\omega)=5$. $G_1(\omega)$ is seen to be isomorphic to
the tree depicted in Figure 4.
\begin{figure}[h]
\caption{The tree $G_1(\omega)$}
\setlength{\unitlength}{1mm}
\begin{picture}(100,40)
\put(30,15){\makebox(20,10)[r]{$G_1(\omega)\cong$}}
\multiput(55,20)(16,8){2}{\circle*{3}}
\put(55,20){\line(2,1){16}}
\put(55,20){\line(2,-1){16}}
\put(71,12){\circle*{3}}
\put(71,12){\line(1,0){31}}
\multiput(87,12)(16,0){2}{\circle*{3}}
\end{picture}
\end{figure}
In Figure 5, it is shown how the tree $G_1(\omega)$ grows in $\omega$
from the 0th generation (the root) to the third generation.
\begin{figure}[h]
\caption{How $G_1(\omega)$ grows in $\omega$}
\setlength{\unitlength}{1mm}
\begin{picture}(200,80)(10,0)
\put(10,50){\line(2,1){7}}
\put(10,50){\circle*{1}}
\put(18,54){\circle{3}}
\put(10,15){\makebox(20,7)[l]{0th gen.}}
\put(40,50){\line(2,1){7}}
\put(40,50){\circle*{1}}
\put(48,54){\circle{3}}
\put(50,55){\line(2,1){13}}
\put(56,58){\circle*{1}}
\put(64,62){\circle{3}}
\put(40,50){\line(2,-1){7}}
\put(48,46){\circle{3}}
\put(40,15){\makebox(20,7)[l]{0th and 1st gen.}}
\put(80,50){\line(2,1){7}}
\put(80,50){\circle*{1}}
\put(88,54){\circle{3}}
\put(90,55){\line(2,1){13}}
\put(96,58){\circle*{1}}
\put(96,58){\line(2,-1){8}}
\put(104,54){\circle*{1}}
\put(104,54){\line(2,1){7}}
\put(112,58){\circle{3}}
\put(104,62){\circle{3}}
\put(80,50){\line(2,-1){7}}
\put(88,46){\circle{3}}
\put(80,15){\makebox(20,7)[l]{0th, 1st and}}
\put(80,8){\makebox(20,10)[l]{2nd gen.}}
\put(125,50){\line(2,1){7}}
\put(125,50){\circle*{1}}
\put(133,54){\circle{3}}
\put(135,55){\line(2,1){13}}
\put(141,58){\circle*{1}}
\put(141,58){\line(2,-1){8}}
\put(149,54){\circle*{1}}
\put(149,54){\line(2,1){7}}
\put(149,54){\line(2,-1){7}}
\put(157,50){\circle{3}}
\put(157,58){\circle{3}}
\put(149,62){\circle{3}}
\put(125,50){\line(2,-1){7}}
\put(133,46){\circle{3}}
\put(125,15){\makebox(20,7)[l]{0th, 1st, 2nd}}
\put(125,8){\makebox(20,10)[l]{and 3rd gen.}}
\end{picture}
\end{figure}
\subsection{Asymptotic behavior of the distribution of ${\cal Y}_k$}
By Theorem \ref{thm:2}, the analysis of the asymptotic behavior of
$P({\cal Y}_k=n)$ as $n\to\infty$ is essentially reduced to that of
$P(Z=n)$ with a proper choice of offspring distribution. Namely if we
let $\sigma_k$ be the radius of convergence of the power series $g_k(w)$
and if we define $b_k\in(0,\sigma_k]$ by (\ref{eqn:2-6}), that is
by the relation
$$\inf_{00$. Then $P({\cal Y}_k=n)>0$ only for those $n$ such that
$n\equiv 1$ {\rm (mod $d(\Pi^{(k)})$)}.
\medskip
(ii) $\limsup_{n\to\infty}P({\cal Y}_k=n)^{1/n}=g_k(b_k)/b_k$ .
\medskip
(iii) If $00\}
\cup\{j\geq k\ \vert\ p_{j+1}>0\}\right]\ .$$
\end{prop}
\noindent{\it Proof.}
Note that
$$d(\Pi^{(k)})=\max\{\ell\geq1\ \vert\ g_k(e^{\frac{2\pi}{\ell}i})=1\}\ .$$
On the other hand, $g_k(w)=1$ is equivalent to
$h_k(w)=1-\varphi_k(w)$, namely to the condition
$$\Gamma_k(w):=\sum_{j=0}^{k-1}p_jw^j+(p_k+p_{k+1})w^k+
\sum_{j=k+1}^{\infty}p_{j+1}w^{j+1}=1\ ,$$
and therefore
\begin{eqnarray*}
d(\Pi^{(k)})&=&\max\{\ell\geq1\ \vert\ \Gamma_k(e^{\frac{2\pi}{\ell}i})=1\} \\
&=&\left\{\begin{array}{rl}
g.c.d.\left[\{0\leq j\leq k\ \vert\ p_j>0\}\cup\{k\}\cup
\{j\geq k\ \vert\ p_{j+1}>0\}\right] \\
\quad \mbox{if}\ p_k+p_{k+1}>0 \\
\\
g.c.d.\left[\{0\leq j\leq k\ \vert\ p_j>0\}\cup
\{j\geq k\ \vert\ p_{j+1}>0\}\right] \\
\quad \mbox{if}\ p_k+p_{k+1}=0\ ,
\end{array}\right.
\end{eqnarray*}
which gives the desired result.
Now we shall give a condition for $01$. In this case, there is a
$\sigma_k\in(0,\rho)$ such that $\varphi_k(\sigma_k)=1$. This $\sigma_k$ is
the radius of convergence of the power series
$g_k(w)$ and we have $g_k(\sigma_k-)=\infty$.
Consequently $b_k\in(0,\sigma_k)$.
\item[{\it case 2.}] If $\varphi_k(\rho-)=1$, then $\sigma_k=\rho<\infty$
and $g_k(\sigma_k)=\infty$. In this case also, one has $b_k\in(0,\sigma_k)$.
\item[{\it case 3.}] When $0<\varphi_k(\rho-)<1$, one has
$\sigma_k=\rho<\infty$ and $g_k(\sigma_k-)<\infty$.
\item[{\it case 4.}] Finally when $\varphi_k(\rho-)=0$, then
$g_k(w)=f(w)$ and we trivially have $b_k=a$.
\end{description}
\bigskip
In the last two cases, both $b_k<\sigma_k$ and $b_k=\sigma_k$ are
possible.
\begin{prop}
$00\ .$$
\end{prop}
\noindent{\it Proof.}
Define
$$\Delta_k(z):=(z-f(z))h'_k(z)-(1-f'(z))h_k(z)\ .$$
Then
\begin{equation}
zg'_k(z)-g_k(z)=\frac{\Delta_k(z)}{(1-\varphi_k(z))^2}\ ,
\label{eqn:15}
\end{equation}
and after some computation we get
\begin{eqnarray}
\Delta_k(z)&=&\sum_{\ell=0}^k(\ell-1)p_{\ell}z^{\ell}+
\sum_{j=k+1}^{\infty}\sum_{\ell=0}^k(j-\ell)p_jp_{\ell}z^{j+\ell-1} \nonumber\\
&=&\sum_{\ell=1}^k(\ell-1)p_{\ell}z^{\ell}+
\sum_{\ell=1}^k\sum_{j=k+1}^{\infty}(j-\ell)p_jp_{\ell}z^{j+\ell-1}+\nonumber\\
& &\qquad +p_0\left(\sum_{j=k+1}^{\infty}jp_jz^{j-1}-1\right)\ ,
\label{eqn:16}
\end{eqnarray}
which shows in particular $\Delta'_k(z)>0$ for $z>0$.
From the preliminary consideration preceeding the proposition
and the condition (\ref{eqn:2-5})
(see \S2) applied to $g_k(z)$, we first see that $00$.
Hence if $00\ .$$
On the other hand, in case
$\varphi_k(\rho-)\geq1$, we have $\varphi_k(\sigma_k)=1$, namely
$$\sum_{j=k+1}^{\infty}p_j\sigma_k^{j-1}=1\ .$$
Since $p_0+p_1<1$, this implies
$$\sum_{j=k+1}^{\infty}jp_j\sigma_k^{j-1}>1\ ,$$
so that $\Delta_k(\sigma_k)>0$ by (\ref{eqn:16}). Since $\rho\geq\sigma_k$,
this implies $\Delta_k(\rho-)\geq\Delta_k(\sigma_k)>0$.
Conversely suppose $\Delta_k(\rho-)>0$. If, in addition,
$\varphi_k(\rho-)\geq1$, then one has $00\ ,$$
namely $0k$, then $g_k(z)=f(z)$ and we have
equality also in the second inequalty. In all the other cases, the
inequalities are strict.
Finally it holds that
\begin{equation}
\lim_{k\to\infty}\frac{g_k(b_k)}{b_k}=\frac{f(a)}{a}\ .
\label{eqn:18}
\end{equation}
\end{prop}
\noindent{\it Proof.}
First note that
\begin{equation}
g_{k+1}(z)-g_k(z)=\frac{z(z-f(z))(h_{k+1}(z)-h_k(z))}
{(z-f(z)+h_k(z))(z-f(z)+h_k(z))}\ .
\label{eqn:19}
\end{equation}
For the moment, we suppose that there exists $q_1$ and $q_2$ such that
$f(q_i)=q_i$, $i=1,2$, and that $00$,
$g_k(z)/z>(f(z)/z)-\epsilon$ holds for all $z\in[q_1,q_2]$ and for all
sufficiently large $k$. Taking $z=b_k$ and $z=a$, we obtain
$$\frac{f(a)}{a}\geq\frac{g_k(a)}{a}\geq\frac{g_k(b_k)}{b_k}
>\frac{f(b_k)}{b_k}-\epsilon\geq\frac{f(a)}{a}-\epsilon$$
for large $k$. This shows $\lim_{k\to\infty}g_k(b_k)/b_k=f(a)/a$.
Now suppose $f(z)$ is supercritical and let $q$ be the extinction
probability: $f(q)=q$. Then we can take $q_1=q$, $q_2=1$ and (\ref{eqn:17})
and (\ref{eqn:18}) are proved in this case. When $f(z)$ is
critical, or subcritical with $\rho=1$, we have
$$a=f(a)=b_k=g_k(b_k)=1$$
and there is nothing to be proved. Next consider the case where
$f(z)$ is sub-critical (i.e. $f'(1)<1$), $\rho>1$, but $f(z)1$, and that $p_{k+1}>0$. Then $h_{k+1}(z)>h_k(z)$ for $z>0$ and
hence we have $g_{k+1}(z)>g_k(z)$ on $(q_1,q_2)$ or on $(1,\rho)$.
Thus
$$\frac{g_{k+1}(b_{k+1})}{b_{k+1}}>\frac{g_k(b_{k+1})}{b_{k+1}}
\geq\frac{g_k(b_k)}{b_k}$$
and the (first) inequalty is strict.
\section{The joint distribution of $Z$ and ${\cal Y}_k$}
\subsection{Generality}
For complex numbers $u$, $v_j$ ($j=0,1,\ldots$) satisfying
$\vert u\vert,\vert v_j\vert\leq1$, let
\begin{equation}
w:=G(u;v_0,v_1,\ldots):=\mathbf{E}\left[Z<\infty;\ u^Z\prod_{j=0}
^{\infty}v_j^{Y_j}\right]
\label{eqn:20}
\end{equation}
be the joint probability generating function of $Z,Y_0,Y_1,\ldots$.
Here $\prod_{j=0}^{\infty}v_j^{Y_j}$ is
actually a finite product because of $\sum_{j=0}^{\infty}Y_j=Z<\infty$.
Due to the relations (\ref{eqn:2-1}) and
\begin{equation}
Y_k(\omega)=1_{\{\nu_{\phi}(\omega)=k\}}+\sum_{j=1}^{\nu_{\phi}(\omega)}
Y_k(T_j(\omega))\ ,
\label{eqn:21}
\end{equation}
we can proceed, using the formula of Neveu (page 202 of \cite{N}),
\begin{eqnarray*}
w&=&\mathbf{E}\left[Z<\infty;\ u^{1+\sum_{j=1}^{\nu_{\phi}}Z\circ T_j}
\prod_{k=0}^{\infty}v_k^{1_{\{\nu_{\phi}=k\}}+
\sum_{j=1}^{\nu_{\phi}}Y_k\circ T_j}
\right] \\
&=&u\mathbf{E}\left[\left(\prod_{j=1}^{\nu_{\phi}}1_{\{Z<\infty\}}\circ T_j
\right)\left(\prod_{k=0}^{\infty}v_k^{1_{\{\nu_{\phi}=k\}}}\right)
\left\{\prod_{j=1}^{\nu_{\phi}}\left(u^Z\prod_{k=0}^{\infty}v_k^{Y_k}
\right)\circ T_j\right\} \right] \\
&=&u\mathbf{E}\left[\prod_{k=0}^{\infty}v_k^{1_{\{\nu_{\phi}=k\}}}
\mathbf{E}\left[\left.\prod_{j=1}^{\nu_{\phi}}\left(1_{\{Z<\infty\}}u^Z
\prod_{k=0}^{\infty}v_k^{Y_k}\right)\circ T_j\right\vert{\cal F}_1\right]
\right] \\
&=&u\mathbf{E}\left[\prod_{k=0}^{\infty}v_k^{1_{\{\nu_{\phi}=k\}}}
\prod_{j=1}^{\nu_{\phi}}\mathbf{E}\left[Z<\infty;\ u^Z\prod_{k=0}^{\infty}
v_k^{Y_k} \right] \right] \\
&=&u\mathbf{E}\left[\prod_{k=0}^{\infty}v_k^{1_{\{\nu_{\phi}=k\}}}
w^{\nu_{\phi}}\right] \\
&=&u\sum_{k=0}^{\infty}p_kv_kw^k\ .
\end{eqnarray*}
Thus if we define
$$\Phi(w)=\Phi(w;v_0,v_1,\ldots):=\sum_{k=0}^{\infty}p_kv_kw^k\ ,$$
then $w$ is a solution of the equation $w=u\Phi(w)$. If we assume
$v_0\ne0$, then $\Phi(0)=p_0v_0\ne0$, and we can again apply Lagrange
inversion, to obtain the formula
\begin{equation}
\mathbf{E}\left[Z=n;\ \prod_{k=0}^{\infty}v_k^{Y_k}\right]=
\frac1{2\pi in}\oint\left\{\frac{\Phi(w)}{w}\right\}^ndw
\label{eqn:22}
\end{equation}
for the coefficients of the power series
$$w=\sum_{n=1}^{\infty}\mathbf{E}
\left[Z=n;\ \prod_{k=0}^{\infty}v_k^{Y_k}\right]u^n\ .$$
Now if $Z(\omega)=n$, then we have $Y_k(\omega)=0$ for $k\geq n$. Moreover
$\sum_{k=0}^{n-1}Y_k(\omega)=1+\sum_{k=1}^{n-1}kY_k(\omega)=n$.
Hence for $r\geq1$, $0\leq k_1<\cdotsn\ ,
\end{array}\right.$$
for non-negative integers $n$ and $r$,
so that in particular $n^{[0]}=1$ and $n^{[1]}=n$ for any $n\geq0$,
and
$r_k>0$ only for finite number of $k$'s. More specifically, we shall
assume $r_k=0$ for $k\geq n$ in view of (\ref{eqn:23-0}), and set
$r=\sum_{k=0}^{n-1}r_k$. Now it is easy to compute, using (\ref{eqn:22}),
\begin{eqnarray}
M(n;r_0,r_1,\ldots)
%\nonumber\\
&=&\left.\frac{\partial^r}
{\partial v_0^{r_0}\partial v_1^{r_1}\cdots\partial v_{n-1}^{r_{n-1}}}
\mathbf{E}\left[Z=n;\ \prod_{k\geq0}v_k^{Y_k}\right]\right
\vert_{v_0=v_1=\cdots=1} \nonumber\\
&=&\frac1{2\pi in}\oint\frac1{z^n}\left.\frac{\partial^r}
{\partial v_0^{r_0}\partial v_1^{r_1}\cdots\partial v_{n-1}^{r_{n-1}}}
\Phi(z;v_0,v_1\ldots)^n\right\vert_{v_0=v_1=\cdots=1}dz \nonumber\\
&=&\frac1{2\pi in}\oint\frac1{z^n}n^{[r]}f(z)^{n-r}
\prod_{k=0}^{n-1}p_k^{r_k}z^{kr_k}dz \nonumber\\
&=&\frac{n^{[r]}}{2\pi in}\left(\prod_{k=0}^{n-1}p_k^{r_k}\right)
\oint\frac{f(z)^{n-r}}{z^{n-s}}\ dz\ ,
\label{eqn:factorialmoment}
\end{eqnarray}
where we have set $s=\sum_{k=0}^{n-1}kr_k$. This formula may be used
in obtaining means and covariances of $Y_k$'s under the conditional
distribution $P(\bullet\vert Z=n)$. Moreover when Condition A holds,
we can apply the analysis in \S2.2 to the above formula, to obtain
an asymptotic expansion of $M(n;r_0,r_1,\ldots)$ as $n\to\infty$.
For example, we obtain an asymptotic expression as $n\to\infty$ for the
expectation $\mathbf{E}_n(Y_k)$,
variance $\mathbf{Var}_n(Y_k)$ and covariance
$\mathbf{Cov}_n(Y_k,Y_{k'})$ ($k\ne k'$)
of $Y_k$'s under the conditional distribution $P(\bullet\vert Z=n)$
as follows:
\begin{equation}
\mathbf{E}_n(Y_k)=\rho_kn+{\cal O}(1)\ ;
\label{eqn:ex}
\end{equation}
\begin{equation}
\mathbf{Var}_n(Y_k)=\frac{\rho_k}{\kappa_2}[(1-\rho_k)\kappa_2-
(k-1)^2\rho_k]n+{\cal O}(1)\ ;
\label{eqn:var}
\end{equation}
\begin{equation}
\mathbf{Cov}_n(Y_k,Y_{k'})=-\frac{\rho_k\rho_{k'}}{\kappa_2}
[\kappa_2+(k-1)(k'-1)]n+{\cal O}(1)\ ,
\label{eqn:cov}
\end{equation}
where as before $\rho_k:=p_ka^k/f(a)$, and $\kappa_2$ is the variance
of the probability distribution $\Pi_a:=\{\rho_k\}_{k\geq0}$.
\bigskip
Let us now discuss several examples. See \cite{A} for related topics.
\subsection{Example 1: Geometric offspring distribution}
Suppose $\Pi=\{p_k\}_{k=0}^{\infty}$ is the geometric
distribution with parameter $p$, namely suppose that
$p_k=(1-p)p^k$, $k=0,1,2,\ldots$, for some $00$ and $b_k>0$ for some $k\geq2$, we
let
$$p_k(\theta)=\frac{b_k\theta^k}{B(\theta)}\ ,\ k=0,1,2,\ldots$$
for $0<\theta0$, $p_0(\theta)+p_1(\theta)<1$, and
we have the following proposition.
\begin{prop}
Let $P_{\theta}$ be the probability measure for the Galton-Watson tree
with offspring distribution $\Pi(\theta)$.
Then, the total progeny $Z$
is a sufficient statistics for the statistical model
$(\Omega,{\cal F},\{P_{\theta}(\bullet\vert Z<\infty)\}_{\theta\in(0,R)})$
in the sense that
for any $n\geq1$, the conditional distribution
$P_{\theta}(\bullet\vert Z=n)$ does not depend on $\theta$.
\end{prop}
\noindent{\it Proof.}
The generating function of $\Pi(\theta)$ is given by
$B(\theta z)/B(\theta)$. Hence by (\ref{eqn:2-3}),
$$P(Z=n)=\frac1{2\pi in}\oint\frac1{z^n}\left(\frac{B(\theta z)}{B(\theta)}
\right)
^ndz=\frac1{2\pi in}\frac{\theta^{n-1}}{B(\theta)^n}\oint\frac{B(w)^n}{w^n}
dw\ .$$
On the other hand, for a tree $\omega$ with $Z(\omega)=n$,
$$P(\{\omega\})=\prod_{u\in\omega}p_{\nu_{u}(\omega)}(\theta)
=\frac{\theta^{n-1}}{B(\theta)^n}\prod_{u\in\omega}b_{\nu_u(\omega)}\ ,$$
so that by dividing, the factors involving $\theta$ cancel out in
$P(\{\omega\}\vert Z=n)$.
\section{The weak law of large numbers and the central limit theorem
for the distribution of $\{Y_k\}$, conditioned on $Z$}
In this section, we prove two conditional limit theorems for $\{Y_k\}$,
namely the assertions (i) and (ii) of Theorem 3 below. Although the assertion
(i), the weak law of large numbers, is actually due to Otter (Theorem 6
in \cite{O}), we shall give an alternative proof, which will be completed
almost simultaneously with the proof of the central limit theorem (ii).
\bigskip
\begin{thm}
Suppose Condition A holds. Then the following limit theorems hold, where
we let $n\to\infty$ keeping $n\equiv1$ {\rm (mod $d(\Pi)$)}:
\bigskip
\noindent
(i) the weak law of large numbers: for any $k\geq0$,
$$P\left(\left.\frac{Y_k}{n}\in\bullet\ \right\vert\ Z=n\right)
\longrightarrow\delta_{\rho_k}(\bullet)\ ,$$
where $\delta_b(\cdot)$ is the point mass concentrated on $b$. Here
$\{\rho_k\}_{k\geq0}$ is the probability distribution on $\mathbf{Z}_+$
defined by $\rho_k=p_ka^k/a^k$.
\bigskip
\noindent
(ii) the central limit theorem: for any finite subset $A$ of $\mathbf{Z}_+$,
$$P\left(\left.\left\{\sqrt{n}\left(\frac{Y_k}{n}-\rho_k
\right)\right\}_{k\in A}\in\bullet\ \right\vert\ Z=n\right)
\longrightarrow N_A(0,V_A)\ ,$$
where $N_A(0,V_A)$ is the $\vert A\vert$-dimensional Gaussian distribution
with mean $0$, and with the covariance matrix $V_A$ determined from the
quadratic form
\begin{eqnarray*}
V(\{t_k\})
&=&\sum_{k\in A}t_k^2\rho_k
-\left(\sum_{k\in A}t_k\rho_k\right)^2
-\frac1{\sum_{k\geq2}k(k-1)\rho_k}\left
(\sum_{k\in A}kt_k\rho_k-\sum_{k\in A}t_k\rho_k\right)^2 \ .
\end{eqnarray*}
Here $V_A$ is strictly positive definite if and only if $A\subset S$ and
$\vert S\setminus A\vert\geq2$, where we let $S:=\{k\in\mathbf{Z}_+;p_k>0\}$.
\end{thm}
\bigskip
\noindent
{\em Remark.}
The special case $A=\{0\}$ of the central limit theorem is
known to combinatorialists. See e.g. Theorem 12 of \cite{Dr}.
On the other hand, under the condition that $f(z)$ be entire, Dembo,
M\"orters and Sheffield (\cite{De}) proved a general large deviation principle
which reduces to the large deviation principle corresponding to the
law of large numbers (i).
(Set ${\cal X}=\mbox{singleton}$ in Theorem 2.2 of \cite{De}.)
For other types of conditional limit theorems considered on the event
$\{Z=n\}$, see e.g. \cite{Ken} and \cite{Kes}.
\bigskip
\noindent{\em Proof.}
Take a real sequence $\{t_k\}_{k\geq0}$, where $t_k\ne0$
for only finitely many $k$'s, and let $v_k=e^{\zeta t_k}$ with
$\zeta\in\mathbf{C}$ in the formula (\ref{eqn:22}). Then we obtain
\begin{equation}
\mathbf{E}\left[Z=n;\ \exp\left(\zeta\sum_{k\geq0}t_kY_k\right)\right]
=\frac1{2\pi in}\oint\exp\{nh(z,\zeta)\}dz\ ,
\label{eqn:5-1}
\end{equation}
where we let
$$h(z,\zeta):=\log\left\{\frac{\Phi(z,\zeta)}{z}\right\}\quad
\mbox{and}\quad \Phi(z,\zeta):=\sum_{k\geq0}p_ke^{\zeta t_k}z^k\ .$$
If we further define
\begin{eqnarray*}
M(z,\zeta)&:=&\sum_{k\geq1}kp_ke^{\zeta t_k}z^k-
\sum_{k\geq0}p_ke^{\zeta t_k}z^k \\
&=&z\frac{\partial}{\partial z}\Phi(z,\zeta)-\Phi(z,\zeta)\ ,
\end{eqnarray*}
then we get
$$\frac{\partial}{\partial z}h(z,\zeta)=\frac{M(z,\zeta)}{z\Phi(z,\zeta)}\ .$$
In order to apply the saddle point approximation to the integral in
(\ref{eqn:5-1}), we need to know the zero of the function
$\partial h/\partial z$, or equivalently we need to solve the equation
$M(z,\zeta)=0$ with respect to $z$. Since
$\Phi(z,0)=f(z)$, we have $M(a,0)=af'(a)-f(a)=0$. On the other hand, we have
$(\partial M/\partial z)(a,0)=af^{\prime\prime}(a)>0$. Hence by the
implicit function theorem, there is a unique analytic function $a(\zeta)$,
which is defined in a neighbourhood of the origin, such that
$a(0)=a$ and that $M(a(\zeta),\zeta)=0$.
Now if we take the contour $\vert z\vert=\vert a(\zeta)\vert$ in the integral
in (\ref{eqn:22}), and if we assume $n\equiv1$ (mod $d(\Pi)$), the as in
(\ref{eqn:2-8}), we obtain
\begin{equation}
\mathbf{E}\left[Z=n;\ \prod_{k\geq0}\exp(\zeta t_kY_k)\right]
=\frac{a(\zeta)d}{2\pi n}\int_{-\pi/d}^{\pi/d}\exp\{n\psi(\theta,\zeta)\}
e^{i\theta}d\theta\ ,
\label{eqn:5-2}
\end{equation}
where we have set
$$\psi(\theta,\zeta):=h(a(\zeta)e^{i\theta},\zeta)
=\log\left[\frac{\Phi(a(\zeta)e^{i\theta},\zeta)}{a(\zeta)e^{i\theta}}
\right]\ .$$
For this function $\psi(\theta,\zeta)$, the following assertion can be
easily verified:
\begin{description}
\item[I] As $\zeta\to0$ in $\mathbf{C}$, $\psi(\theta,\zeta)$, as well
as all its derivatives with respect to $\theta$, converges uniformly
to those of
$$\psi(\theta):=h(ae^{i\theta},0)=
\log\left[\frac{f(ae^{i\theta})}{ae^{i\theta}}\right]\ .$$
\item[II] In particular,
$$\psi(0,\zeta)=\log\left[\frac{\Phi(a(\zeta),\zeta)}{a(\zeta)}\right]
\longrightarrow\log\left[\frac{f(a)}{a}\right]\ ,$$
as $\zeta\to0$.
\item[III] $$\left.\frac{\partial}{\partial \theta}\psi(\theta,\zeta)
\right\vert_{\theta=0}
=ia(\zeta)\frac{\partial h}{\partial\zeta}(a(\zeta),\zeta)=0\ .$$
\item[IV] One has
$$-K(\zeta):=\left.\frac{\partial^2}{\partial\theta^2}\psi(\theta,\zeta)
\right\vert_{\theta=0}=-a(\zeta)^2\frac{\partial^2h}{\partial z^2}
(a(\zeta),\zeta)\ ,$$
and as $\zeta\to0$,
$$-K(\zeta)\
\longrightarrow-\frac{a^2f^{\prime\prime}(a)}{f(a)}
=-K<0\ .$$
\item[V] By I, we can write
$$\psi(\theta,\zeta)=\psi(0,\zeta)-\frac12 K(\zeta)\theta^2+
\theta^3\beta(\theta,\zeta)\ ,$$
where $\beta(\theta,\zeta)$ is analytic and uniformly bounded
in $(\theta,\zeta)$.
\item[VI] By III, IV and V, we can choose positive constants $\gamma$,
$\delta$ and $\eta$ so that
$$\mathbf{Re}\psi(\theta,\zeta)\leq\mathbf{Re}\psi(0,\zeta)-\eta\theta^2$$
holds for $\vert\theta\vert\leq\delta$ and $\vert\zeta\vert\leq\gamma$.
\item[VII] From I,II and VI, we infer that if $\vert\zeta\vert$ is
sufficiently small, then
$$\vert\Phi(a(\zeta)e^{i\theta},\zeta)/a(\zeta)\vert
=\exp(\mathbf{Re}\psi(\theta,\zeta))$$
takes its maximum value at $\theta=0$ and that if
$0<\vert\theta\vert\leq \pi/d$,
$$\left\vert\frac{\Phi(a(\zeta)e^{i\theta},\zeta)}{a(\zeta)}\right\vert
<\left\vert\frac{\Phi(a(\zeta),\zeta)}{a(\zeta)}\right\vert\ .$$
\item[VIII] Let $\Delta_{\delta}$ be defined by (\ref{eqn:2-81}).
From I and VI, if we take
$0<\epsilon<\frac13\{(f(a)/a)-\Delta_{\delta}\}$, then for $\zeta$
sufficiently near to $0$, we have
$$\Delta_{\zeta,\delta}:=\sup_{\delta\leq\vert\theta\vert\leq\pi/d}
\left\vert\frac{\Phi(a(\zeta)e^{i\theta},\zeta)}{a(\zeta)}\right\vert
<\Delta_{\delta}+\frac{\epsilon}3<\frac{f(a)}{a}-\frac{\epsilon}3
<\left\vert\frac{\Phi(a(\zeta),\zeta)}{a(\zeta)}\right\vert\ .$$
\end{description}
Now we can perform an analysis similar to that in \S2.2. First we rewrite
(\ref{eqn:5-2}) as
\begin{eqnarray}
& &\mathbf{E}
\left[Z=n;\ \exp\left(\sum_{k\geq0}\zeta t_kY_k\right)\right] \nonumber \\
&=&\frac{a(\zeta)d}{2\pi n}\left(\frac{\Phi(a(\zeta),\zeta)}{a(\zeta)}
\right)^n\int_{-\delta}^{\delta}\exp\left\{-\frac n2 K(\zeta)\theta^2+n\theta^3
\beta(\theta,\zeta)+i\theta\right\}d\theta \nonumber\\
& &\qquad\quad+{\cal O}\left(\frac1n\Delta_{\zeta,\delta}^n\right)\ .
\label{eqn:5-3}
\end{eqnarray}
If we introduce
$$P_{\zeta}(\omega,\theta):=\exp(i\theta+\omega\beta(\theta,\zeta))=
\sum_{\ell,m\geq0}c_{\ell m}(\zeta)\omega^{\ell}\theta^m$$
and
$$Q_{\zeta}(\omega,\theta):=c_{00}(\zeta)+c_{10}(\zeta)\omega+
c_{01}(\zeta)\theta\ ,$$
then we have
$$\vert P_{\zeta}(\omega,\theta)-Q_{\zeta}(\omega,\theta)\vert
={\cal O}(\vert \omega\vert^2)+{\cal O}(\vert \theta\vert^2)\ ,$$
where the estimate ${\cal O}(\cdot)$ is valid uniformly in $\zeta$
sufficiently near to $0$. Now
replace $\delta$ in the limit of integration in (\ref{eqn:5-3}) by
$\tau_n:=n^{-1/3}$, and then replace $\exp(i\theta+n\theta^3
\beta(\theta,\zeta))$ by $Q_{\zeta}(n\theta^3,\theta)$. The error
committed by these procedures are estimated as in \S2.2 and we obtain
\begin{eqnarray*}
\mathbf{E}\left[Z=n;\ \exp\left(\sum_{k\geq0}\zeta t_kY_k\right)\right]
&=&\frac{a(\zeta)d}{2\pi n}\left(\frac{\Phi(a(\zeta),\zeta)}{a(\zeta)}
\right)^n\times \\
& &\times
\left[\sum_{\ell+m\leq1}c_{\ell m}(\zeta)n^{\ell}\int_{-\tau_n}^{\tau_n}
\exp(-\frac n2K(\zeta)\theta^2)\theta^{3\ell+m}d\theta
+{\cal O}(n^{-3/2})\right]\ .
\end{eqnarray*}
Finally we extend the integration to $(-\infty,\infty)$, with a small
error which is absorbed in the term ${\cal O}(n^{-3/2})$. We thus arrive at
\begin{eqnarray*}
& &\mathbf{E}\left[Z=n;\ \exp\left(\sum_{k\geq0}\zeta t_kY_k\right)\right] \\
%&=&\frac{a(\zeta)d}{2\pi n}\left(\frac{\Phi(a(\zeta),\zeta)}{a(\zeta)}
%\right)^n\left[\sum_{\ell+m\leq1}c_{\ell m}(\zeta)n^{\ell}
%\int_{-\tau_n}^{\tau_n}\exp(-\frac n2 K(\zeta)\theta^2)\theta^{3\ell+m}d\theta
%+{\cal O}(n^{-3/2})\right] \\
&=&\frac{a(\zeta)d}{n}\left(\frac{\Phi(a(\zeta),\zeta)}{a(\zeta)}
\right)^n\sqrt{\frac1{2\pi nK(\zeta)}}\ (1+{\cal O}(n^{-3/2}))\ .
\end{eqnarray*}
Note that the integrals for $\ell+m=1$ vanish because of symmetry, and
that the estimate ${\cal O}(n^{-3/2})$ of the error is uniform in $\zeta$.
Combining this result with Theorem 1, or rather Otter's theorem, we get
\begin{eqnarray*}
\mathbf{E}\left[\left.\exp\left(\sum_{k\geq0}\zeta t_kY_k\right)
\right\vert Z=n\right] &=&
\frac{a(\zeta)\left(\frac{\Phi(a(\zeta),\zeta)}{a(\zeta)}\right)^n
\sqrt{\frac1{K(\zeta)}}\ (1+{\cal O}(n^{-3/2}))}
{a\left(\frac{f(a)}{a}\right)^n\sqrt{\frac{f(a)}{a^2f^{\prime\prime}(a)}}
(1+{\cal O}(n^{-3/2})}\ .
\end{eqnarray*}
If we take a sequence $\zeta_n\to0$,
then $K(\zeta_n)\to a^2f^{\prime\prime}(a)/f(a)$ and $a(\zeta_n)\to a$.
Hence we finally obtain
\begin{equation}
\mathbf{E}\left[\left.\exp\left(\sum_{k\geq0}\zeta_n t_kY_k\right)
\right\vert Z=n\right]
\sim
\left\{\frac{a}{f(a)}\frac{\Phi(a(\zeta_n),\zeta_n)}{a(\zeta_n)}\right\}^n\ ,
\label{eqn:5-4}
\end{equation}
where $n\to\infty$ keeping $n\equiv1$ (mod $d(\Pi)$).
Now let us take $\zeta_n=-1/n$ and suppose $t_k\geq0$. Noting
$f'(a)=f(a)/a$, it is easy to compute
$$\log\Phi\left(a(-1/n),-1/n\right)=\log f(a)-
\frac1n\left\{\frac1{f(a)}\sum_{k\geq0}p_kt_ka^k+\frac{a'(0)}{a}\right\}
+{\cal O}\left(n^{-2}\right)$$
and
$$\log a(-1/n)=\log a-\frac1n\frac{a'(0)}{a}+{\cal O}(n^{-2})\ .$$
Thus we can conclude from (\ref{eqn:5-4})
$$\mathbf{E}\left[\left.\exp\left(-\sum_{k\geq0}t_k\frac{Y_k}n\right)
\right\vert Z=n\right]
\longrightarrow\exp\left\{-\sum_{k\geq0}\frac{p_ka^k}{f(a)}t_k\right\}\ ,$$
completing the proof of (i).
\bigskip
Let us remark that $\{\rho_k\}_{k\geq0}:=\{p_ka^k/f(a)\}_{k\geq0}$ is a
probability distribution on $\mathbf{Z}_+$ with mean $1$:
$$\sum_{k\geq1}k\rho_k=\frac1{f(a)}\sum_{k\geq1}kp_ka^k
=\frac{af'(a)}{f(a)}=1\ .$$
\bigskip
In order to prove the assertion (ii), we expand $\log[\Phi(a(\zeta),\zeta)]$
and $\log a(\zeta)$ to the second order terms for small $\zeta$, to obtain
\begin{eqnarray*}
& &\log\left[\frac{a}{f(a)}\frac{\Phi(a(\zeta),\zeta)}{a(\zeta)}\right] \\
& &\\
&=&\frac1{f(a)}\left(\frac{\partial \Phi}{\partial \zeta}(a,0)\right)\zeta+ \\
& &\qquad+\left[\frac1{2f(a)}\left(f^{\prime\prime}(a)a^{\prime}(0)^2+
\frac{\partial^2\Phi}{\partial \zeta^2}(a,0)+
2\frac{\partial^2\Phi}{\partial\zeta\partial z}(a,0)a'(0)\right)\right. \\
& &\\
& &\qquad\qquad\left.-\frac1{2f(a)^2}\left(f'(a)a'(0)+
\frac{\partial\Phi}{\partial\zeta}(a,0)\right)^2+\frac12\frac{a'(0)^2}{a^2}
\right]\zeta^2+{\cal O}(\zeta^3)\ .
\end{eqnarray*}
On the other hand, differentiating $M(a(\zeta),\zeta)=0$, we get
$$a'(0)=-\frac1{af^{\prime\prime}(a)}\left\{a
\frac{\partial^2\Phi}{\partial\zeta\partial z}(a,0)-
\frac{\partial \Phi}{\partial \zeta}(a,0)\right\}\ ,$$
which, inserted in the above formula, gives
\begin{eqnarray*}
& &\log\left[\frac{a}{f(a)}\frac{\Phi(a(\zeta),\zeta)}{a(\zeta)}\right] \\
& &\\
&=&\frac1{f(a)}\left(\frac{\partial \Phi}{\partial \zeta}(a,0)\right)\zeta+ \\
& &\qquad+\left[-\frac{f^{\prime\prime}(a)}{2f(a)}a'(0)^2+
\frac1{2f(a)}\frac{\partial^2\Phi}{\partial \zeta^2}(a,0)-
\frac1{2f(a)^2}\left(\frac{\partial \Phi}{\partial \zeta}(a,0)\right)^2
\right]\zeta^2+{\cal O}(\zeta^3)\ .
\end{eqnarray*}
Letting $t_k\in\mathbf{R}$ and $\zeta=i/\sqrt{n}$ in (\ref{eqn:5-4}),
we finally obtain
\begin{eqnarray*}
& &\lim_{n\to\infty}\mathbf{E}\left[\left.\exp\left\{i\sum_{k\geq0}t_k\sqrt{n}
\left(\frac{Y_k}{n}-\frac{p_ka^k}{f(a)}\right)\right\}\right\vert\
Z=n\right] \\
&=&\lim_{n\to\infty}\exp\left\{-i\sqrt{n}\sum_{k\geq0}t_k
\frac{p_ka^k}{f(a)}\right\}
\left\{\frac{a}{f(a)}\frac{\Phi(a(i/\sqrt{n}),i/\sqrt{n})}{a(i/\sqrt{n})}
\right\}^n \\
&=&\lim_{n\to\infty}\exp\left\{-n\frac1{f(a)}\left(
\frac{\partial\Phi}{\partial\zeta}(a,0)\right)\frac{i}{\sqrt{n}}\right\}
\left\{\frac{a}{f(a)}\frac{\Phi(a(i/\sqrt{n}),i/\sqrt{n})}{a(i/\sqrt{n})}
\right\}^n \\
&=&\exp\left[\frac{f^{\prime\prime}(a)}{2f(a)}a'(0)^2
-\frac1{2f(a)}\frac{\partial^2\Phi}{\partial\zeta^2}(a,0)
+\frac1{2f(a)^2}\left(\frac{\partial\Phi}{\partial\zeta}(a,0)\right)^2\right]\\
&=&\exp\left[-\frac12 V(\{t_k\})\right]\ ,
\end{eqnarray*}
where we have set
\begin{eqnarray*}
V(\{t_k\})
&=&\frac1{f(a)}\sum_{k\geq0}p_kt_k^2a^k
-\frac1{f(a)^2}\left(\sum_{k\geq0}p_kt_ka^k\right)^2 \\
& &\qquad
-\frac1{a^2f(a)f^{\prime\prime}(a)}\left
(\sum_{k\geq1}kp_kt_ka^k-\sum_{k\geq0}p_kt_ka^k\right)^2 \ .
\end{eqnarray*}
In terms of $\rho_k$ introduced above, this can be expressed as
\begin{eqnarray*}
V(\{t_k\})
&=&\sum_{k\geq0}t_k^2\rho_k
-\left(\sum_{k\geq0}t_k\rho_k\right)^2
-\frac1{\sum_{k\geq2}k(k-1)\rho_k}\left
(\sum_{k\geq1}kt_k\rho_k-\sum_{k\geq0}t_k\rho_k\right)^2 \ .
\end{eqnarray*}
Now let $X$ be a $\mathbf{Z}_+$-valued random variable with distribution
$\{\rho_k\}$ and let the function $T:\mathbf{Z}_+\mapsto\mathbf{R}$
be defined by $T(k)=t_k$. Then $\mathbf{E}[X]=1$ and
$$\sum_{k\geq2}k(k-1)\rho_k=\mathbf{E}[X(X-1)]=\mathbf{E}[(X-1)^2]>0$$
because the distribution $\{p_k\}$ is not degenerate to a point
by our basic assumption, so that
\begin{eqnarray*}
& &\left(\sum_{k\geq2}k(k-1)\rho_k\right)V(\{t_k\}) \\
&=&\mathbf{E}[(X-1)^2]\left\{\mathbf{E}[T(X)^2]-\mathbf{E}[T(X)]^2\right\}
-\left\{\mathbf{E}[XT(X)]-\mathbf{E}[T(X)]\right\}^2 \\
&=&\mathbf{E}[(X-1)^2]\mathbf{E}[\{T(X)-\mathbf{E}[T(X)]\}^2]
-\mathbf{E}[(X-1)\{T(X)-\mathbf{E}[T(X)]\}]^2\ ,
\end{eqnarray*}
which is actually non-negative by Schwarz's inequality applied to random
variables $X-1$ and $T(X)-\mathbf{E}[T(X)]$.
Now suppose $A\subset S$, $A\ne\emptyset$ and $\vert S\setminus A\vert\geq2$.
Suppose further that for some $\lambda\in\mathbf{R}$, the relation
$$T(X)-\mathbf{E}[T(X)]=\lambda(X-1),\quad \mbox{a.s.}$$
holds, where we assume
$T(k)=t_k=0$ for $k\notin A$. Then if $\ell\in S\setminus A$,
one has $-\mathbf{E}[T(X)]=\lambda(X-1)$. But in case
$\vert S\setminus A\vert\geq2$,
this is possible only if $\lambda=0$ . Thus the inequality
must be strict in the above mentioned Schwarz's inequality, unless
$t_k=0$ for all $k\in A$. Thus the limiting Gaussian distribution of
$\{\sqrt{n}(n^{-1}Y_k-\rho_k)\}_{k\in A}$ conditioned on $\{Z=n\}$ is
non-degenerate.
Conversely suppose $A\setminus S\ne\emptyset$. Since $Y_k=0$, a.s.
for $k\notin S$, the distribution of $\{Y_k\}_{k\in A}$ is already degenerate.
If, on the other hand, $A=S\setminus\{\ell\}$ for some $\ell\in S$, then
since the relations $\sum_{k\in S}Y_k=Z$ and $\sum_{k\in S}kY_k=Z-1$ yields
$$\sum_{k\in S\setminus\{\ell\}}(\ell-k)Y_k=(\ell-1)Z+1\ ,$$
the conditional distribution $P(\{\sqrt{n}(n^{-1}Y_k-\rho_k)\}_{k\in A}\in
\bullet\vert Z=n)$ is concentrated on a hyperplane of dimension
$\leq\vert A\vert-2$. Hence its limiting Gaussian distribution is degenerate.
This is also the case when $A=S$. The proof of Theorem 3 is now complete.
As an application of Theorem 3, we consider the following question
treated by Mahmoud \cite{Ma}. Let ${\cal C}_n$ be the totality of uniform
binary trees of size $n$. (See \S4.2 for the definition.) Let further
$X_i(\gamma)$, $i=0,1,2$, be the number of vertices of the tree
$\gamma\in{\cal C}_n$ which has $i$ children. As we saw in \S4.2, we have
\begin{equation}
Q_n(\{\gamma\in{\cal C}_n;\ X_i(\gamma)=n_i,i=0,1,2\})=
P(Y_i=n_i,i=0,1,2\vert\ Z=n)\ ,
\label{eqn:5-5}
\end{equation}
where $Q_n$ is the uniform distribution on ${\cal C}_n$ and $P$ is the
distribution of the Galton-Watson tree whose offspring distribution is the
binomial distribution $\mbox{Bin}(2,p)$ with $0