Total path length for random recursive trees

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, converges to W in LP for each 0 < p < co. 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 [GRAPHICS] where E(x) := -xlnx - (1 - 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. Simulations exhibit a high degree of accuracy in the approximation.