A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree

Abstract

Abstract Let X n be the number of cuts needed to isolate the root in a random recursive tree with n 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,\ldots\}$ are recursively defined by $X_n {{\rm d}\atop{=}} X_{n-D_n} + 1, \; n=2,3,\ldots, \; X_1=0$ , where D n is a discrete random variable with ℙ ${\{ D_n = k \} = {1 \over {k(k+1)}} {n \over {n-1}}, \; k=1,2,\ldots, n-1}$ , which is independent of $(X_2,\ldots, X_n)$ . This distributional recursion was not studied previously in the sense of weak convergence. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009