Comparing Confidence Intervals for Hoeffding’s and Bernstein’s Inequality

We have now been introduced to four different concentration inequalities: Markov’s Inequality, Chebyshev’s Inequality, Hoeffding’s Inequality, and Bernstein’s Inequality We have even compared the tightness of all four of them. In this article, we will only consider Hoeffding’s and Bernstein’s Inequality. However, this time we will look at another version of the bounds — when we fix ε and instead define the bound using δ.

Remembering Hoeffding’s Inequality