The Monty Hall problem involves a classical game show situation and is named after Monty Hall, the long-time host of the TV game show Let's Make a Deal. There are three doors labeled 1, 2, and 3. A car is behind one of the doors, while goats are behind the other two:

The rules are as follows:

- The player selects a door.
- The host selects a different door and opens it.
- The host gives the player the option of switching from her original choice to the remaining closed door.
- The door finally selected by the player is opened and she either wins or loses.

The Monty Hall problem became the subject of intense controversy because of several articles by Marilyn Vos Savant in the Ask Marilyn column of Parade magazine, a popular Sunday newspaper supplement. The controversy began when a reader posed the problem in the following way:

Suppose you're on a game show, and you're given a choice of three doors. Behind one door is a car; behind the others, goats. You pick a door--say No. 1--and the host, who knows what's behind the doors, opens another door--say No. 3--which has a goat. He then says to you,Do you want to pick door No. 2?Is it to your advantage to switch your choice?

Marilyn's response was that the contestant should switch doors, claiming that there is a $1/3$ chance that the car is behind door 1, while there is a $2/3$ chance that the car is behind door 2. In two follow-up columns, Marilyn printed a number of responses, some from academics, most of whom claimed in angry or sarcastic tones that she was wrong and that there are equal chances that the car is behind doors 1 or 2. Marilyn stood by her original answer and offered additional, but non-mathematical, arguments.

Think about the problem. Do you agree with Marilyn or with her critics, or do you think that neither solution is correct?

In the Monty Hall game, set the host strategy to *standard* (the meaning of this strategy will be explained in the below). Play the Monty Hall game 50 times with each of the following strategies. Do you want to reconsider your answer to Exercise 1?

- Always switch
- Never switch

In the Monty Hall game, set the host strategy to *blind* (the meaning of this strategy will be explained below). Play the Monty Hall game 50 times with each of the following strategies. Do you want to reconsider your answer to Exercise 1?

- Always switch
- Never switch

When we begin to think carefully about the Monty Hall problem, we realize that the statement of the problem by Marilyn's reader is so vague that a meaningful discussion is not possible without clarifying assumptions about the strategies of the host and player. Indeed, we will see that misunderstandings about these strategies are the cause of the controversy.

Let us try to formulate the problem mathematically. In general, the actions of the host and player can vary from game to game, but if we are to have a random experiment in the classical sense, we must assume that the same probability distributions govern the host and player on each game and that the games are independent.

There are four basic random variables for a game:

- $U$: the number of the door containing the car.
- $X$: the number of the first door selected by the player.
- $V$: the number of the door opened by the host.
- $Y$: the number of the second door selected by the player.

Each of these random variables has the possible values 1, 2, and 3. However, because of the rules of the game, the door opened by the host cannot be either of the doors selected by the player, so
$V\neq X$
and
$V\neq Y$.
In general, we *will* allow the possibility
$V=U$,
that the host opens the door with the car behind it. Whether this is a *reasonable* action of the host is the source of the controversy about this problem.

The Monty Hall experiment will be completely defined mathematically once the joint distribution of the basic variables is specified. This joint distribution in turn depends on the strategies of the host and player, which we will consider next.

In the Monty Hall experiment, note that the host determines the probability density function of the door containing the car:

$$(U=i)\text{,\hspace{1em}}i\in \{1, 2, 3\}$$The obvious choice for the host is to randomly assign the car to one of the three doors. This leads to the uniform distribution, and unless otherwise noted, we will always assume that $U$ has this distribution:

$$(U=i)=1/3\text{,\hspace{1em}}i\in \{1, 2, 3\}$$The host also determines the conditional density function of the door he opens, given knowledge of the door containing the car and the first door selected by the player:

$$(V=k, U=iX=j)\text{,\hspace{1em}}\left(\begin{array}{c}i\\ j\\ k\end{array}\right)\in \{1, 2, 3\}^{3}$$Recall that since the host cannot open the door chosen by the player, this probability must be 0 for $k=j$. The distribution of $U$ and the conditional distribution of $V$ constitute the host strategy.

