Content-Type: multipart/mixed; boundary="-------------0409212214632"

This is a multi-part message in MIME format.

---------------0409212214632
Content-Type: text/plain; name="04-295.comments"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="04-295.comments"

AMS 2000 subject classification 60J80, 60B99
---------------0409212214632
Content-Type: text/plain; name="04-295.keywords"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="04-295.keywords"

branching process; Galton-Watson process; random trees; construction of probability space
---------------0409212214632
Content-Type: application/x-tex; name="construction.tex"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline; filename="construction.tex"

\documentclass[a4paper,12pt]{article}
\usepackage{amssymb}
\topmargin=0cm
\oddsidemargin=0cm
\evensidemargin=0cm
\textwidth=16cm
\textheight=23cm
\pagestyle{plain}
%%%%%%    TEXT START    %%%%%%
\begin{document}
\newtheorem{proposition}{Proposition}
\newtheorem{thm}{Theorem}
\newtheorem{rem}{Remark}
\newtheorem{cor}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\title{The Equivalence of Two Constructions of \\
Galton-Watson Processes 
%\thanks{Running head : Two constructions of Galton-Watson processes}
}
\author{Kenji KURATA 
\thanks{Institute of Mathematics, University of Tsukuba, 
Tsukuba, 305-8571, Japan}
\and Nariyuki MINAMI \thanks
{Institute of Mathematics, University of Tsukuba, Tsukuba, 
305-8571, Japan} 
\thanks{e-mail : minami@math.tsukuba.ac.jp}}
\date{}
\maketitle
\begin{abstract}
In most textbooks on branching processes, the Galton-Watson process is 
defined as an integer valued Markov chain with a special kind of transition 
probability, somtimes supplemented with an intuitive description of random 
family trees. A precise construction of the Galton-Watson process on the 
space of trees was first given by R. Otter in 1949, and later independently 
by J. Neveu in 1986. In this note, we show that these two constructions are 
actually equivalent.

\bigskip
\noindent{\bf Keywords :} branching process; Galton-Watson process; 
random trees; 
construction of probability space
\end{abstract}

\section{Introduction} 
In his elegant paper \cite{Neveu}, J. Neveu gave a convenient 
definition of a $\sigma$-field ${\cal F}$ and a probability measure $P$ 
on the space $\Omega$ of trees, obtaining a probability space which 
describes every detail of a Galton-Watson branching process. Neveu was 
motivated by the lack of fundamental theory of this kind in the existing 
works on branching processes, but apparently he did not know that already 
in 1949, R. Otter \cite{Otter} had given a similar definition 
which turns out to be equivalent to Neveu's definition. 
The purpose of this note is to show this equivalence. 

Otter's construction looks more honest to our intuition of branching 
processes, if not as concise as Neveu's, 
and is closely related to the topological 
structure of the space $\Omega$ of trees. Also, it is remarkable that 
Otter already emphasizes in \cite{Otter} the conceptual advantage of 
realizing Galton-Watson processes on the space of trees, instead of treating 
them merely as Markov chains with a special kind of transition probabilities.

\section{The construction by Neveu (\cite{Neveu})}
Let $U$ be the totality of finite sequences of 
strictly positive integers, of which the empty sequence is denoted by 
$\phi$. We can write $U=\sum_{n\geq0}(\mathbf{N}^{\ast})^{n}$, where 
$\mathbf{N}^{\ast}=\{1,2,\ldots\}$, $(\mathbf{N}^{\ast})^{0}=\{\phi\}$, 
and $(\mathbf{N}^{\ast})^{n}$ is the totality of 
sequences $u=j_1j_2\cdots j_n$ 
of length $n$. By defintion, a tree is a subset $\omega\subset U$ 
which satisfies the following three conditions: 
a) $\phi\in\omega$ ; 
b) $uj\in\omega$ implies $u\in\omega$ whenever $u\in U$ and 
$j\in\mathbf{N}^{\ast}$, where we write $uj=j_1j_2\cdots j_nj$ if 
$u=j_1j_2\cdots j_n$ ; 
c) for each $u\in\omega$, there is an integer 
$\nu_u(\omega)\geq0$ such that for any $j\in\mathbf{N}^{\ast}$, 
$uj\in\omega$ if and only if $1\leq j\leq\nu_u(\omega)$. 
Let $\Omega$ be the totality of trees in this sense. Then ${\cal F}$ is 
defined to be the smallest $\sigma$-field containing all subsets 
$\Omega_u:=\{\omega\in\Omega\ \vert\ \omega\ni u\}$, $u\in U$.

