Consider the following problem:
Let $f:[0,1]\rightarrow[0,1]$ be a continuous function. We want to determine the integral $\int_0^1 f(x)dx$.
We can do it using a following method:
Suppose $X_1,Y_1,X_2,Y_2,...$ are independent and each $\mathfrak{U}(0,1)$ distributed. Define the random variable
$Z_n:\left\{\begin{array}{ll} 1, & Y_n<f(X_n) \\ 0, & Y_n \geq f(X_n)\end{array}\right. .$
Show that then $\frac{1}{n}\sum_{k=1}^n Z_k \rightarrow \int_0^1 f(x) dx$ almost sure applies.
Use the Hoeffding inequality to find a lower bound for $n \in \mathbb{N}$ so that the integral of $f$ with a probability of at least 0.95 is determined to an accuracy of at least 0.01.
Honestly, I don't know how to attack this problem, I hope someone can help me..?
It is not hard to see, that $Z_1, Z_2, ... $ are i.i.d. random variables $\sim Bern(p)$. Let's find $p$:
$p = P(Y_1 \leq f(X_1)) = \int_0^1 P(Y_1 \leq f(x))dx = \int_0^1 f(x)dx$
Then, we can deduce the following:
$\frac{1}{n}\sum_{i=1}^n Z_i \to E[Z_1] = \int_0^1 f(x)dx$ a.s.
$P(|\frac{1}{n}\sum_{i=1}^n - E[Z_1]| > t) \leq 2e^{-2nt^2}$
That means, we want to find a lower bound for $n \in \mathbb{N}$ so that the integral of $f$ with a probability of at least $1-\alpha$ is determined to an accuracy of at least $\beta$, we need to solve the equation
$2e^{-2n\alpha^2} = \beta$
That is $n = -\frac{\ln(\frac{\beta}{2})}{2\alpha^2}$.