uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Distances Between Pairs of Vertices and Vertical Profile in Conditioned Galton-Watson Trees
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
2011 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 38, no 4, 381-395 p.Article in journal (Refereed) Published
Abstract [en]

We consider a conditioned Galton-Watson tree and prove an estimate of the number of pairs of vertices with a given distance, or, equivalently, the number of paths of a given length. We give two proofs of this result, one probabilistic and the other using generating functions and singularity analysis. Moreover, the latter proof yields a more general estimate for generating functions, which is used to prove a conjecture by Bousquet-Melou and Janson (Bousquet-Melou and Janson, Ann Appl Probab 16 (2006) 1597-1632), saying that the vertical profile of a randomly labelled conditioned Galton-Watson tree converges in distribution, after suitable normalization, to the density of ISE (Integrated Superbrownian Excursion).

Place, publisher, year, edition, pages
2011. Vol. 38, no 4, 381-395 p.
Keyword [en]
random Galton-Watson tree, paths of given length, vertical profile, probabilistic analysis of algorithms, branching process
National Category
URN: urn:nbn:se:uu:diva-154521DOI: 10.1002/rsa.20319ISI: 000290773600001OAI: oai:DiVA.org:uu-154521DiVA: diva2:421090
Available from: 2011-06-07 Created: 2011-06-07 Last updated: 2011-06-07Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text
By organisation
Analysis and Applied Mathematics
In the same journal
Random structures & algorithms (Print)

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 180 hits
ReferencesLink to record
Permanent link

Direct link