Corollary of Hoeffding’s Inequality

Question

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

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

$$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$.