Tree-valued Markov chains derived from Galton-Watson processes.

*(English)*Zbl 0917.60082From the authors’ introduction: This paper develops some theory for Galton-Watson trees \({\mathcal G}\) (i.e. family trees associated with Galton-Watson branching processes), starting from the following two known facts: (i) [Lemma 10] For fixed \(0\leq u\leq 1\) let \({\mathcal G}_u\) be the “pruned” tree obtained by cutting edges of \({\mathcal G}\) (and discarding the attached branch) independently with probability \(1-u\). Then \({\mathcal G}_u\) is another Galton-Watson tree. (ii) [Proposition 2] For critical or subcritical \({\mathcal G}\) one can define a tree \({\mathcal G}^\infty\), interpretable as \({\mathcal G}\) conditioned on non-extinction. Qualitatively, \({\mathcal G}^\infty\) consists of a single infinite “spine” to which finite subtrees are attached.

We interpret (i) as defining a pruning process \(({\mathcal G}_u,\;0\leq u\leq 1)\), which is a tree-valued continuous-time inhomogeneous Markov chain such that \({\mathcal G}_0\) is the trivial tree consisting only of the root vertex, and \({\mathcal G}_1= {\mathcal G}\). An analogous pruning process \(({\mathcal G}^*_u,\;0\leq u\leq 1)\) with \({\mathcal G}^*_1= {\mathcal G}^\infty\) is constructed from the conditioned tree \({\mathcal G}^\infty\) of (ii). Section 3 gives a careful description of the transition rates and transition probabilities of these processes. These results simplify, and further connections appear, in the special case of Poisson offspring distribution, which is the subject of Section 4. There we consider \(({\mathcal G}_\mu\), \(0\leq\mu <\infty)\), where \({\mathcal G}_\mu\) is the family tree of the Galton-Watson branching process with Poisson \((\mu)\) offspring, and the associated pruned conditioned process \(({\mathcal G}_\mu^*,\;0\leq\mu\leq 1)\). Other topics include consequent distributional identities relating Borel and size-biased Borel distributions (Sections 4.5 and 4.7) and the interpretation of trees conditioned to be infinite as explicit Doob \(h\)-transforms, with the related identification of the Martin boundary of \((\mu,{\mathcal G}_\mu)\) (Section 4.4).

We interpret (i) as defining a pruning process \(({\mathcal G}_u,\;0\leq u\leq 1)\), which is a tree-valued continuous-time inhomogeneous Markov chain such that \({\mathcal G}_0\) is the trivial tree consisting only of the root vertex, and \({\mathcal G}_1= {\mathcal G}\). An analogous pruning process \(({\mathcal G}^*_u,\;0\leq u\leq 1)\) with \({\mathcal G}^*_1= {\mathcal G}^\infty\) is constructed from the conditioned tree \({\mathcal G}^\infty\) of (ii). Section 3 gives a careful description of the transition rates and transition probabilities of these processes. These results simplify, and further connections appear, in the special case of Poisson offspring distribution, which is the subject of Section 4. There we consider \(({\mathcal G}_\mu\), \(0\leq\mu <\infty)\), where \({\mathcal G}_\mu\) is the family tree of the Galton-Watson branching process with Poisson \((\mu)\) offspring, and the associated pruned conditioned process \(({\mathcal G}_\mu^*,\;0\leq\mu\leq 1)\). Other topics include consequent distributional identities relating Borel and size-biased Borel distributions (Sections 4.5 and 4.7) and the interpretation of trees conditioned to be infinite as explicit Doob \(h\)-transforms, with the related identification of the Martin boundary of \((\mu,{\mathcal G}_\mu)\) (Section 4.4).

Reviewer: L.Mutafchiev (Sofia)

##### MSC:

60J80 | Branching processes (Galton-Watson, birth-and-death, etc.) |

05C05 | Trees |

60C05 | Combinatorial probability |

60J27 | Continuous-time Markov processes on discrete state spaces |