Exercise 1.10d

[saitama]

I can see why coin c_1 obeys the Hoeffding bound since we restrict our attention to a single coin (eg a single bin). And i can understand why c_min does not hold since we pick an optimal value (ie minimum) over multiple coins (kind of like the best hypothesis over multiple bins).

However, I'm having a hard time understanding why the Hoeffding bound also applies to the c_rand coin. Although we don't pick an optimal value we do consider multiple coins (eg multiple bins). Does considering multiple coins not matter in this case??

[don slowik]

Just one bin is being considered after you have chosen it. Just like choosing bin 1..
Hoeffding should apply to any one of the 100,000 runs, but not to the 'best' or 'worst' run.

[saitama]

I think I understand now. I guess the c_rand coin does only considering one bin at a time when choosing an optimal value. Its not like we search multiple coins. Thanks for the reply