Approximate counting with m counters: A probabilistic analysis

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].

Keywords

• Approximate counting, Moments, Constant and fluctuating components, Complex analysis, Product ofFourier series

References

1. J. Cichoń and W. Macyna, Approximate counters for flash memory, 17th IEEE International Confer- ence on Embedded and Real-Time Computing Systems and Applications (RTCSA), Toyama, Japan, 20 P. Flajolet, Approximate counting: A detailed analysis, BIT, 25, 113–134, 1985.
2. P. Flajolet and R. Sedgewick, Digital search trees revisited, SIAM J. Comput., 3, 748–767, 1986.
3. M. Fuchs, C. K. Lee, and H. Prodinger, Approximate counting via the Poisson-Laplace-Mellin method, DMTCS, proc AQ, 13–28, 2012.
4. H.-K. Hwang, M. Fuchs and V. Zacharovas, Asymptotic variance of random symmetric digital search trees, Discrete Math. Theor. Comput. Sci., 12, 103–166, 2010.
5. P. Kirschenhofer and H. Prodinger, Approximate counting: An alternative approach, RAIRO Theor. Inform. Appl., 25, 43–48, 1991.
6. D. E. Knuth, The art of computer programming, volume 3: Sorting and searching, Addison-Wesley, 1973, (Second edition, 1998).
7. M. Loève, Probability theory, 3rd ed, D. Van Nostrand, 1963.
8. G. Louchard, Exact and asymptotic distributions in digital and binary search trees, RAIRO Theor. Inform. Appl., 21(4), 479–496, 1987.

9. G. Louchard and H. Prodinger, Asymptotics of the moments of extreme-value related distribution functions, Technical report, 2005. Long version: http://www.ulb.ac.be/di/mcs/louchard/moml.ps.
10. G. Louchard and H. Prodinger, Asymptotics of the moments of extreme-value related distribution functions, Algorithmica, 46, 431–467, 2006.
11. G. Louchard and H. Prodinger, Generalized approximate counting revisited, Theoret. Comput. Sci., 391, 109–125, 2008.
12. H. Prodinger, Hypothetic analyses: Approximate counting in the style of Knuth, path length in the style of Flajolet, Theoret. Comput. Sci., 100, 243–251, 1992.
13. H. Prodinger, Approximate counting via Euler transform, Mathematica Slovaka, 44, 569–574, 1994.
14. H. Prodinger, Periodic oscillations in the analysis of algorithms and their cancellations, J. Iran. Stat. Soc., 3, 251–270, 2004.
15. H. Prodinger, Approximate counting with m counters: a detailed analysis, Theoret. Comput. Sci., 439, 58–68, 2012.