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.


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


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.