View Single Post
Old 06-05-2016, 06:47 AM
henry2015 henry2015 is offline
Join Date: Aug 2015
Posts: 31
Default Re: Stuck on Problem 1.7

1. I think here is how P[max(..)>\epsilon] relates to the Rule of Addition:

Let's say A=|v0-u0|>\epsilon, B=|v1-u1|>\epsilon
<= P[A or B]
= P[A] + P[B] - P[A and B]

Since P[A] and P[B] are both bound by Hoeffding Inequality (HI), hence,
P[A] + P[B] - P[A and B]
<= 2 * (HI's bound) - P[A and B]
<= 2 * (HI's bound) because P[A and B] >= 0

In this case, we can see that M is 2 (as expected because we are using 2 coins).

2. See above.

3. I believe that if you rerun your script several times, you will see that the vanilla HI doesn't apply but M*HI's bound does. The reason your plot showed that HI applied because you were just lucky, and HI is talking about the upper bound, which indicates "always true" if the condition meets; that's why Exercise 1.10 asks the reader to run 100000 trials and then pick the min to make sure the reader won't be "lucky" to have vmin bound by the vanilla HI but M * HI's bound.

4. See #3.

I am not an expert so I could be wrong.

If any prof can confirm, it would be benefit for everyone reading here


Originally Posted by MaciekLeks View Post
Hello Professor Malik Magdon-Ismail,

I did Exercise 1.10/c and Problem 1.7. I've done it but I still do not know how to interpret the results correctly.

1. How the worst deviation method you mentioned is related to the hint in the book (the sum rule)?
2. If I use Hoeffding Inequality with your method, should I multiply RHS of Hoeffding Inequality by a number of coins (in this case M=2)? IMHO, I should not.
3. Why cmin in (Exercise 1.10) does not hold the hoeffding bound while max deriation in Problem 1.7 holds the bound (see the plot and the linked post)?
4. While increasing the sample size to N=10 the Hoeffding bound is not longer held for Problem 1.7. Why?

The plots:

N=6, RHS=2.0*exp(-2.0*(ε^2.0)*N)

N=10, RHS=2.0*exp(-2.0*(ε^2.0)*N)

P.S. Please see my unanswered question for Exercise 1.10 (c) here:

Last edited by henry2015; 06-05-2016 at 09:29 PM. Reason: clarity
Reply With Quote