Analysis of a splitting process arising in probabilistic counting and other related algorithms

Abstract. In this paper we describe an approach that allows to analyze a class of "splitting algorithms" which generalize the well-known "probabilistic counting" procedure due to Flajolet and Martin. Similar splitting processes occur in selecting the leader, estimating the number of questions necessary to identify distinct objects, searching algorithms based on digital tries, approximate counting, and so forth. Our technique belongs to the toolkit of the analytical analysis of algorithms, and it involves solutions of functional equations, analytical poissonization and depoissonization, Mellin transform, etc. In particular, we deal with a functional equation of the form $g(z)=\beta a(z)g(z/2)+b(z)$ where $a(z)$ and $b(z)$ are given functions, and $\beta<1$ is a constant. With respect to our generalized probabilistic counting algorithms we obtain asymptotic expansions of the first two moments of the estimate. We also derive the {\it asymptotic} distribution of the estimate, and observe that it actually fluctuates, leading to a conclusion that its {\it limiting} distribution does not exist.

helmut@gauss.cam.wits.ac.za,

Peter.Kirschenhofer@tuwien.ac.at,
spa@cs.purdue.edu (Wojciech Szpankowski),

This paper is available in the Tex, Dvi, and PostScript format.

(Back to List of Papers)