Asymptotic Joint Normality of Outdegrees of Nodes in Random Recursive Trees
- 1 January 1992
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 3 (3) , 255-266
- https://doi.org/10.1002/rsa.3240030305
Abstract
We study the joint probability distribution of the number of nodes of outdegree 0, 1, and 2 in a random recursive tree. We complete the known partial list of exact means and variances for outdegrees up to two by obtaining exact combinatorial expressions for the remaining means, variances, and covariances. The joint probability distribution of the number of nodes of outdegree 0, 1, and 2 is shown to be asymptotically trivariate normal and the asymptotic covariance structure is explicitly determined. It is also shown how to extend the results (at least in principle) to obtain a limiting multivariate normal distribution for nodes of outdegree 0, 1, …, k.Keywords
This publication has 6 references indexed in Scilit:
- On the Distribution of Leaves in Rooted Subtrees of Recursive TreesThe Annals of Applied Probability, 1991
- Asymptotic Normality in the Generalized Polya–Eggenberger Urn Model, with an Application to Computer Data StructuresSIAM Journal on Algebraic Discrete Methods, 1985
- On the number of terminal vertices in certain random trees with an application to stemma construction in philologyJournal of Applied Probability, 1982
- A Probability Model of a Pyramid SchemeThe American Statistician, 1977
- Distribution of nodes of a tree by degreeMathematical Biosciences, 1970
- A simple urn modelCommunications on Pure and Applied Mathematics, 1949