False coins

[BMAD]

We have two coins: coin A gives heads with probability 1/3; coin B gives heads with probability 9/10.
 

Pick one of the two, call it C, is selected randomly (using equal probability).

 

Devise a scheme that involves flipping C at most n times, looking at the results, and declaring whether C = A or C = B. We want the declaration to be correct at least 999,999 times out of a million. And we want n to be as small as possible.

[k-man]

You need to calculate the probability that you have a coin A (or B) after each flip and make a declaration as soon as either probability exceeds 99.9999%. To calculate the probability you can use Bayes' theorem.

 

Let's say after n flips we observed h heads. Notating this event as (h,n), the probability that we have a coin A is

 

P(A|h,n) = P(h,n|A) * P(A) / (P(h,n|A) * P(A) + P(h,n|B) * P(B)

 

where

P(A)=P(B)=0.5 because both coins have equal probability to be chosen initially

P(h,n|A) = choose(n,h) * 9^h/10ⁿ

P(h,n|B) = choose(n,h) * 2^n-h/3ⁿ

 

Once the P(A|h,n) exceeds .999999 or drops below .000001 we can make the declaration.

 

I plugged the formulas into Excel and observed that

 

1) It takes at least 8 flips and all of them must be tails to get the necessary confidence that we have coin B.

 

2) It takes at least 14 flips and all of them must be heads to get the necessary confidence that we have coin A.

 

3) It will take some greater number of flips in any mixed outcome and there is no fixed number n that will theoretically always be sufficient. For example, if you're continuosly flipping 2 heads followed by one tail, you will not get the necessary level of confidence even after 300 flips. However, this type of outcome is extremely unlikely given the coins A and B, so

 

4) Practically speaking, we don't need to flip more than 84 times. If after 84 flips the number of heads is 56 or more declare A, if 55 or less declare B. The reason is the following

 

4a) for 60 or more heads from 84 flips P(A|h,n) > 0.999999, so we would declare A with the needed confidence anyway.

4b) for 50 or less heads P(A|h,n) < 0.000001, so we would declare B anyway

4c) between 51 and 59, we can declare A or B based on the value of P(A|h,n) - A is more likely for 56-59, while B is more likely for 51-55. Even though the confidence level is below the threshold, the combined probability of getting between 51 and 59 heads after 84 flips is less than 0.000001