On the number of leaves in a random recursive tree
Author:
- Yazhe ZhangYZYazhe Zhang
Open Access
- 1 November 2015
- journal article
- Published by Institute of Mathematical Statistics in Brazilian Journal of Probability and Statistics
- Vol. 29 (4) , 897-908
Abstract
This paper studies the asymptotic behavior of the number of leaves $L_{n}$ in a random recursive tree $T_{n}$ with $n$ nodes. By utilizing the size-bias method, we derive an upper bound on the Wasserstein distance between the distribution of $L_{n}$ and a standard normal distribution. Furthermore, we obtain a weak version of an Erdös–Rényi type law and a large deviation principle for $L_{n}$.
Keywords
This publication has 13 references indexed in Scilit:
- Fundamentals of Stein’s methodProbability Surveys, 2011
- Concentration of measures via size-biased couplingsProbability Theory and Related Fields, 2009
- Stochastically evolving networksPhysical Review E, 2003
- Implications for QoS Provisioning Based on Traceroute MeasurementsLecture Notes in Computer Science, 2002
- Breakage and restoration in recursive treesJournal of Applied Probability, 2002
- Multivariate normal approximations by Stein's method and size bias couplingsJournal of Applied Probability, 1996
- Hopf-algebraic structure of families of treesJournal of Algebra, 1989
- On the number of terminal vertices in certain random trees with an application to stemma construction in philologyJournal of Applied Probability, 1982
- Cutting down recursive treesMathematical Biosciences, 1974
- Distribution of nodes of a tree by degreeMathematical Biosciences, 1970