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:

enter image description here

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.