Premium
On the covariance of the level sizes in random recursive trees
Author(s) -
van der Hofstad Remco,
Hooghiemstra Gerard,
Van Mieghem Piet
Publication year - 2002
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10030
Subject(s) - covariance , mathematics , tree (set theory) , covariance mapping , probability distribution , fraction (chemistry) , covariance and correlation , combinatorics , random tree , multivariate random variable , random variable , distance correlation , statistics , discrete mathematics , covariance function , sum of normally distributed random variables , computer science , covariance intersection , artificial intelligence , chemistry , organic chemistry , motion planning , robot
Abstract In this paper we study the covariance structure of the number of nodes k and l 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. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20: 519–539, 2002