LFD Book Forum - View Single Post

magdon · #20 10-26-2016, 02:38 PM

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

Then, $e^{-\frac18\epsilon^2N}\ge e^{-\frac12\epsilon^2N}\ge\frac14$ .

In which case $4 m(2N) e^{-\frac18\epsilon^2N}\ge 4m(2N)/4\ge 1$ and the bound in Theorem A.1 is trivial.

Quote:

Originally Posted by CountVonCount

Hi,

I have a question about the sentence on page 190:

While I understand the argument here, I don't understand, why it is especially the value 1/4?
When set the above term to 1/4 I will receive -2*ln(1/4) as value for N*eps^2.
Now I can set N*eps^2 to that value in Theorem A.1 and I will get on the RHS (assuming the growth function is just 1) 4*0,707... so it is much more than 1.

A value of 1 in the RHS would be sufficient to say the bound in Theorem A.1 is trivially true. And this would assume, that the above term is less than 1/256.
With this in mind 1 - 2*e^(-0.5*N*eps^2) is greater than 0,99... and thus instead of a 2 in the lemmas outcome, I would receive a value around 1, which is a much better outcome.

So why is the value 1/4 chosen for the assumption?

Best regards,
André