Number of the records: 1
Asymptotic Normality of Almost Local Functionals in Conditioned Galton-Watson Trees
- 1.0491225 - ÚI 2019 RIV DE eng C - Conference Paper (international conference)
Ralaivaosaona, D. - Šileikis, Matas - Wagner, S.
Asymptotic Normality of Almost Local Functionals in Conditioned Galton-Watson Trees.
29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2018 - (Ward, M.; Fill, J.), č. článku 33. Leibniz International Proceedings in Informatics, 110. ISBN 978-395977078-1. ISSN 1868-8969.
[AofA 2018: International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms /29./. Uppsala (SE), 25.06.2018-29.06.2018]
R&D Projects: GA ČR GJ16-07822Y
Institutional support: RVO:67985807
Keywords : Galton-Watson trees * central limit theorem * additive functional
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=8926
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.
Permanent Link: http://hdl.handle.net/11104/0285264
File Download Size Commentary Version Access a0491225.pdf 7 425.4 KB Publisher’s postprint open-access
Number of the records: 1