Total Path Length for Random Recursive Trees

Source abstract

Total path length, or search cost, for a rooted tree is defined as the sum of all root-to-node distances. Let T n be the total path length for a random recursive tree of order n . Mahmoud [10] showed that W n := ( T n − E [ T n ])/ n converges almost surely and in L 2 to a nondegenerate limiting random variable W . Here we give recurrence relations for the moments of W n and of W and show that W n converges to W in L p for each 0 < p < ∞. We confirm the conjecture that the distribution of W is not normal. We also show that the distribution of W is characterized among all distributions having zero mean and finite variance by the distributional identity formula here where [Escr ]( x ) := − x ln x − (1 minus; x ) ln(1 − x ) is the binary entropy function, U is a uniform (0, 1) random variable, W * and W have the same distribution, and U , W and W * are mutually independent. Finally, we derive an approximation for the distribution of W using a Pearson curve density estimator.