Geodesic
Leaf multiplicity in a Bienaym\'e-Galton-Watson tree
Discrete mathematics & theoretical computer science, Tome 24 (2022) no. 1.

Voir la notice de l'article provenant de la source Episciences

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.
DOI : 10.46298/dmtcs.7515
Classification : 05C05, 60J80 
@article{DMTCS_2022_24_1_a7,
     author = {Brandenberger, Anna M. and Devroye, Luc and Goh, Marcel K. and Zhao, Rosie Y.},
     title = {Leaf multiplicity in a {Bienaym\'e-Galton-Watson} tree},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {24},
     number = {1},
     year = {2022},
     doi = {10.46298/dmtcs.7515},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.7515/}
}
TY  - JOUR
AU  - Brandenberger, Anna M.
AU  - Devroye, Luc
AU  - Goh, Marcel K.
AU  - Zhao, Rosie Y.
TI  - Leaf multiplicity in a Bienaym\'e-Galton-Watson tree
JO  - Discrete mathematics & theoretical computer science
PY  - 2022
VL  - 24
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.7515/
DO  - 10.46298/dmtcs.7515
LA  - en
ID  - DMTCS_2022_24_1_a7
ER  - 
%0 Journal Article
%A Brandenberger, Anna M.
%A Devroye, Luc
%A Goh, Marcel K.
%A Zhao, Rosie Y.
%T Leaf multiplicity in a Bienaym\'e-Galton-Watson tree
%J Discrete mathematics & theoretical computer science
%D 2022
%V 24
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.7515/
%R 10.46298/dmtcs.7515
%G en
%F DMTCS_2022_24_1_a7
Brandenberger, Anna M.; Devroye, Luc; Goh, Marcel K.; Zhao, Rosie Y. Leaf multiplicity in a Bienaym\'e-Galton-Watson tree. Discrete mathematics & theoretical computer science, Tome 24 (2022) no. 1. doi : 10.46298/dmtcs.7515. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.7515/

Cité par Sources :