Reading Jeff Atwood’s post The Problem of the Unfinished Game, reminded me of a similar problem. The Monty Hall Problem is a well known probability puzzle that has tricked many people. In fact, if you are not familiar with it already, chances are that you’ll get it wrong. And you would be in good company along with many mathematicians and physicists, including the great mathematician, Paul Erdos. This puzzle is loosely based on the television show Let’s Make a Deal, and is equivalent to some much older puzzles you may be familiar with (e.g. the three prisoners problem). In its simplest form, it asks the following question:
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?
This definition of the problem is admittedly ambiguous. Thankfully Wikipedia points us towards a more exact definition:
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 [that is, booby prizes]. The car and the goats were placed randomly behind the doors before the show. The rules of the game show are as follows: After you have chosen a door, the door remains closed for the time being. The game show host, Monty Hall, who knows what is behind the doors, now has to open one of the two remaining doors, and the door he opens must have a goat behind it. If both remaining doors have goats behind them, he chooses one randomly. After Monty Hall opens a door with a goat, he will ask you to decide whether you want to stay with your first choice or to switch to the last remaining door. Imagine that you chose Door 1 and the host opens Door 3, which has a goat. He then asks you “Do you want to switch to Door Number 2?” Is it to your advantage to change your choice?
Think about it for a moment, then read on. To answer this question, most people will try to determine which of the two possible outcomes has a higher probability. Problems arise when trying to correctly calculate the probability of these two events though. There are two closed doors and the car could be behind either of them. Hence, most people’s “common sense” and psychology leads them to believe that there is a 50% chance that the car is behind the initially selected door, and 50% that it’s behind the other closed door that was offered up by Monty. Initially it would seem that switching or staying with the first choice doesn’t really make a difference.
Unfortunately that’s not the right answer. The correct answer is that there is a two out of three chance of winning by switching to the other door; so switching is always to your advantage. This result is considered to be a paradox because it’s very counterintuitive to the way that many people think. It is in fact so counterintuitive that most people will argue with you in an attempt to convince you otherwise. I invite you to check out the Wikipedia entry on the problem/paradox, to read a step-by-step explanation with figures about why switching gives you about 66.7% chance of winning the car and why staying with the initial choice gives you only a 33.3% success rate.
When you make your first choice your probability of winning the car is only 1/3. If you decide to switch, you will win only if the first choice you made was wrong. And since your first choice came with a 2 out of 3 chance of picking a goat, switching will then (logically) give you 2/3 chance of winning. Another easy way to come to intuitively accept this surprising result, is to wildly exaggerate the terms of the problem. If there were a billion doors, you picked one, and then Monty proceeded to open up all the remaining doors but one, we’d have a situation where it would be extremely unlikely that you picked the right door at the beginning, while it would be extremely likely that the remaining door was the one that was concealing the car.
Even after reading several explanations and aids to understand these results, there are still people who are skeptical or refuse to believe them. Let’s verify the outcome with a simulation.
What you find below is a quick Ruby script that I wrote to run a Monte Carlo Simulation of the Monty Hall problem/paradox. It runs the game a million times and then measures how many times the player won by sticking with their first choice, and how many times switching would have led to winning the car.
#!/usr/bin/env ruby -w
# Monte Carlo simulation for the Monty Hall Problem:
# https://en.wikipedia.org/wiki/Monty_Hall_problem
=begin
When using a Ruby version older than 1.8.7
define the following two methods:
class Array
def shuffle
self.sort_by { rand }
end
def choice
self.shuffle.first
end
end
=end
# Utility class for the simulation of a single Monty Hall game.
class MontyHall
def initialize
@doors = ['car', 'goat', 'goat'].shuffle
end
# Return a number representing the player's first choice.
def pick_door
return rand(3)
end
# Return the index of the door opened by the host.
# This cannot represent a door hiding a car or the player's chosen door.
def reveal_door(pick)
available_doors = [0, 1, 2]
available_doors.delete(pick)
available_doors.delete(@doors.index('car'))
return available_doors.choice
end
# Return true if the player won by staying
# with their first choice, false otherwise.
def staying_wins?(pick)
won?(pick)
end
# Return true if the player won by switching, false otherwise.
def switching_wins?(pick, open_door)
switched_pick = ([0, 1, 2] - [open_door, pick]).first
won?(switched_pick)
end
private
# Return true if the player's final pick hides a car, false otherwise.
def won?(pick)
@doors[pick] == 'car'
end
end
if __FILE__ == $0
ITERATIONS = (ARGV.shift || 1_000_000).to_i
staying = 0
switching = 0
ITERATIONS.times do
mh = MontyHall.new
picked = mh.pick_door
revealed = mh.reveal_door(picked)
staying += 1 if mh.staying_wins?(picked)
switching += 1 if mh.switching_wins?(picked, revealed)
end
staying_rate = (staying.to_f / ITERATIONS) * 100
switching_rate = (switching.to_f / ITERATIONS) * 100
puts "Staying: #{staying_rate}%."
puts "Switching: #{switching_rate}%."
end
And here is an “equivalent” version I wrote in Python:
#!/usr/bin/env python
"""
Monte Carlo simulation for the Monty Hall Problem:
https://en.wikipedia.org/wiki/Monty_Hall_problem.
"""
import sys
from random import randrange, shuffle, choice
DOORS = ['car', 'goat', 'goat']
def pick_door():
"""Return a number representing the player's first choice."""
return randrange(3)
def reveal_door(pick):
"""Return the index of the door opened by the host.
This cannot be a door hiding a car or the player's chosen door.
"""
all_doors = set([0, 1, 2])
unavailable_doors = set([DOORS.index('car'), pick])
available_doors = list(all_doors - unavailable_doors)
return choice(available_doors)
def staying_wins(pick):
"""Return True if the player won by staying
with their first choice, False otherwise.
"""
return won(pick)
def switching_wins(pick, open_door):
"""Return True if the player won by switching,
False otherwise.
"""
other_doors = set([pick, open_door])
switched_pick = (set([0, 1, 2]) - other_doors).pop()
return won(switched_pick)
def won(pick):
"""Return True if the player's final pick hides a car,
False otherwise.
"""
return (DOORS[pick] == 'car')
def main(iterations=1000000):
"""Run the main simulation as many
times as specified by the function argument.
"""
shuffle(DOORS)
switching = 0
staying = 0
for dummy in xrange(iterations):
picked = pick_door()
revealed = reveal_door(picked)
if staying_wins(picked):
staying += 1
if switching_wins(picked, revealed):
switching += 1
staying_rate = (float(staying) / iterations) * 100
switching_rate = (float(switching) / iterations) * 100
print "Staying: %f%%" % staying_rate
print "Switching: %f%%" % switching_rate
if __name__ == "__main__":
if len(sys.argv) == 2:
main(int(sys.argv[1]))
else:
main()
Even if you are not familiar with Ruby or Python, you may be able to understand what’s going on here. The main body of the program emulates the game and keeps track of the number of victories when the player sticks with their initial choice, and when they switch. Notice that this code intentionally tries not to be clever, in order not to annoy “skeptical” people.
There are many points in the code where correct assumptions about the problem would lead us to code that is faster and much more compact. For example, if the player wins a given game by sticking with his first answer, it’s obvious that switching would have made him lose. We could just calculate the difference between 100 and the success rate of staying with the first choice, and we’d obtain the success rate for switching. But here we are trying to simulate the problem as faithfully as possible and abstract as little as necessary.
As always with Monte Carlo Simulations, the outcome is slightly variable during each run since it depends on random input; but by the law of large numbers, it will very slowly converge to the expected values (despite the pseudo-randomness used here). For example, when I executed the code above for the first time on my machine, I obtained the following:
Staying: 33.382%. Switching: 66.618%.
The results of this simulation should be enough to convince you that the theoretical results are actually true; we are easily fooled, and the mathematicians who got it right were not making stuff up. 😉
Happy New Year to my readers, I wish you all the best for a happy, successful 2009!
Get more stuff like this
Subscribe to my mailing list to receive similar updates about programming.
Thank you for subscribing. Please check your email to confirm your subscription.
Something went wrong.
Just an observation, but wouldn’t it be more correct to shuffle the doors as well? Although i guess it doesnt actually affect the probability in the situation since trials are independent?
Next time someone doubts this, you can tell them that the same principle is what keeps their inbox with a spam/ham rate less than 1.000.000
http://www.paulgraham.com/spam.html
@Niels: It wouldn’t change the outcome, but the doors are shuffled in both scripts.
@Lucas: Indeed. 🙂
For the curious,
$ time ruby monty.rb
Staying: 33.2946%.
Switching: 66.7054%.
real 0m13.506s
user 0m12.129s
sys 0m1.296s
$ time python monty.py
Staying: 33.225700%
Switching: 66.774300%
real 0m11.449s
user 0m11.305s
sys 0m0.008s
$ time python monty-psyco.py
Staying: 33.389400%
Switching: 66.610600%
real 0m4.798s
user 0m4.776s
sys 0m0.012s
…on my laptop.
Wow, that was surprising!
Here, a Groovy version of the program:
http://snipplr.com/view/10837/monte-carlo-simulation-for-the-monty-hall-problem/
Peter, I know you did it for fun, but these implementations are really two different beasts. The Python one uses functions that allows it to be more pythonic, while the Ruby one uses an utility class. Also, these implementation are meant to be “proof” for the skeptic reader who may not be a programmer, and as such are not written for speed or conciseness. I could probably write a version that would be 1/5 the length and 10 times as fast, but it would use less intuitive abstractions to model the problem at hand, and it would be less of a step-by-step simulation of the game. I feel that for these two scripts, comparative benchmarks should be left out of the picture. 🙂
Reading this problem recently, I found it extremely counterintuitive too and was planning to write something like this.
I thought the python code could be improved at places. ‘reveal_door’ is unnecessarily complicated with sets.
I rewrote reveal_door as follows –
def reveal_door(pick): """Return index of door opened by host """ return choice([door for door in range(3) if door!=pick and door!=DOORS.index('car')])———————-
Timings on my thinkpad –
raja@ /data/tmp:
time python monte_carlo.py
Staying: 33.264000%
Switching: 66.736000%
real 0m13.573s
user 0m13.457s
sys 0m0.012s
## Code modified ##
raja@ /data/tmp:
time python monte_carlo.py
Staying: 33.281600%
Switching: 66.718400%
real 0m12.657s
user 0m12.621s
sys 0m0.024s
Antonio,
Of course this is “mathematically correct” (Or statistically correct if you want to be specific :-)). But I think it’s one of the cases where common sense has it advantage. Although numerically the chances are between three doors, when the show’s host opens up his door, that leaves us without a door to choose from (Who would pick a door which we already know has a goat behind it).
However, these things are true and I’m quoting here something similar: Suppose that you’re going off for the weekend and I ask you “Are you sure that you turn the lights off before going out?” and you reply “Yes, I’m 99% sure”. Then I propose you this:
We have a jar with 99 white balls and 1 black ball. I’ll give you $1000 if either you can assure that you really did turn off the lights or if you’re able to pick a white ball from the jar (The probability of doing so is, in fact, 99%, the same amount you’ve said about turning the lights off). We keep doing this rising the amount of black balls in the jar (Replacing the white balls of course). Just when you’d prefer go home to check on the lights rather than picking up a white ball from the jar, is at that point you really can say “I’m XX% sure that I turned the lights off” (XX being the probability to pick up a white ball from the jar)
Antonio:
Statistics can only be used for multiple events, which is why it is invalid to apply them to a single game of Let’s Make a Deal. Without a doubt, your Monte Carlo simulation is valid for predicting the frequency of outcomes from a large sample of identical scenarios. However, for a single game show participant, faced with 2 doors only, and only one choice, why would it matter what would happen over the course of a million games? I think it makes no difference which door he chooses. In the exagerated case of the billion doors, Monty does him a favor and eliminates all but one of the goats, and at that point there are still just 2 doors. Why does it matter that there used to be a bunch of other doors with goats? How does the prior existence of other doors with goats affect the situation at the moment when the participant must make his choice? At that moment, there are 2 doors, 1 car, and 1 goat. Statistics don’t apply.
A related example is this: Let’s say that in the general population, there is a 1% incidence of a gene for a rare fatal disease. Does that mean that I personally have a 1% chance of dying of that disease? No, because I personally either have the gene or I don’t. If I haven’t been tested, I may not know whether I have it or not, but my ignorance doesn’t change the fact that I either have it or I don’t. Statistics don’t apply to single incidences of anything.
On perhaps a related note: Richard Feynman said in one of his public lectures: “While driving to the lecture, I saw a car with the license plate XRB-367. Out of all the license plates in this state, what are the odds that I would see this particular plate! This is a truly amazing circumstance! I can hardly believe it!” (Quote not exact) Of course, he was joking to make a point that unusual events happen constantly, and that you have to be careful when applying statistics to isolated events. At least, I’m pretty sure those were his points.
@Kent:
I sort of understand your line of thought, but you are confused about probability theory.
For a participant in real life, statistics does apply and he really stands a better chance if he opts for the other door.
For your genetics example, if there is a 1% prevalence of the gene in the population, you do have a 1% chance of having it. After you test for it, you know if you have it or not, but that doesnt mean statistics doesn’t mean anything here.
Same goes for the car plate. Before Feynman started for his lecture, the probability that he would see that number on a license plate is indeed small.
What are the times with Groovy?, looks interesting and very clean code. I like Python one, looks very clean too.
Raja:
Thanks for your thoughtful reply. I may be confused as you say. But it does seem strange to apply statistics to single events, doesn’t it? Maybe that’s where the counterintuitiveness arises from.
I think what is driving my thinking on this is the common example from statistics classes of the coin flipped 9 times in a row, all heads. The question then is asked, what is the probability that the 10th flip will be heads as well? The answer (50%) is counterintuitive to many people, who think: What are the odds of getting heads 10 times in a row? Of course the coin doesn’t “know” that it was previously flipped 9 times in a row with a heads result.
I was trying to apply similar reasoning to the Monty Hall question, i.e. the two remaining doors don’t “know” that there used to be other doors in the equation. But this reasoning is faulty, you are saying.
Thanks again for a good discussion.
thx for the nice post!
Here’s a variation that I really like. One day on the show, Monty forgets to find out where the car in advance. In the spirit of “the show must go on”, he opens one of the doors and luckily, reveals a goat. Nobody else knows that he had any doubts. What are the odds now for staying vs switching?
Think about the Monty Hall question with a hundred doors. You pick one at random. Monty opens all the others but one. Only your door and one other remain closed. Do you switch?
What if we start with a million doors?
Jonathan, did you read the part of my post were I talked about a billion doors? 🙂
@Kent: Unlike the coin flipping example, Monty isn’t opening doors at random — he is opening doors that he knows do not have the car behind them. So your initial choice was at random but Monty’s choices definitely are not.
@Tim Kington: Interesting case, but I don’t think it changes anything. Monty had a 50-50 chance of opening the wrong door and showing a car. Since he got lucky and showed a goat, I now still have a 2/3 chance of getting the car by switching. Think about the 1 billion doors again. Monty forgets which door has the car. He then opens all but one and he gets lucky (very lucky!) and opens doors with only goats. Are you going to switch? I certainly would.
@Chad: It’s very counter intuitive, but it does change the probability. Switching doesn’t matter if Monty doesn’t know where the car is. In your case with a billion, it seems like you have a better chance by switching, but you actually don’t – Monty will accidentally show you the car almost every time, and the chance of him luckily not exposing it is the same as you choosing it in the first place. You can prove it by running a simulation. When Monty opens a door, you have him choose it at random, and you throw out the cases where he accidentally exposes the car.
As a result of reading your column, I wrote up a quick Monte Carlo Solution to the Birthday Problem:
Given N number of people with randomized birthdays (excluding Feb 29th birthdays), what is the minimum value of N where you can expect (ie: 50% probability) at least two people having the same birthday?
http://gist.github.com/44189
Surprisingly enough, the answer is 23.
I find it easier to think of this as if you are actually switching from your single chosen door to both of the two other doors.
Since the rules are known before the game you know you’ll pick one door and then you’ll be able to switch to the other two. Since you know you’ll switch you can think of it as if you already “own” the two other doors. When Monty opens one of them, he is just helping you to open a losing door first.
It’s actually just like if you were given the choice of selecting one of the three doors or two of the three doors.
What’s really amazing is the number of posts here without a single disrespectful comment. In this day of internet anonymity, what are the odds of that?
I almost said something awful just because of your comment, Kent.
Not really, just kidding.
On my desktop :
What if I switch the previously selected door with itself? It’s the same as switching with the other one, right?
I’m no math-geek at all, I just want to see the light because I’m really puzzled! 🙂
Monty Hall problem
Lets suppose the contestant comes on stage and selects door # 1 in the hope that a prize is in door 1 and not a goat. Before Monty Hall does or says anything, an associate comes out and whispers something to Monty Hall. Now Monty Hall turns to the contestant and says: I just have been informed that you are a veteran. Therefore I want to better your odds and have you decide only between 2 doors. He than tells a Stage hand to remove Door 3 from the stage. ( Of course Monty knew that there was a goat behind door 3). Now he turns to the contestant and says: “There you are, 2 doors. New game. You want to switch from door # 1 to door # 2, or stay with your original choice?” Same setup as in the original problem, nothing changed except there only 2 doors now, and the contestant has now a chance of staying with his original choice or selecting the other door.
That’s now 50-50 probability, even though it’s the same problem. Which means the original problem must also be a 50-50 proposition.
Gustav, it’s not a true 50/50. Since he picked his door when there were more goats than cars, the veteran’s door is more likely to have a goat in it, His door, therefore, is tainted by previous bad odds.
The only time it’d be 50/50 is if Monty removed the goat first, then let the vet select a door. One may think this is the same thing, but remember: the door eliminated in your scenario is guaranteed NOT to be the contestant’s door. This means the contestant keeps the odds he was originally dealt (1:3), unless he switches.
How do you modify the script to simulate a case where there are say 2 cars and 5 goats?