English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Wojciech S:r,pankowskit Dept. Computer Science Purdue University W. Lafayette, IN 47907 U.S.A. vVe present an analytical method of analyzing a class of "splitting algorilhms" 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, ,mel so forth. In our disCl1ssion we concentrate on the analysis of a generalized probabilistic counting algorithm. Our techniquc belongs to lhe toolkit of the a.nalytical analysis of algorithms, and it involves solutions offunctional equations, analytical poissoniJr.ation and depoissorllzation, Mellin transform, etc. In particular, we deal with a functional equation of lhe form g(z) = fJa(z)g(z/2) + b(z) where a(z) and b(z) are given funclions, and fJ < 1 is a constant. With respect to our generalized probabilistic counting algorithm, we obtain asymptotic expansions of the first two moments of an estimatc of the cardinality of a set that is computed by the algorithm. We also derive the asymptotic distribution of tIllS cstimate, and observe that it actually flucluales, leading to a conclusion that its limiting distribution docs not exist . •A preliminary version of parts of tilis paper was presented ill }CALP 92, Vienna [26]. This work w~ supported by NSF Grants INT-8912631 and CCH.-9201078. lThis author was additionally was supported by NSF Grants NSF Gra.nts NCH.-!l206315 and NCH9115191, and in part by NATO Collaborative Grant CRG.!l50060.

Analysis of a splitting process arising in probabilistic counting and other related algorithms