On the Distribution of Leaves in Rooted Subtrees of Recursive Trees
Mahmoud, Hosam M. ; Smythe, R. T.
Ann. Appl. Probab., Tome 1 (1991) no. 4, p. 406-418 / Harvested from Project Euclid
We study the structure of $T^{(k)}_n$, the subtree rooted at $k$ in a random recursive tree of order $n$, under the assumption that $k$ is fixed and $n \rightarrow \infty$. Employing generalized Polya urn models, exact and limiting distributions are derived for the size, the number of leaves and the number of internal nodes of $T^{(k)}_n$. The exact distributions are given by intricate formulas involving Eulerian numbers, but a recursive argument based on the urn model suffices for establishing the first two moments of the above-mentioned random variables. Known results show that the limiting distribution of the size of $T^{(k)}_n$, normalized by dividing by $n$ is $\operatorname{Beta}(1, k - 1)$. A martingale central limit argument is used to show that the difference between the number of leaves and the number of internal nodes of $T^{(k)}_n$, suitably normalized, converges to a mixture of normals with a $\operatorname{Beta}(1, k - 1)$ as the mixing density. The last result allows an easy determination of limiting distributions of suitably normalized versions of the number of leaves and the number of internal nodes of $T^{(k)}_n$.
Publié le : 1991-08-14
Classification:  Recursive trees,  rooted subtrees,  generalized Polya urn models,  martingale central limit theorem,  05C05,  60G42,  68E05
@article{1177005874,
     author = {Mahmoud, Hosam M. and Smythe, R. T.},
     title = {On the Distribution of Leaves in Rooted Subtrees of Recursive Trees},
     journal = {Ann. Appl. Probab.},
     volume = {1},
     number = {4},
     year = {1991},
     pages = { 406-418},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1177005874}
}
Mahmoud, Hosam M.; Smythe, R. T. On the Distribution of Leaves in Rooted Subtrees of Recursive Trees. Ann. Appl. Probab., Tome 1 (1991) no. 4, pp.  406-418. http://gdmltest.u-ga.fr/item/1177005874/