There is currently an active discussion of the Monty Hall problem on the Clojure discussion group. The discussion centers on the simulation of the problem; here I want to look at it from first principles. The problem is actually an easy one to reason about when looked at from the right perspective.

Here is how the Monty Hall problem was stated in the discussion mentioned above.

Suppose you’re on a game show and you’re given the choice of three doors [and will win what is behind the chosen door]. Behind one door is a car; behind the others, goats [unwanted 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 [uniformly] at random. 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?

Let’s generalize the problem. You are presented with N doors, behind one is the car, behind the other N-1 doors there are goats. Monty knows what is behind each door. You choose a door, then Monty opens all but two of the doors, yours and one other. Behind the N-2 open doors are goats. Two doors remain closed. Should you switch from your original choice?

Not to ruin the suspense, but for N > 2 you should switch. Let’s see why.

We need to consider the probabilities of several events; here is some notation to describe the relevant events.

  • C: the event that your original choice of door hides the car.
  • C: the event that your original choice of door does not hide the car.
  • M: the event that Monty opens N-2 doors, none reveal the car.
  • MC: both M and C occur.
  • MC: both M and C occur.

By the time you are asked to reconsider your choice, event M has happened, and one but not both of C and C has happened. Another way to put it is that MC xor MC has happened. These two events are mutually exclusive, and one or the other occurred, but you don’t know which. So you need to decide which was more probable.

The choice before you is to decide which is larger: P(MC), the probability of MC, or P(MC), the probability of MC. If P(MC) is larger, you should stick with your orginal choice. If P(MC) is larger, you should switch. If the two are equal, it does not matter whether you switch.

The first key observation: P(M) = 1. No matter what door you chose, Monty always can and always will open all doors but yours and one other, and not reveal the car. He can easily do this because he knows what is behind every door.

The next key observation concerns the notion of probabilistically independent events. Events A and B are independent iff P(AB) = P(A)*P(B). This is a special relationship; not all events are independent. But we have here a special case. An event of probability 1 is independent of any other event.

In particular, since P(M)=1, then M is independent of C, hence P(MC)=P(M)*P(C)=P(C). Similarly, P(MC)=P(M)*P(C)=P(C).

This reduces the choice before us to deciding which is larger, P(C) or P(C). But this is trivial: P(C) is 1/N, and P(C) is (N-1)/N.

An interesting special case of the game is for N=2. There are only two doors, Monty opens no doors, and it makes no difference whether or not you switch doors. For N>2 you should switch.

If you are not convinced that it pays to switch, I have a proposition for you. Let’s play the game a few times with a deck of cards, say using 10 red cards as goats, one black card as the car (N=11). You play the role of Monty, I’ll be your opponent. I’ll consistently play the always-switch strategy. Play is for a dollar a round (more if you prefer). Monty pays if the opponent gets the car, the opponent pays otherwise. I’ll be happy to play for long as you like.