The Monty Hall Problem

The Monty Hall Problem is an interesting problem in probability theory.  The problem comes from the old TV show Let's Make a Deal hosted by Monty Hall.  You can read more about the background here on Wikipedia.  The basic premise is that there are 3 doors, behind one is a prize (like a new car), and behind the other two is nothing.  As the contestant you get to pick a door and you win whatever is behind it.  The wrinkle is this, first you pick one of the three doors, then Monty picks and opens one of the 2 remaining doors revealing a losing door.  Now he asks you if you want to stay with your first pick, or switch to the other closed door.  What should you do?

Monty Hall
(I dig the doo!)

My first thought was, well when you picked the door at the beginning, it had a 1 in 3 chance of being right. Now Monty has shown you one door that was a loser, so you have 1 in 2 chance of being right.  From this you can reason that switching to the remaining door also results in a 1 in 2 chance of being right, so it's arbitrary, you have a 50% chance of winning either way.  Boy this logic seems intuitive, but it turns out it is wrong!!

In fact, you should always switch from the door you first chose to the door that remains after Monty shows you a loser door.  Switching doubles your chance of winning! (you have a 1/3 chance of winning if you stay with your original door, and a 2/3 chance if you switch)  The trick is basically doing some careful bookkeeping and tracking conditional probabilities.  When Monty opens a door showing you a loser he is giving you valuable information.  You can read all about conditional probabilities at the Wikipedia link given above.

For me, doing is believing, so I have to play the Monty Hall game for this to really sink in.  One way would be to get a willing friend to help me play many rounds of the game some where I switch, and others where I don't and track how often I win using either strategy.  Sounds tedious.  Another route is to have a computer play the game for me.  Below is how I played 10,000 rounds of the Monty Hall game in Python.

from random import *
from collections import defaultdict

def count_all(xlist, proportions=False):
    '''Count all the items in a list, return a dict
       with the item as key and counts as value'''
    out =  defaultdict(int)
    for i in xlist: out[i]+=1
    if proportions:
        out2 = {}
        tot_sz = float(sum(out.values()))
        for i in out: out2[i] = out[i] / tot_sz
        return out2
    else: return out

switch = []
no_switch = []

m = [0,0,1]  #a representation of Monty's doors, two losers (i.e. zeros) and one winner (i.e. one)

for i in xrange(10000): #ten thousand games
    shuffle(m) #randomly shuffle which door is the winner
    p = choice([0,1,2]) #contestant randomly picks a door
    x = [idx for idx,i in enumerate(m) if not i]  #find the two loser doors
    if p in x: show = set(x) - set([p]) #if our pick (p) is a loser pick the other door
    if p not in x: show = set([choice(x)]) #if our pick is the winner, randomly choose one of the two losers to show
    show = show.pop() #the door we will show
    all_s = set(range(3)) #setting up a set of all doors
    f = set([p, show]) # setting up a set with the orig pick and the loser we will show
    new_p = all_s.difference(f) #new_p is the set diff, meaning it's the door we'd switch to after Monty shows the loser
    new_p = new_p.pop()
    if m[p]: no_switch.append(1) #if the no switch strategy succeeded add 1 to list
    else: no_switch.append(0) # if no switch was a loser add 0 to list
    if m[new_p]: switch.append(1) #ditto above, but for switch strategy
    else: switch.append(0)

print 'switch strategy', count_all(switch).items()  #print the counts of the results
print 'no switch strategy', count_all(no_switch).items()

I run this code with Python and here is what I get:

switch strategy [(0, 3362), (1, 6638)]

no switch strategy [(0, 6638), (1, 3362)]

(here zero represents a loss and one is a win, both followed by the count among 10,000 games)

So out of 10,000 randomly generated Monty Hall trials switching won 6,638 (pretty close to the expected 2/3), and not switching only won 3,362 (about the expected 1/3).  It works!  My initial intuition that they should be about 50/50 is proved wrong.

As I mentioned above, you can get to this result without the simulations by using probability theory, but for me the result really becomes concrete and intuitive only after I code it up and see it for myself.

[Another thing worth pointing out is how simple it is to express this game in Python using sets, though I might have gotten a little carried away with them!]