in one of the courses the professor said that Hoeffding's Inequality equation is this enter image description here but for me that does not make any sense as it can be greater than $1.$

For example, assume

$$\varepsilon = 0.00001$$

$$N = 1000$$

That will make the probability $\leq 2( e^{-2\cdot 0.0000000001\cdot 1000}) = 2\cdot 0.999999 = 1.99999.$

Is there something wrong here?


1 Answer 1


Nothing is wrong - if the right hand side is greater than $1$, it just means that the inequality is pointless in that case, since all probabilities are less than or equal to $1$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .