Normal approximation and Hoeffding bound

Question

Hoeffding bound for any $\epsilon>0$ is: $$P_F(|\bar{X}_n-\mu(F)|\geq \epsilon)\leq 2 \exp\{-\frac{n\epsilon^2}{2}\}=h(\sqrt{n}\epsilon)$$ wherever $|X|<1$.

Now I want to have a comparison between this normal approximation and Hoeffding bound. I read that the normal approximation $2\Phi(\frac{\sqrt{n}\epsilon}{\sigma})-1$ gives lower results than $h$ in tails if $P(|X|\leq 1)=1$ because, if $\sigma^2\leq 1$, $1-\Phi(t)\sim\phi(t)/t$ as $t\rightarrow\infty$. I have a bit difficulty in understanding and also verifying this.

Answer 1

Here's how you show $1-\Phi(t)\leq \phi(t)/t$, which is enough in your problem

$$1-\Phi(t) = \frac{1}{\sqrt{2\pi}}\int_t^\infty e^{-x^2/2}\,dx$$ Now $$\int_t^\infty e^{-x^2/2}\,dx=\frac{\int_t^\infty te^{-x^2/2}\,dx}{t}<\frac{\int_t^\infty xe^{-x^2/2}\,dx}{t}$$ and the integrand is minus the derivative of $\exp(-x^2/2)$, so the integral is $\exp(-t^2/2)$. Thus we have $$1-\Phi(t) = \frac{1}{\sqrt{2\pi}}\int_t^\infty e^{-x^2/2}\,dx< \frac{1}{\sqrt{2\pi}}\frac{e^{-t^2/2}}{t}=\phi(t)/t$$

So, yes, the Hoeffding bound of $\exp(-(\sqrt{n}\epsilon)^2/2)$ is larger than the result from the Normal approximation.

That's not particularly surprising. We know the Hoeffding bound won't be smaller in any uniform way, because then the Normal approximation would violate it for large enough $n$.