Approximate counting with m counters: A detailed analysis

摘要

The classical algorithm approximate counting has been recently modified by Cichori and Macyna: instead of one counter, m counters are used, and the assignment of an incoming item to one of the counters is random. The parameter of interest is the sum of the values of all the counters. We analyse expectation and variance, getting explicit and asymptotic formulae.