Content-Type: multipart/mixed; boundary="-------------0503012217697" This is a multi-part message in MIME format. ---------------0503012217697 Content-Type: text/plain; name="05-89.keywords" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="05-89.keywords" Galton-Watson trees; total progeny; Lagrange inversion; central limit theorem ---------------0503012217697 Content-Type: application/x-tex; name="vertices.tex" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="vertices.tex" \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 k0$, 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 i