Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Leaf multiplicity in ...
Article

Leaf multiplicity in a Bienaym\'e-Galton-Watson tree

Anna M. Brandenberger ORCID, Luc Devroye, Marcel K. Goh, Rosie Y. Zhao
Download article
Open on arXiv
Submitted on
May 26, 2021
Accepted on
February 19, 2022
Published on
March 30, 2022
Last modified on
March 31, 2025
Volume 24
vol. 24:1
Analysis of Algorithms
DOI
10.46298/dmtcs.7515
License
arXiv.org - Non-exclusive license to distribute
Indicators
1715
Views
1367
Downloads

Leaf multiplicity in a Bienaym\'e-Galton-Watson tree

Anna M. Brandenberger ORCID, Luc Devroye, Marcel K. Goh, Rosie Y. Zhao
Abstract
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
Keywords
  • Mathematics - Probability
Mathematics Subject Classification 2020
  • 05C05 - Trees
  • 60J80 - Branching processes (Galton-Watson, birth-and-death, etc.)
Linked publications - datasets - software
  • Has review

    Review available on zbMATH Open, by Heinrich Hering (Rockenberg) (English)

Preview
Loading PDF preview...