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 tree

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


Share

Consultation statistics

This page has been seen 247 times.
This article's PDF has been downloaded 274 times.