LFD Book Forum  

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

Reply
 
Thread Tools Display Modes
  #1  
Old 04-16-2012, 08:20 AM
gordonbr gordonbr is offline
Junior Member
 
Join Date: Apr 2012
Posts: 3
Default What does it mean to "satisfy" Hoeffding's Inequality?

I'm confused about the process of determining whether a particular random sample "satisfies" Hoeffding's inequality.

In particular, when we run some experiments and determine the average proportion of green marbles, we generate some averages for several E_{in} values. Can't we say that all of these E_{in} values satisfy Hoeffding's Inequality, since Hoeffding's Inequality only says that the probability of something bad happening (i.e., E_{in} not tracking E_{out}) for a random sample is small? I would think that any E_{in} satisfies this condition, regardless of how we determined the sample.

I suppose my question is: how does a particular E_{in} value fail to satisfy an inequality that seems to be a blanket statement for all possible E_{in} values?
Reply With Quote
  #2  
Old 04-16-2012, 11:10 AM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: What does it mean to "satisfy" Hoeffding's Inequality?

Quote:
Originally Posted by gordonbr View Post
I'm confused about the process of determining whether a particular random sample "satisfies" Hoeffding's inequality.

In particular, when we run some experiments and determine the average proportion of green marbles, we generate some averages for several E_{in} values. Can't we say that all of these E_{in} values satisfy Hoeffding's Inequality, since Hoeffding's Inequality only says that the probability of something bad happening (i.e., E_{in} not tracking E_{out}) for a random sample is small? I would think that any E_{in} satisfies this condition, regardless of how we determined the sample.

I suppose my question is: how does a particular E_{in} value fail to satisfy an inequality that seems to be a blanket statement for all possible E_{in} values?
If the expression "satisfies Hoeffding's inequality" is used for a particular E_{\rm in}, it is informal or figurative. It just says that this particular E_{\rm in} is within \epsilon of E_{\rm out}. Hoeffding asserts that this is likely to be the case, hence the word "satisfies."

The formal statement would not involve an individual E_{in}, but rather a full experiment, and it would be a statement that Hoeffding's inequalty holds under the conditions of such experiment. For instance, the multiple-bin experiment does not satisfy the basic Hoeffding inequality.
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote
  #3  
Old 04-16-2012, 12:39 PM
gordonbr gordonbr is offline
Junior Member
 
Join Date: Apr 2012
Posts: 3
Default Re: What does it mean to "satisfy" Hoeffding's Inequality?

Thanks, professor! That clears it up.
Reply With Quote
  #4  
Old 01-14-2013, 11:26 AM
ripande ripande is offline
Senior Member
 
Join Date: Jan 2013
Posts: 71
Default Re: What does it mean to "satisfy" Hoeffding's Inequality?

Is Hoeffding's Inequality true for every experiment and hypothesis ? Is it possible that P[Ein -Eout] for some hypothesis is not bounded by 2exp( -2e2N) ?
Reply With Quote
  #5  
Old 01-14-2013, 11:37 AM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: What does it mean to "satisfy" Hoeffding's Inequality?

Quote:
Originally Posted by ripande View Post
Is Hoeffding's Inequality true for every experiment and hypothesis ? Is it possible that P[Ein -Eout] for some hypothesis is not bounded by 2exp( -2e2N) ?
If you fix any hypothesis then run the experiment, the probability will always be bounded by that term.
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote
  #6  
Old 01-15-2013, 12:37 PM
ripande ripande is offline
Senior Member
 
Join Date: Jan 2013
Posts: 71
Default Re: What does it mean to "satisfy" Hoeffding's Inequality?

I am sorry, but I still dont get it. Let us say one person is tossing a fair coin 10 times and got all heads. Here one coin refers to one hypothesis correct ?, so that is fixed. N is also fixed to 10. Does this mean that this experiment would satisfy hoefding's inequality ?

I am confused by the statement that hoeffding's inequlity is universally true for fixed hypothesis and experiment.
Reply With Quote
  #7  
Old 01-15-2013, 01:22 PM
ripande ripande is offline
Senior Member
 
Join Date: Jan 2013
Posts: 71
Default Re: What does it mean to "satisfy" Hoeffding's Inequality?

Thinking on it more...does it mean that if the experiment involves multiple iterations of flipping the same coin 10 times then it will be bounded by hoeffding's inequality?
Reply With Quote
  #8  
Old 01-15-2013, 02:56 PM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: What does it mean to "satisfy" Hoeffding's Inequality?

Quote:
Originally Posted by ripande View Post
Thinking on it more...does it mean that if the experiment involves multiple iterations of flipping the same coin 10 times then it will be bounded by hoeffding's inequality?
If you are applying Hoeffding to the 10 flips, and you are considering multiple attempts at 10 flips, then we are in the "multiple bin" rather than single bin regime. You can apply the regular (single bin) Hoeffding to all the flips considered together (N would be multiple of 10 given your description).
__________________
Where everyone thinks alike, no one thinks very much
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 11:15 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.