4
$\begingroup$

If I am correct, both Hoeffding inequality and Chernoff bound are about bounds on the probability of sample mean deviates from the true mean.

Besides that, I wonder how Hoeffding inequality and chernoff bound are related?

Is the conditionin Hoeffding inequality more restricted than Chernoff bound's?

Is the bound in Hoeffding inequality tighter than Chernoff bound's?

Is one the special case of the other? I.e. one can be derived from the other?

Thanks!

  • 0
    Both Hoeffding and Chernoff bounds are exponentially tight, which is better than Markov/Chebyshev, and both are special cases of Bernstein inequality (there is a Wikipedia article on it too2012-10-16
  • 0
    Thanks, @Alex! How is the relation between Bennett's inequality, and Bernstein inequality and other inequalities?2012-10-16
  • 0
    Have a look in Bennet's article, http://www.jstor.org/stable/10.2307/2282438, as far as I know Chernoff is the only one that exists readily in multiplicative form. All of them can be derived from Markov inequality, have a look here for example http://math.stackexchange.com/questions/195064/chernoff-inequalities-for-the-sum-of-exponential-rvs2012-10-16
  • 0
    Thanks! I feel there are so many similar inequalities, and am so not sure which leads to which. Do you have some nice references for summarizing the results?2012-10-16
  • 0
    Yes, one of the (fairly recent) achievements include proof of Kolmogorov inequality. Try an article called 'Concentration inequalities' by Boucherone, Lugosi and Bousquet2012-10-16

0 Answers 0