LFD Book Forum  

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

Reply
 
Thread Tools Display Modes
  #1  
Old 07-22-2012, 10:10 PM
fgpancorbo fgpancorbo is offline
Senior Member
 
Join Date: Jul 2012
Posts: 104
Default Q1 and Q2

I am a bit confused about these two questions. Without getting the actual answers, any insight would be appreciated.

First, with regards to Q1; I have run the experiment many times, and I don't get any of the suggested answers. This is my code,

v_1 = 0;
v_rand = 0;
v_min = 0;
vmins = zeros(100000,1);
for i=1:100000
experiment = zeros (10,1000);
vs = zeros (1,1000);
experiment = randi([0 1],10,1000); % Do the experiment
vs = sum(experiment)/10; % compute frequencies
v_1 = v_1 + vs(1);
v_rand = v_rand + vs(randi(1000));
vmins(i) = min(vs); % find v_min
v_min = v_min + vmins(i);
end

v_1 = v_1/100000
v_rand = v_rand/100000
v_min = v_min/100000

With that code I get a v_min which is neither of the suggested. I don't see what I am doing wrong.

Regarding Q2; there is another thread on the matter http://book.caltech.edu/bookforum/showthread.php?t=880 but I am still unclear. I kind of believe what is the right answer, but I am confused about the wording of the question.

Hoeffding’s inequality requires a particular setup to be useful from a quantitative point of view: N (number of experiments, in Q1 that's 10) and epsilon (the tolerance, which we haven't been given). Without a required epsilon, we cannot reach any conclusions from a quantitative point of view. My feeling is that Q2 is a question independent of any N (thus, forget about 10) or epsilon (thus not required). Something along the lines:

"suppose we have 1000 thousand identical coins and we wanted to estimate the bias of any the coins. We choose c_1, c_rand and c_min as explained in Q1. For which coin (or coins) could we use Hoeffding’s inequality to get a fair estimate of the number of samples required to have an estimate of the bias for a given tolerance? For example, plugging in N = 10000, epsilon = 0.01, 2*exp(-2*(0.01)^2*100000) = 4.1223e-009, which is pretty good. Which coin(s) will give us the coin bias with a probability 1 - 4.1223e-009?"

If Q2 is about what goes in between "", then I know the answer. If not, I am confused.
Reply With Quote
  #2  
Old 07-23-2012, 02:12 AM
tzs29970 tzs29970 is offline
Invited Guest
 
Join Date: Apr 2012
Posts: 52
Default Re: Q1 and Q2

Quote:
Originally Posted by fgpancorbo View Post
With that code I get a v_min which is neither of the suggested. I don't see what I am doing wrong.
The reason you can't see what you are doing wrong is simple: you aren't doing anything wrong!

Q1 asks which of the 5 given answers is closest to v_min. When the professor says "closest" in this course, it doesn't mean one answer is going to turn out to be the expected value of the experiment and you should expect to get an answer close to that, just deviating a little due to chance. Nope. The homework choices often are several standard deviations from the expected experimental result.

For instance, if the expected value of some experiment was 40 with a standard deviation of 5, the homework might give you choices of 1, 10, and 100. None of those are numbers you would ever actually see in your experiment. The right answer in that case would be 10, because abs(10-40) = 30, and that is less than abs(100-40).

I ran your code in Octave, and the result it gave was within 0.0004 of what my Python code gave. I've already submitted mine, and I got it right, so you are fine as long as you correctly pick which is closest to your result.

Last edited by tzs29970; 07-23-2012 at 02:14 AM. Reason: I accidentally a word
Reply With Quote
  #3  
Old 07-23-2012, 09:39 AM
fgpancorbo fgpancorbo is offline
Senior Member
 
Join Date: Jul 2012
Posts: 104
Default Re: Q1 and Q2

Quote:
Originally Posted by tzs29970 View Post
I ran your code in Octave, and the result it gave was within 0.0004 of what my Python code gave. I've already submitted mine, and I got it right, so you are fine as long as you correctly pick which is closest to your result.
Thanks . I'll run it tonight and will let you know.

Cheers,

Fernando.
Reply With Quote
  #4  
Old 07-23-2012, 09:10 PM
fgpancorbo fgpancorbo is offline
Senior Member
 
Join Date: Jul 2012
Posts: 104
Default Re: Q1 and Q2

Quote:
Originally Posted by fgpancorbo View Post
Thanks . I'll run it tonight and will let you know.

Cheers,

Fernando.
I've run it and the method works. I got this one right . Now, I want to point out that my understanding of question 2 seems to be correct as well.
Reply With Quote
  #5  
Old 01-16-2013, 11:24 AM
Marc Zucker Marc Zucker is offline
Member
 
Join Date: Jan 2013
Posts: 24
Default Re: Q1 and Q2

I have a quick question regarding the 2nd question on the 2nd homework. When the question asks for which coin or coins satisfy Hoeffding's Inequality, is it asking which coin(s) satisfy the conditions for us to apply Hoeffding's Inequality, or is it asking practically which actually satisfy the Inequlaity. If it is the latter of the two, how are we to choose epsilon for this question?

Thanks.
Reply With Quote
  #6  
Old 01-16-2013, 11:56 AM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: Q1 and Q2

Quote:
Originally Posted by Marc Zucker View Post
I have a quick question regarding the 2nd question on the 2nd homework. When the question asks for which coin or coins satisfy Hoeffding's Inequality, is it asking which coin(s) satisfy the conditions for us to apply Hoeffding's Inequality, or is it asking practically which actually satisfy the Inequlaity. If it is the latter of the two, how are we to choose epsilon for this question?
Hi Marc,

It is the former.
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote
  #7  
Old 01-16-2013, 03:20 PM
nroger nroger is offline
Member
 
Join Date: Jan 2013
Posts: 10
Default Re: Q1 and Q2

But does question 2 ask:
(a) whether the nu's from question 1 can be plugged in to Hoeffding's Inequality (involving an average over 100000 experiments), or
(b) whether the nu's from just 10 flips can be plugged in ?
Thanks....Neil
Reply With Quote
  #8  
Old 01-16-2013, 05:49 PM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: Q1 and Q2

Quote:
Originally Posted by nroger View Post
But does question 2 ask:
(a) whether the nu's from question 1 can be plugged in to Hoeffding's Inequality (involving an average over 100000 experiments), or
(b) whether the nu's from just 10 flips can be plugged in ?
Thanks....Neil
For Problem 2, it's (b).
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote
  #9  
Old 01-17-2013, 06:18 AM
melipone melipone is offline
Senior Member
 
Join Date: Jan 2013
Posts: 72
Default Re: Q1 and Q2

How to choose epsilon?
I understand that any epsilon will do for the Hoeffding inequality but I think I want an epsilon that will give me a probability that P(v - mu) > epsilon is greater than 0, correct?
What is a good range of epsilon to try?
Reply With Quote
  #10  
Old 01-17-2013, 08:55 AM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: Q1 and Q2

Quote:
Originally Posted by melipone View Post
How to choose epsilon?
I understand that any epsilon will do for the Hoeffding inequality but I think I want an epsilon that will give me a probability that P(v - mu) > epsilon is greater than 0, correct?
What is a good range of epsilon to try?
For Problem 2, satisfying Hoeffding's Inequality means that the inequality is valid for all \epsilon's. Whether applying the Inequality with a particular \epsilon leads to a useful bound is a separate question.
__________________
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 07:03 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.