Need mathematical steps for Hoeffding's Inequality applied to Bernoulli Distribution

Question

I am trying to understand Hoeffiding's Inequality in Machine Learning and I am referring to WikiPedia for it. Hoeffding's Inequality is defined as follows:

$ P(|\hat{\theta} - \theta)| \ge \epsilon) \le 2e^{-2n\epsilon^2} $

But when the inequality applied to Independent and Identically Distributed Bernoulli Random Variables, the inequality becomes as follows:

How can I derive the second inequality from the first ineqaulity? I hope to get understandable mathematical steps from the first to the second inequality.

Answer 1

Let $X_1, \ldots X_n$ be iid Bernoulli random variables with parameter $p$ - think of this as a sequence of coin tosses, where $X_i = 1$ represents heads on the ith trial. Then, let $H(n)$ be the number of heads in the previous sequence: in other words,

$$H(n) = \sum_{i=1}^n X_i.$$

Hoeffding's inequality states that

$$P(|\overline{X} - \mathbb{E}[\overline{X}]| \geq \epsilon) \leq 2e^{-2n\epsilon^2},$$

Where $\overline{X} = \frac{1}{n}\sum_i X_i = H(n) / n$ is the sample mean. Next, note that $\mathbb{E}[\overline{X}] = p$. Therefore, we have that

\begin{align*} P(|H(n) / n - p| \geq \epsilon) &\leq 2e^{-2n\epsilon^2} \\ 1 - P(|H(n) / n - p| \leq \epsilon) &\leq 2e^{-2n\epsilon^2} \\ 1 - P(-\epsilon + p \leq H(n) / n \leq \epsilon + p) &\leq 2e^{-2n\epsilon^2} \\ 1 - P(n(p - \epsilon) \leq H(n) \leq n(p + \epsilon)) &\leq 2e^{-2n\epsilon^2} \\ P(n(p - \epsilon) \leq H(n) \leq n(p + \epsilon)) &\geq 1 - 2e^{-2n\epsilon^2} \end{align*}