A result in order statistics related to probabilistic counting

Abstract. 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)