Branching structure of uniform recursive trees

作者：Feng QQ^*; Su C; Hu ZS

来源：Science in China Series A-Mathematics, 2005, 48(6): 769-784.

DOI：10.1360/03ys0299

• uniform recursive tree
• branch
• depth
• distribution law
• limit theorem

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 eta(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 eta(n) follow easily from this method. Next it is shown that eta(n) and,, the depth of vertex n, have the same distribution, and the distribution law of zeta(n),(m), the number of branches of size m, is also given, whose asymptotic distribution is the Poisson distribution with parameter lambda = 1/m. In addition, the joint distribution and the asymptotic M 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 -> infinity.

• 出版日期2005-6
• 单位中国科学技术大学