The Monty Hall Problem

The Monty Hall Problem derives its name from the American TV show Let’s Make A Deal, originally hosted by Monty Hall.

The problem in its essential format is:

You are shown 3 doors. Behind one of them is a prize or reward. You are asked to choose which door you think has the prize. The host then opens one of the other 2 doors, revealing that it does not contain the prize. He then asks if you want to stick with your original choice or switch to the remaining closed door. 

You also know from the game rules that the host knows where the prize is and will not open a door containing it. Should you switch?

As a concrete example, suppose you choose Door 1. The host opens Door 2 and you see there is no prize behind it. He then asks: “Do you want to stick with Door 1 or change to Door 3?”

The concept behind this question predates Let’s Make A Deal. An equivalent puzzle involving prisoners appeared in Martin Gardner’s Mathematical Games column in the Oct 1959 issue of Scientific American, with discussion of the solution in the November issue.

The problem in the form I have described above appears in a letter to the editor by Steve Selvin in the Feb 1975 issue (Vol 29 (1)) of American Statistician, with a follow up discussion in the Aug 1975 issue (Vol 29 (3)).

However it really gained public attention as a result of Marilyn vos Savant’s solution in her Ask Marilyn column in the 9 Sep, 1990 issue of Parade magazine.

She explains that after the host opens another door, your probability of winning is 1/3 if you stick to your choice and 2/3 if you switch.

Remarkable is the number of bombastic letters, many signed PhD, all confidently telling her she’s wrong and the probabilities are both 1/2.

Their common reasoning is that opening Door 2 in my concrete example above changes the information about both Doors 1 & 3. All we know now is that the prize is behind one of them, so the probabilities are equal ie equal to 1/2.

Many people with mathematics qualifications give this answer, even initially a genuine giant of the field, Paul Erdos.

But this reasoning is wrong: it misunderstands the symmetry breaking in the information caused by the action of the host in opening the door. The solution is a fairly straightforward exercise in conditional probability and Marilyn is correct.

I’ll explain why.

First note that if we brought in another contestant who had not witnessed the previous events and asked them to choose between Doors 1 & 3, their probabilities would be {1/2, 1/2}. But that is because they do not know that Door 1 was chosen by the first contestant and the host, knowing the prize was not behind Door 2, chose that door to open.

This is a good example of probabilities being representations of information. The second contestant has validly (in terms of logic) assigned probabilities of {1/2, 1/2} to Doors 1 & 3, whereas the first contestant, if they are reasoning correctly, assigns probabilities of {1/3, 2/3}. The reason for the difference is the first contestant has information provided by the action of the host that is not available to the second contestant.

Both contestants’ probability assignments are logically correct in that they are correctly derived from the information each has. However, being different, they can’t both be correct in the sense of being true. Suppose the prize is actually behind Door 3, which the host knows. Then the host’s probabilities are {0, 1}.

So, 3 different sets of probabilities, each a valid representation of the available information.

Which one is actually true in the sense that it is a representation of reality?

The host’s: {0, 1}. That’s because the event has already occurred.

Another example is:

Suppose Person A is told that a 6 sided die will be rolled and if it shows a 1, they will win a prize. They calculate a probability of winning of 1/6.

Now suppose Person B is told that A was lied to and shown the die to be rolled: it is 12 sided. They calculate a probability of winning of 1/12. 

A and B’s probabilities will both be valid representations of the information they have. However only B’s probabilities are correct in the sense of being a true representation of reality, because the event of rolling the die has not yet occurred … unless we believe in determinism, in which case both A’s and B’s probabilities are validly assigned but false.

Solution to the Monty Hall Problem

As a general principle, suppose an event has some set S of possible outcomes. If there is a permutation of a subset T of S which does not change the information we have about the event, then the probabilities we assign to the outcomes in T are equal, since permuting any of them does not change our view.

In particular, if all we know is that an event has n possible outcomes, we assign a probability of 1/n to each. For example, we think of the chances of a fair coin as being {1/2, 1/2}.

So our familiar assignment of equal chances to outcomes where we know nothing more than the number of possibilities actually derives from a symmetry argument. It is also the probability distribution with maximum entropy, however that principle also derives in part from symmetry arguments.

Presented with 3 doors and no other information, we assign probabilities of {1/3, 1/3, 1/3} for the prize.

Because the classic Monty Hall initial situation has full symmetry ie is unaltered by any permutation of the labels {1, 2, 3} on the doors, we can assume without loss of generality that we choose Door 1.

Write R = k for the reward being behind Door k and D = k for the host opening Door k.

We have chosen Door 1. Suppose the host opens Door 2. The reasoning will be the same had the host opened Door 3, so for concreteness, we will do the calculation for Door 2, seeing that the answer will be the same had we done it for Door 3.

We want the probability that R = 1, conditional on the host opening Door 2:

P(R = 1 | D = 2) = P(R = 1 ∧ D = 2) / P(D = 2)

We can calculate conditionals the other way around:

Prior to opening, P(D = 2 | R = 1) = 1 / 2, since the host could have opened Door 2 or 3.

