On the covariance of the level sizes in random recursive trees
In this paper we study the covariance structure of the number of nodes k and I steps away from the root in random recursive trees. We give an analytic expression valid for all k, l and tree sizes N. The fraction of nodes k steps away from the root is a random probability distribution in k. The expression for the covariances allows us to show that the total variation distance between this (random) probability distribution and its mean converges in probability to zero. (C) 2002 Wiley Periodicals, Inc.
recursive trees convergence in probability covariance of level sizes convergence in total variation