View Single Post
Old 07-21-2012, 02:12 PM
yaser's Avatar
yaser yaser is offline
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,478
Default Re: Hoeffding’s inequality

Originally Posted by rakhlin View Post
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?
Where everyone thinks alike, no one thinks very much
Reply With Quote