How to Count Quickly and Accurately:
A Unified Analysis of Probabilistic Counting and Other
Related Problems
Abstract.
We consider a class of probabilistic counting algorithms parameterized by
an integer $d\geq 0$ that estimate the number of elements $N$
in a large set.
Our algorithms generalize an idea of Flajolet and Martin
who limited themselves to the case $d=0$.
As noted by Brassard and Bratley
``it is far from obvious how to carry out a more precise analysis of
the unbiased estimate of $N$ \dots ''.
We present a novel and complete analysis of
these new counting algorithms that
-- to the best of our knowledge -- cannot be
obtained by an extension of the analysis
by Flajolet and Martin.
We present results concerning the average value, the variance
and the limiting generating function
of an estimate of $N$.
Moreover, our novel approach is {\it not} limited to
probabilistic counting algorithms,
and it can be applied in the investigation
of several other ``splitting algorithms" such as
selecting the loser within a group of people, estimating the
number of questions
necessary to identify the number of distinct objects,
searching algorithms based on digital tries, approximate
counting, electing $d$ finalists in a contest (cf. polling system),
and so forth.
helmut@gauss.cam.wits.ac.za,
Peter.Kirschenhofer@tuwien.ac.at,
spa@cs.purdue.edu,
This paper is available in the Tex, Dvi, and PostScript format.
(Back to List of Papers)