Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleAnalysis of a splitting process arising in probabilistic counting and other related algorithms
Author(s) Peter Kirschenhofer, Helmut Prodinger, Wojciech Szpankowski
TypeArticle in Journal
AbstractWe 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.
CopyrightJohn Wiley & Sons, Inc.
URL dx.doi.org/10.1002/(SICI)1098-2418(199612)9:4<379::AID-RSA3>3.0.CO;2-U
JournalRandom Structures and Algorithms
Translation No
Refereed No