Approximate counting: a detailed analysis (Q1057061)

Approximate counting is a probabilistic algorithm proposed by \textit{R. Morris} [Commun. ACM 21, 840-842 (1978; Zbl 0386.68035)] that allows the storage of (many) large counts in small counters. The algorithm allows counting up to some integer n in space \(\approx \log_ 2\log_ 2n+\delta\) with a constant expected relative accuracy that is \(O(2^{- \delta /2})\). For instance, using only 8 bits, one can count up to \(2^{16}=65536\) with an accuracy of about 15 \%. The paper presents a complete analysis of the algorithm which is equivalent to a pure birth process with discrete time and birth probabilities of the form \(2^{- k}\). The probability distribution of the approximate result is characterized exactly and is also shown to tend to a limiting distribution. Mean and variance of the result are estimated asymptotically using a combination of: (i) combinatorial identities in the theory of integer partitions; (2) Mellin transform techniques. The paper concludes with a comparison of approximate counting with direct sampling methods. One should also note that related methods appear in the space-efficient simulation of deterministic machines by probabilistic machines (Freivalds, Gill).