I am asked to devise a random algorithm for the next question: Input: a list of n real numbers $\in [0,1], \epsilon>0, \delta>0$. Output: a real number t. Requierment: For each input, $|\frac{a_1+a_2+a_3+...a_n}{n}-t|<\epsilon$ with probability at least $1-\delta$.
I have tried to use Chernoff inequality and got some unuseable answer- $\frac{2\epsilon^2}{ln(\frac{2}{\delta})}>k$ which means that if I take less elements I get closer to the mean. Even worse, for little $\epsilon$'s I get a number less than 1 which make no sense at all.
I would very appreciate the help. Thanks.
This, like the related question asks for a randomized algorithm. What's random here is not the $a_i$ numbers but the random subset $S$ described below.
For a value of $m$ to be determined later, which will depend on $\epsilon$ and $\delta$ but not $n$, pick a random subset $S\subseteq[n]$ of size $m$, and let $x$ be the average of the $a_i$ such that $i\in S$.
It is easy to see that the expectation of $x$ is $\mu$ and the variance of $x$ goes like $2/m$. (Write $x=\sum_{i\in S} a_i / m = \sum_{i=1}^n I_i a_i / m$ where $I_i$ is the indicator of the event that $i\in S$. (Note that $P(\sum_{i=1}^n I_i=m)=1$ so the $I_i$ are not independent.) Check that $$EI_i = \frac m n,$$ $$\text{Var}(I_i) = \frac mn(1-\frac mn),$$ $$\text{Cov}(I_i,I_j) = \frac m n \frac{m-n}{n(n-1)}\text{ if } i\ne j$$ and so on.)
Now use Chebyshev's inequality: for given $\epsilon$ you can choose $m$ so big (independent of $n$) that the $\delta$ condition is satisfied.