Given a probability distribution $\Pi=\{p_n\}_{n=0}^{\infty}$ on non-negative 
integers $\mathbf{N}$, let 
$(\Omega^{\ast},{\cal F}^{\ast},P^{\ast})$ be the product space 
$(\mathbf{N},\Pi)^{\otimes U}$, ${\cal F}^{\ast}$ being the $\sigma$-
field generated by the coordinate maps 
$\nu_v^{\ast}:\omega^{\ast}=(\omega_u^{\ast})_{u\in U}\mapsto\omega_v^{\ast}$,
 $v\in U$. If we define the map $\psi:\Omega^{\ast}\mapsto\Omega$ by

$$\psi(\omega^{\ast})=\{u=j_1\ldots j_p\in U\vert\ j_{k+1}
\leq\nu_{j_1\cdots j_k}(\omega^{\ast})\ ,\ \mbox{for}\ 0\leq k<p\}\ ,$$
then $\psi$ is ${\cal F}^{\ast}/{\cal F}$-measurable, and we can consider 
the induced measure $P=P^{\ast}\circ\psi^{-1}$ on $(\Omega,{\cal F})$. 
The resulting probability space $(\Omega,{\cal F},P)$ then describes 
every detail of the Galton-Watson process with the offspring distribution 
$\Pi$. In particular, if $Z_n(\omega)$ is the 
cardinality of $\omega\cap(\mathbf{N}^{\ast})^n$, 
then under this probability measure $P$, 
$\{Z_n(\omega)\}_{n=0}^{\infty}$ is an $\mathbf{N}$-valued 
Markov chain with transition probability 
$P(x,y)=(\Pi^{\ast x})(\{y\})$, where \lq\lq$\ ^{\ast}$\rq\rq 
deotes the convolution.

\section{The construction by Otter (\cite{Otter})}
Since the definition of trees by Otter (\cite{Otter}) is obviously seen 
to be equivalent to Neveu's definition, we shall work on the same space 
$\Omega$ introduced in the previous section. 

For each tree $\omega$, we define the set ${\cal I}(\omega)$ 
of its inner points and the set ${\cal E}(\omega)$ of its 
endpoints as follows:
$${\cal I}(\omega):=\{u\in\omega\ \vert\ \nu_u(\omega)>0\}\quad;\quad
{\cal E}(\omega):=\{u\in\omega\ \vert\ \nu_u(\omega)=0\}\ .$$

