The Game Show Host Problem

Introduction

In the movie 21 they make mention of The Game Show Host problem. The gist of the problem is this: You are on a game show. The host presents you with 3 doors, 1 of which has a car behind it, the other 2 have goats. The game show host tells you to pick a door. You do so, at which point the game show host opens up a door to show you a goat behind the door and then asks you if you would like to switch your choice to the other closed door. The question is then, should you switch your choice?

Also known as the Monty Hall Problem; it's a probability puzzle based on the American television game show Let's Make a Deal. The name comes from the show's host, Monty Hall. The problem is also called the Monty Hall paradox, as it is a veridical paradox in that the solution is counterintuitive.

By the law of large numbers, this experiment is likely to approximate the probability of winning, and running the experiment over enough rounds should not only verify that the player does win by switching two times out of three, but show why.

The Law of large numbers states: Given a random variable with a finite expected value, if its values are repeatedly sampled, as the number of these observations increases, their mean will tend to approach and stay close to the expected value.

The following is the implementation of the Monty Hall problem:

namespace ats.MontyHall
{ 
public static String MontyHallSolve(int totalDoors) 
{
//int[] doors = {0,0,0};//0 is a goat, 1 is a car
int TRIALS = 1000;
int switchWins = 0;
int stayWins = 0;
Random gen = new Random();
for (int plays = 0; plays < TRIALS; plays++)
	{ 
	         //put a winner in a random door
		int prize = gen.Next(totalDoors); 
		int userChoice1 = gen.Next(totalDoors); 
	         // host opens door other than user's choice without prize
		int hostChoice = chooseAnotherDoor(prize, userChoice1);
	         // user always switches
		int userChoice2 = chooseAnotherDoor(userChoice1, hostChoice);
		if (userChoice2 == prize)
		switchWins++;
		else stayWins++;
	}
double ratioSwitch = 100 * (switchWins / (double)TRIALS);
double ratioStay = 100 * (stayWins / (double)TRIALS);

return "Switching wins " + switchWins + " times"+ Environment.NewLine +
    "Staying wins " + stayWins + "times."+Environment.NewLine +
    "Percent Switch ratio : " + ratioSwitch +Environment.NewLine +
    "Percent Stay ratio: " + ratioStay;
}

private static int chooseAnotherDoor(int door1, int door2)
{
Random gen = new Random();
int result;
do
	result = gen.Next(3);
while (result == door1 || result == door2);
return result;
}
}

Output

Switching wins 640 times. Staying wins 360 times.

Solution

One way to think about this problem is to consider the sample space, which Monty alters by opening one of the doors that has a goat behind it. In doing so, he effectively removes one of the two losing doors from the sample space.

We will assume that there is a winning door and that the two remaining doors, A and B, both have goats behind them. There are three options:

1. The contestant first chooses the door with the car behind it. She is then shown either door A or door B, which reveals a goat. If she changes her choice of doors, she loses. If she stays with her original choice, she wins.
2. The contestant first chooses door A. She is then shown door B, which has a goat behind it. If she switches to the remaining door, she wins the car. Otherwise, she loses.
3. The contestant first chooses door B. She is then is shown door A, which has a goat behind it. If she switches to the remaining door, she wins the car. Otherwise, she loses.

Each of the above three options has a 1/3 probability of occurring, because the contestant is equally likely to begin by choosing any one of the three doors. In two of the above options, the contestant wins the car if she switches doors; in only one of the options does she win if she does not switch doors. When she switches, she wins the car twice (the number of favorable outcomes) out of three possible options (the sample space). Thus the probability of winning the car is 2/3 if she switches doors, which means that she should always switch doors - unless she wants to become a goatherd.

This result of 2/3 may seem counterintuitive to many of us because we may believe that the probability of winning the car should be 1/2 once Monty has shown that the car is not behind door A or door B. Many people reason that since there are two doors left, one of which must conceal the car, the probability of winning must be 1/2. This would mean that switching doors would not make a difference. As we've shown above through the three different options, however, this is not the case.

One way to convince yourself that 2/3 is the correct probability is to do a simulation with a friend. Have your friend impersonate Monty Hall and you be the contestant. Keep track of how often you win the car by switching doors and by not switching doors.

Other Solutions

If you're still not convinced that 2/3 is the correct probability, here are two more ways to think about the problem.

1. It seems to make sense that you have a 1/3 chance of picking the correct door. This means, however, that since the probabilities must add up to one - and the car has to be somewhere - you also have a 2/3 chance of not picking the correct door. In other words, you are more likely not to win the car than to win it.

   Imagine that Monty opens a door and shows that there's only a goat behind it. Consider that the car is more likely to be behind a door other than the one you choose. Monty has just shown that one of those two doors - which together have the greater probability of concealing the car - actually conceals a goat. This means that you should definitely switch doors, because the remaining door now has a 2/3 chance of concealing the car. Why? Well, your first choice still has a 1/3 probability of being the correct door, so the additional 2/3 probability must be somewhere else. Since you know that one of the two doors that previously shared the 2/3 probability does not hide the car, you should switch to the other door, which still has a 2/3 chance of concealing the car.

2. What if there were 1,000 doors? You would have a 1/1,000 chance of picking the correct door. If Monty opens 998 doors, all of them with goats behind them, the door that you chose first will still have a 1/1,000 chance of being the one that conceals the car, but the other remaining door will have a 999/1,000 probability of being the door that is concealing the car. Here switching sounds like a pretty good idea.

Other

It may be easier to appreciate the solution by considering the same problem with 1,000,000 doors instead of just three (vos Savant 1990). In this case, there are 999,999 doors with goats behind them and one door with a prize. The player picks a door. The game host then opens 999,998 of the other doors revealing 999,998 goats—imagine the host starting with the first door and going down a line of 1,000,000 doors, opening each one, skipping over only the player's door and one other door. The host then offers the player the chance to switch to the only other unopened door. On average, in 999,999 out of 1,000,000 times the other door will contain the prize, as 999,999 out of 1,000,000 times the player first picked a door with a goat. A rational player should switch. Intuitively speaking, the player should ask how likely is it, that given a million doors, he or she managed to pick the right one.

Stibel et al. (2008) propose working memory demand is taxed during the Monty Hall problem and that this forces people to "collapse" their choices into two equally probable options. They report that when increasing the number of options to over 7 choices (7 doors) people tend to switch more often, however most still incorrectly judge the probability of success at 50/50.

Some of the applications of this would be to solve:

Three Prisoners Problem

Where there are three prisoners scheduled to be executed, A, B, and C, although one will be pardoned. A asks the warden to tell him the name of one of the others who will be executed. As the question is not directly about A's fate, the warden obliges—secretly flipping a coin to decide which name to give A if A is the one being pardoned. Assuming the warden's truthfulness, there are now only two possibilities for who will be pardoned: A, and whichever of B or C the warden did not name. Did A gain any information as to his own fate, that is, does he change his estimate of the chances he will be pardoned? To make the analogy to the Monty Hall problem more explicit: if the warden says "B will be executed" and A could switch fates with C, should he?

The Three Card Problem or the Bertrand's Box Paradox

Suppose you have three cards:

• a black card that is black on both sides
• a white card that is white on both sides, and
• a mixed card that is black on one side and white on the other

You put all of the cards in a hat, pull one out at random, and place it on a table. The side facing up is black. What are the odds that the other side is also black?

History

• 8 Jan 2009 - Draft