In most real game shows, the host would always open a door with a goat behind it. If the player's first choice is incorrect, then the host has no choice; he cannot open the door with the car or the player's choice and must therefore open the only remaining door. On the other hand, if the player's first choice *is* correct, then the host can open either of the remaining doors, since goats are behind both. Thus, he might naturally pick one of these doors at random.

Show that this strategy leads to the following conditional distribution:

$$(V=k, U=iX=j)=\begin{cases}1 & \text{if $(i\neq j)\land (i\neq k)\land (k\neq j)$}\\ 1/2 & \text{if $(i=j)\land (k\neq i)$}\\ 0 & \text{if $(k=i)\land (k=j)$}\end{cases}$$The distribution in Exercise 4, along with the uniform distribution for $U$, will be referred to as the standard strategy for the host.

In the Monty Hall game, set the host strategy to *standard*. Play the game 50 times with each of the following player strategies. Which works better?

- Always switch
- Never switch

Another possible second-stage strategy is for the host to always open a door chosen at random from the two possibilities. Thus, the host might well open the door containing the car.

Show that this strategy leads to the following conditional distribution:

$$(V=k, U=iX=j)=\begin{cases}1/2 & \text{if $k\neq j$}\\ 0 & \text{if $k=j$}\end{cases}$$The distribution in Exercise 6, together with the uniform distribution for $U$, will be referred to as the blind strategy for the host. The blind strategy seems a bit odd. However, the confusion between the two strategies is the source of the controversy concerning this problem.

In the Monty Hall game, set the host strategy to
*blind*. Play the game 50 times with each of the following player strategies. Which works better?

- Always switch
- Never switch

The player, on the other hand, determines the probability density function of her first choice:

$$(X=j)\text{,\hspace{1em}}j\in \{1, 2, 3\}$$The obvious first choice for the player is to randomly choose a door, since the player has no knowledge at this point. This leads to the uniform distribution:

$$(X=j)=1/3\text{,\hspace{1em}}j\in \{1, 2, 3\}$$The player also determines the conditional density function of her second choice, given knowledge of her first choice and the door opened by the host:

$$(Y=l, X=jV=k)\text{,\hspace{1em}}\left(\begin{array}{c}j\\ k\\ l\end{array}\right)\in \{1, 2, 3\}^{3}\text{\hspace{0.5em}with\hspace{0.5em}}j\neq k$$Recall that since the player cannot choose the door opened by the host, this probability must be 0 for $l=k$. The distribution of $X$ and the conditional distribution of $Y$ constitute the player strategy.

Suppose that the player switches with probability $p$. Show that this leads to the following conditional distribution

$$(Y=l, X=jV=k)=\begin{cases}p & \text{if $(j\neq k)\land (j\neq l)\land (k\neq l)$}\\ 1-p & \text{if $(j\neq k)\land (l=j)$}\\ 0 & \text{if $(j=k)\land (l=k)$}\end{cases}$$In particular, if $p=1$, the player always switches, while if $p=0$, the player never switches.

We must make some independence assumptions to incorporate the lack of knowledge that the host and player have about each other's actions. First, the player has no knowledge of the door containing the car, so we assume that $U$ and $X$ are independent. Also, the only information about the car door that the player has when she makes her second choice is the information (if any) revealed by her first choice and the host's subsequent selection. Mathematically, this means that $Y$ is conditionally independent of $U$ given $X$ and $V$.

The host and player strategies form the basic data for the Monty Hall problem. Because of the independence assumptions, the joint distribution of the basic random variables is completely determined by these strategies.

Use the multiplication rule of conditional probability to show that

$$(U=i, X=j, V=k, Y=l)=(U=i)(X=j)(V=k, U=iX=j)(Y=l, X=jV=k)\text{,\hspace{1em}}\left(\begin{array}{c}i\\ j\\ k\\ l\end{array}\right)\in \{1, 2, 3\}^{4}$$The probability of any event defined in terms of the Monty Hall problem can be computed by summing the joint density over the appropriate values of $\left(\begin{array}{c}i\\ j\\ k\\ l\end{array}\right)$.

Show that with either of the basic host strategies, $V$ is uniformly distributed on $\{1, 2, 3\}$.