But P(D = 2 | R = 2) = 0 and P(D = 2 | R = 3) = 1.

That’s because if R = 3, the host must necessarily open Door 2.

So P(D = 2) = ∑_k P(D = 2 | R = k) P(R = k) = 1/3 * 1/2 + 0 + 1/3 * 1 = 1/2.

Now from above, P(R = 1 ∧ D = 2) = P(D = 2 | R = 1) P(R = 1) = 1/2 * 1/3 = 1/6.

Put these together to get 

P(R = 1 | D = 2) = P(R = 1 ∧ D = 2) / P(D = 2) = 1/6 / 1/2 = 1/3.

That means P(R = 3 | D = 2) = 2/3, since R = 2 is impossible if D = 2.

So there is a 1/3 probability of the prize being behind Door 1 and a 2/3 probability of it being behind Door 3. That is, a 2/3 probability of winning if we switch.

Clearly the same reasoning carries through if the host opens Door 3 instead.

There is a 2/3 probability of winning if we switch and 1/3 if we stick to our first choice.

Why Does This Happen?

One way to look at it is that the host opening another door not containing the prize does not give us any additional information about the correctness of the contestant's original choice, because we knew a priori the host would choose a door which is not the contestant's choice and not the prize. So the probability of the original choice being right cannot change: it remains 1/3. 

People are fooled as to the change in probabilities because the host opening the door makes them think we have received new information about both the location of the prize and therefore the correctness of the original guess. We have certainly received new information about the location of the prize: if the host opens Door 2, the probability it is behind Door 3 has risen from 1/3 to 2/3. The error is the "therefore". People see a link between information about the location of the prize and the correctness of the original guess. But there isn't one.

This is counterintuitive for many people.

The separation happens because both our guess and the location of the prize influence which door is opened, but not symmetrically.

In terms of a causal graph:  Choice → Door ← Prize.

Door is what’s known as a collider. Information on the door D opened makes all probabilities conditional on D.

If you condition on a collider, you introduce a dependency between Choice and Prize, despite them being independent without the conditioning. It is this dependency which breaks the original {1/3, 1/3, 1/3} probability symmetry.

Recall our discussion of symmetry at the beginning of the Solution section. In general, introducing dependency and certainly introducing asymmetric information breaks symmetry in the probability distribution.

An easier to see example is:

Toss a pair of coins many times, say 100 or 1000, making sure all tosses are independent, including the pair in each trial. Record the result H or T of coin 1 in column 1 and coin 2 in column 2.

You should see the data in each column are statistically independent.

Now censor the data to remove all rows with T, T. 

The 2 columns are now clearly dependent: seeing a T in column 1 tells you column 2 has an H in that row and vice versa.

The causal graph:  Coin 1 → Retain Data ← Coin 2

Since both Coin 1 and Coin 2 causally influence Retain Data, it is a collider, so conditioning on it by only observing Retain Data = 1 introduces a dependence between the previously independent Coin 1 and Coin 2.

Simulation

We can easily simulate the Monty Hall game. It is trivial to extend it to n doors.

In fact, it was a simulation which convinced Paul Erdos.

We'll actually see why the answer is {1/3, 2/3} when we optimise the simulation algorithm.

Why is a simulation sufficient to show that switching is better?

Frequencies after the fact are not ontologically equivalent to probabilities, which exist before the experiment or event(s). But the Law of Large Numbers shows that if we have a sufficiently large number of independent events or trials with identical probability distribution, the frequency distribution of the outcomes converges to the a priori probability distribution. 

For a small number of independent trials, there is a non-negligible probability that due to pure chance, the observed frequencies differ from the true probability distribution by more than some defined amount δ, which we are free to choose, no matter how small. But as the number of trials increases, the probability that this difference > δ decreases, until it becomes vanishingly small. 

That is what converges means: if we do enough independent trials, the observed frequencies are valid estimates of the true, perhaps unknown probabilities, to within any number of decimal places we want. The more decimal places, the more trials we'll need. But the point is that if we do enough, our experimental estimate will have the desired accuracy.

In our case, we are simulating a large number of independent, but identically set up Monty Hall games, say 100,000, some where the contestant doesn't switch and some where they do. With modern computing power, this runs in seconds, even on a standard laptop.

We end up with 2 sets of data.

The first is all the simulations where the contestant doesn't switch. We count the proportion of outcomes in which the contestant wins. We'll see that this is very close to 1/3.

The second set is all the simulations where the contestant switches. Again, we count the proportion of outcomes in which the contestant wins. We'll see that this is very close to 2/3.

From our discussion above, if the true probabilities are not close to {1/3, 2/3}, the chance our simulation will produce frequencies of very close to {1/3, 2/3} is vanishingly small.

In particular, {1/2, 1/2} is so far from {1/3, 2/3} that our simulation will demonstrate with near certainty that {1/2, 1/2} is the wrong answer.

Algorithm

For each simulation path:

