Probabilistic analysis of adaptative sampling
Guy Louchard · Random Structures and Algorithms · 2000
This paper analyzes the asymptotic properties of a classical algorithm: the adaptative sampling which solves the following problem; how to estimate the number M of distinct elements of a large collection of n data. Using tools such as the random tree and techniques such as Mellin transforms, combinatorial identities on Stirling numbers and Bessel functions, we analyze all moments and the asymptotic distribution function of the algorithm. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10, 157–168 (1997)