LFD Book Forum

LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Homework 2 (http://book.caltech.edu/bookforum/forumdisplay.php?f=131)
-   -   Q1 and Q2 (http://book.caltech.edu/bookforum/showthread.php?t=900)

fgpancorbo 07-22-2012 10:10 PM

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.

tzs29970 07-23-2012 02:12 AM

Re: Q1 and Q2
 
Quote:

Originally Posted by fgpancorbo (Post 3598)
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.

fgpancorbo 07-23-2012 09:39 AM

Re: Q1 and Q2
 
Quote:

Originally Posted by tzs29970 (Post 3599)
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 :D. I'll run it tonight and will let you know.

Cheers,

Fernando.

fgpancorbo 07-23-2012 09:10 PM

Re: Q1 and Q2
 
Quote:

Originally Posted by fgpancorbo (Post 3608)
Thanks :D. 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 :D. Now, I want to point out that my understanding of question 2 seems to be correct as well.

Marc Zucker 01-16-2013 11:24 AM

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.

yaser 01-16-2013 11:56 AM

Re: Q1 and Q2
 
Quote:

Originally Posted by Marc Zucker (Post 8731)
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.

nroger 01-16-2013 03:20 PM

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

yaser 01-16-2013 05:49 PM

Re: Q1 and Q2
 
Quote:

Originally Posted by nroger (Post 8742)
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).

melipone 01-17-2013 06:18 AM

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?

yaser 01-17-2013 08:55 AM

Re: Q1 and Q2
 
Quote:

Originally Posted by melipone (Post 8766)
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.


All times are GMT -7. The time now is 02:43 AM.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2020, 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.