Implementing Monty-Hall problem
Today, I am going to write about the Monty-Hall problem simulation I ran programmatically. What is this Monty-Hall problem you may ask?
According to Wikipedia,
The Monty Hall problem is a brain teaser, in the form of a probability puzzle, loosely based on the American television game show Let's Make a Deal and named after its original host, Monty Hall. The problem was originally posed (and solved) in a letter by Steve Selvin to the American Statistician in 1975 (Selvin 1975a), (Selvin 1975b)
Let's look at the problem definition taken - again from Wikipedia,
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, 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?
Looking at the problem description what do you think? Should you switch? Or the game show host is just trying to trick you into switching? However, as depicted with Simple Solution and more formal probabilistic proof, the probability of winning is 2/3 after switching as compared to non-switching.
Let's look at the outcome of simulation in two conditions
1. The probability of winning when no switch is made
2. The probability of winning when the choice is switched
1. The probability of winning when no switch is made
First, we will generate as much real situation as possible with random function and selection of choices,
Let's maintain an array of size 3 which will be initialized with all 0 values. Every index of this array indicates either goat or a car.
Value of 0 at index i indicates the presence of goat at door i. Similarly, the value of 1 at index i indicates the presence of car at door i. For this example, there will be exactly one car in the given array and rest of the positions will be filled by a goat.
// Let's initialize it with all goats
var myDoors: [Int] = [0, 0, 0]
Next, we want to run this simulation several times. In this case, I will run this experiment 100 times to get a percentage of a win when no switch is made.
for _ in 0..<100 {
// Simulation code goes here
}
Similar to the game show, we will generate a random number between and including 0 and 2. This represents where the car will be placed. The contestant is unaware of this position, but we know the host is.
We will set the value at that index to 1 and set to 0 for rest of 2 positions.
for _ in 0..<100 {
let carPosition = Int(arc4random_uniform(3))
myDoors[carPosition] = 1
for i in 0..<3 {
if i == carPosition { continue }
myDoors[i] = 0
}
}
}
Next, we will generate another random number between the same range of 0 and 2. This number represents the choice selected by the contestant,
let selectedPosition = Int(arc4random_uniform(3))
Now, we will use this number as an index and check if the value of the array at that position is 1. Since contestant, in this case, does not switch, it's their final choice and will decide the winner,
let selectedPrize = myDoors[selectedPosition] == 1
if selectedPrize {
print("You won the game")
}
Now here's the full code and let's run it 100 times and see how many times it prints that magic text You won the game,
var myDoors: [Int] = [0, 0, 0]
for _ in 0..<100 {
let carPosition = Int(arc4random_uniform(3))
myDoors[carPosition] = 1
for _ in 0..<3 {
if i == carPosition { continue }
myDoors[i] = 0
}
let selectedPosition = Int(arc4random_uniform(3))
let selectedPrize = myDoors[selectedPosition] == 1
if selectedPrize {
print("You won the game")
}
}
After running it multiple times, it prints You won the game between 30-34 times. So on an average chance of winning a car are 1/3 when the contestant does not switch.
2. The probability of winning when the choice is switched
This is the second case when contestant make the first choice, but will switch when the host opens another door and reveals a goat behind it (Remember, the host knows which door has a car behind it so he will never open the door with the car)
Our initial code to generate a random number for car door and contestant choosing a random door remains the same,
var myDoors: [Int] = [0, 0, 0]
for _ in 0..<100 {
let carPosition = Int(arc4random_uniform(3))
myDoors[carPosition] = 1
for _ in 0..<3 {
if i == carPosition { continue }
myDoors[i] = 0
}
let selectedPosition = Int(arc4random_uniform(3))
}
Now here's the twist. After making a choice host will open another door with a goat behind it and contestant will switch the choice. Since host opens only that door with a goat behind it when switching happens contestant will win only if he has chosen the goat in the first try.
So contestant will win in case of the switch only if selectedPosition doesn't have a car behind it.
Extending above code,
if myDoors[selectedPosition] == 0 {
print("You won the game after making a switch")
}
After running it multiple times, it prints You won the game after making a switch between 58-64 times. So on an average chance of winning a car are 2/3 when the contestant makes a switch.
Thus the chances of the contestant winning a car are increased when he makes a switch in a game like this. This is non-intuitive. why would a switch make you win the game? It seems the probability is 50-50 in this case.
However, consider the game with 1000 doors with 1 door having a car and other 999 having goats behind them. When the contestant chooses one door, the host will open 998 other doors with the choice to switch or not.
Now think about the probability of choosing the car in the first try among the 1000 doors. This is 1/1000. With 998 open doors, if you do not switch the probability of winning a car is only 1/1000.
Now consider that you make a switch. There is only one case where the switch will make you lose the game. Rest 999 times you will have chosen a goat and when the host opens 998 doors (Remember again, the host knows which door has a car behind it, so he will never open that one door) and you make a switch to one unopened door, you will have won the car. That means that odd of winning a car after a switch is 999/1000.
So remember, when encountered a situation similar to Monty-Hall game show, always make a switch!
Reference: