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. The Width of Galton- ...
Article

The Width of Galton-Watson Trees Conditioned by the Size

Michael Drmota (1), Bernhard Gittenberger ORCID (1)
(1) Institut für Diskrete Mathematik und Geometrie [Wien]
Download article
Open on HAL
Imported on
March 26, 2015
Published on
January 1, 2004
Last modified on
March 31, 2025
Volume 6
vol. 6:2
DOI
10.46298/dmtcs.323
License
https://about.hal.science/hal-authorisation-v1
P 16053
Indicators
717
Views
871
Downloads

The Width of Galton-Watson Trees Conditioned by the Size

Michael Drmota (1), Bernhard Gittenberger ORCID (1)
(1) Institut für Diskrete Mathematik und Geometrie [Wien]
Abstract
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.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • branching processes
  • simply generated tree
  • generating functions
  • convergence of moments
Cited by

Source: OpenCitations

  • Width and mode of the profile for some random trees of logarithmic height

    The Annals of Applied Probability

    Authors : Luc Devroye ORCID, Hsien-Kuei Hwang ORCID

    Journal reference : Volume 16, 2006, pp.

    DOI : 10.1214/105051606000000187

  • Stochastic analysis of tree–like data structures

    Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences

    Authors : Michael Drmota ORCID

    Journal reference : Volume 460, 2004, pp. 271-307

    DOI : 10.1098/rspa.2003.1243

  • Sub-Gaussian tail bounds for the width and height of conditioned Galton–Watson trees

    The Annals of Probability

    Authors : Louigi Addario-Berry, Luc Devroye, Svante Janson

    Journal reference : Volume 41, 2013, pp.

    DOI : 10.1214/12-aop758

  • Approche probabiliste

    Mathématiques et applications

    Authors : Brigitte Chauvin, Julien Clément ORCID, Danièle Gardy ORCID

    Journal reference : Volume , 2018, pp. 183-215

    DOI : 10.1007/978-3-319-93725-0_5

  • Asymptotic Evolution of Acyclic Random Mappings

    Electronic Journal of Probability

    Authors : Steven Evans ORCID, Tye Lidman

    Journal reference : Volume 12, 2007, pp.

    DOI : 10.1214/ejp.v12-437
Preview
Loading PDF preview...