LFD Book Forum  

Go Back   LFD Book Forum > Course Discussions > Online LFD course > Homework 2

Reply
 
Thread Tools Display Modes
  #1  
Old 10-16-2012, 07:39 PM
chris chris is offline
Junior Member
 
Join Date: Sep 2012
Posts: 5
Default Q2.2/Hoeffding clarifications

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...
Reply With Quote
  #2  
Old 10-16-2012, 09:16 PM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: Q2.2/Hoeffding clarifications

Quote:
Originally Posted by chris View Post
- 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

Quote:
- 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 \mu (out of sample) may not suffice.

Quote:
- 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 N of the Hoeffding inequality is 100,000.
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote
  #3  
Old 10-17-2012, 09:27 PM
chris chris is offline
Junior Member
 
Join Date: Sep 2012
Posts: 5
Default Re: Q2.2/Hoeffding clarifications

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?
Reply With Quote
  #4  
Old 10-18-2012, 05:46 PM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: Q2.2/Hoeffding clarifications

Quote:
Originally Posted by chris View Post
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.

Quote:
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.
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote
  #5  
Old 10-19-2012, 12:26 AM
chris chris is offline
Junior Member
 
Join Date: Sep 2012
Posts: 5
Default Re: Q2.2/Hoeffding clarifications

Quote:
Originally Posted by yaser View Post
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?

Quote:
Originally Posted by yaser View Post
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?
Reply With Quote
  #6  
Old 10-19-2012, 02:09 AM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: Q2.2/Hoeffding clarifications

Quote:
Originally Posted by chris View Post
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.

Quote:
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.
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote
  #7  
Old 10-19-2012, 04:42 AM
chris chris is offline
Junior Member
 
Join Date: Sep 2012
Posts: 5
Default Re: Q2.2/Hoeffding clarifications

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.
Reply With Quote
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -7. The time now is 04:54 PM.


Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. Abu-Mostafa, Malik Magdon-Ismail, and Hsuan-Tien Lin, and participants in the Learning From Data MOOC by Yaser S. Abu-Mostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.