Posts Tagged ‘math’

Monty Python Hall: A Monty Hall simulator in Python

March 25th, 2019


Public domain illustration from Wikipedia
 

The infamous Monty Hall problem goes something like this: Monty Hall, the host of TV game show “Let’s Make A Deal” shows a contestant three doors. Behind one door is a new car. If the contestant picks that door, they win the car.

The other two doors have a goat behind them, which are not prizes. I guess this puzzle falls apart if you for some reason find a goat more valuable than a car. Anyway, point is the door with the car behind it is the prize.

Once the contestant picks a door, the host Mr. Hall opens a second door to reveal a goat. Now Mr. Hall asks the contestant to select one of two options:

  1. Stay with the original door they picked
  2. Switch to a different door (the one remaining door that is not open)

Here’s where most of us get tripped up: it shouldn’t matter, right? There are only two remaining doors, one has a car behind it and the other a goat. Why does it matter if you stay or switch doors?
 

What’s going on?

As it turns out the odds in this situation are counterintuitively not 50%. When the contestant initially selected a door the odds they selected the prize door were one out of three. But this changes once Mr. Hall opens a door to reveal a goat using his prior knowledge. We know Mr. Hall will never open a door with a car behind it, and he will never open the same door the contestant initially selected.

The contestant’s initial choice remains fixed in time: one out of three. Now that a door revealing a goat has been opened the initial choice is still one out of three. But if the contestant switches doors, something unexpected happens — their new choice has a two out of three chance of winning.

If this problem sounds familiar you probably heard about it in Parade magazine back in the 90′s when columnist Marilyn vos Savant spent years covering this problem. It’s also been tested on Mythbusters. For a quick explanation check out AsapSCIENCE’s video on YouTube.
 

Another approach

Like many people, I often find probability mathematics baffling — and the Monty Hall problem is no exception.

When I was a kid I remember visiting The Exploratorium here in San Francisco and coming across a simple computer exhibit that simulated dice rolls. I’d never considered before that when you roll one six sided die the probability of landing on each side is equal, but when you roll two dice and add the numbers together, the probability of rolling any number between two and twelve are not equal. There’s only one way to roll a two or a twelve, but plenty of ways of getting, for example, an eight.

The exhibit drew a graph of the number of times it simulated a two-dice roll, with a bar for each possible outcome. After some number of rolls it always looked like a hill with most of the rolls in the middle range and fewer at the higher and lower numbers.

Since I was learning to program at the time, this idea of taking a mathematical problem and breaking it down into a computer simulation really appealed to me. In fact when I got home I wrote my own version of the dice roll simulator in QBasic. In only an hour or two I managed to put together a working dice roll simulator complete with a bar graph, just like the exhibit at The Exploratorium.

A computer simulation isn’t a mathematical proof of course, but it’s a good sanity check to validate a hypothesis.

Thinking about the Monty Hall problem again recently I thought I’d take that approach I’d learned as a kid and write a simple program to simulate it and tally up the results.
 

Monty Hall problem in Python

As a software engineer I mostly work in Python these days. It’s a fairly easy to understand language so I thought it’d be perfect for simulating the Monty Hall problem. That’s how I came up with “Monty Python Hall,” a Monty Hall problem simulator in Python. The idea is to run the Monty Hall three door problem any number of times and tally up the results at the end.

Once you’ve installed a Python interpreter on your system you can try out my Monty Hall simulator from the command line. Clone the repo, open the directory in a console and type “python run.py” and you’ll see an output like this:

Games run: 1000
Games won stayed: 351
Games won switched: 683

If you edit the source you can change the number of games run, but the result always comes out about the same: the contestant wins 2/3 of the time if they switch, and only 1/3 of the time if they stay.

I designed the program to prioritize simplicity over efficiency, so if you run it too many times it may be slower than you expect. For example look at the way the host selects a door:

while host_choice == player_choice or host_choice == car_at:
    host_choice = pick_random_door(num_doors)

This is more complex than it needs to be; the host’s choice is simulated randomly until it meets the required conditions.

Why? I think it’s more interesting to let people play around with the program, and the simpler the logic the easier it is to modify.

For example what if you change the number of doors? It needs to be at least three for the contestant and host’s choice to work. But what if there were ten doors? In my version of the program the host opens one door with a goat behind it no matter how many doors there are. But what if the host opens half the doors with goats behind them? Or all of the doors except the one that may hide a car?

My implementation of the Monty Hall simulator in Python is available under the free, open source MIT license. I encourage you to try it and modify it as you see fit.

If you find this useful in any way feel free to send me an email. I’d love to hear about it!
 

Find this project on Github