View Single Post
Old 07-24-2012, 02:10 PM
fgpancorbo fgpancorbo is offline
Senior Member
Join Date: Jul 2012
Posts: 104
Default Re: Hoeffding’s inequality

Originally Posted by raghu View Post
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).
Reply With Quote