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

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.

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.

DOI : https://doi.org/10.1214/11-AIHP423
Classification : 05C05,  60J80,  60J27
Mots clés : 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 cois 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},
     zbl = {1256.60028},
     mrnumber = {2976559},
     language = {en},
     url = {archive.numdam.org/item/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, Tome 48 (2012) no. 3, pp. 688-705. doi : 10.1214/11-AIHP423. http://archive.numdam.org/item/AIHPB_2012__48_3_688_0/

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

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

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

[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 1641670 | Zbl 0917.60082

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

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

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

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

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