While studying Hoeffding's Inequality, I am kind of struggling to understand the following equation:
$P(|\hat{\theta}-\theta|\geq\epsilon) = P(\hat{\theta}\notin [\theta-\epsilon, \theta+\epsilon]) \leq 2e^{-2n\epsilon^2}\leq \alpha$
How come I can write $\alpha$ on the last right side? What is the logical way of thinking about it?
If we let $X_1, \ldots, X_n \stackrel{\text{i.i.d.}}{\sim}$ Bernoulli$(p)$, then since $X_i \in [0, 1]$ for each $i$ Hoeffding's inequality says that $$ P(|\bar{X} - p| \geq t) \leq 2 e^{- 2n t^2} $$ or $$ P(|\bar{X} - p| < t) \geq 1 - 2 e^{- 2n t^2} . $$ If we want a $\alpha \times 100\%$ confidence interval for $p$ say, we can equate the right hand side to $\alpha$ and solve for $t$ which then could be used to find the endpoints of a $\alpha \times 100\%$ confidence interval for $p$.
I hope you are able to connect the two now.