Quote:
Originally Posted by rakhlin
First, c_rand and c_min aren't certain coins.

This is precisely the point why there is a question whether or not they satisfy Hoeffding inequality. The fact that they are not fixed coins does not prevent us from recording whether we got heads or tails from them in each iteration, so we can compute the frequency of heads. Since all the coins are identical in terms of the probability of getting a head or a tail, we have that same probability of heads regardless of which coin comes out.
Now the question is, when you compute the statistics of heads and tails in such experiment, do these statistics happen to fall under the bound that the basic Hoeffding inequality predicts for a fixed coin, notwithstanding that this experiment is not based on a fixed coin?