Details:
Title  Analysis of a splitting process arising in probabilistic counting and other related algorithms  Author(s)  Peter Kirschenhofer, Helmut Prodinger, Wojciech Szpankowski  Type  Article in Journal  Abstract  We present an analytical method of analyzing a class of "splitting algorithms" that include probabilistic counting, selecting the leader, estimating the number of questions necessary to identify distinct objects, searching algorithms based on digital tries, approximate counting, and so forth. In our discussion we concentrate on the analysis of a generalized probabilistic counting algorithm. Our technique belongs to the toolkit of the analytical analysis of algorithms, and it involves solutions of functional equations, analytical poissonization and depoissonization as well as Mellin transform. In particular, we deal with an instance of the functional equation 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 algorithm, we obtain asymptotic expansions of the first two moments of an estimate of the cardinality of a set that is computed by the algorithm. We also derive the asymptotic distribution of this estimate, and observe that it actually fluctuates, leading to a conclusion that its limiting distribution does not exist.  Copyright  John Wiley & Sons, Inc. 
URL 
dx.doi.org/10.1002/(SICI)10982418(199612)9:4<379::AIDRSA3>3.0.CO;2U 
Language  English  Journal  Random Structures and Algorithms  Volume  9  Number  4  Pages  379401  Year  1996  Edition  0  Translation 
No  Refereed 
No 
