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 using the . The implementation is in python, a programming language whose name is in itself a tribute to the British Comedy Group - Monty Hall problem Monte Carlo method 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 and . Michael David Stevens of Vsauce 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 W ikipedia " 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 = [ , , ]
shuffle(doors) 0 1 0 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() i,d enumerate(doors): d == i != door_selected: non_car_doors.append(i)

door_opened = choice(non_car_doors) for in if 0 and Now, evaluate the following two choices 1. Wins a car by sticking onto the initial selection non_switch_success = doors[door_selected] == True if 1 else False 2. Wins a car by switching to the remaining door remaining_door = set([ , , ]).difference([door_selected, door_opened])
remaining_door = remaining_door.pop()
switch_success = doors[remaining_door] == 0 1 2 True if 1 else False Finally, return the success for each of the choices non_switch_success, switch_success return 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. non_switch_success_count = switch_success_count = i range(n):
        ns, ss = monty_hall()
        non_switch_success_count += ns
        switch_success_count += ss

    print( )
    print( )
    print( ) : def monte_carlo (n) 0 0 for in f"Number of plays: " {n} f"Number of success on switch: %" {switch_success_count} {(switch_success_count/n)* } 100 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. https://gist.github.com/samzer/3a8a10d4046d87d2b1a4330b597dbeb random shuffle, choice sys argv doors = [ , , ]
    shuffle(doors) door_selected = choice([ , , ]) non_car_doors = list() i,d enumerate(doors): d == i != door_selected: non_car_doors.append(i)

    door_opened = choice(non_car_doors) non_switch_success = doors[door_selected] == remaining_door = set([ , , ]).difference([door_selected, door_opened])
    remaining_door = remaining_door.pop()
    switch_success = doors[remaining_door] == non_switch_success, switch_success non_switch_success_count = switch_success_count = i range(n):
        ns, ss = monty_hall()
        non_switch_success_count += ns
        switch_success_count += ss

    print( )
    print( )
    print( )

N = int(argv[ ])
monte_carlo(N) #!/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 import from import : def monty_hall () # Create the doors with random allocation of the car i.e 1 0 1 0 # Choose a door among the three 0 1 2 # Open the door that does not have the car for in if 0 and # Success if the player does not switch True if 1 else False # Success if the player switches 0 1 2 True if 1 else False return : def monte_carlo (n) 0 0 for in f"Number of plays: " {n} f"Number of success on switch: %" {switch_success_count} {(switch_success_count/n)* } 100 f"Number of success on non-switch: %" {non_switch_success_count} {(non_switch_success_count/n)* } 100 1 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.

Too Long; Didn't Read

Making security fun one episode at a time

Answering The Famous Monty Hall Puzzle with the Monte Carlo Technique

Too Long; Didn't Read

Samir Madhavan

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

Answering The Famous Monty Hall Puzzle with the Monte Carlo Technique

Too Long; Didn't Read

Samir Madhavan

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES