Combinatorics of geometrically distributed random variables: Left-to-right maxima

被引:48
作者
Prodinger, H [1 ]
机构
[1] VIENNA TECH UNIV,DEPT ALGEBRA & DISCRETE MATH,A-1040 VIENNA,AUSTRIA
关键词
D O I
10.1016/0012-365X(95)00141-I
中图分类号
O1 [数学];
学科分类号
0701 [数学]; 070101 [基础数学];
摘要
Assume that the numbers x(1),..., x(n) are the output of n independent geometrically distributed random variables. The number x(i) is a left-to-right maximum if it is greater (or equal, for a variation) than x(1),..., x(i-1). A precise average case analysis is performed for the parameter number of left-to-right maxima'. The methods include generating functions and a technique from complex analysis, called Rice's method. Some additional results are also given.
引用
收藏
页码:253 / 270
页数:18
相关论文
共 17 条
[1]
APPLICATIONS OF THE THEORY OF RECORDS IN THE STUDY OF RANDOM TREES [J].
DEVROYE, L .
ACTA INFORMATICA, 1988, 26 (1-2) :123-130
[2]
Devroye L., 1992, ANN APPL PROBAB, V2, P597
[3]
FLAJOLET P, 1988, LECT NOTES COMPUT SC, V317, P239
[4]
DIGITAL SEARCH-TREES REVISITED [J].
FLAJOLET, P ;
SEDGWICK, R .
SIAM JOURNAL ON COMPUTING, 1986, 15 (03) :748-767
[5]
PROBABILISTIC COUNTING ALGORITHMS FOR DATABASE APPLICATIONS [J].
FLAJOLET, P ;
MARTIN, GN .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1985, 31 (02) :182-209
[6]
FLAJOLET P, 1990, HDB THEORETICAL COMP, VA, P431
[7]
KEMP R, 1982, FUNDAMENTLAS AVERAGE
[8]
KIRSCHENHOFER P, 1990, LECT NOTES MATH, V1452, P117
[9]
A RESULT IN ORDER-STATISTICS RELATED TO PROBABILISTIC COUNTING [J].
KIRSCHENHOFER, P ;
PRODINGER, H .
COMPUTING, 1993, 51 (01) :15-27
[10]
KIRSCHENHOFER P, 1992, LECT NOTES COMPUT SC, V623, P211