Abstract
In this note we find the exact probability distribution ofdn,i, the outdegree of the nodei in a random recursive tree withn nodes, Fori=in increasing as a linear function onn, we show thatdn,in is asymptotically normal.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.
Similar content being viewed by others
References
K. T. Balinska, L. V. Quintas and J. Szymanski,Random Recursive Forests, Random Structures and Algorithms5 (1994), 3–12.
C. Berge,Graphs and hypergraphs, North-Holland, Amsterdam, 1973.
L. Devroye,Applications of the theory of records in the study of random trees, Acta Informatica26, (1985) 123–130.
J. Gastwirth and P. Bhattacharya,Two probability models of pyramids or chain letter schemes demonstrating that their promotional calims are unreliable, Operations Research32 (1984), 527–536.
H. Mahmoud and R. Smythe,Asymptotic joint normality of outdegrees of nodes in random recursive trees, Random Structures and Algorithms3 (1992), 255–266.
J. Moon,The distance between nodes in recursive trees, London Math. Soc. Lecture Notes, vol.13, Cambridge Univ. Press, London, 1974, 125–132.
D. Najock and C. Heyde,On the number of terminal vertices in certain random trees with an application to stemma construction in philology, J. Applied Prob.19 (1982), 675–680.
R. T. Smythe and H. M. Mahmoud,A survey of recursive trees, Theor. Probability and Math. Statist.51, 1–27, 1995.
Sukumar Mondal, Modhumangal Pal and Tapan K. Pal,An optimal algorithm for finding depth-first spanning tree on permutation graphs, Korean J. Comput. & Appl. Math. Vol.6 (1999), No. 3, 464–493.
Taenam Kim, Dukwan Oh and Eunki Lim,A new parallel algorithm for rooting a tree, Korean J. Comput. & Appl. Math. Vol.5 (1998), No. 2, 360–385.
Author information
Authors and Affiliations
Department of Statistics, Shahid Beheshti University, Tehran, Iran
Mehri Javanian & Mohammad Q. Vahidi-Asl
- Mehri Javanian
You can also search for this author inPubMed Google Scholar
- Mohammad Q. Vahidi-Asl
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toMehri Javanian.
Additional information
Mehri Javanian received her MSC from Shahid Beheshti University of Iran, in 2002. Her research interests focus on the random structures and algoritms.
Mohammad Q. Vahidi-Asl received his Ph.D from Oregon State University of USA, under the direction of Robert Smythe. Since 1996, he has been at Shahid Beheshti University, Which named his a University Teaching Fellow. His research interests focus on the random graphs and percolation theory.
Rights and permissions
About this article
Cite this article
Javanian, M., Vahidi-Asl, M.Q. Note on the outdegree of a node in random recursive trees.JAMC13, 99–103 (2003). https://doi.org/10.1007/BF02936077
Received:
Revised:
Issue Date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative