Revisiting Monty Hall
I have never truly grokked the famous Monty Hall problem and why it is true. Why does the player choosing to change the door wins two thirds of the time? While the player choosing to stay with the initial door only wins one third of the time?
I once came across the idea that to fully understand a concept, you should be able to describe it using multiple approaches. Can you describe it graphically? Can you put into an equation? Is there a canonical definition or description what you are doing? Can you describe it algorithmically?
That is what we will do with the Monty Hall problem. We will simulate the game to better understand what is happening.
There are three big closed doors. There is a prize car behind one of these doors, which the player can win if he chooses the right door. And each of the other two doors have a goat behind them.
First, Monty will place a car behind one of the doors. Next, the player chooses a door with the aim of winning the car.
import "math/rand/v2"
var r *rand.Rand = rand.New(rand.NewPCG(1, 7)) // variable r will let us choose a door randomly.
func main() {
carDoor = r.IntN(3) // Monty will choose a random door to place the car.
playerInitialDoor = r.IntN(3) // Player will choose a random door, making his first guess.
}
At this point, the game show host Monty will reveal a goat behind one of the doors. The player is then given a choice to stay with the same door or change the door.
func main() {
carDoor = r.IntN(3) // Monty will choose a random door to place the car.
playerInitialDoor = r.IntN(3) // Player will choose a random door, making his first guess.
// Monty will always show a goat, even if player chooses correct door.
// Monty won't show the car door or the players initial door.
for goatDoor == carDoor || goatDoor == playerInitialDoor {
goatDoor = r.IntN(3)
}
}
And now the main crux of the algorithm. We want to see what would happen if player switches the door.
func main() {
/// ...............
// The loop ensures that player won't choose
// the goat door again (duh), or his initial door (duh).
for playerSwitchesToDoor == goatDoor || playerSwitchesToDoor == playerInitialDoor {
playerSwitchesToDoor = r.IntN(3)
}
// If player switches to correct door.
if playerSwitchesToDoor == carDoor {
switchingWins++
}
}
So if the player wins that is great. But he might not win. Maybe his initial choice of door was the correct one, in which case staying would have won.
func main() {
/// ...............
// If player switches to correct door
if playerSwitchesToDoor == carDoor {
switchingWins++ // Increment the counter that tracks switching wins.
} else /*staying would have won */ {
stayingWins++ // Increment the counter that tracks staying wins.
}
}
And that's the crux of the game. Either switching wins or staying wins.
And now since we want to find out which strategy wins more often - either switching or staying - lets wrap the entire single run of the game into a million simulations.
const NUM_SIMULATIONS = 1000000
func main() {
for i := 0; i < NUM_SIMULATIONS; i++ {
carDoor = r.IntN(3) // Monty will choose a random door to place the car.
playerInitialDoor = r.IntN(3) // Player will choose a random door, making his first guess.
// Monty will always show a goat, even if player chooses correct door.
// He won't show the car door or the players initial door.
for goatDoor == carDoor || goatDoor == playerInitialDoor {
goatDoor = r.IntN(3)
}
// The loop ensures that player won't choose
// the goat door again (duh), or his initial door (duh).
for playerSwitchesToDoor == goatDoor || playerSwitchesToDoor == playerInitialDoor {
playerSwitchesToDoor = r.IntN(3)
}
// If player switches to correct door.
if playerSwitchesToDoor == carDoor {
switchingWins++ // Increment the counter that tracks switching wins.
} else /*staying would have won */ {
stayingWins++ // Increment the counter that tracks staying wins.
}
}
}
To clean up the main logic, I took out some of the repetitive parts into separate functions. Here is the full program.
const NUM_SIMULATIONS = 1000000
var carDoor, goatDoor, playerInitialDoor, playerSwitchesToDoor int
var switchingWins, stayingWins int
var r *rand.Rand = rand.New(rand.NewPCG(1, 7))
func main() {
for i := 0; i < NUM_SIMULATIONS; i++ {
carDoor = chooseDoor(r)
playerInitialDoor = chooseDoor(r)
goatDoor = showGoat(carDoor, playerInitialDoor)
playerSwitchesToDoor = switchDoor(playerInitialDoor, goatDoor)
if playerSwitchesToDoor == carDoor {
switchingWins++
} else /*staying would have won */ {
stayingWins++
}
}
fmt.Println("Switching wins:", switchingWins)
fmt.Println("Staying wins:", stayingWins)
}
// chooseDoor chooses a door out of 0, 1 or 2.
func chooseDoor(r *rand.Rand) int {
return r.IntN(3)
}
// showGoat will always show a goat from one of the 2 non car doors.
func showGoat(carDoor, playerInitialDoor int) (goatDoor int) {
for goatDoor == carDoor || goatDoor == playerInitialDoor {
goatDoor = chooseDoor(r)
}
return goatDoor
}
// switchDoor will switch the door to the only door left for the player.
func switchDoor(playerInitialDoor, goatDoor int) (playerSwitchesToDoor int) {
for playerSwitchesToDoor == goatDoor || playerSwitchesToDoor == playerInitialDoor {
playerSwitchesToDoor = chooseDoor(r)
}
return playerSwitchesToDoor
}
You will find that switching will win 67 percent of the time and staying will win 33 percent of the time like so.
➜ go run montyhall.go
Switching wins: 666902
Staying wins: 333098
Here is what is happening. Monty places a car somewhere. Lets say on the right side.
goat goat car
Lets try to enumerate all the places where you can land. And then choose a strategy that wins. Start by asking how many ways are there of winning by the switching strategy?
You choose the left door. Monty shows the goat in the middle door. You switch to the door on the right, as you have only one place to switch to. You win.
1.goat(initial) 2.goat(reveal) 3.car(switch and win)
You choose the door in the middle. Monty reveals the goat in the left door. You switch to the door on the right. You win.
2.goat(reveal) 1.goat(initial) 3.car(switch and win)
There are two initial places from where you can win by switching. Those two place are the goats. How many goat doors are there? There are two goat doors out of three. This is chance of winning.
In case you land on the car door in the first try. Then no matter which door you switch to, you lose. How likely is it that you land on the car door in you first try. 1/3, right? But you are switching. Whichever door you switch to, you lose.
goat goat car(initial, switch to any door but lose)
There is only one way of losing by switching. And that is by landing on the car in you first try. Staying with your initial door would have won. But the chance of landing on the car door in you first try is always 1/3.
Monty is doing you a favor by showing where one of the goats are. How likely is it that you land on a goat on you first trial? It's 2/3, since there are two goats. Just switch and win.
You can do the same analysis whether the car is on the right, middle or left. In total, there are six places from where you can win by switching while there are three places from where you can win by staying. It does not matter where the car is placed. Switching wins two thirds of the times.