So the exercise is the following:
Let $g(x):[0,1] \to [0,1]$ a continuous function, we want to estimate the integral:
$\int_{0}^{1} g(x)\ \mathrm{d}x$
How many samples $g(X_n)$, with $X_n \sim \mathcal{U}_{[0,1]}$ are needed to estimate the integral with an error of $0.01$ with a probability of $0.99$ with:
$\frac{1}{n}(g(X_1) + g(X_2) + \ldots + g(X_n))$
The only hint is to use the Bernstein Inequality which says:
$\mathbb{P}(\frac{S_n}{n} > t) \leq \exp(\frac{nt^2}{2(v+Bt)})$
I hope someone can give me a hint on this.
Best Answer
Note that $\mathsf{E}g(X_i)=\int_0^1 g(x)\,dx$. Then, one may use Hoeffding's inequality to get $$ \mathsf{P}\!\left(\left|\frac{1}{n}\sum_{i=1}^n g(X_i)-\mathsf{E}g(X_1)\right|>t\right)\le 2\exp\!\left(-2nt^2\right). $$ Plugging $t=0.01$, the bound $2\exp(-2\cdot 10^{-4}n)\le (1-0.99)$ when $n\ge 26,\!492$.