Understanding a binary classifier problem

Question

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.

Answer 1

This kind of analysis could be confusing if you are new to it. I think you need some intuition about what's going on. I will assume you understood until this point

$$ Pr[|p - \frac{1}{n} \sum_{i = 1}^{n} X_i| > \epsilon] \leq 2 e^{-2n\epsilon^2} $$

(If not, hold tight and ask in the comments, I will elaborate).

So this inequality tells you this. You should be expecting the average value to be around the expected value of the average (that's why they call it expected value), and larger and larger deviations should be less and less likely. So if you ask what is the probability the average is at least $0.01$ away from the expected value, you plug-in $\epsilon = 0.01$ in the right hand side and get an upper bound on the probability that this happens.

Notice that as $\epsilon$ gets larger the probability gets smaller and smaller. Also notice that as $n$ gets larger, the probability gets smaller. These reason behind these two statements should be clear to you. (If not, pause and think about it).

Now you ask the inverse question. If I want to be 95% sure that the average is within $\epsilon$ from the expected, how big must epsilon be. Notice that the answer to this question must necessarily be a lower bound on $\epsilon$. Since if you are 95% sure that the average is within $\epsilon$ from the expected value, then with even bigger probability you are sure that it is within a bigger range from expected.

So what you want to do is assert that $Pr[\dots > \epsilon] \leq 0.05$, that is the probability that the average is farther away than $\epsilon$ be at most 5%. You cannot calculate the probability exactly, but you do have an upper bound on how big it can be (given by your inequality above). So if you want to be certain the probability is less than 5%, you can assert that the upperbound on the probability is less than 5%. That is, you want to solve:

$$ 2 e^{-2n\epsilon^2} \leq \alpha = 0.05 $$

Note, that solving this will give you something like $\epsilon \geq \dots$ That means as long as you choose $\epsilon$ to be at least this, you are sure that the probability of deviating from the expected value by at least $\epsilon$ is at most 0.05.

Of course you can do the entire analysis for a variable $\alpha$ instead of 0.05.