Thread: Q1 and Q2
View Single Post
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);

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 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