Limit Laws For Two Random Tree Models

Some limit laws for the branches and subtrees in a random recursive tree and binary search tree are established in this dissertation.A branch in a rooted tree is defined as a subtree rooted at a node in the first level. For the branching structure of random recursive trees, via a combinatorics technique, the exact distribution of the number of branches with size m in a random recursive tree of order n is given first, from which one can easily get that the limiting distribution for it is a Poisson distribution with parameter 1/m. The, asymptotic independent of the numbers of branches with various sizes is also shown. Moreover, the joint and asymptotic joint distributions of the numbers of branches with different sizes are obtained.Based on these branching structure properties, the limiting distribution for the length of a simple downward random walk on a random recursive tree with size n is shown.The extreme branch sizes in random recursive trees of order n are further investigated. Using generating functions and the exponential formula, the limiting distributions for the minimum and maximum branch sizes are determined. After some numerical work, the images of the distribution function and density function of the maximum case (scaled by n) are drawn.The variety problem of subtrees is considered both in random recursive trees and binary search trees. The numbers of subtrees with fixed sizes and shapes lying on the fringe of a recursive tree are considered especially first, where the limit distributions for them (suitably normalized) are shown to be normal via the contraction method, and a connection to P(?)lya urns indicates that, convergence may be strengthened to the almost sure mode.More generally, if let the subtree size k depend on n, the order of a random recursive tree or binary search tree, then three cases are identified: the subcritical, i.e. as k(n)/(?)n. → 0; the critical, i.e. as fc(n) = (?)((?)n); the supercritical, i.e. as k{n)/(?)n → ∞. Utilizing the analytic methods based on functional equations for generating functions, the following results are proved: In the subcritical case, the number of subtrees with size k (after normalization) is shown to be asymptotically normal distributed; whereas in the supercritical case, it converges to 0. In the critical case, if k/(?)n approaches a finite limit, then it converges in distribution to a Poisson random variable. This provides for recursive trees and binary search trees an understanding of the complete spectrum of phases of the number of subtree with size k and the gradual change from the subcritical to the supercritical phase.