Quote:
Originally Posted by raghu
From what I understood we are sampling a coin's error 100,000 times and then we plot the probability distribution and this should satisfy the Hoffding inequality.

Statistically speaking, there is no difference between c_1 and c_rand.
One way to see this is to consider you have only 1 coin and want to know coin bias by using 10 experiments. If you just take that coin and perform the 10 experiments, you might, or might not, get 10*p (p is the bias) heads. To make sure that you have a statistically meaningful result, you average over 100000 different realizations of that experiment.
Now go back to the situation where you have the 1000 coins. c_1 obviously corresponds to the case where you have 1 coin only. However, if all 1000 coins have the same bias, when you average over 100000 realizations of the the experiment, it doesn't matter whether you pick, for a given realization, any of the available 1000 coins at random since they will all behave the same, statistically speaking.
The case of c_min is different because you are making the distinction of, for each realization, which one is the worst behaved vs how the average coin behaves (which is what c_1 and c_rand measure).