__
TR97-020 | 15th May 1997 00:00
__

#### A Sample of Samplers -- A Computational Perspective on Sampling (survey).

**Abstract:**

We consider the problem of estimating the average of a huge set of values.

That is,

given oracle access to an arbitrary function $f:\{0,1\}^n\mapsto[0,1]$,

we need to estimate $2^{-n} \sum_{x\in\{0,1\}^n} f(x)$

upto an additive error of $\epsilon$.

We are allowed to employ a randomized algorithm which may err

with probability at most $\delta$.

We survey known algorithms for this problem

and focus on the ideas underlying their construction.

In particular, we present an

algorithm which makes $O(\epsilon^{-2} \cdot \log(1/\delta))$ queries

and uses $n+O(\log(1/\epsilon))+O(\log(1/\delta))$ coin tosses,

both complexities being very close to the corresponding lower bounds.