Monte Carlo is a conceptually simple but powerful technique that is widely used. It makes use of randomness to answer questions.
In this post, I'll explain how to solve the Monty Hall problem using the Monte Carlo method. The implementation is in python, a programming language whose name is in itself a tribute to the British Comedy Group - Monty Python.
Monty Hall Problem
The first time I was introduced to the Monty Hall problem was in the movie - 21. This clip showcases the problem.
There are explanations for the same by Michael David Stevens of Vsauce and Vox.
Let's jump into the problem - Imagine, you have three doors in front of you.
The game show host asks you to choose one of the doors. If you choose the correct door then you win a car otherwise you get a goat.
Let's say you chose Door No. 1
The game show host who knows what is behind each door, opens Door no. 3 and reveals a goat.
The game show host then gives you two options
- Stick with Door no. 1
- Switch to Door no. 2
Which one would you choose?
It might seem there is 50/50 probability but its not!
Monte Carlo Experiments
The definition of Monte Carlo Experiments according to Wikipedia
"Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be deterministic in principle."
It means that you can simulate an experiment, any number of times based on some condition or conditions, and then analyse the results of the simulation to arrive at a solution.
In the movie Avengers: Infinity War, Doctor Strange performs nearly 14 million simulations of the future to determine how many of the future outcomes, do the avengers win? Essentially, he is applying the principles of Monte Carlo experiments.
Simulating Monty Hall with Monte Carlo
Imagine the game described previously is stuck in a loop like Bill Murray in the movie - Groundhog Day.
Each time the game occurs, we record the success and failure on sticking with the first selected door and also switching to the new door.
Let's say that the game has been conducted 100 times. We'll check in how many of those 100 games, the car was won by not switching the door and switching the door.
By looking at these ratios, we'll know which option increases the chance of success.
Codifying Monty Hall and Monte Carlo
Lets define a function that simulates the Monty Hall Problem
def monty_hall():
...Within the function, create the three doors with the car randomly allocated to one of the doors. The value "1" in the list represents the car
doors = [0, 1, 0]
shuffle(doors)The player chooses a door to open. The value 0,1 and 2 represent the indexes of the list variable "doors"
door_selected = choice([0, 1, 2])
The game show host now opens a door that does not have the car behind it
non_car_doors = list()
for i,d in enumerate(doors):
if d == 0 and i != door_selected: non_car_doors.append(i)
door_opened = choice(non_car_doors)Now, evaluate the following two choices
1. Wins a car by sticking onto the initial selection
non_switch_success = True if doors[door_selected] == 1 else False
2. Wins a car by switching to the remaining door
remaining_door = set([0,1,2]).difference([door_selected, door_opened])
remaining_door = remaining_door.pop()
switch_success = True if doors[remaining_door] == 1 else FalseFinally, return the success for each of the choices
return non_switch_success, switch_success
Define the Monte Carlo function that takes a single argument "n" that represents the number of simulations to run. Run the Monte Hall simulation for the "n" number of times and return the success distribution for each of the choices.
def monte_carlo(n):
non_switch_success_count = 0
switch_success_count = 0
for i in range(n):
ns, ss = monty_hall()
non_switch_success_count += ns
switch_success_count += ss
print(f"Number of plays: {n}")
print(f"Number of success on switch: {switch_success_count}
{(switch_success_count/n)*100}%")
print(f"Number of success on non-switch: {non_switch_success_count}
{(non_switch_success_count/n)*100}%")The full code can be found below and how to run it in the header comments.
#!/usr/bin/env python
#title :Monty Hall with Monte Carlo
#description :This script uses Monte Carlo simulation on Monty Hall problem
# to determine the answer to the Monty Hall problem
#author : Samir Madhavan
#website : https://www.samirmadhavan.com
#date :20190817
#version :0.1
#usage :python monty_monte.py 10000
#python_version : >=3.6
#==============================================================================
from random import shuffle, choice
from sys import argv
def monty_hall():
# Create the doors with random allocation of the car i.e 1
doors = [0, 1, 0]
shuffle(doors)
# Choose a door among the three
door_selected = choice([0, 1, 2])
# Open the door that does not have the car
non_car_doors = list()
for i,d in enumerate(doors):
if d == 0 and i != door_selected: non_car_doors.append(i)
door_opened = choice(non_car_doors)
# Success if the player does not switch
non_switch_success = True if doors[door_selected] == 1 else False
# Success if the player switches
remaining_door = set([0,1,2]).difference([door_selected, door_opened])
remaining_door = remaining_door.pop()
switch_success = True if doors[remaining_door] == 1 else False
return non_switch_success, switch_success
def monte_carlo(n):
non_switch_success_count = 0
switch_success_count = 0
for i in range(n):
ns, ss = monty_hall()
non_switch_success_count += ns
switch_success_count += ss
print(f"Number of plays: {n}")
print(f"Number of success on switch: {switch_success_count} {(switch_success_count/n)*100}%")
print(f"Number of success on non-switch: {non_switch_success_count} {(non_switch_success_count/n)*100}%")
N = int(argv[1])
monte_carlo(N)Running the simulation
Let's simulate 100 games
╰─$ ./main.py 100
Number of plays: 100
Number of success on switch: 71 71.0%
Number of success on non-switch: 29 28.999999999999996%
We can see that there is a higher success in switching.
Let's run it again
╰─$ ./main.py 100
Number of plays: 100
Number of success on switch: 62 62.0%
Number of success on non-switch: 38 38.0%
We can still see that there is a higher success with switching but the success percentages vary a lot.
Let's run the same simulation for 1 million games and let's do it 3 times to see if the success percentages vary a lot.
╰─$ ./main.py 1000000
Number of plays: 1000000
Number of success on switch: 666566 66.6566%
Number of success on non-switch: 333434 33.3434%
╰─$ ./main.py 1000000
Number of plays: 1000000
Number of success on switch: 666588 66.6588%
Number of success on non-switch: 333412 33.3412%
╰─$ ./main.py 1000000
Number of plays: 1000000
Number of success on switch: 666628 66.6628%
Number of success on non-switch: 333372 33.3372%
We can see that the success percentages don't vary much and it tells us that if we make the switch then the chances of winning are 2 out of 3 times.
Make the switch!
Conclusion
The motivation of this post was to introduce the Monte Carlo method and applying it to a problem that is easy to understand and interesting for someone new to this. The Monte Carlo method might look simple conceptually but it is a powerful method that is heavily used in the Financial Industry, Reinforcement Learning, Physical Sciences, Computational Biology etc to name a few.