Q2.2/Hoeffding clarifications

[chris]

A few questions regarding question 2.2:

- Is the question asking which statistics (v_1, v_r and v_min) fit the assumptions underlying application of the Hoeffding inequality for estimating the bias of an individual coin (i.e. mu = out of sample probability of a head)?

- Is it fair to say that Hoeffding can be applied to any of these statistics as long as mu reflects the out of sample distribution of that statistic?

- What is the appropriate value of N when applying Hoeffding to the average of 100,000 repetitions of the average number of heads realised by 10 coin flips? Is it 100,000 or 1,000,000? Seems to me that the overall process is equivalent to averaging the number of heads over 1,000,000 coin flips?

Thanks in advance for your help...

[yaser]

Originally Posted by chris

- Is the question asking which statistics (v_1, v_r and v_min) fit the assumptions underlying application of the Hoeffding inequality for estimating the bias of an individual coin (i.e. mu = out of sample probability of a head)?

Correct

- Is it fair to say that Hoeffding can be applied to any of these statistics as long as mu reflects the out of sample distribution of that statistic?

Hoeffding involves both in-sample and out-of-sample frequencies, so just (out of sample) may not suffice.

- What is the appropriate value of N when applying Hoeffding to the average of 100,000 repetitions of the average number of heads realised by 10 coin flips? Is it 100,000 or 1,000,000? Seems to me that the overall process is equivalent to averaging the number of heads over 1,000,000 coin flips?

If the basic event here involves 10 coin tosses (say the event being that the number of heads out of 10 tosses is 10), and that experiment is repeated 100,000 times, then of the Hoeffding inequality is 100,000.

[chris]

Thanks for your reply Yaser, much appreciated.

Regarding my second question, I was trying to determine whether Hoeffding can be applied to v_min using mu = the expected minimum fraction of heads from 10 flips of 1000 coins (<< 0.5 for unbiased coins) rather than mu = the expected fraction of heads from 10 flips of a single coin (0.5 for an unbiased coin). I interpreted the question as assuming the latter but my understanding of Hoeffding is that it could be applied to v_min assuming the former. Does that make sense?

And to clarify my final question, I was thinking about the case of v_1 where the expected value of the statistic in question is not affected by the number of coins or number of flips of each coin per experiment. Specifically, I would like to understand the difference between 2 approaches to estimating the probability of flipping a head from a Hoeffding perspective (1) averaging the fraction of heads realised by 10 coin flips over 100,000 experiments, and (2) the fraction of heads realised by 1,000,000 repetitions of a single flip. They are the same in terms of the calculation of the average statistic over 1,000,000 total flips but (2) gives a tighter Hoeffding bound. Presumably to calculate a simple statistic such as the probability of a head for a specific coin (vs a more complex statistic such as the min fraction of heads from 10 flips of 1000 coins), one would always frame the experiment as (2) to take advantage of the lower Hoeffding probability of error bound?

[yaser]

Originally Posted by chris

Regarding my second question, I was trying to determine whether Hoeffding can be applied to v_min using mu = the expected minimum fraction of heads from 10 flips of 1000 coins (<< 0.5 for unbiased coins) rather than mu = the expected fraction of heads from 10 flips of a single coin (0.5 for an unbiased coin).

Hoeffding cannot be directly applied, but more general forms that use expected values and variances of general random variables (rather than just the probability of an event and the frequency of occurence of that event) can be applied.

Specifically, I would like to understand the difference between 2 approaches to estimating the probability of flipping a head from a Hoeffding perspective (1) averaging the fraction of heads realised by 10 coin flips over 100,000 experiments, and (2) the fraction of heads realised by 1,000,000 repetitions of a single flip.

Hoeffding can be directly applied to (1), the event being "ten heads out of 10 flips," whereas (2) involves the expected value of a random variable as discussed above.

[chris]

Originally Posted by yaser

Hoeffding cannot be directly applied, but more general forms that use expected values and variances of general random variables (rather than just the probability of an event and the frequency of occurence of that event) can be applied.

I think I'm starting to converge on an understanding. So the basic form of Hoeffding introduced in lecture only addresses estimating the probability of an event. I checked the Wikipedia entry for the Hoeffding inequality (http://en.wikipedia.org/wiki/Hoeffding%27s_inequality) and it states a more general form that covers the expected value of bounded random variables. Is this one of the more general forms that you mentioned? Looks like the Hoeffding equation in the lecture could be derived from this form by setting the lower and upper bounds to 0 and 1. Am I on the right track here?

Originally Posted by yaser

Hoeffding can be directly applied to (1), the event being "ten heads out of 10 flips," whereas (2) involves the expected value of a random variable as discussed above.

Could the basic form of Hoeffding be used for (2) where the event is described as flipping a head on a single coin toss?

[yaser]

Originally Posted by chris

it states a more general form that covers the expected value of bounded random variables. Is this one of the more general forms that you mentioned?

Correct. You can also look up Chebyshev inequality and Chernoff bounds.

Could the basic form of Hoeffding be used for (2) where the event is described as flipping a head on a single coin toss?

Yes, although this case may not be of particular interest.

[chris]

Thanks for your help in resolving my queries Yaser, it is very much appreciated. Fantastic course by the way and looking forward to reading the book when it arrives in my post box.