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.

Questions:

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:

http://book.caltech.edu/bookforum/showthread.php?t=4616