Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-19T23:58:12.871Z Has data issue: false hasContentIssue false
  • English
  • Français

Limiting Distributions for Path Lengths in Recursive Trees

Published online by Cambridge University Press:  27 July 2009

Hosam M. Mahmoud
Hosam M. Mahmoud
Affiliation:
Department of Statistics/Computer & In formation Systems George Washington University Washington, D.C. 20052, U.S.A.
Get access Rights & Permissions [Opens in a new window]

Abstract

The depth of insertion and the internal path length of recursive trees are studied. Luc Devroye has recently shown that the depth of insertion in recursive trees is asymptotically normal. We give a direct alternative elementary proof of this fact. Furthermore, via the theory of martingales, we show that In, the internal path length of a recursive tree of order n, converges to a limiting distribution. In fact, we show that there exists a random variable I such that (In – n In n)/n→I almost surely and in quadratic mean, as n → α. The method admits, in passing, the calculation of the first two moments of In.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 5 , Issue 1 , January 1991 , pp. 53 - 59
Copyright
Copyright © Cambridge University Press 1991

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Breiman, L. (1968). Probability. Reading, Massachusetts: Addison-Wesley.Google Scholar
Devroye, L. (1988). Applications of the theory of records in the study of random trees. Acta Informatica 26: 123–130.CrossRefGoogle Scholar
Gastwirth, J.L. & Bhattacharya, P.K. (1984). Two probability models of pyramid or chain letter schemes demonstrating that their promotional claims are unreliable. Operations Research 32:(3) 527–536.CrossRefGoogle Scholar
Gastwirth, J.L. (1977). A probability model of a pyramid scheme. American Statistician 31: 79–82.Google Scholar
Moon, J.W. (1974). The distance between nodes in recursive trees. London Mathematics Society Lecture Notes Series, No. 13. London: Cambridge University Press, 125–132.Google Scholar
Régnier, M. (1987). A limiting distribution for quicksort. Research Report No. 739, INRIA, Le Chesnay, France.Google Scholar
Szymański, J. (1990). On the maximum degree and the height of a random recursive tree, Random Graphs '87 (Karoński, M. & Ruciński, A., eds.), North-Holland, John Wiley & Sons, 313–324.Google Scholar
Szymański, J. (1990). On the complexity of algorithms on recursive trees. Theoretical Computer Science 74: 355–361.CrossRefGoogle Scholar