I'm trying to understand a problem that's more mathematical in nature that I'm accustomed to. Below I'll try to present the problem and what I have so far understood of it.
The problem
We have $X_1,..,X_n$ i.i.d. binary outcomes distributed according to Bernoulli distribution. The probability that $X_i = 1$ is given by $E[X_i] = p$. Hoeffding's inequality is somehow useful in solving the problem. It tells us that the total number of outcomes with value $1$ divided by $n$ is not too far from its expectation, which is $E[\frac{1}{n} \sum_{i=1}^n X_i] = \frac{1}{n} \sum_{i=1}^n E[X_i] = p$:
$Pr[|p-\frac{1}{n}\sum_{i=1}^n X_i| > \epsilon] \le 2exp(-2n\epsilon^2)$
Now I have to solve for the value $\epsilon$ for which the above probability equals $\alpha$. E.g. $n = 10$, $\alpha = 0.05$ this provides a bound that guarantees that with 95 % probability, the observed number of occurrences of $X_i = 1$ is within the interval $[n(p − \epsilon), n(p + \epsilon)]$. I must also evalute the width of this interval.
My understanding right now
The outcomes $X_1,..,X_n$ are something like coin tosses with a biased coin. We have some expectation $p$ for the coin toss to equal heads. The Hoeffding's inequality part says that if we take the sum of all of the expected values and multiply it with $\frac{1}{n}$ we get something close to $p$ (but why is it not $\frac{np}{n} = p$?) and the probability for it to be greater than $\epsilon$ is some (rather small?) number.
Now if we use the values of the example, the inequality would look like $0.05 \le 2^{-20\epsilon^2}$. I suppose I could solve that $\epsilon$ but the result is still an inequality and I think I need a concrete value to calculate $[10(p - \epsilon), 10(p + \epsilon)]$.
And if I'm correct the answer to the problem is some real valued range like $[5, 8]$ which says that there's a 95% possibility to get from 5 to 8 heads in 10 tosses, but I have no idea how to come up with the true range using that inequality.
I'm also not sure whether it's good to apply any real world scenarios in to this kind of abstract problems, or should I just try to learn to think on an abstract level and forget about the physical world? Especially if I'm to see a lot more problems like this.
Do you know of any materials that could possibly show me what's actually going on in that kind of equations? It's ok if I can't solve the problem but I would love to understand it on a level that doesn't make me want to scream and run away.
tl;dr
I'm having a hard time understanding probability distributions and inequalities with greek letters, but I would like to. Right now I'm stuck and I could use a pointer to the right direction.
I'll try to post updates as I go on.
Update
Ok so this is what I gathered:
So what the inequality is essentially saying is that when the amount of trials grows, the probability that we would deviate from our expected average by over some number $\epsilon$ decreases. And higher deviation also means smaller probability. It makes sense if I consider those coin tosses, because it's easy to see that during a large amount of trials the distribution should follow the the bias (if the coin has some).
Now if I estimate this $\alpha = 0.05$ for $100$ trials, I get that $2e^{-2*100*0.136^2} = 0.0494 \le 0.05$, which allows me to claim that in 95% of the cases I would deviate from the expected average by at most $0.136$.
How we arrive in to this conclusion without knowing anything about the initial probabilities is still beyond me. If I do not know them, the interval in the problem will take the form of $[100p-0.136, 100p+0.136]$ if I'm not mistaken?
Thanks for the explanation, I hope I understood it correctly and my apologies in advance if I didn't.