Tuesday, March 16, 2010

Red card


Another set of videos from the Machine Learning Summer School 2009 features David MacKay on Information Theory (link). He poses a problem in probability which I believe is famous, but I can't find the reference now...

[UPDATE: The Box Paradox (Grinstead & Snell, p. 181)]

In his formulation, you are shown three cards. One is red on both sides, while the second is white on both sides, and a third one is red on one side and white on the other. I pick a card at random (out of sight) and show you the "up" side, which is red. What is the probability that the other side is also red?

In the class, about 50 said 1/2 and about 70 picked 2/3.

One way to solve the problem is to consider the "sample space" carefully.

Another is to write a simulation of the cards in Python. This seems to fit quite naturally with a "Card" class. We simulate a small number of draws (105), and get the answer trivially (result below).

However, MacKay suggests that we solve the problem by the application of Bayes Theorem. That took me a bit to puzzle through, but after a while I came up with the following. First of all, remember Bayes' rule. We compute:

P(H|D) = P(D|H) P(H) divided by Σ P(D|H*) P(H*) for all hypotheses

What is our hypothesis? Let's say it is the event that we drew the card with two red sides, so that the side that is yet unseen is also red. What is the prior for this hypothesis? It seems uncontroversial to use the fraction of the cards which fit this hypothesis:

P(H) = 1/3

The data (or datum) is clear: one card with a red side up. What is the probability of the data we observed, given this hypothesis? Since the card is red on both sides, we have:

P(D|H) = 1

What is the marginal probability of the data, the probability under all hypotheses? This normalizing constant is:

Σ P(D|H*) P(H*) =
1/3 * 0 + 1/3 * 1/2 + 1/3 * 1 = 1/2

[UPDATE: Realized that I used the symbol * in the last line for multiplication, in the usual Python way. But H* in the line above uses * as a wildcard, to mean all H. ]

P(H|D) = P(D|H) P(H) / sum
= 1 * 1/3 divided by 1/2
= 2/3


The simulation prints:

$ python Card.py 
{'r': 33465, 'w': 16681}

Here's the code:

import random
class Card:
def __init__(self,*args):
self.colors = args
def __repr__(self):
return ''.join(self.colors)
def sideup(self):
self.up = random.choice(self.colors)
return self.up
def sidedown(self):
i = self.colors.index(self.up)
if i:  return self.colors[0]
return self.colors[1]

L = [Card('r','r'),Card('r','w'),Card('w','w')]
countDict = { 'r':0, 'w':0 }
for i in range(int(1E5)):
c = random.choice(L)
if c.sideup() == 'r':
reverse = c.sidedown()
countDict[reverse] += 1
print countDict

No comments: