I am not from a statistics background. I came across the following corollary of Hoeffding’s Inequality and couldn't find the derivation or proof for it. Could anyone please share some reference of proof or just prove it here?

Hoeffding’s Inequality

Let $Y_1, Y_2, \cdots, Y_n$ be i.i.d. observations such that $\mathbb{E}(Y_i) = \mu$ and $a \leq Y_i \leq b$. Then for any $\epsilon > 0$; $$ \mathbb{P}( | \bar{Y_n} - \mu | \geq \epsilon) \leq 2 e^{-2 n \epsilon^2 / (b - a)^2} $$

Corollary of Hoeffding’s Inequality

Let $Y_1, Y_2, \cdots, Y_n$ are independent with $\mathbb{P}( a \leq Y_i \leq b ) = 1$ and common mean $\mu$, then, with probability at least $1 - \delta$,

$$ | \bar{Y_n} - \mu | \leq \sqrt{ \frac{c}{2n} \log{(\frac{2}{\delta})}} $$



1 Answer 1


Let's start with putting the corollary in a probability form (note that $c=(b-a)^2$: $$P\left( |\bar{Y}_n - \mu| \leq \sqrt{\frac{c}{2n}log(\frac{2}{\delta})} \right) \geq 1-\delta$$

Now, from the theorem we know that

$$P\left( |\bar{Y}_n - \mu| \geq \sqrt{\frac{c}{2n}log(\frac{2}{\delta})} \right) \leq 2e^k$$ where



$$P\left( |\bar{Y}_n - \mu| \geq \sqrt{\frac{c}{2n}log(\frac{2}{\delta})} \right) \leq 2e^{log(0.5\delta)}=2\cdot 0.5\delta=\delta.$$

Multiplying by -1:

$$-P\left( |\bar{Y}_n - \mu| \geq \sqrt{\frac{c}{2n}log(\frac{2}{\delta})} \right) \geq -\delta$$

Adding 1 to both sides: $$1-P\left( |\bar{Y}_n - \mu| \geq \sqrt{\frac{c}{2n}log(\frac{2}{\delta})} \right) \geq 1-\delta$$

but assuming $x$ is continuous, $1-P(x \geq z)= P(x\leq z)$, so:

$$P\left( |\bar{Y}_n - \mu| \leq \sqrt{\frac{c}{2n}log(\frac{2}{\delta})} \right) \geq 1-\delta$$



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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