1 Search Results for "Sileikis, Matas"

Document
DOI: 10.4230/LIPIcs.AofA.2018.33
Asymptotic Normality of Almost Local Functionals in Conditioned Galton-Watson Trees

Authors: Dimbinaina Ralaivaosaona, Matas Sileikis, and Stephan Wagner

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

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.
Cite as

Dimbinaina Ralaivaosaona, Matas Sileikis, and Stephan Wagner. Asymptotic Normality of Almost Local Functionals in Conditioned Galton-Watson Trees. 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. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ralaivaosaona_et_al:LIPIcs.AofA.2018.33,
  author =	{Ralaivaosaona, Dimbinaina and Sileikis, Matas and Wagner, Stephan},
  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 =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.33},
  URN =		{urn:nbn:de:0030-drops-89262},
  doi =		{10.4230/LIPIcs.AofA.2018.33},
  annote =	{Keywords: Galton-Watson trees, central limit theorem, additive functional}
}
  • Refine by Author
  • 1 Ralaivaosaona, Dimbinaina
  • 1 Sileikis, Matas
  • 1 Wagner, Stephan

  • Refine by Classification
  • 1 Mathematics of computing → Trees

  • Refine by Keyword
  • 1 Galton-Watson trees
  • 1 additive functional
  • 1 central limit theorem

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact