×

Distances in random plane-oriented recursive trees. (English) Zbl 0768.05029

Summary: The average number of nodes in a stratum of random plane-oriented recursive trees is found. The expression is used to determine the exact probability distribution of the depth of the \(n\)th node. It is further shown that the limiting distribution of the normalized depth of this node is the standard normal distribution. Via martingales, the normalized external path length is shown to converge almost surely and in \(L^ 2\) to a limiting random variable.

MSC:

05C05 Trees
05C12 Distance in graphs
05C80 Random graphs (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam · Zbl 0483.05029
[2] Devroye, L., Applications of the theory of records in the study of random trees, Acta Inform., 26, 123-130 (1988) · Zbl 0656.68065
[3] Dwyer, R., Las Vegas gift-wrapping is twice as fast, Private communications (1990)
[4] Gastwirth, J., A probability model of a pyramid scheme, Amer. Statist., 31, 79-82 (1977) · Zbl 0366.62128
[5] Graham, R.; Knuth, D.; Patashnik, O., Concrete Mathematics: a Foundation for Computer Science (1989), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0668.00003
[6] Hall, P.; Heyde, C., Martingale Limit Theory and Applications (1980), Academic Press: Academic Press New York · Zbl 0462.60045
[7] Knuth, D., The Art of Computer Programming, Vol. 3: Sorting and Searching (1973), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0302.68010
[8] Mahmoud, H., Limiting distributions for path lengths in recursive trees, Probab. Engrg. Inform. Sci., 5, 53-59 (1991) · Zbl 1134.68361
[9] Meir, A.; Moon, J., On the altitude of nodes in random trees, Canad. J. Math., XXX, 5, 997-1015 (1978) · Zbl 0394.05015
[10] Moon, J., The distance between nodes in recursive trees, (London Math. Soc. Lecture Note Ser., 13 (1974), Cambridge Univ. Press: Cambridge Univ. Press London), 125-132 · Zbl 0297.05101
[11] Najock, D.; Heyde, C., On the number of terminal vertices in certain random trees with an application to stemma construction in philology, J. Appl. Probab., 19, 675-680 (1982) · Zbl 0487.60012
[12] Régnier, M., A limiting distribution for quicksort, Theoret. Inform. Appl., 23, 335-343 (1989) · Zbl 0677.68072
[13] Szymański, J., On the complexity of algorithms on recursive trees, Theoret. Comput. Sci., 74, 3, 355-361 (1990) · Zbl 0701.68051
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.