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)1098-2418(199612)9:4<379::AID-RSA3>3.0.CO;2-U |
| Language | English | | Journal | Random Structures and Algorithms | | Volume | 9 | | Number | 4 | | Pages | 379-401 | | Year | 1996 | | Edition | 0 | | Translation |
No | | Refereed |
No |
|
