The Width of Galton-Watson Trees Conditioned by the Size
It is proved that the moments of the width of Galton-Watson trees of size n and with offspring variance σ ^2 are asymptotically given by (σ √n)^pm_p where m_p are the moments of the maximum of the local time of a standard scaled Brownian excursion. This is done by combining a weak limit theorem and...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2004-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/323/pdf |
| _version_ | 1797270221493370880 |
|---|---|
| author | Michael Drmota Bernhard Gittenberger |
| author_facet | Michael Drmota Bernhard Gittenberger |
| author_sort | Michael Drmota |
| collection | DOAJ |
| description | It is proved that the moments of the width of Galton-Watson trees of size n and with offspring variance σ ^2 are asymptotically given by (σ √n)^pm_p where m_p are the moments of the maximum of the local time of a standard scaled Brownian excursion. This is done by combining a weak limit theorem and a tightness estimate. The method is quite general and we state some further applications. |
| first_indexed | 2024-04-25T02:00:49Z |
| format | Article |
| id | doaj.art-9d694ecd0f834df8bd4516c7ef2177e9 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:00:49Z |
| publishDate | 2004-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-9d694ecd0f834df8bd4516c7ef2177e92024-03-07T15:06:37ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502004-01-01Vol. 6 no. 210.46298/dmtcs.323323The Width of Galton-Watson Trees Conditioned by the SizeMichael Drmota0Bernhard Gittenberger1https://orcid.org/0000-0002-2639-8227Institut für Diskrete Mathematik und Geometrie [Wien]Institut für Diskrete Mathematik und Geometrie [Wien]It is proved that the moments of the width of Galton-Watson trees of size n and with offspring variance σ ^2 are asymptotically given by (σ √n)^pm_p where m_p are the moments of the maximum of the local time of a standard scaled Brownian excursion. This is done by combining a weak limit theorem and a tightness estimate. The method is quite general and we state some further applications.https://dmtcs.episciences.org/323/pdfbranching processessimply generated treegenerating functionsconvergence of moments[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Michael Drmota Bernhard Gittenberger The Width of Galton-Watson Trees Conditioned by the Size Discrete Mathematics & Theoretical Computer Science branching processes simply generated tree generating functions convergence of moments [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | The Width of Galton-Watson Trees Conditioned by the Size |
| title_full | The Width of Galton-Watson Trees Conditioned by the Size |
| title_fullStr | The Width of Galton-Watson Trees Conditioned by the Size |
| title_full_unstemmed | The Width of Galton-Watson Trees Conditioned by the Size |
| title_short | The Width of Galton-Watson Trees Conditioned by the Size |
| title_sort | width of galton watson trees conditioned by the size |
| topic | branching processes simply generated tree generating functions convergence of moments [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/323/pdf |
| work_keys_str_mv | AT michaeldrmota thewidthofgaltonwatsontreesconditionedbythesize AT bernhardgittenberger thewidthofgaltonwatsontreesconditionedbythesize AT michaeldrmota widthofgaltonwatsontreesconditionedbythesize AT bernhardgittenberger widthofgaltonwatsontreesconditionedbythesize |