Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-28T00:08:21.775Z Has data issue: false hasContentIssue false
  • English
  • Français

Limit distributions for the number of leaves in a random forest

Part of: Markov processes Limit theorems Geometric probability and stochastic geometry Stochastic processes

Published online by Cambridge University Press:  01 July 2016

T. Mylläri
T. Mylläri*
Affiliation:
Åbo Akademi University and Petrozavodsk State University
*
∗ Postal address: Department of Mathematics, Åbo Akademi University, FIN-20500 Åbo, Finland. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Galton-Watson forests consisting of N roots (or trees) and n nonroot vertices are studied. The limit distributions of the number of leaves in such a forest are obtained. By a leaf we mean a vertex from which there are no arcs emanating.

Keywords

Conditioned Galton-Watson processlocal limit theoremnormal disributionoffspring distributionspanarray schemeMukhin's theorem

MSC classification

Primary: 60J80: Branching processes (Galton-Watson, birth-and-death, etc.) 60F05: Central limit and other weak theorems 60D05: Geometric probability and stochastic geometry
Secondary: 60G50: Sums of independent random variables; random walks
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 34 , Issue 4 , December 2002 , pp. 904 - 922
Copyright
Copyright © Applied Probability Trust 2002 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Cheplyukova, I. A. (1998). The emergence of a giant tree in a random forest. Discrete Math. Appl. 8, 17–33.Google Scholar
[2] Drmota, M. (1994). A bivariate asymptotic expansion of coefficients of powers of generating functions. Europ. J. Combinatorics 15, 139–152.Google Scholar
[3] Drmota, M. (1994). Distribution of the height of leaves of rooted trees. Discrete Math. Appl. 4, 45–58.Google Scholar
[4] Gnedenko, B. V. and Kolmogorov, A. N. (1954). Limit Distribution for Sums of Independent Random Variables. Addison-Wesley, Reading, MA.Google Scholar
[5] Karlin, S. and Taylor, H. M. (1975). A First Course in Stochastic Processes. Academic Press, New York.Google Scholar
[6] Kazimirov, N. I. and Pavlov, Y. L. (2000). A remark on Galton–Watson forests. Discrete Math. Appl. 10, 49–62.Google Scholar
[7] Kennedy, D. P. (1975). The Galton–Watson process conditioned on the total progeny. J. Appl. Prob. 12, 800–806.Google Scholar
[8] Kolchin, V. F. (1986). Random Mappings. Springer, New York.Google Scholar
[9] Mukhin, A. V. (1992). Local limit theorems for lattice random variables. Theory Prob. Appl. 27, 698–713.Google Scholar
[10] Mylläri, T. B. (2002). Limit distribution of the number of leaves of a Galton–Watson forest. In Probabilistic Methods in Discrete Mathematics (Proc. 5th Internat. Petrozavodsk Conf.), eds Kolchin, V. F. et al., VSP, Utrecht, pp. 257–272.Google Scholar
[11] Pavlov, Y. L. (2000). Random Forests. VSP, Utrecht.Google Scholar
[12] Pavlov, Y. L. and Cheplyukova, I. A. (1999). Limit distributions of the number of vertices in strata of a simply generated forest. Discrete Math. Appl. 9, 137–154.CrossRefGoogle Scholar