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 k0\}\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--