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

We remember that we have already seen Hoeffding’s Inequality in the following manner:

This simply gives an upper bound on the probability that the sum of bounded independent random variables deviates from its expected value by more than a certain amount. The different parts are the following:

• N: This is the number of samples we have, also defined as sample size.
• µ: This is the expected value of our random variables.
• v: This is the observed mean value of our random variables.
• ε: This is epsilon, which defines the deviation of v from µ.

Now, we have already worked with and compared this specific version of the inequality quite a few times. This time we are interested in fixing ε and instead define the bound using δ. We then get the following bound: