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.