Monty Hall revisited

When Sasha Gnedin was interviewed for his position here, he had lunch with me and told me about his new take on the Monty Hall problem. It has now appeared here in the Mathematical Intelligencer.

To summarise briefly: you are a contestant on a game show, where the host, Monty Hall, shows you three doors. Behind one of the doors is a car, and the other two conceal goats. Assume that you really want to win the car, and have no use whatever for goats. Monty invites you to choose a door. He then opens a different door from the one you chose and reveals a goat; he asks you do you want to hold your original choice or switch to the third door. What should you do?

This is usually analysed as a problem in probability. Indeed, much of the misunderstanding arises from the assumption that, when one door has been opened, the car is equally likely to lie behind either of the other doors, so it doesn’t matter what you choose. I have previously quoted Einstein as saying,

In calculating entropy by molecular-theoretic methods, the word “probability” is often used in a sense differing from the way the word is defined in probability theory. In particular, “cases of equal probability” are often hypothetically stipulated when the theoretical methods employed are definite enough to permit a deduction rather than a stipulation.

In other words, don’t assume that outcomes are equally likely,
especially if you have enough information to show that they are not!

However, Sasha contends that probability doesn’t really come into it: this is a problem in game theory. The whole procedure is a very simple game with four moves. First (before the show), Monty chooses a door to conceal the car. Then you choose a door. Next, Monty chooses (if the option exists) which door to open. Finally, you choose whether to hold or switch.

What are all the possible strategies available to you and to Monty? A pure strategy is a rule telling a player what to do at each possible stage of the game. As von Neumann and Morgenstern observed, there are also mixed strategies, where a player choose at random among the pure strategies available. This will come in later, but for the first part of the analysis, only pure strategies arise; I will simply call them strategies.

Monty Hall has six possible strategies. Each can be described by a pair of distinct integers from the set {1,2,3}. Thus, for example, 32 means that Monty hides the car behind door 3; if you choose door 3, he opens door 2 rather than door 1. (If you choose a door other than 3, Monty’s move is forced; the strategy simply stores the information in case it is needed.)

You, the contestant, have twelve possible strategies. First you choose a door; then you have to know whether to hold or switch when Monty opens either of the other two doors. I will regard the doors as being circularly ordered for the purpose of writing down the strategy, so that if H and S denote “hold” and “switch”, the first letter refers to the next door in the circular order and the second to the last door. Thus, for example, strategy 2HS means “Choose door 2; if Monty opens door 3 then hold; if Monty opens door 1 then switch”.

Now the heart of Sasha’s proof that it is always better to switch is the following observation:

Any strategy A of the contestant which involves holding in any circumstance is dominated by another strategy B which switches in both cases, in the sense that, no matter what Monty does, the outcome of B is at least as good as the outcome of A.

To see this, we first observe that the “always switch” strategy 1SS loses if the car is behind door 1 and wins in all other cases. Now consider, for example, the strategy 2HS. This strategy only ever ends up with door 2 or door 3, and so it loses if the car is behind door 1 (and in another case as well, namely if the car is behind door 2 and Monty opens door 1). So it does worse than 1SS in all cases. The arguments for other strategies are almost identical.

So it is always better to switch, and nine of the twelve possible strategies for the contestant can be disregarded.

At this point one can reintroduce some classical game theory. If the game is a “zero-sum game” (in other words, if your gain in winning the car is Monty Hall’s loss), then the game is completely specified by the pay-off matrix (written with Monty’s strategies labelling columns and the contestant’s labelling rows)

12 13 21 23 31 32
1SS 0 0 1 1 1 1
2SS 1 1 0 0 1 1
3SS 1 1 1 1 0 0

From this it can be shown that the contestant should adopt a mixed strategy by choosing the door at random with probability 1/3 and then always switching. It is also possible to discover the best mixed strategy for Monty Hall, as Sasha points out in the paper.

However, now (like Bob Dylan in the final stanza of “Black Diamond Bay”) let us step back and observe that we are really watching this on television. The contestant’s strategy is to win the car, but Monty Hall’s strategy is to increase the ratings for his show (if they fall too low, he will be out of a job). The way to do this may not be to try to defeat the contestant if at all possible. It may be that, the more prizes are given away (up to a point), the higher the ratings; so Monty may have some interest in the contestant winning from time to time. In this case, the analysis of mixed strategies falls down. If the contestant finds that Monty is dropping hints about where the car is, she may be best off to abandon her strategy and follow these hints!

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , , . Bookmark the permalink.

4 Responses to Monty Hall revisited

  1. Gabriel Verret says:

    I think much of the misunderstanding often comes from the way the problem is stated. It is very important to state the Monty knows where the car is and that he is picking a door hiding a goat on purpose.

    For example, from your summary of the problem, a person seeing this problem for the first time could easily understand that Monty is just picking doors randomly and happened to pick a door with a goat, under which assumption the usually wrong answer becomes the right answer : it doesn’t matter if you switch or hold.

    • Indeed, anyone watching a chess game for the first time could easily understand that any piece can be moved anywhere, in which case the strategy would be rather different.

      I almost added a last paragraph saying that, if Monty doesn’t obey the rules of the game, then the analysis is different.

  2. Woodstone Sorenson says:

    Complicated instructions for this puzzle based on mathematics are unnecessarily complex and misleading. This is a logic puzzle – not a question of probability.

    You select one of three doors. (Try to select one with a goat. Your odds are two out of three.) If you select a door with a goat, your probability of winning becomes 100%. They don’t open your door (goat 1), they open the door with goat 2 and you choose the remaining door.)

    Odds of winning – very simple – two out of three!

    • The Sudoku instructions in The Independent say “There is no mathematics involved; solve the puzzle with reasoning and logic”. You are saying something similar. But mathematics is nothing but reasoning and logic.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s