LOWER BOUNDS FOR SAMPLING ALGORITHMS FOR ESTIMATING THE AVERAGE

Authors
CANETTI R EVEN G GOLDREICH O
Citation
R. Canetti et al., LOWER BOUNDS FOR SAMPLING ALGORITHMS FOR ESTIMATING THE AVERAGE, Information processing letters, 53(1), 1995, pp. 17-25
Citations number
8
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
53
Issue
1
Year of publication
1995
Pages
17 - 25
Database
ISI
SICI code
0020-0190(1995)53:1<17:LBFSAF>2.0.ZU;2-P
Abstract
We show lower bounds on the number of sample points and on the number of coin tosses used by general sampling algorithms for estimating the average value of functions over a large domain. The bounds depend on t he desired precision and on the error probability of the estimate. Our lower bounds match upper bounds established by known algorithms, up t o a multiplicative constant. Furthermore, we give a non-constructive p roof of existence of an algorithm that improves the known upper bounds by a constant factor.