The Monty Hall problem is a counter intuitive problem in probability mathematics that deals with picking the right prize from a set of three doors. The problem is named after the television celebrity Monty Hall and is loosely based on the USA game show Let's Make a Deal.
This has become a popular problem in programming as it is a good exercise in thinking through a problem to prove what outcome actually occurs. Lots of examples have been posted online so I thought I would sit down and attempt to solve it myself. The problem is most commonly summarised as follows (this example was taken from Rosetta Code):
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. The car and the goats were placed randomly behind the doors before the show.
The rules of the game show are as follows:
After you have chosen a door, the door remains closed for the time being. The game show host, Monty Hall, who knows what is behind the doors, now has to open one of the two remaining doors, and the door he opens must have a goat behind it. If both remaining doors have goats behind them, he chooses one randomly. After Monty Hall opens a door with a goat, he will ask you to decide whether you want to stay with your first choice or to switch to the last remaining door.
For example:
Imagine that you chose Door 1 and the host opens Door 3, which has a goat. He then asks you "Do you want to switch to Door Number 2?" Is it to your advantage to change your choice?
Note that the player may initially choose any of the three doors (not just Door 1), that the host opens a different door revealing a goat (not necessarily Door 3), and that he gives the player a second choice between the two remaining unopened doors.
Simulate at least a thousand games using three doors for each strategy and show the results in such a way as to make it easy to compare the effects of each strategy.
Rather than just post a block of code I thought I would go through the steps I took to generate the numbers of cars won using each strategy.
The first thing I needed was a place to store the results of each game. This meant creating an array so that I could store how many goats and cars were found for the switch and stick strategies.
// Set up initial game results table
$results = [
'stick' => [
'goat' => 0,
'car' => 0,
],
'switch' => [
'goat' => 0,
'car' => 0,
],
];
Before creating a loop to test lots of games I decided to create a single game of each strategy. The first thing to do is to set up the game so that there are three doors, two of which contain a goat and one contains a car. A simple array was created to store this information, and the doors were then shuffled in order to create a level of chance.
// setup the game
$doors = array_fill(1, 3, 'goat');
$doors[array_rand($doors)] = 'car';
shuffle($doors);
The first thing that the contestant does in this game is to pick a door. This is done using the array_rand() function, which returns an element key from the doors array.
// contestant picks a door
$pick = array_rand($doors);
With the first door chosen Monty Hall then needs to open one of the other doors that isn't the car. A simple loop is used to go through the doors array and pick out the first door that is a goat and also hasn't already been picked by the contestant. We simulate this by simply removing the door from the doors array.
// Monty Hall shows a door that the contestant hasn't picked and contains a goat.
foreach ($doors as $id => $door) {
if ($door == 'goat' && $id != $pick) {
unset($doors[$id]); break;
}
}
Now we come to the part where the contestant either elects to stick with the door they have chosen or picks the other door, which is where the results array comes in. As the results array has the same keys as the values of the doors array we just select the door element using the contestants choice and increment the count in the results array. We can do both of these strategies during the same game, but the stick strategy must be done first. Recording the result of the stick strategy is simple.
// stick with the same door
$results['stick'][$doors[$pick]]++;
The switch strategy is slightly different. We know that we want to select the other element in the doors array (remember we removed one earlier on) but we can't be sure what the key of that element is. We therefore need to loop through the doors array and pick the element that has a different key to the current contestant selection. The selection is then stored in the results array.
// switch to another door
foreach ($doors as $id => $door) {
if ($id != $pick) {
$pick = $id; break;
}
}
$results['switch'][$doors[$pick]]++;
What we have done so far is simulate a single game and recorded the result of what happens with each strategy. The next step here is to create a simple loop that runs the games 1 million times. A sufficiently large number of games is needed to increase the accuracy of the results that we get out of the end. Here is the steps detailed above contained within a loop.
// Double iterations as strategies are done separately.
$iterations = 1000000;
for ($i = 0; $i < $iterations; ++$i) {
// setup the game
$doors = array_fill(1, 3, 'goat');
$doors[array_rand($doors)] = 'car';
shuffle($doors);
// contestant picks a door
$pick = array_rand($doors);
// Monty Hall shows a door that the contestant hasn't picked and contains a goat.
foreach ($doors as $id => $door) {
if ($door == 'goat' && $id != $pick) {
unset($doors[$id]);
break;
}
}
// stick with the same door
$results['stick'][$doors[$pick]]++;
// switch to another door
foreach ($doors as $id => $door) {
if ($id != $pick) {
$pick = $id;
break;
}
}
$results['switch'][$doors[$pick]]++;
}
After running the games a million times we can now work out how each strategy compares. This involves a simple percentage calculation for both the stick and the switch strategies.
// print results
$string = '';
$string .= 'Stick: ' . ($results['stick']['car'] / $iterations) * 100 . '%' . PHP_EOL;
$string .= 'Switch: ' . ($results['switch']['car'] / $iterations) * 100 . '%' . PHP_EOL;
print $string;
This prints the following:
Stick: 33.3427%
Switch: 66.6573%
So we can see here that the best strategy is to switch doors, which confirms the result of the probability calculations. If you haven't already found out then the answer to the Monty Hall problem is to always switch doors as there is a 33% greater chance of getting the car.
One thing that is missing here is the need to show the results in a way that makes it very clear which strategy is the best. To do this I used the same percentage calculations that I had run before but passed them through a str_repeat() function so that the percentages for each strategy were represented by a line of stars. A nested loop was used in order to print the results of the number of goats and the number of cars found for each strategy.
$string = '';
foreach ($results as $strategy => $result) {
$string .= PHP_EOL . $strategy . PHP_EOL;
foreach ($result as $prize => $numbers) {
$string .= $prize . "\t" . str_repeat('*', ($numbers / $iterations) * 100) . PHP_EOL;
}
}
print $string;
This prints out the following:
stick
goat ******************************************************************
car *********************************
switch
goat *********************************
car ******************************************************************
This simple graph makes it very clear how much more successful the switching strategy is to the sticking strategy. I'm sure this code can be improved slightly by abstracting certain parts of repeating functionality, but I just wanted to keep things simple and generate the correct result. During my research into the Monty Hall problem I also found that many people were experimenting with the number of doors present in the problem, and often leaving the user with two doors to chose from in the end. The number of doors can easily be changed by altering the initial array_fill() function call and setting the second parameter to something larger but more work would be needed to remove everything but the contestants current door and the one with the car behind it. I haven't looked into how this effects the outcome of the situation, but I leave this as an exercise for the user.
Rather than piece this code together here is the code above in full. Feel free to play around with it.
// Set up initial game results table
$results = [
'stick' => [
'goat' => 0,
'car' => 0,
],
'switch' => [
'goat' => 0,
'car' => 0,
],
];
$iterations = 1000000;
for ($i = 0; $i < $iterations; ++$i) {
// setup the game
$doors = array_fill(1, 3, 'goat');
$doors[array_rand($doors)] = 'car';
shuffle($doors);
// contestant picks a door
$pick = array_rand($doors);
// Monty Hall shows a door that the contestant hasn't picked and contains a goat.
foreach ($doors as $id => $door) {
if ($door == 'goat' && $id != $pick) {
unset($doors[$id]);
break;
}
}
// stick with the same door
$results['stick'][$doors[$pick]]++;
// switch to another door
foreach ($doors as $id => $door) {
if ($id != $pick) {
$pick = $id; break;
}
}
$results['switch'][$doors[$pick]]++;
}
// print results
$string = '';
$string .= 'Stick: ' . ($results['stick']['car'] / $iterations) * 100 . '%' . PHP_EOL;
$string .= 'Switch: ' . ($results['switch']['car'] / $iterations) * 100 . '%' . PHP_EOL;
foreach ($results as $strategy => $result) {
$string .= PHP_EOL . $strategy . PHP_EOL;
foreach ($result as $prize => $numbers) {
$string .= $prize . "\t" . str_repeat('*', ($numbers / $iterations) * 100) . PHP_EOL;
}
}
print $string;
Add new comment