Anna M. Brandenberger ; Luc Devroye ; Marcel K. Goh ; Rosie Y. Zhao - Leaf multiplicity in a Bienaymé-Galton-Watson tree

dmtcs:7515 - Discrete Mathematics & Theoretical Computer Science, March 30, 2022, vol. 24, no. 1 - https://doi.org/10.46298/dmtcs.7515
Leaf multiplicity in a Bienaymé-Galton-Watson treeArticle

Authors: Anna M. Brandenberger ; Luc Devroye ; Marcel K. Goh ; Rosie Y. Zhao

    This note defines a notion of multiplicity for nodes in a rooted tree and presents an asymptotic calculation of the maximum multiplicity over all leaves in a Bienaymé-Galton-Watson tree with critical offspring distribution $\xi$, conditioned on the tree being of size $n$. In particular, we show that if $S_n$ is the maximum multiplicity in a conditional Bienaymé-Galton-Watson tree, then $S_n = \Omega(\log n)$ asymptotically in probability and under the further assumption that ${\bf E}\{2^\xi\} < \infty$, we have $S_n = O(\log n)$ asymptotically in probability as well. Explicit formulas are given for the constants in both bounds. We conclude by discussing links with an alternate definition of multiplicity that arises in the root-estimation problem.


    Volume: vol. 24, no. 1
    Section: Analysis of Algorithms
    Published on: March 30, 2022
    Accepted on: February 19, 2022
    Submitted on: May 26, 2021
    Keywords: Mathematics - Probability

    Consultation statistics

    This page has been seen 991 times.
    This article's PDF has been downloaded 865 times.