A result in order statistics related to probabilistic counting
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.
This paper is available in the Tex, Dvi, and PostScript format.
(Back to List of Papers)