On the distribution of distances in recursive trees
Author:
- Robert P. DobrowRDRobert P. Dobrow
- 1 September 1996
- journal article
- Published by Cambridge University Press (CUP) in Journal of Applied Probability
- Vol. 33 (3) , 749-757
Abstract
Recursive trees have been used to model such things as the spread of epidemics, family trees of ancient manuscripts, and pyramid schemes. A tree Tn with n labeled nodes is a recursive tree if n = 1, or n > 1 and Tn can be constructed by joining node n to a node of some recursive tree Tn–1. For arbitrary nodes i < n in a random recursive tree we give the exact distribution of Xi,n, the distance between nodes i and n. We characterize this distribution as the convolution of the law of Xi,j+1 and n – i – 1 Bernoulli distributions. We further characterize the law of Xi,j+1 as a mixture of sums of Bernoullis. For i = in growing as a function of n, we show that is asymptotically normal in several settings.Keywords
This publication has 6 references indexed in Scilit:
- Asymptotic Joint Normality of Outdegrees of Nodes in Random Recursive TreesRandom Structures & Algorithms, 1992
- Limiting Distributions for Path Lengths in Recursive TreesProbability in the Engineering and Informational Sciences, 1991
- Records, permutations and greatest convex minorantsMathematical Proceedings of the Cambridge Philosophical Society, 1989
- Applications of the theory of records in the study of random treesActa Informatica, 1988
- Two Probability Models of Pyramid or Chain Letter Schemes Demonstrating that Their Promotional Claims are UnreliableOperations Research, 1984
- On the number of terminal vertices in certain random trees with an application to stemma construction in philologyJournal of Applied Probability, 1982