LIPIcs.AofA.2018.34.pdf
- Filesize: 496 kB
- 11 pages
Document
Local Limits of Large Galton-Watson Trees Rerooted at a Random Vertex
Author
-
Part of:
Volume:
29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-06-18
Cite AsGet BibTex
Benedikt Stufler. Local Limits of Large Galton-Watson Trees Rerooted at a Random Vertex. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 34:1-34:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.AofA.2018.34
https://doi.org/10.4230/LIPIcs.AofA.2018.34
Abstract
We prove limit theorems describing the asymptotic behaviour of a typical vertex in random simply generated trees as their sizes tends to infinity. In the standard case of a critical Galton-Watson tree conditioned to be large, the limit is the invariant random sin-tree constructed by Aldous (1991). Our main contribution lies in the condensation regime where vertices of macroscopic degree appear. Here we describe in complete generality the asymptotic local behaviour from a random vertex up to its first ancestor with "large" degree. Beyond this distinguished ancestor, different behaviours may occur, depending on the branching weights. In a subregime of complete condensation, we obtain convergence toward a novel limit tree, that describes the asymptotic shape of the vicinity of the full path from a random vertex to the root vertex. This includes the important case where the offspring distribution follows a power law up to a factor that varies slowly at infinity.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Stochastic processes
Keywords
- Galton-Watson trees
- local weak limits
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- R. Abraham, A. Bouaziz, and J.-F. Delmas. Local limits of Galton-Watson trees conditioned on the number of protected nodes. ArXiv e-prints, 2015. URL: http://arxiv.org/abs/1509.02350.
- R. Abraham, J.-F. Delmas, and H. Guo. Critical Multi-Type Galton-Watson Trees Conditioned to be Large. ArXiv e-prints, 2015. URL: http://arxiv.org/abs/1511.01721.
-
Romain Abraham and Jean-François Delmas. Local limits of conditioned Galton-Watson trees: the condensation case. Electron. J. Probab., 19:no. 56, 29, 2014.
-
Romain Abraham and Jean-François Delmas. Local limits of conditioned Galton-Watson trees: the infinite spine case. Electron. J. Probab., 19:no. 2, 19, 2014.
- David Aldous. Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab., 1(2):228-266, 1991. URL: http://links.jstor.org/sici?sici=1050-5164(199105)1:2<228:AFDFGF>2.0.CO;2-8&origin=MSN.
- Inés Armendáriz and Michail Loulakis. Conditional distribution of heavy tailed random variables on large deviations of their sum. Stochastic Process. Appl., 121(5):1138-1147, 2011. URL: http://dx.doi.org/10.1016/j.spa.2011.01.011.
- Michael Drmota. Random trees. SpringerWienNewYork, Vienna, 2009. An interplay between combinatorics and probability. URL: http://dx.doi.org/10.1007/978-3-211-75357-6.
- C. Holmgren and S. Janson. Fringe trees, Crump-Mode-Jagers branching processes and m-ary search trees. ArXiv e-prints, 2016. URL: http://arxiv.org/abs/1601.03691.
- Svante Janson. Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation. Probab. Surv., 9:103-252, 2012. URL: http://dx.doi.org/10.1214/11-PS188.
- Svante Janson, Thordur Jonsson, and Sigurdur Örn Stefánsson. Random trees with superexponential branching weights. J. Phys. A, 44(48):485002, 16, 2011. URL: http://dx.doi.org/10.1088/1751-8113/44/48/485002.
- Thordur Jonsson and Sigurdur Örn Stefánsson. Condensation in nongeneric trees. J. Stat. Phys., 142(2):277-313, 2011. URL: http://dx.doi.org/10.1007/s10955-010-0104-8.
- Igor Kortchemski. Limit theorems for conditioned non-generic Galton-Watson trees. Ann. Inst. Henri Poincaré Probab. Stat., 51(2):489-511, 2015. URL: http://dx.doi.org/10.1214/13-AIHP580.
-
Sophie Pénisson. Beyond the Q-process: various ways of conditioning the multitype Galton-Watson process. ALEA Lat. Am. J. Probab. Math. Stat., 13(1):223-237, 2016.
- Robin Stephenson. Local convergence of large critical multi-type galton-watson trees and applications to random maps. Journal of Theoretical Probability, pages 1-47, 2016. URL: http://dx.doi.org/10.1007/s10959-016-0707-3.
-
B. Stufler. Local limits of large Galton-Watson trees rerooted at a random vertex. To appear in Annales de l'Institut Henri Poincaré Probabilités et Statistiques.