Corollary of Hoeffding’s Inequality Question
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})}}
$$
References

*

*Theorem 6 and Corollary 7 in this pdf

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
$$k=\frac{−2n}{(b−a)^2}\left(\sqrt{\frac{c}{2n}log(\frac{2}{\delta})}\right)^2=\frac{−2n}{c}\frac{c}{2n}log(\frac{2}{\delta})=-log(\frac{2}{\delta})=log(0.5\delta)$$
so
$$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$$
$\blacksquare$.
