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...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2022-03-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/7515/pdf |
| _version_ | 1797270042079920128 |
|---|---|
| author | Anna M. Brandenberger Luc Devroye Marcel K. Goh Rosie Y. Zhao |
| author_facet | Anna M. Brandenberger Luc Devroye Marcel K. Goh Rosie Y. Zhao |
| author_sort | Anna M. Brandenberger |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-11T21:32:14Z |
| format | Article |
| id | doaj.art-e1cfe43e361746acb0ac3c29040d1d91 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:58Z |
| publishDate | 2022-03-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-e1cfe43e361746acb0ac3c29040d1d912024-03-07T15:46:22ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502022-03-01vol. 24, no. 1Analysis of Algorithms10.46298/dmtcs.75157515Leaf multiplicity in a Bienaym\'e-Galton-Watson treeAnna M. BrandenbergerLuc DevroyeMarcel K. GohRosie Y. ZhaoThis 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.https://dmtcs.episciences.org/7515/pdfmathematics - probability |
| spellingShingle | Anna M. Brandenberger Luc Devroye Marcel K. Goh Rosie Y. Zhao Leaf multiplicity in a Bienaym\'e-Galton-Watson tree Discrete Mathematics & Theoretical Computer Science mathematics - probability |
| title | Leaf multiplicity in a Bienaym\'e-Galton-Watson tree |
| title_full | Leaf multiplicity in a Bienaym\'e-Galton-Watson tree |
| title_fullStr | Leaf multiplicity in a Bienaym\'e-Galton-Watson tree |
| title_full_unstemmed | Leaf multiplicity in a Bienaym\'e-Galton-Watson tree |
| title_short | Leaf multiplicity in a Bienaym\'e-Galton-Watson tree |
| title_sort | leaf multiplicity in a bienaym e galton watson tree |
| topic | mathematics - probability |
| url | https://dmtcs.episciences.org/7515/pdf |
| work_keys_str_mv | AT annambrandenberger leafmultiplicityinabienaymegaltonwatsontree AT lucdevroye leafmultiplicityinabienaymegaltonwatsontree AT marcelkgoh leafmultiplicityinabienaymegaltonwatsontree AT rosieyzhao leafmultiplicityinabienaymegaltonwatsontree |