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

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.

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*}

• Thank you and understood it. – Changhee Kang Jan 31 at 3:37