Premium
Analysis of a splitting process arising in probabilistic counting and other related algorithms
Author(s) -
Kirschenhofer Peter,
Prodinger Helmut,
Szpankowski Wojciech
Publication year - 1996
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199612)9:4<379::aid-rsa3>3.0.co;2-u
Subject(s) - cardinality (data modeling) , probabilistic logic , algorithm , probabilistic analysis of algorithms , mathematics , set (abstract data type) , counting process , distribution (mathematics) , class (philosophy) , constant (computer programming) , mellin transform , computer science , statistics , artificial intelligence , mathematical analysis , laplace transform , data mining , programming language
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) = βa(z)g(z/2) + b(z) , where a(z) and b(z) are given functions and β < 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. © 1996 John Wiley & Sons, Inc. Random Struct. Alg. , 9 , 379–401 (1996)