Limit Theorems For Some Random Variables In Random Trees

In this dissertation, the limiting behaviors of some random variables in several kinds of random trees such as random binary search tree, random recursive tree and binary interval tree are established.There are totally three types of different nodes in random binary search trees, i.e. the nodes with 0, 1, and 2 children. Let X_n, X_n⁽¹⁾ and X_n⁽²⁾ be the numbers of these three types of nodes in random search trees of size n, respectively. First, we build the recursive function for the number of leaves X_n, from which the expectation and variance of X_n are drawn after careful calculation. Then, it is also shown that X_n is asymptotically normal as n→∞by applying the contraction method. Finally, a linear relationship between X_n and X_n is found, and the similar results for X_n⁽¹⁾ and X_n⁽²⁾ are achieved.For arbitrary positive integer i=i_n≤n-1, a function of n, we demonstrate D_(in),n, the distance between nodes i_n and n in random recursive trees of size n. Many authors have already discussed this topic and have gotten some properties of D_(in),n for some special cases of i_n. For example, they ha,ve given the exact expression of the expectation and variance of D_(in),n, and have divided D_(in),n into the sum of some independent random variables. With the help of their conclusions, we apply the normal approximation method to solve the most general situation of D_(in),n without any restriction on i_n, and show that D_(in),n is asymptotically normal as n→∞. By the way, the Large Number Law of D_(in),n is also got.Binary interval trees are generated from the process of random divisions of interval (0, x). The limiting distribution of S_x, the size of binary interval tree, is investigated. First, we construct the probability space of binary interval trees, and prove the Large Number Law of S_x. Then, the distributional recursive equation of S_x is built. Following this recursive function, the calculation of the expectation and variance of S_x could be transformed into the problem of solving first-order ordinary differential equations and the exact solution are achieved. At last, it is shown that the S_x with suitable standardization converges in distribution to the standard normal random variable according to the contraction method in continuous case.