LFD Book Forum - View Single Post

magdon · #25 11-09-2016, 06:23 AM

You are correct. We could have made other assumptions.

But there is a special reason why we DO want 1. Because we are bounding the probability, and so there is nothing to prove if we claim that a probability is less equal to 1. So, whenever the RHS (i.e. the bound) evaluates to 1 or bigger, there is nothing to prove. So we only need to consider the case when the bound evaluates to less than 1.

Quote:

Originally Posted by CountVonCount

Hello,

thanks for the answer. I understand this argument, however this holds also for

$e^{-\frac12\epsilon^2N}\ge\frac18$

or for

$e^{-\frac12\epsilon^2N}\ge\frac{1}{16}$

Thus the value 1/4 is somehow magic for me.

Edit: I think you choose 1/4 because it is so easy to see, that the RHS of Theorem A.1 gets 1. Nevertheless with a different value you would get a different outcome of the final formula.