Exact confidence interval for generalized Flajolet-Martin algorithms

This paper develop a deep mathematical-statistical approach to analyze a class of Flajolet-Martin algorithms (FMa), and provide a exact analytical confidence interval for the number $F_0$ of distinct elements in a stream, based on Chernoff bounds. The class of FMa has reached a significant popularity in bigdata stream learning, and the attention of the literature has mainly been based on algorithmic aspects, basically complexity optimality, while the statistical analysis of these class of algorithms has been often faced heuristically. The analysis provided here shows a deep connections with special mathematical functions and with extreme value theory. The latter connection may help in explaining heuristic considerations, while the first opens many numerical issues, faced at the end of the present paper. Finally, MonteCarlo simulations are provided to support our analytical choice in this context.