A RESULT IN ORDER-STATISTICS RELATED TO PROBABILISTIC COUNTING

被引：22

作者：

KIRSCHENHOFER, P

PRODINGER, H

机构：

[1] Department of Algebra and Discrete Mathematics, TU Vienna, Vienna, A-1040

来源：

COMPUTING | 1993年 / 51卷 / 01期

关键词：

ORDER STATISTICS; ASYMPTOTIC ANALYSIS;

D O I：

10.1007/BF02243826

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 [计算机软件与理论];

摘要：

Considering geometrically distributed random variables the d-maximum of these events is investigated, i.e. the d-th largest element (with repetitions allowed). The quantitative behaviour of expectation and variance is analyzed thoroughly. In particular the asymptotics of the variance for d getting large is established by means of nontrivial techniques from combinatorial analysis and complex variable theory. These results apply to probabilistic counting algorithms, where the cardinalities of large sets are estimated.

引用

页码：15 / 27

页数：13

共 14 条

[1]

[Anonymous], 1970, HDB MATH FNCTIONS

[2]

DIGITAL SEARCH-TREES REVISITED [J].