Approximate counting with m counters: A probabilistic analysis
Keywords:
Approximate counting, Moments, Constant and fluctuating components, Complex analysis, Product of Fourier series
Abstract
Motivated by a recent paper by Cicho\'n and Macyna [1], who introduced $m$ counters (instead of just one) in the approximate counting scheme first analysed by Flajolet [2], we analyse the moments of the sum of the $m$ counters, using techniques that proved to be successful already in several other contexts [11].
