zbMATH — the first resource for mathematics

Lower bounds for sampling algorithms for estimating the average. (English) Zbl 0875.68529
Summary: 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 the desired precision and on the error probability of the estimate. Our lower bounds match upper bounds established by known algorithms, up to a multiplicative constant. Furthermore, we give a non-constructive proof of existence of an algorithm that improves the known upper bounds by a constant factor.

68Q25 Analysis of algorithms and problem complexity
65C05 Monte Carlo methods
Full Text: DOI
[1] Bellare, M.; Goldreich, O.; Goldwasser, S., Randomness in interactive proofs, (), 563-571
[2] Canetti, R.; Even, G.; Goldreich, O., Lower bounds for sampling algorithms for estimating the average, () · Zbl 0875.68529
[3] Goldreich, O.; Wigderson, A., Tiny families of functions with random properties: A quality-size trade-off for hashing, () · Zbl 1345.68117
[4] Hoefding, W., Probability inequalities for sums of bounded random variables, J. amer. statist. assoc., 58, 13-30, (1963) · Zbl 0127.10602
[5] Karp, R.M.; Luby, M., Monte-Carlo algorithms for enumeration and related problems, (), 56-64 · Zbl 0596.90033
[6] Karp, R.M.; Luby, M.; Madras, N., Monte-Carlo approximation algorithms for enumeration problems, J. algorithms, 10, 3, 429-448, (1989) · Zbl 0678.65001
[7] Newman, I., Private vs. common random bits in communication complexity, Inform. process. lett., 39, 67-71, (1991) · Zbl 0735.68034
[8] Van Trees, H.L., Detection, estimation, and modulation theory, (1968), John Wiley & Sons New York, Part 1 · Zbl 0202.18002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.