Pruning Galton–Watson trees and tree-valued Markov processes

Romain Abraham; Jean-François Delmas; Hui He

Annales de l'I.H.P. Probabilités et statistiques (2012)

  • Volume: 48, Issue: 3, page 688-705
  • ISSN: 0246-0203

Abstract

top
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.

How to cite

top

Abraham, Romain, Delmas, Jean-François, and He, Hui. "Pruning Galton–Watson trees and tree-valued Markov processes." Annales de l'I.H.P. Probabilités et statistiques 48.3 (2012): 688-705. <http://eudml.org/doc/271979>.

@article{Abraham2012,
abstract = {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 $\lbrace \mathcal \{G\}(u)\rbrace $ by pruning Galton–Watson trees and an analogous process $\lbrace \mathcal \{G\}^\{*\}(u)\rbrace $ 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 $\lbrace \mathcal \{G\}(u)\rbrace $ run until its ascension time has a representation in terms of $\lbrace \mathcal \{G\}^\{*\}(u)\rbrace $. 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.},
author = {Abraham, Romain, Delmas, Jean-François, He, Hui},
journal = {Annales de l'I.H.P. Probabilités et statistiques},
keywords = {pruning; branching process; Galton–Watson process; random tree; ascension process; Galton-Watson process},
language = {eng},
number = {3},
pages = {688-705},
publisher = {Gauthier-Villars},
title = {Pruning Galton–Watson trees and tree-valued Markov processes},
url = {http://eudml.org/doc/271979},
volume = {48},
year = {2012},
}

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
PB - Gauthier-Villars
VL - 48
IS - 3
SP - 688
EP - 705
AB - 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 $\lbrace \mathcal {G}(u)\rbrace $ by pruning Galton–Watson trees and an analogous process $\lbrace \mathcal {G}^{*}(u)\rbrace $ 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 $\lbrace \mathcal {G}(u)\rbrace $ run until its ascension time has a representation in terms of $\lbrace \mathcal {G}^{*}(u)\rbrace $. 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.
LA - eng
KW - pruning; branching process; Galton–Watson process; random tree; ascension process; Galton-Watson process
UR - http://eudml.org/doc/271979
ER -

References

top
  1. [1] R. Abraham and J.-F. Delmas. Fragmentation associated with Lévy processes using snake. Probab. Theory Related Fields141 (2008) 113–154. Zbl1142.60048MR2372967
  2. [2] R. Abraham and J.-F. Delmas. A continuum-tree-valued Markov process. Ann. Probab.40 (2012) 1167–1211. Zbl1252.60072MR2962090
  3. [3] D. Aldous. The continuum random tree I. Ann. Probab.19 (1991) 1–28. Zbl0722.60013MR1085326
  4. [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. Zbl0917.60082MR1641670
  5. [5] K. B. Athreya and P. E. Ney. Branching Processes. Die Grundlehren der Mathematischen Wissenschaften 196. Springer, New York, 1972. Zbl0259.60002MR373040
  6. [6] H. Kesten. Subdiffusive behavior of random walk on a random cluster. Ann. Inst. H. Poincaré Probab. Statist.22 (1987) 425–487. Zbl0632.60106MR871905
  7. [7] J.-F. Le Gall. Random trees and applications. Probab. Surv.2 (2005) 245–311. Zbl1189.60161MR2203728
  8. [8] G. Miermont. Self-similar fragmentations derived from the stable tree. II. Splitting at nodes. Probab. Theory Related Fields 131 (2005) 341–375. Zbl1071.60065MR2123249
  9. [9] J. Neveu. Arbres et processus de Galton–Watson. Ann. Inst. H. Poincaré Probab. Statist.22 (1986) 199–207. Zbl0601.60082MR850756

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.