Q1 and Q2

[fgpancorbo]

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]

Originally Posted by fgpancorbo

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]

Originally Posted by tzs29970

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.

[fgpancorbo]

Originally Posted by fgpancorbo

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.

[Marc Zucker]

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]

Originally Posted by Marc Zucker

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]

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]

Originally Posted by nroger

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]

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?

[palmipede]

For Q1, the exact distribution of n_min can be computed and the analytical answer matches my empirical answer but none of the listed answers exactly.