SOLUTION: Consider a biased coin with probability p=1/3 of landing heads. Suppose the coin is flipped 'n' times. Use the Chernoff bound to determine the smallest value for 'n' so that the pr

Algebra ->  Probability-and-statistics -> SOLUTION: Consider a biased coin with probability p=1/3 of landing heads. Suppose the coin is flipped 'n' times. Use the Chernoff bound to determine the smallest value for 'n' so that the pr      Log On


   

Question 1042698: Consider a biased coin with probability p=1/3 of landing heads. Suppose the coin is flipped 'n' times. Use the Chernoff bound to determine the smallest value for 'n' so that the probability that more than half of the coin flips come out heads is less than 0.001.
a) 9
b) 249
c) 99
d) 499

Answer by robertb(5830) About Me  (Show Source):
You can put this solution on YOUR website!
You seem to be using the version P%28X+%3E+%281%2Bepsilon%29%2Amu%29+%3C=+exp%28-epsilon%5E2%2F3%2Amu%29 of the Chernoff bound, where X+=+sum%28X%5Bi%5D%2C+i+=+1%2Cn%29, and each X%5Bi%5D is Bernoulli.

You want P%28X+%3E+n%2F2%29+%3C=+0.001.
Let %281%2Bepsilon%29mu+=+n%2F2. Since mu+=+n%2F3, we get
%281%2Bepsilon%29%28n%2F3%29+=+n%2F2.
===> epsilon+=+1%2F2.
Next, let
===> -n%2F36+=+ln0.001 ===> n+=-36%2Aln0.001++=+248.68, or highlight%28n+=+249%29, rounded to the nearest whole number.