Hostname: page-component-745bb68f8f-5r2nc Total loading time: 0 Render date: 2025-02-12T04:58:48.308Z Has data issue: false hasContentIssue false
  • English
  • Français

Local limits of Galton–Watson trees conditioned on the number of protected nodes

Part of: Markov processes Graph theory Probability theory on algebraic and topological structures

Published online by Cambridge University Press:  04 April 2017

Romain Abraham ,
Aymen Bouaziz  and
Jean-François Delmas
Romain Abraham*
Affiliation:
Université d’Orléans
Aymen Bouaziz*
Affiliation:
Université de Tunis El Manar
Jean-François Delmas*
Affiliation:
Ecole des Ponts
*
* Postal address: Laboratoire MAPMO, Université d’Orléans, BP 6759, 45067 Orléans Cedex 2, France. Email address: romain.abraham@univ-orleans.fr
** Postal address: Institut préparatoire aux études scientifiques et techniques, Université de Tunis El Manar, 2070 La Marsa, Tunis, Tunisie.
*** Postal address: CERMICS, Ecole des Ponts, Université Paris-Est, Champs-sur-Marne, 77455 Marne-la-Vallée Cedex 2, France.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We consider a marking procedure of the vertices of a tree where each vertex is marked independently from the others with a probability that depends only on its out-degree. We prove that a critical Galton–Watson tree conditioned on having a large number of marked vertices converges in distribution to the associated size-biased tree. We then apply this result to give the limit in distribution of a critical Galton–Watson tree conditioned on having a large number of protected nodes.

Keywords

Galton--Watson treerandom treelocal limitprotected node

MSC classification

Primary: 60J80: Branching processes (Galton-Watson, birth-and-death, etc.) 60B10: Convergence of probability measures
Secondary: 05C05: Trees
Type
Research Papers
Information
Journal of Applied Probability , Volume 54 , Issue 1 , March 2017 , pp. 55 - 65
Copyright
Copyright © Applied Probability Trust 2017 

References

[1] Abraham, R. and Delmas, J.-F. (2014).Local limits of conditioned Galton–Watson trees: the infinite spine case.Electron. J. Prob. 19, 19 pp.Google Scholar
[2] Abraham, R. and Delmas, J.-F. (2015).An introduction to Galton–Watson trees and their local limits. Lecture given in Hammamet, December 2014. Available at https://arxiv.org/abs/1506.05571.Google Scholar
[3] Devroye, L. and Janson, S. (2014).Protected nodes and fringe subtrees in some random trees.Electron. Commun. Prob. 19, 10 pp.CrossRefGoogle Scholar
[4] He, X. (2015).Local convergence of critical random trees and continuous-state branching processes. Preprint. Available at https://arxiv.org/abs/1503.00951.Google Scholar
[5] Janson, S. (2016).Asymptotic normality of fringe subtrees and additive functionals in conditioned Galton–Watson trees.Random Structures Algorithms 48,57–101.CrossRefGoogle Scholar
[6] Kesten, H. (1986).Subdiffusive behavior of random walk on a random cluster.Ann. Inst. H. Poincaré Prob. Statist. 22,425–487.Google Scholar
[7] Neveu, J. (1986).Arbres et processus de Galton–Watson..Ann. Inst. H. Poincaré Prob. Statist. 22,199–207.Google Scholar
[8] Rizzolo, D. (2015).Scaling limits of Markov branching trees and Galton–Watson trees conditioned on the number of vertices with out-degree in a given set.Ann. Inst. H. Poincaré Prob. Statist. 51,512–532.Google Scholar