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?
It’s 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.
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.
For each simulation path:
- Due to the discussion above, set the contestant’s choice H to Door 1: H = 1.
- Generate a random sample from {1, 2, …, n}. That is the value of R, the location of the prize.
- If R = 1, generate another random sample from {2, …, n}.
Else if R = k > 1, generate the random sample from {2, …, n} – {k}.
That is the value D = d, the door opened by the host. - Generate a random sample W from {0, 1}.
- 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. - 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.
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.