PROBABILISTIC ANALYSIS OF ADAPTATIVE SAMPLING

Authors
LOUCHARD G
Citation
G. Louchard, PROBABILISTIC ANALYSIS OF ADAPTATIVE SAMPLING, Random structures & algorithms, 10(1-2), 1997, pp. 157-168
Citations number
8
Categorie Soggetti
Mathematics,Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Random structures & algorithms → ACNP
ISSN journal
10429832
Volume
10
Issue
1-2
Year of publication
1997
Pages
157 - 168
Database
ISI
SICI code
1042-9832(1997)10:1-2<157:PAOAS>2.0.ZU;2-0
Abstract
This paper analyzes the asymptotic properties of a classical algorithm : the adaptative sampling which solves the following problem; how to e stimate the number M of distinct elements of a large collection of n d ata. Using tools such as the random tree and techniques such as Mellin transforms, combinatorial identities on Stirling numbers and Bessel f unctions, we analyze all moments and the asymptotic distribution funct ion of the algorithm. (C) 1997 John Wiley & Sons, Inc.