Understanding a binary classifier problem
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| &gt; \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 &gt; \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.