1. Due to the discussion above, set the contestant’s choice H to Door 1: H = 1.
2. Generate a random sample from {1, 2, …, n}. That is the value of R, the location of the prize.
3. If R = 1, generate another random sample from {2, …, n}. 
   Else if R = k > 1, generate the random sample from {2, …, n} – {k}.
   This is the value D = d, the door opened by the host.
4. Generate a random sample W from {0, 1}. 
5. If W = 1, the contestant switches, simulated by generating a random sample H = r from {2, …, n} – {d}. 
   Note that if n = 3, we don’t need a random sample: if d = 2, H = 3 else d = 3 so H = 2.
6. If W = 0, record a 1 in the W = 0 column if R = 1 and a 0 otherwise.
   If W = 1, record a 1 in the W = 1 column if R = r (see Step 5) and a 0 otherwise.

If you run this simulation over many paths, you’ll see the proportion of 1s in the W = 0 column (the instances when the contest doesn’t switch and is correct) converges to P(0) = 1/n.

Harder to see is that the proportion of 1s in the W = 1 column (the instances when the contest switches and is correct) converges to P(1) = (n – 1) / n (n – 2).

For n = 3, P(1) = 2/3, so you should be able to see the proportion in your output is close to 0.667.

  ***********

The above algorithm was more to demonstrate how we could mirror the exact steps of the game. It is not optimised for runtime and certainly not how a programmer would write it.

Optimising the algorithm actually lets us see why the probability is 1 / n if you don't switch and hence
(n – 1) / n (n – 2) if you do switch to one of the other n - 2 doors.

If we run N simulation paths, we can vectorise the location of the prize R in Step 2 ie generate a random vector of length N from {1, 2, …, n}.

We only need to split the simulation into 2 subsets: one set where the contestant switches and one where they don't. Since the paths are all independent, we don't even need to randomise the switching: setting W = 1 (switch) for the first N / 2 paths and W = 0 for the rest is fine. We could generate a random vector for W, but independence of the paths means it doesn't matter.

Note that for paths with W = 0 where the contestant doesn't switch, we don't even need to simulate the host opening the door because it doesn't affect the outcome: we are only interested in whether R = the contestant's choice = 1. This fits with our assertion above that the host opening another door not containing the prize does not give us any additional information about the correctness of the contestant's original choice.

So we would actually generate the vector W as Step 3 and just loop over all paths with W = 1, doing Steps 3 and 5 in the original algorithm, now as Steps 4 and 5.

The last two paragraphs show us the answer to the problem: if the contestant doesn't switch (W = 0), we are counting the proportion of randomly generated R which are 1. That will be close to 1/n. So we expect the answer 1/3 when we set n = 3 to simulate the original problem.

In paths where the contestant switches (W = 1), if n = 3, only 1/3 of them have R = 1. But for n = 3, the switch is deterministic. Therefore only 1/3 switch away from the correct choice. So the other 2/3 must switch to the correct choice.

Generalization of the Problem

We can extend the problem to any number n of doors. After your guess, the host opens m of the other n – 1 doors.

If m = 1, it’s not hard to mirror the argument in the n = 3 case above.

Prior to opening, for any k > 1:

P(D = k | R = 1) = 1 / (n – 1).

P(D = k | R = r) = 1 / (n – 2) for k ≠ r.

Thus P(D = k) = 1 / (n – 1).

Also P(R = 1 ∧ D = k) = P(D = k | R = 1) P(R = 1) = 1 / n (n – 1).

If r > 1 & k ≠ r, P(R = r ∧ D = k) = P(D = k | R = r) P(R = r) = 1 / n (n – 2).

Put these together to get 

P(R = 1 | D = k) = P(R = 1 ∧ D = k) / P(D = k) = 1 / n.

P(R = r | D = k) = P(R = r ∧ D = k) / P(D = k) = (n – 1) / n (n – 2).

That is, after the host opens door k ≠ 1, if you stay with your original choice of Door 1, the probability of winning the prize is P(R = 1 | D = k) = 1 / n.

If you switch your choice to Door r, the probability of winning the prize is P(R = r | D = k) = (n – 1) / n (n – 2).

Now if the host opens some set S of m > 1 doors:

P(D = S | R = 1) = 1 / choose(n - 1, m).

P(D = S | R = r) = 1 / choose(n - 2, m) for r ∉ {1, S}.

With a little algebra, P(D = S) = 1 / choose(n - 1, m).

Therefore

P(R = 1 | D = S) = P(R = 1 ∧ D = S) / P(D = S) = 1 / n.

If r ∉ {1, S}, P(R = r | D = S) = P(R = r ∧ D = S) / P(D = S) = (n – 1) / n (n – m – 1).

That is, after the host opens m doors, if you stay with your original choice of Door 1, the probability of winning the prize is still 1 / n.

If you switch your choice to one of the remaining n – m – 1 closed doors, the probability of winning the prize is
(n – 1) / n (n – m – 1) > 1 / n.

So no matter how many doors there are or how many doors the host opens, it’s always better to switch, even if your switch means having another guess from the multiple closed doors which remain.