Interview Question: Fair and Unfair Coins and Bayes' Theorem

Short post for today, based on the first probability question I was asked during an onsite interview. The question went as follows:

You are given a bag of 100 coins, with 99 fair ones flipping heads and tails with 0.50.5 probability each, and one unfair coin which flips heads with 1.01.0 probability. You pick a coin randomly and flip it 10 times, getting heads every single time. What is the probability that you picked the unfair coin?

The question can be answered quite easily using Bayes' Theorem from probability theory. The extended formula from the theorem is:

P(AB)=P(BA)P(A)P(BA)P(A)+P(B¬A)P(¬A) P(A|B) = \frac{P(B|A)\,P(A)}{ P(B|A) P(A) + P(B|\neg A) P(\neg A)}\cdot

Here we let AA be the even of having picked the unfair coin, and BB be the event of having flipped 10 heads in a row. So we have P(A)=0.01P(A) = 0.01 , P(BA)=1.0P(B|A) = 1.0 , P(B¬A)=(12)10P(B|\neg A) = (\frac{1}{2})^{10} , and P(¬A)=0.99P(\neg A) = 0.99 . Putting it all together we get

P(AB)=1.0×0.011.0×0.01+(12)10×0.99 P(A|B) = \frac{1.0 \times 0.01}{ 1.0 \times 0.01 + (\frac{1}{2})^{10} \times 0.99}

which is approximately 0.91180.9118 . So there is a 91.18% chance we picked the unfair coin.

Let's test this out empirically in Python, using the Bernoulli process generator from the the post on iterators and generators. I ran the experiment 100,000 times and printed the ratio. First the code for this experiment. (Note that I cheat and use the gi_frame attribute, which in general, is not a good idea since it's CPython specific. I do it here because this is not production code and just an experiment.)

def pick_random_coin(fair_coin_probablity):
    if random.random() < fair_coin_probablity:
        return bernoulli_process(0.5)
        return bernoulli_process(1.0)

a = 0  # number of times we get 10 heads in a row AND coin was unfair
b = 0  # total number of times we get 10 heads in a row
for __ in xrange(100000):
    coin = pick_random_coin(0.99)
    if True not in [ for __ in xrange(10)]:
        b += 1
        # check to see if the coin is unfair, or we
        # just got really lucky
        if coin.gi_frame.f_locals['p'] > 0.6:
            a += 1

print float(a) / b

The output from my first run was 0.91630.9163 , and the second run 0.90700.9070 which is convincing. Of course, the true test would be to start from the basics and prove we did everything right. The empirical test was more a curiosity.