Pruning Galton-Watson trees and tree-valued Markov processes

摘要

We present a new pruning procedure on discrete trees by adding marks on the nodes of trees. This procedure allows us to construct and study a tree-valued Markov process {G(u)} by pruning Galton-Watson trees and an analogous process {G*{u)} by pruning a critical or subcritical Galton-Watson tree conditioned to be infinite. Under a mild condition on offspring distributions, we show that the process {G(u)} run until its ascension time has a representation in terms of {G*(u)}. A similar result was obtained by Aldous and Pitman {Ann. Inst. H. Poincare Probab. Statist. 34 (1998) 637-686) in the special case of Poisson offspring distributions where they considered uniform pruning of Galton-Watson trees by adding marks on the edges of trees.%Nous présentons une nouvelle procédure d'élagage d'arbres discrets en ajoutant des marques sur les noeuds de 1'arbre. Cette procédure nous permet de definir un processus de Markov {G(u)} à valeurs arbres en élaguant un arbre de Galton-Watson. Nous définissons également de manière analogue un processus {G*(u)} en élaguant un arbre de Galton-Watson critique ou sous-critique conditionné à être infini. Sous de faibles hypothèses sur Ia loi de reproduction, nous montrons que le processus {(G(u)) arrêté en son temps d'ascension admet une représentation en terme du processus {G*(u)}- Un résultat similaire a été obtenu par Aldous et Pitman (Ann. Inst. H. Poincaré Probab. Statist. 34 (1998) 637-686) dans le cas particulier de lois de reproductions poissoniennes en considérant un élagage uniforme sur les branches de l'arbre.