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.