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 sh...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics and theoretical computer science 2022-03, Vol.24, no. 1 (Analysis of Algorithms)
Main Authors: Brandenberger, Anna M., Devroye, Luc, Goh, Marcel K., Zhao, Rosie Y.
Format: Article
Language:English
Subjects:
mathematics - probability
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1365-8050
1365-8050
DOI:10.46298/dmtcs.7515