Pruning Galton-Watson trees and tree-valued Markov processes
Annales de l'I.H.P. Probabilités et statistiques, Volume 48 (2012) no. 3, pp. 688-705.

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 {𝒢(u)} by pruning Galton-Watson trees and an analogous process {𝒢 * (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 {𝒢(u)} run until its ascension time has a representation in terms of {𝒢 * (u)}. A similar result was obtained by Aldous and Pitman (Ann. Inst. H. Poincaré 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 l’arbre. Cette procédure nous permet de définir un processus de Markov {𝒢(u)} à valeurs arbres en élaguant un arbre de Galton-Watson. Nous définissons également de manière analogue un processus {𝒢 * (u)} en élaguant un arbre de Galton-Watson critique ou sous-critique conditionné à être infini. Sous de faibles hypothèses sur la loi de reproduction, nous montrons que le processus {𝒢(u)} arrêté en son temps d’ascension admet une représentation en terme du processus {𝒢 * (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.

DOI: 10.1214/11-AIHP423
Classification: 05C05, 60J80, 60J27
Keywords: pruning, branching process, Galton-Watson process, random tree, ascension process
@article{AIHPB_2012__48_3_688_0,
     author = {Abraham, Romain and Delmas, Jean-Fran\c{c}ois and He, Hui},
     title = {Pruning {Galton-Watson} trees and tree-valued {Markov} processes},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     pages = {688--705},
     publisher = {Gauthier-Villars},
     volume = {48},
     number = {3},
     year = {2012},
     doi = {10.1214/11-AIHP423},
     mrnumber = {2976559},
     zbl = {1256.60028},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1214/11-AIHP423/}
}
TY  - JOUR
AU  - Abraham, Romain
AU  - Delmas, Jean-François
AU  - He, Hui
TI  - Pruning Galton-Watson trees and tree-valued Markov processes
JO  - Annales de l'I.H.P. Probabilités et statistiques
PY  - 2012
SP  - 688
EP  - 705
VL  - 48
IS  - 3
PB  - Gauthier-Villars
UR  - http://archive.numdam.org/articles/10.1214/11-AIHP423/
DO  - 10.1214/11-AIHP423
LA  - en
ID  - AIHPB_2012__48_3_688_0
ER  - 
%0 Journal Article
%A Abraham, Romain
%A Delmas, Jean-François
%A He, Hui
%T Pruning Galton-Watson trees and tree-valued Markov processes
%J Annales de l'I.H.P. Probabilités et statistiques
%D 2012
%P 688-705
%V 48
%N 3
%I Gauthier-Villars
%U http://archive.numdam.org/articles/10.1214/11-AIHP423/
%R 10.1214/11-AIHP423
%G en
%F AIHPB_2012__48_3_688_0
Abraham, Romain; Delmas, Jean-François; He, Hui. Pruning Galton-Watson trees and tree-valued Markov processes. Annales de l'I.H.P. Probabilités et statistiques, Volume 48 (2012) no. 3, pp. 688-705. doi : 10.1214/11-AIHP423. http://archive.numdam.org/articles/10.1214/11-AIHP423/

[1] R. Abraham and J.-F. Delmas. Fragmentation associated with Lévy processes using snake. Probab. Theory Related Fields 141 (2008) 113-154. | MR | Zbl

[2] R. Abraham and J.-F. Delmas. A continuum-tree-valued Markov process. Ann. Probab. 40 (2012) 1167-1211. | MR | Zbl

[3] D. Aldous. The continuum random tree I. Ann. Probab. 19 (1991) 1-28. | MR | Zbl

[4] D. Aldous and J. Pitman. Tree-valued Markov chains derived from Galton-Watson processes. Ann. Inst. H. Poincaré Probab. Statist. 34 (1998) 637-686. | Numdam | MR | Zbl

[5] K. B. Athreya and P. E. Ney. Branching Processes. Die Grundlehren der Mathematischen Wissenschaften 196. Springer, New York, 1972. | MR | Zbl

[6] H. Kesten. Subdiffusive behavior of random walk on a random cluster. Ann. Inst. H. Poincaré Probab. Statist. 22 (1987) 425-487. | Numdam | MR | Zbl

[7] J.-F. Le Gall. Random trees and applications. Probab. Surv. 2 (2005) 245-311. | MR | Zbl

[8] G. Miermont. Self-similar fragmentations derived from the stable tree. II. Splitting at nodes. Probab. Theory Related Fields 131 (2005) 341-375. | MR | Zbl

[9] J. Neveu. Arbres et processus de Galton-Watson. Ann. Inst. H. Poincaré Probab. Statist. 22 (1986) 199-207. | Numdam | MR | Zbl

Cited by Sources: