No CrossRef data available.
Article contents
The Hitting Time for the Height of a Random Recursive Tree
Published online by Cambridge University Press: 01 November 2008
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
In this paper we provide a simple formula for the expected time for a random recursive tree to grow to a given height.
Information
- Type
- Paper
- Information
- Copyright
- Copyright © Cambridge University Press 2008
References
[1]Charalambides, C. A. and Singh, J. (1988) A review of the Stirling numbers, their generalizations and statistical applications. Comm. Statist. Theory Methods 17 2533–2595.CrossRefGoogle Scholar
[2]Devroye, L. (1988) Applications of the theory of records in the study of random trees. Acta Inform. 26 123–130.CrossRefGoogle Scholar
[3]Dobrow, R. P. (1996) On the distribution of distances in recursive trees. J. Appl. Probab. 33 749–757.CrossRefGoogle Scholar
[4]Feller, W. (1968) An Introduction to Probability Theory and its Applications, Vol. I, 3rd edn, Wiley, New York.Google Scholar
[5]Gastwirth, J. L. (1977) A probability model of a pyramid scheme. Amer. Statist. 31 79–82.Google Scholar
[6]Gastwirth, J. L. and Bhattacharya, P. K. (1984) Two probability models of pyramid or chain letter schemes demonstrating that their promotional claims are unreliable. Oper. Res. 32 527–536.CrossRefGoogle Scholar
[7]Harper, L. H. (1967) Stirling behavior is asymptotically normal. Ann. Math. Statist. 38 410–414.CrossRefGoogle Scholar
[8]Janson, S. (2005) Asymptotic degree distribution in random recursive trees. Random Struct. Alg. 26 69–83.CrossRefGoogle Scholar
[9]Kuba, M. and Panholzer, A. (2006) Descendants in increasing trees. Electron. J. Combin. 13 #8 (electronic).CrossRefGoogle Scholar
[10]Mahmoud, H. M. (1994) A strong law for the height of random binary pyramids. Ann. Appl. Probab. 4 923–932.CrossRefGoogle Scholar
[11]Mahmoud, H. M. and Smythe, R. T. (1991) On the distribution of leaves in rooted subtrees of recursive trees. Ann. Appl. Probab. 1 406–418.CrossRefGoogle Scholar
[12]Meir, A. and Moon, J. W. (1976) Climbing certain types of rooted trees I. In Proc. Fifth British Combinatorial Conference (University of Aberdeen 1975), Vol. XV of Congressus Numerantium, pp. 461–469.Google Scholar
[13]Meir, A. and Moon, J. W. (1978) Climbing certain types of rooted trees II. Acta Math. Acad. Sci. Hungar. 31 43–54.CrossRefGoogle Scholar
[14]Moon, J. W. (1974) The distance between nodes in recursive trees. In Combinatorics: Proc. British Combinatorial Conference (University College Wales, Aberystwyth, 1973), Vol. 13 of London Mathematical Society Lecture Notes, Cambridge University Press, pp. 125–132.CrossRefGoogle Scholar
[15]Najock, D. and Heyde, C. C. (1982) On the number of terminal vertices in certain random trees with an application to stemma construction in philology. J. Appl. Probab. 19 675–680.CrossRefGoogle Scholar
[16]Neininger, R. (2002) The Wiener index of random trees. Combin. Probab. Comput. 11 587–597.CrossRefGoogle Scholar
[17]Panholzer, A. (2004) The distribution of the size of the ancestor-tree and of the induced spanning subtree for random trees. Random Struct. Alg. 25 179–207.CrossRefGoogle Scholar
[18]Su, C., Feng, Q. and Hu, Z. (2006) Uniform recursive trees: Branching structure and simple random downward walk. J. Math. Anal. Appl. 315 225–243.CrossRefGoogle Scholar
[19]Szymański, J. (1990) On the maximum degree and the height of a random recursive tree. In Random Graphs '87 (Poznań 1987), Wiley, pp. 313–324.Google Scholar
[20]Tetzlaff, G. T. (2002) Breakage and restoration in recursive trees. J. Appl. Probab. 39 383–390.CrossRefGoogle Scholar
You have
Access