For two trees $\omega,\omega'\in\Omega$, we say that 
$\omega$ extends $\omega'$ and write 
$\omega\geq\omega'$, if the following two conditions hold: 
i) $\omega\supset\omega'$ ; ii) $\nu_u(\omega)=\nu_u(\omega')$ for each 
$u\in{\cal I}(\omega')$. 

Next let $\Omega^f$ be the totality of finite trees. 
For a $T\in\Omega^f$ and $\Lambda=(\lambda_e;e\in{\cal E}(T))\in
\mathbf{N}^{{\cal E}(T)}$, define 
$$[T;\Lambda]=\{\omega\in\Omega\ \vert\ \omega\geq T\ ,\ \nu_e(\omega)
=\lambda_e\ \mbox{for}\ e\in{\cal E}(T)\}\ ,$$
which Otter called a \lq\lq neighborhood \rq\rq. 


Given a probability distribution $\Pi=\{p_n\}_{n=0}^{\infty}$ on 
$\mathbf{N}$, Otter constructs a $\sigma$-field ${\cal B}$ and a 
probability measure $Q$ on $(\Omega,{\cal B})$ in the following way. 

First he let ${\cal S}$ be the class of subsets $S\subset\Omega$ 
of the form $S=\sum_{\Lambda\in A}[T;\Lambda]$ with $T\in\Omega^f$ and 
$A=\prod_{e\in{\cal E}(T)}A_e\subset\mathbf{N}^{{\cal E}(T)}$. 
Then ${\cal S}$ is shown to be a semi-algebra. 
Next he defines a set function $\tilde{Q}$ on ${\cal S}$ by
$$\tilde{Q}([T;\Lambda])=\left(\prod_{u\in{\cal I}(T)}p_{\nu_u(T)}\right)
\left(\prod_{e\in{\cal E}(T)}p_{\lambda_e}\right)
\quad;\quad
\tilde{Q}(S)=\sum_{\Lambda\in A}\tilde{Q}([T;\Lambda])\ ,$$
where the value of $\tilde{Q}(S)$ turns out to 
be independent of the expression of $S$. 
He then shows that $\tilde{Q}$ is countably additive on ${\cal S}$, and hence 
is extended to a probability measure $Q$ on the $\sigma$-field 
${\cal B}$ generated by ${\cal S}$ (or equivalently generated by ${\cal N}$ ).

Otter's discussion is actually quite sketchy, and in order to fill its 
details, it 
is necessary to prepare several lemmas concerning the sets $[T;\Lambda]$, 
which are not as trivial as regarded by Otter. Among those lemmas, 
the following one will be useful in the rest of this note:

\begin{lemma}
The class ${\cal N}$ defined by
$${\cal N}:=\{[T;\Lambda]\ \vert\ T\in\Omega^f\ ,\ \Lambda\in
\mathbf{N}^{{\cal E}(T)}\}\cup\{\emptyset\}$$
is a $\pi$-system, namely is closed under the formation of 
finite intersection.
\end{lemma}

\noindent
{\it Proof.} 
We shall show that if $[T_i;\Lambda_i]\in{\cal N}$, $i=1,2$, 
have non-empty intersection, then we can construct a $T_3\in\Omega^f$ and 
$\Lambda_3\in\mathbf{N}^{{\cal E}(T_3)}$ such that 
$$[T_1;\Lambda_1]\cap[T_2;\Lambda_2]=[T_3;\Lambda_3]\ .$$
For this purpose, let $T_3=T_1\cup T_2$. Then obviously $T_3\in\Omega^f$. 
It is also easy to see that ${\cal I}(T_3)={\cal I}(T_1)\cup{\cal I}(T_2)$, 
and that 
$${\cal E}(T_3)=[{\cal E}(T_1)\setminus T_2]+[{\cal E}(T_2)\setminus T_1]
+[{\cal E}(T_1)\cap{\cal E}(T_2)]\ .$$
Now suppose $\omega\in[T_1;\Lambda_1]\cap[T_2;\Lambda_2]$. If 
$u\in{\cal I}(T_1)\cap{\cal I}(T_2)$, then since $\omega\geq T_i$, $i=1,2$, 
we have $\nu_u(T_1)=\nu_u(\omega)=\nu_u(T_2)$. In this case, we also have 
$\nu_u(T_3)=\nu_u(\omega)$. If on the other hand, $u\in{\cal I}(T_1)
\setminus{\cal I}(T_2)$, we see from $\omega\geq T_1$ that $\nu_u(T_1)=
\nu_u(T_3)=\nu_u(\omega)$, and if $u\in{\cal I}(T_2)
\setminus{\cal I}(T_1)$, we see from $\omega\geq T_2$ that 
$\nu_u(T_2)=\nu_u(T_3)=\nu_u(\omega)$. Thus $T_3\geq T_i$, $i=1,2$, 
and whenever $u\in{\cal I}(T_3)$, one has $\nu_u(T_3)=\nu_u(\omega)$, 
showing $\omega\geq T_3$.

Let us write $\Lambda_i=(\lambda^i_e;e\in{\cal E}(T_i))$ for $i=1,2$. 
If $e\in{\cal E}(T_1)\setminus T_2$, then $\omega\in[T_1;\Lambda_1]$ implies 
$\nu_e(\omega)=\lambda_e^1$, and if $e\in{\cal E}(T_2)\setminus T_1$, 
then $\omega\in[T_2;\Lambda_2]$ implies $\nu_e(\omega)=\lambda_e^2$. 
Finally if $e\in{\cal E}(T_1)\cap{\cal E}(T_2)$, then we must have 
$\lambda_e^1=\nu_e(\omega)=\lambda_e^2$ by $\omega\in[T_1;\Lambda_1]\cap
[T_2;\Lambda_2]$. Thus if we define 
$\Lambda_3=(\lambda_e^3;e\in{\cal E}(T_3))$ by
$$\lambda_e^3=\left\{
\begin{array}{rl}
\lambda_e^1, &\quad\mbox{for}\ e\in{\cal E}(T_1)\setminus T_2 \\
\lambda_e^2, &\quad\mbox{for}\ e\in{\cal E}(T_2)\setminus T_1 \\
\lambda_e^1=\lambda_e^2, &\quad\mbox{for}\ e\in{\cal E}(T_1)
\cap{\cal E}(T_2) \ ,
\end{array}\right.
$$
then we must have $\omega\in[T_3;\Lambda_3]$. Since $\omega$ was arbitrarily 
chosen from $[T_1;\Lambda_1]\cap[T_2;\Lambda_2]$, we conclude 
$[T_1;\Lambda_1]\cap[T_2;\Lambda_2]\subset[T_3;\Lambda_3]$. 

To prove the converse inclusion, let $w\in[T_3;\Lambda_3]$ be arbitrary. 
Since $T_3\geq T_i$, $i=1,2$, we have $w\geq T_i$, $i=1,2$. 
If $e\in{\cal E}(T_1)\setminus{\cal I}(T_2)$, then $e\in{\cal E}(T_3)$ 
and $\nu_e(w)=\lambda_e^3=\lambda_e^1$. 
If on the other hand, 
$e\in{\cal E}(T_1)\cap{\cal I}(T_2)$, then $\nu_e(w)=\nu_e(T_2)$. 
But we are assuming $[T_1;\Lambda_1]\cap[T_2;\Lambda_2]\ne\emptyset$, so 
that there exists an $\omega$ such that $\omega\geq T_2$ and that 
$\nu_e(\omega)=\lambda_e^1$. Hence $\nu_e(T_2)=\nu_e(\omega)=\lambda_e^1$. 
In any case, $e\in{\cal E}(T_1)$ implies $\nu_e(w)=\lambda_e^1$. Thus 
$w\in[T_1;\Lambda_1]$. Similarly one can show $w\in[T_2;\Lambda_2]$, 
completing the proof of the lemma.


\section{The equivalence of two constructions}
We are now ready to prove our main assertion.

\begin{proposition}
${\cal B}={\cal F}$ and $Q=P$, hence the 
probability space constructed by Otter and Neveu coincide.
\end{proposition}

\noindent
{\it Proof.} 
Since we can write, with the convention $u0=u$, 
$$[T;\Lambda]=\left(\bigcap_{u\in T}\Omega_u\right)\cap
\left(\bigcap_{u\in{\cal I}(T)}\Omega^c_{u(\nu_u(T)+1)}\right)\cap
\left(\bigcap_{u\in{\cal E}(T)}\Omega_{u\lambda_u}\setminus
\Omega_{u(\lambda_u+1)}\right)\ ,$$
we see $[T;\Lambda]\in{\cal F}$ and hence ${\cal B}\subset{\cal F}$.

Conversely we can also write
$$\Omega_u=\bigcup\{[T;\Lambda]\ \vert\ u\in T\in\Omega^f\ ,\ 
\Lambda\in\mathbf{N}^{{\cal E}(T)}\}\ ,$$
hence $\Omega_u\in{\cal B}$ for any $u\in U$, proving ${\cal F}\subset
{\cal B}$.

On the other hand, since
$$\psi^{-1}([T;\Lambda])=\left(\bigcap_{u\in{\cal I}(T)}
\{\omega^{\ast}\ \vert\ \nu^{\ast}_u(\omega^{\ast})=\nu_u(T)\}\right)
\cap\left(\bigcap_{u\in{\cal E}(T)}
\{\omega^{\ast}\ \vert\ \nu^{\ast}_u(\omega^{\ast})=\lambda_u\}\right)\ ,$$
we have
$$P([T;\Lambda])=P^{\ast}(\psi^{-1}([T;\Lambda]))
=\left(\prod_{u\in{\cal I}(T)}p_{\nu_u(T)}\right)
\left(\prod_{e\in{\cal E}(T)}p_{\lambda_e}\right)=Q([T;\Lambda])\ .$$
Thus $P$ and $Q$ coincide on the $\pi$-system ${\cal N}$, hence on 
${\cal F}={\cal B}$, which is generated by ${\cal N}$.


\section{$\Omega$ as a metric space}
As was mentioned by Otter (\cite{Otter}), 
and as is obvious from Lemma 1, we can make $\Omega$ into a 
topological space by calling \lq\lq open\rq\rq those subsets $G\subset\Omega$ 
which are written as unions of $[T;\Lambda]$ 's. In particular, our 
$\sigma$-field ${\cal F}$ is the Borel $\sigma$-field corresponding to 
this topology. Let us briefly show that this topology is generated by a metric 
on $\Omega$.

For $n\geq0$, let $z_n(\omega)=\omega\cap(\mathbf{N}^{\ast})^n$. Given 
$\omega\ ,\ \omega^{\prime}\in\Omega$, let us define
$$\mu(\omega,\omega^{\prime})
=\sup\{n\geq0\ \vert\ z_n(\omega)=z_n(\omega^{\prime})\ \}\ ,$$
where we let $\mu(\omega,\omega^{\prime})=\infty$ if 
$z_n(\omega)=z_n(\omega^{\prime})$ for 
all $n\geq1$, namely if $\omega=\omega^{\prime}$. Since we have 
$$\mu(\omega,\omega^{\prime\prime})\geq\min\{
\mu(\omega,\omega^{\prime})\ ,\ \mu(\omega^{\prime},\omega^{\prime\prime})\ \}
\ ,$$
we can define a metric $d$ on $\Omega$ by letting 
$d(\omega,\omega^{\prime}):=\exp\{-\mu(\omega,\omega^{\prime})\}$.

Now let $G\subset\Omega$ be open in the sense already defined. Then for each 
$\omega\in G$, we can choose a $[T;\Lambda]$ such that $\omega\in[T;\Lambda]
\subset G$. Let $h(T)=\max\{n\geq0\vert T\cap(\mathbf{N}^{\ast})^n\ne
\emptyset\}$ be the \lq\lq height \rq\rq of the finite tree $T$. Then 
$\omega^{\prime}\in[T;\Lambda]$ as soon as $z_n(\omega^{\prime})=z_n(\omega)$ 
for $0\leq n\leq h(T)+1$, or equivalently as soon as 
$d(\omega^{\prime},\omega)\leq\exp\{-(h(T)+1)\}$. This shows that $G$ is 
open with respect to the metric $d$. Conversely, suppose $G$ is open in the 
metric $d$. Then for each $\omega\in G$, there is an integer $m\geq1$ such 
that $\omega^{\prime}\in G$ whenever $z_n(\omega^{\prime})=z_n(\omega)$, 
$0\leq n\leq m$. If we define $T=\cup_{n=0}^{m-1}z_n(\omega)$ and 
$\Lambda=(\lambda_e\ ;\ e\in{\cal E}(T))$ with $\lambda_e=\nu_e(\omega)$, 
then the last condition is equivalent to $\omega^{\prime}\in[T;\Lambda]$. 
Thus $\omega\in[T;\Lambda]\subset G$ and $G$ is open in the original sense.

\bigskip
Since ${\cal N}=\{[T;\Lambda]\}\cup\{\emptyset\}$ is a countable basis of 
topology, our metric space $(\Omega,d)$ thus obtained is separable. It is 
also complete. To see this, let $\{\omega^{(k)}\}_{k=1}^{\infty}$ be a 
Cauchy sequence with respect to the metric $d$. Then we can choose an 
increasing sequence $N_n\nearrow\infty$ such that 
$d(\omega^{(k)},\omega^{(\ell)})\leq e^{-n}$ for all $k,\ell\geq N_n$. In 
other words, we have $z_j(\omega^{(k)})=z_j(\omega^{(\ell)})$, 
$1\leq j\leq n$ for all $k,\ell\geq N_n$. If we let 
$\omega^{(\infty)}=\{\phi\}\cup\bigcup_{n=1}^{\infty}z_n(\omega^{(N_n)})$, 
then $\omega^{(\infty)}$ is a tree, and it is clear that 
$d(\omega^{(k)},\omega^{(\infty)})\to0$ as $k\to\infty$. 

\bigskip
Noting that ${\cal N}$ is also a $\pi$-system, we can apply Theorem 2.2 of 
\cite{Billingsley}, to obtain the following criterion for the weak convergence 
of probability measures on $\Omega$.

\begin{proposition}
Let $P$ and $P_n$, $n=1,2,\ldots$ be probability 
measures on $\Omega$. If $P_n([T;\Lambda])\to P([T;\Lambda])$ 
for each $[T;\Lambda]\in{\cal N}$, then one has 
$P_n\Rightarrow P$.
\end{proposition}

As an immediate corollary of this proposition, we see that if $P_n$ and 
$P$ are the probability measures for Galton-Watson processes with offspring 
distributions $\Pi_n$ and $\Pi$ respectively, and if $\Pi_n\Rightarrow\Pi$ 
on $\mathbf{N}$, the $P_n\Rightarrow P$ on $\Omega$.

\bigskip
\noindent
{\it Acknowledgment.} 
The authors  are grateful to Professor M. Kanda for his continual 
encouragement. 
The second author is also grateful to Professors K. Fukuyama and Y. Higuchi 
for valuable discussion  and for giving him opportunity to 
lecture on this subject.
% Place the text of your acknowledgements after the \acks command.
% \acks generates the heading "Acknowledgements".
% If you wish to make only one acknowledgement, use \ack.
% \ack generates the heading "Acknowledgement".


\begin{thebibliography}{99}
\footnotesize

\bibitem{Billingsley}
{\sc Billingsley, P.} (1999). {\em Convergence of Probability Measures.}, 
2nd~edn. John Wiley, New York.

\bibitem{Neveu}
{\sc Neveu, J.} (1986). Arbres et processus de Galton-Watson. 
\emph{Ann. Inst. H. Poincar\'e, Probabilit\'es et 
Statistique} {\bf 22,} 199--207.

\bibitem{Otter}
{\sc Otter, R.} (1949).  The Multiplicative Process. 
{\em Ann. Math. Stat.} {\bf 20,} 206--224.

\end{thebibliography}

\end{document}
---------------0409212214632--
