The Monty Hall problem is a relatively well-known puzzle based loosely on the game show “Let’s Make a Deal.” It’s known for its ability to confuse, and the winning strategy to the puzzle may not seem intuitive at first. Here, I want to describe and prove the winning strategy (with Bayes’ Theorem) and model the puzzle with Python to show that the described strategy actually wins the puzzle with the described probability.
You are on a game show and there are three doors in front of you, as in the illustration below. Behind one of the doors sits a prize, but the door has been chosen at random. You’re asked to select a door, and if you select correctly you will win the prize. So, it should seem obvious at this point that, all things being equal and random, there is a 1/3 probability of you selecting the correct door.
But, there’s a catch: When you announce which door you have chosen, the game show host opens one of the other doors. That is, he opens a door that is neither the door you selected nor the door containing the prize. He then asks if you’d like to change your choice of door. There are only two doors remaining – the one you selected and another closed door. Should you stick with your original choice of door, or should you switch your choice to the only other closed door? Does it matter?
A Winning Strategy
Yes, it matters. Always change your choice of door. Always. Simply put, if you stick with your original door selection, you will only win one out of every three times you play the game. If you change your selection, you will win two out of every three times you play.
Proving The Strategy
Intuitively, it is pretty straightforward that your original choice (when there are three doors to choose from) has a 1/3 probability of winning the game. Where things become complicated is when a door is removed. Many would argue that you now have a 1/2 probability of winning by selecting either door, but this isn’t the case.
One critical aspect that you must realize is the following: The game show host can select a door to remove because he knows (a) which door you selected and (b) which door has the prize. The act of removing a door from the game is not random. In fact, in many cases, the host must remove a specific door. For instance, if you select door 1 and the prize is behind door 3, the host has no other option than to remove door 2. You must realize that the choice of which door to remove is conditional on both the prize door and the door you initially select. The only “new” information that a removed door gives you is that it tells you where the prize isn’t. How can you use that information?
Think of the situation this way: When you made your original door selection, there was an equal and random 1/3 probability that the prize was behind any particular door. That situation looks like the following picture, where we’ve selected door 1 as an example.
Put another way, there is a 1/3 probability that door 1 contains the prize and a 2/3 probability that the prize is behind one of the two other doors. That looks like this picture.
So, what happens when we open door 2 or 3? Actually, nothing. The probability doesn’t magically change – it doesn’t change at all. There’s still a 1/3 probability that the prize is behind door 1 and a 2/3 probability that the prize is not behind door 1. The only new information we have is about where the prize is not – as removing a door is completely dependent on the host knowing where the prize isn’t. So, now we have a situation that looks like this.
Of course, the fact that door 2 was opened in this example shows us that there is a 0% probability that the prize is behind door 2. The implication, as strange as it feels, is that there is a 2/3 probability that the prize is behind door 3… because the combined probability of the prize being behind doors 2 and 3 is 2/3 and we know that the prize isn’t behind door 2. Clearly, you should change your selected door to door 3 in this situation.
Rigorous Proof Using Bayes’ Theorem
Bayes’ Theorem allows us to compute conditional probabilities. That is, Bayes’ Theorem will allow us to compute a probability of the form $P(A|B)$, read as “the probability of event A given that event B holds.” We will use Bayes’ Theorem here to compute the probability of winning the game based on switching or not switching our choice in door once a door is removed.
Without loss of generality, we will select door 1 for our initial door choice. Also without loss of generality, we will say that door 2 is opened (as in the above illustrations), leaving us with doors 1 and 3 as possible prize doors. We define the following events: $D_1$, $D_2$, and $D_3$ are the events that the prize is behind doors 1, 2, and 3, respectively. $O_2$ is the event of the host opening door 2, which is dependent on two things: (a) our initial choice of door 1 and (b) the host’s knowledge that the prize isn’t behind door 2.
We wish to compute two things. The first is formally written as $P(D_1|O_2)$. That is, we wish to compute the probability of the prize being behind door 1 given that the host has removed door 2. This represents the probability of winning the game when we do not change door selection. By Bayes’ Theorem, we have
Two of the three components on the right hand side are relatively straightforward. Namely, $P(D_1)$ is the probability that the prize is behind door 1, which is 1/3. The conditional probability $P(O_2|D_1)$ is literally read as “the probability that door 2 is removed when the prize is located behind door 1.” In such a situation, the host may remove either door 2 or 3, and so this is equal to 1/2. The denominator is more challenging here. $P(O_2)$ is the probability that door 2 is removed from selection without the condition that the prize is in any particular location, and we must calculate that directly.
If we consider all of the possible locations where the prize may be (behind each of the three doors) along with their corresponding probabilities, we see that
We know that $P(D_1)=P(D_2)=P(D_3)=1/3$, and so we consider the other values in question. The first of these values, $P(O_2|D_1)$ is the probability that door 2 is removed given that the prize is behind door 1. We already know that this is 1/2. The second value, $P(O_2|D_2)$ is zero since we’d never have door 2 opened if the prize is behind door 2. The third value, $P(O_2|D_3)$ is 1/1 (or 100%) because the prize being behind door 3 and our selection of door 1 only leaves door 2 to be opened. Thus, we have computed:
If I just did your probability or stats homework, you’re welcome. (Please understand the result if this is the case.) What we have just shown is that keeping our selection of door at door 1 results in a 1/3 chance of us winning the prize. What about the probability of winning when we switch choices to door 3? We have
The denominator here is exactly the same (thank goodness for that). The first value in the numerator, $P(O_2|D_3)$ is 1 (or 100%) since it is the probability of opening door 2 given that the prize is behind door 3, in which case door 2 is the only possible door to open (remember that we have initially selected door 1). The second value, $P(D_3)$ is 1/3 since is represents the unconditional probability of the prize being behind door 3. Thus, the probability of winning if we change our choice to door 3 is
and the result has been proved. QED.
A Python Model
We’ll create a Python class that will model the Monty Hall problem. Each time the class is initialized, it will select a door at random (from the 3 available) representing the contestant’s selection. It will then have the host remove a door and present the contestant with the option to change doors. We’ll run the game one million times with both situations: one million times where the contestant switches doors and one million times where the contestant sticks with the original door choice. We’ll present winning percentages in both cases. The code is a bit verbose. (I’ve used this recently as an introductory example to object oriented programming in Python.) This is saved in a file named MontyHall.py.
#!/usr/bin/python2 # MontyHall.py - Jason B. Hill 2014 # This script models the Monty Hall problem: You are on a gameshow and are # presented with three doors. Behind one door (chosen at random) sits a prize. # You must select (guess) a door. If you guess correctly, you get the prize. # But, when you select your door, the show's host throws in a bit of a twist, # opening one of the other two doors ... specifically a door that doesn't # contain the prize. He asks you if you'd like to change your door selection, # to the only other remaining door (not the one you picked originally and not # the now open door). Do you change your selection? Why? # Answer: Yes. ALWAYS change your selection. By sticking with your original # door selection, you have a 1/3 chance of getting the prize. By switching, you # end up with a 2/3 chance of getting the prize. # I explain why on my code blog at: code.jasonbhill.com # I'm going to write this as a tutorial example for object oriented programming # in Python. The idea is that we'll have a class object representing the game. # We'll have variables inside that class that hold information about the game # state, and methods (functions) that advance the game state. import random # We need the random module to select integers in [1,3] randomly def pick_door(): """ Function to pick a door. Returns an integer 1, 2, or 3 at random. """ return random.randint(1,3) class MontyHall: """ Class to model the Monty Hall problem. """ def __init__(self): """ Creates an instance of the Monty Hall problem. This will be called automatically when the class is formed. """ # Pick a prize door randomly and store as a variable. self.prize_door = pick_door() # We'll create variables for the selected door and removed door as # well, but we won't set them just yet. self.selected_door = None self.removed_door = None def select_door(self): """ Randomly selects a door for the contestant. """ self.selected_door = pick_door() def remove_door(self): """ This is how the host removes a (non-prize/non-selected) door.. """ # Pick a door at random. d = pick_door() # If that door is the prize door or the contestant's door, re-pick. while d == self.selected_door or d == self.prize_door: d = pick_door() # set the removed door to d self.removed_door = d def switch_choice(self): """ Switches the selected door once a non-prize door is removed. """ # 1+2+3=6. There's only one choice of door if we switch our selection. self.selected_door = 6 - self.selected_door - self.removed_door def user_wins(self): """ Determine if the user wins. Return true on win, false on lose. """ if self.selected_door == self.prize_door: return True else: return False def run_game(self, switch=True): """ Once a problem is initialized, run the game. 'switch' determines if the user changes selection during the game. """ # The user selects a door. self.select_door() # The host removes a door. self.remove_door() # The user can switch selection of doors. if switch: self.switch_choice() # Determine if the user wins. return self.user_wins() # Now, we'll run the game. When asked if we want to switch door selection when # the door is removed by the host, we'll say 'yes' and switch our choice of # door. We'll run that experiment one million times, always switching choice # when given the chance. Here's what that looks like: wins, losses = 0, 0 for i in range(1000000): # make an instance of the game, call it 'm' m = MontyHall() # run the game and switch choice of door. if m.run_game(switch=True): # a return value of True means we've won wins += 1 else: # a return value of False means we've lost losses += 1 # Now that the game has been run one million times, compute/display stats. perc_win = 100.0*wins / (wins+losses) print "\nOne million Monty Hall games (with switching):" print " won:", wins, "games" print " lost:", losses, "games" print " odds: %.2f%% winning percentage" % perc_win # Now, we'll run the game one million times and always stick to our original # door selection every single time. wins, losses = 0, 0 for i in range(1000000): # make an instance of the game, call it 'm' m = MontyHall() # run the game and switch choice of door. if m.run_game(switch=False): # a return value of True means we've won wins += 1 else: # a return value of False means we've lost losses += 1 # Now that the game has been run one million times, compute/display stats. perc_win = 100.0*wins / (wins+losses) print "\nOne million Monty Hall games (staying with original choice):" print " won:", wins, "games" print " lost:", losses, "games" print " odds: %.2f%% winning percentage\n" % perc_win
Running the program, we get the following output.
$ python MontyHall.py One million Monty Hall games (with switching): won: 666675 games lost: 333325 games odds: 66.67% winning percentage One million Monty Hall games (staying with original choice): won: 333779 games lost: 666221 games odds: 33.38% winning percentage