10.46298/dmtcs.7515
https://dmtcs.episciences.org/7515
Brandenberger, Anna M.
Anna M.
Brandenberger
Devroye, Luc
Luc
Devroye
Goh, Marcel K.
Marcel K.
Goh
Zhao, Rosie Y.
Rosie Y.
Zhao
Leaf multiplicity in a Bienaym\'e-Galton-Watson tree
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\'e-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\'e-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.
Comment: 17 pages, 6 figures, final journal version
episciences.org
Mathematics - Probability
arXiv.org - Non-exclusive license to distribute
2022-02-19
2022-03-30
2022-03-30
eng
journal article
arXiv:2105.12046
10.48550/arXiv.2105.12046
1365-8050
https://dmtcs.episciences.org/7515/pdf
VoR
application/pdf
Discrete Mathematics & Theoretical Computer Science
vol. 24, no. 1
Analysis of Algorithms
Researchers
Students