Premium
Probabilistic analysis of adaptative sampling
Author(s) -
Louchard Guy
Publication year - 1997
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199701/03)10:1/2<157::aid-rsa8>3.0.co;2-u
Subject(s) - mathematics , bessel function , random tree , struct , sampling (signal processing) , probabilistic logic , stirling numbers of the second kind , tree (set theory) , generating function , moment generating function , algorithm , discrete mathematics , computer science , random variable , combinatorics , statistics , mathematical analysis , artificial intelligence , filter (signal processing) , motion planning , robot , computer vision , programming language
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)