Wednesday, April 09, 2008

Solving the Monty Hall problem with simulation in Python

On at least two occasions I've met the Monty Hall problem. The first time it was in the book "The Curious Incident of the Dog in the Night-time" from Mark Haddon. And today I found it in an article called "Monty Hall strikes again - reveals fatal flaw in some of the most famous psychology experiments"

It is so counter intuitive that it is amazing. The problem is this:

Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?

My intuition says there is no need to change doors. The probability to win a car is obvious and it is 1/3. But the mathematical solution says the probability to win a car if you change doors is 2/3. Amazing if it is true! So lets find out who is right? How? Will make a simulation, will run it many many times and will get the average. This is the Python program that solves the problem:

from __future__ import division
from random import shuffle, choice

def get_random_doors():
doors = ["goat","goat","car"]
return doors

def get_host_open(doors, guest_pick1):
host_open = 0
remaining_doors = [ k for k in [0,1,2]
if k != guest_pick1]
if doors[guest_pick1] == "car":
host_open = choice(remaining_doors)
[host_open] = [d for d in remaining_doors
if doors[d] != "car"]
return host_open

def simulation(strategy):
N = 100000
cars_won = 0
for _ in range(N):
doors = get_random_doors()
guest_pick1 = choice([0,1,2])
host_open = get_host_open(doors, guest_pick1)
if strategy == "stay":
guest_pick_final = guest_pick1
elif strategy == "change":
[guest_pick_final] = [ k for k in [0,1,2]
if k != guest_pick1 and k != host_open]
raise ("Unknown strategy")

if doors[guest_pick_final] == "car":
cars_won += 1

print strategy, cars_won/N


This is a Python 2.4 and 2.5 code. The problem is written with the goal to be easy to read and verify and is not optimized for performance. Lets run it. The result is:

stay 0.33478
change 0.66407

So change doors, definitely change doors if you can!