episciences.org_7515_1669552117
1669552117
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
03
30
2022
vol. 24, no. 1
Analysis of Algorithms
Leaf multiplicity in a Bienaym\'eGaltonWatson tree
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\'eGaltonWatson 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\'eGaltonWatson 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 rootestimation problem.
03
30
2022
7515
https://arxiv.org/licenses/nonexclusivedistrib/1.0
arXiv:2105.12046
10.48550/arXiv.2105.12046
https://arxiv.org/abs/2105.12046v2
https://arxiv.org/abs/2105.12046v1
10.46298/dmtcs.7515
https://dmtcs.episciences.org/7515

https://dmtcs.episciences.org/9237/pdf