A Limiting Distribution for the Number of Cuts Needed to Isolate the Root of a Random Recursive Tree
Let X(n) be the number of cuts needed to isolate the root in a random recursive tree with it vertices. We provide a weak convergence result for X(n). The basic observation for its proof is that the probability distributions of {X(n) : n = 2, 3,...} are recursively defined by X(n) =(d) X(n-Dn) + 1, n = 2, 3,..., X(1) = 0, where D(n) is a discrete random variable with P{D(n) = k} = 1/k(k + 1) n/n - 1, k = 1,2,...,n-1, which is independent of (X(2),...X(n)). This distributional recursion was not studied previously in the sense of weak convergence. (C) 2008 Wiley Periodicals, Inc. Random Struct. Alg., 34, 319-336, 2009
recursive tree stable limiting law singularity analysis