DISTANCES IN RANDOM PLANE-ORIENTED RECURSIVE TREES

被引：37

作者：

MAHMOUD, HM ^{[1
]}

机构：

[1] GEORGE WASHINGTON UNIV,DEPT STAT COMP & INFORMAT SYST,WASHINGTON,DC 20052

来源：

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS | 1992年 / 41卷 / 1-2期

关键词：

RECURSIVE TREE; DEPTH; PATH LENGTH; LIMIT THEOREM; MARTINGALE;

D O I：

10.1016/0377-0427(92)90252-S

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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 nth 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 L2 to a limiting random variable.

引用

页码：237 / 245

页数：9

共 13 条

[1]

Berge C., 1973, GRAPHS HYPERGRAPHS

[2] APPLICATIONS OF THE THEORY OF RECORDS IN THE STUDY OF RANDOM TREES [J].

DEVROYE, L .

ACTA INFORMATICA, 1988, 26 (1-2) :123-130

[3]

DWYER R, 1990, COMMUNICATION

[4]

GASTWIRTH JL, 1977, AM STAT, V31, P79, DOI 10.2307/2683046

[5]

HALL P, 1980, MARTINGALE LIMIT THE

[6]

Knuth D.E., 1997, ART COMPUTER PROGRAM, V3

[7]

Mahmoud H., 1991, PROBAB ENG INFORM SC, V5, P53

[8] ALTITUDE OF NODES IN RANDOM TREES [J].

MEIR, A ;

MOON, JW .

CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 1978, 30 (05) :997-1015

[9]

Moon J. W., 1974, LONDON MATH SOC LECT, V13, P125

[10] ON THE NUMBER OF TERMINAL VERTICES IN CERTAIN RANDOM TREES WITH AN APPLICATION TO STEMMA CONSTRUCTION IN PHILOLOGY [J].

NAJOCK, D ;

HEYDE, CC .

JOURNAL OF APPLIED PROBABILITY, 1982, 19 (03) :675-680

← 1 2 →