Branching structure of uniform recursive trees
2005
The branching structure of uniform recursive trees is investigated in this paper. Using the method of sums for a sequence of independent random variables, the distribution law of η n , the number of branches of the uniform recursive tree of size n are given first. It is shown that the strong law of large numbers, the central limit theorem and the law of iterated logarithm for η n follow easily from this method. Next it is shown that η n and ξ n , the depth of vertex n, have the same distribution, and the distribution law of ζ n,m , the number of branches of size m, is also given, whose asymptotic distribution is the Poisson distribution with parameter \(\lambda = \frac{1}{m}\). In addition, the joint distribution and the asymptotic joint distribution of the numbers of various branches are given. Finally, it is proved that the size of the biggest branch tends to infinity almost sure as n → ∞.
Keywords:
- Combinatorics
- Mathematical analysis
- Central limit theorem
- Empirical distribution function
- Mathematics
- Infinite divisibility (probability)
- Product distribution
- Triangular distribution
- Asymptotic distribution
- Law of the iterated logarithm
- Recursive tree
- Law of large numbers
- Discrete mathematics
- Uniform limit theorem
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
12
References
12
Citations
NaN
KQI