If your experiment needs statistics, you ought to have done a better experiment.
- Ernest Rutherford
What is Monty Hall paradox?
In case you have watched the movie "21", you may remember a scene in the beginning of the film when a lecturer confronts his student with the following logical puzzle:
Suppose you're on a game show, and you're given the choice of three doors: behind one door is a car; behind the others, goats. You pick a door, and the host who knows what's behind the doors opens another door which has a goat. He then asks if you want to rethink and choose another door. Is it to your advantage to switch your choice?
The student agrees to swap his choice, and he is right. His winning chances will then increase from 1/3 to 2/3. The extract from the movie can be viewed here, and Wikipedia has a fairly comprehensive explanation of this paradox known as Monty Hall problem, named after a television show host.
I will not repeat the solution of the problem here. It’s well explained in various sources available on the net. Still, the paradox triggers hot discussions when sometimes theoretical argumentation is not enough - people may insist that such things just can’t happen.
This is why I decided to write a simple Windows Forms application that takes as input the number of doors (let’s show the statistics for any number of doors, not just three, and the host will have to open N-2 doors with goats behind them) and the number of iterations, and shows the chances of a player that chooses to swap his original choice. For clarity, we will assume that the player chooses to switch his initial choice, so all chances and probabilities will be computed with regards to the strategy based on choice switching.
So much depends on the host!
To make a program more illustrative, I decided to show not just Monty Hall’s case. Since so many people insist that swapping the door does not increase the player’s chances, I wanted to show when it is actually true: and it is true if the host opens doors randomly, with a risk to reveal the car. But, if the host knows where the car is and deliberately opens only doors with goats, then swapping the door is in the player’s interest – and the greater the number of the doors is, the higher the winning chances after swapping.
Well-informed host
Let’s start now with the classical Monty Hall case: when the host knows what’s behind the doors and only open doors with goats behind. Let’s make random selections for a lucky door and the player’s initial choice.
int luckyDoor = random.Next(0, numberOfDoors);
int doorSelectedByPlayer = random.Next(0, numberOfDoors);
Now, we should make a selection for the host, shouldn’t we? Well, actually we don’t need to. He has not so much freedom to make a selection, and even when he has a choice, nothing really depends on it. If the player didn’t pick up a door with the car behind it, then the host will have to open all the remaining doors with goats, leaving unopened the door with the car. In this case, swapping our first choice will make the player a winner. But, if the player had luck in his first attempt, that was his bad luck, because as we mentioned earlier, we evaluate the strategy when the player switches his initial choice; so, no matter what door(s) the host selects to open, the player will choose another door and reveal the goat. Here’s how the algorithm will look for the informed host:
if (luckyDoor == doorSelectedByPlayer)
{
return GameResult.Goat;
}
else
{
return GameResult.Car;
}
Clueless host
The case with a clueless host is somewhat more complicated, since what can happen is that the host randomly picks a door with the car behind it. Obviously, such a situation breaks the game – we are evaluating the winning chances in a situation when the host reveals the goats. So, the rules of the game with a clueless host require the game to be replayed in case the car is revealed while the host opens N-2 doors that are not selected by the player. In this case, unlike the classical Monty Hall situation, the host’s selection must be taken into account:
int luckyDoor = random.Next(0, numberOfDoors);
int doorSelectedByPlayer = random.Next(0, numberOfDoors);
int doorNotSelectedByHost = random.Next(0, numberOfDoors - 1);
if (luckyDoor == doorSelectedByPlayer)
{
return GameResult.Goat;
}
else
{
if (luckyDoor < doorSelectedByPlayer && luckyDoor != doorNotSelectedByHost ||
luckyDoor > doorSelectedByPlayer && luckyDoor != doorNotSelectedByHost + 1)
{
return GameResult.Discarded;
}
else
{
return GameResult.Car;
}
}
Let’s look closer at the code above. In case the player initially selects a door with the car, he will again end up with a goat. The situation when he first selects a door with a goat needs further examination. Instead of selecting N-2 doors to be open by the host, we simply select one of the remaining (unselected) N-1 doors not to be open. It is equivalent. The host may not open a door selected by the player, so we need to implement a "hole" in his door set that corresponds to a player’s door. The game result is discarded (and the game is replayed) when the car is behind one of the doors open by the host (i.e., luckyDoor != doorNotSelectedByHost). If the game is not discarded, then the player will become a winner after swapping his initial choice.
Notes on random number generation and threading
As much as I like to implement self-contained classes (especially in such a simple example), I had to create an instance of a Random object and use it in classes that implemented different host strategies (GameWithInformedHost and GameWithCluelessHost). Creating a random generator in each iteration was too slow, and resulted in less randomized data (because of repetitive use of the same seed). Sharing a single instance of the Random object between classes made the application run much faster.
Originally, I considered running simulated games in multiple threads with continuous progress report, but after testing how blazingly fast is to run such algorithms on modern machines, I concluded that multi-threading would only introduce additional code complexity without any gain in practice. Running a million games take only a few seconds, and is enough to produce results with three significant digits.
Million Monty Hall games at once
The Monty Hall application simulates any number of iterations with any number of doors. Here are the results produced with three doors and ten million iterations:
And, here are the results if the car is behind one of hundred doors:
As you can see, in the case of well-informed host, increasing the number of doors makes swapping the player’s initial choice a must: it’s all or nothing. And, if the host is clueless, the player’s chances are still 50/50.
References
- Monty Hall Problem
- 21, the movie
