License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AofA.2018.33
URN: urn:nbn:de:0030-drops-89262
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8926/
Ralaivaosaona, Dimbinaina ;
Sileikis, Matas ;
Wagner, Stephan
Asymptotic Normality of Almost Local Functionals in Conditioned Galton-Watson Trees
Abstract
An additive functional of a rooted tree is a functional that can be calculated recursively as the sum of the values of the functional over the branches, plus a certain toll function. Janson recently proved a central limit theorem for additive functionals of conditioned Galton-Watson trees under the assumption that the toll function is local, i.e. only depends on a fixed neighbourhood of the root. We extend his result to functionals that are almost local, thus covering a wider range of functionals. Our main result is illustrated by two explicit examples: the (logarithm of) the number of matchings, and a functional stemming from a tree reduction process that was studied by Hackl, Heuberger, Kropf, and Prodinger.
BibTeX - Entry
@InProceedings{ralaivaosaona_et_al:LIPIcs:2018:8926,
author = {Dimbinaina Ralaivaosaona and Matas Sileikis and Stephan Wagner},
title = {{Asymptotic Normality of Almost Local Functionals in Conditioned Galton-Watson Trees}},
booktitle = {29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
pages = {33:1--33:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-078-1},
ISSN = {1868-8969},
year = {2018},
volume = {110},
editor = {James Allen Fill and Mark Daniel Ward},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8926},
URN = {urn:nbn:de:0030-drops-89262},
doi = {10.4230/LIPIcs.AofA.2018.33},
annote = {Keywords: Galton-Watson trees, central limit theorem, additive functional}
}
Keywords: |
|
Galton-Watson trees, central limit theorem, additive functional |
Collection: |
|
29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018) |
Issue Date: |
|
2018 |
Date of publication: |
|
18.06.2018 |