Suppose that the player switches with probability $p$. Show that with either of the basic host strategies, $Y$ is uniformly distributed on $\{1, 2, 3\}$.

In the Monty Hall experiment, set the host strategy to *standard*. For each of the following values of
$p$, run the simulation 1000 times with an update frequency of 10. Based on relative frequency, which strategy works best?

- $p=0$ (never switch)
- $p=0.3$
- $p=0.5$
- $p=0.7$
- $p=1$ (always switch)

In the Monty Hall experiment, set the host strategy to *blind*. For each of the following values of
$p$, run the experiment 1000 times with an update frequency of 10. Based on relative frequency, which strategy works best?

- $p=0$ (never switch)
- $p=0.3$
- $p=0.5$
- $p=0.7$
- $p=1$ (always switch)

The event that the player wins a game is $\{Y=U\}$. We will compute the probability of this event with the basic host and player strategies.

Suppose that the host follows the standard strategy and that the player switches with probability $p$. Show that the probability that the player wins is

$$(Y=U)=\frac{1+p}{3}$$In particular, if the player always switches, the probability that she wins is $2/3$ and if the player never switches, the probability that she wins is $1/3$.

In the Monty Hall experiment, set the host strategy to *standard*. For each of the following values of
$p$, run the simulation 1000 times with an update frequency of 10. In each case, note the apparent convergence of the relative frequency of winning to the probability of winning.

- $p=0$ (never switch)
- $p=0.3$
- $p=0.5$
- $p=0.7$
- $p=1$ (always switch)

Suppose that the host follows the blind strategy. Show that for *any* player strategy (not just the standard ones),

In the Monty Hall experiment, set the host strategy to *blind*. For each of the following values of
$p$, run the experiment 1000 times with an update frequency of 10. In each case, note the apparent convergence of the relative frequency of winning to the probability of winning.

- $p=0$ (never switch)
- $p=0.3$
- $p=0.5$
- $p=0.7$
- $p=1$ (always switch)

For a complete solution of the Monty Hall problem, we want to compute the conditional probability that the player wins, given that the host opens a door with a goat behind it:

$$(Y=U, V\neq U)=\frac{(Y=U)}{(V\neq U)}$$With the basic host and player strategies, the numerator, the probability of winning, has been computed. Thus we need to consider the denominator, the probability that the host opens a door with a goat. If the host use the standard strategy, then the conditional probability of winning is the same as the unconditional probability of winning, regardless of the player strategy. If the player switches with probability $p$, then by Exercise 14,

$$(Y=U, V\neq U)=\frac{1+p}{3}$$Show that if the host follows the blind strategy, then for any player strategy, $(V\neq U)=2/3$ and therefore $(Y=U, V\neq U)=1/2$.

In the Monty Hall experiment, set the host strategy to *blind*. For each of the following values of
$p$, run the experiment 500 times updating after each run. In each case, compute the conditional relative frequency of winning, given that the host shows a goat, and compare with the theoretical answer in Exercise 18.

- $p=0$ (never switch)
- $p=0.3$
- $p=0.5$
- $p=0.7$
- $p=1$ (always switch)

The confusion between the conditional probability of winning for these two strategies has been the source of much controversy in the Monty Hall problem. Marilyn was probably thinking of the standard host strategy, while some of her critics were thinking of the blind strategy. This problem points out the importance of careful modeling, of the careful statement of assumptions. Marilyn is correct if the host follows the standard strategy; the critics are correct if the host follows the blind strategy; any number of other answers could be correct if the host follows other strategies.

The mathematical formulation we have used is just about the most complete one possible. However, if we just want to solve Marilyn's problem, there is a much simpler analysis (which you may have discovered yourself). Suppose that the host always opens a door with a goat. If the player's first door is incorrect (contains a goat), then the host has no choice and must open the other door with a goat. Then, if the player switches, she wins. On the other hand, if the player's first door is correct and she switches, then of course she loses. Thus, we see that if the player always switches, then *she wins if and only if her first choice is incorrect*, an event that obviously has probability
$2/3$.
If the player never switches, then she wins if and only if her first choice is correct, an event with probability
$1/3$.