# 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

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