The Monty Hall problem is named for its similarity to the Let’s Make a Deal television game show hosted by Monty Hall. Here’s the problem….
Let’s say you’re on the show. You’re given the choice of three doors: Behind one door is a shiny new car!; behind the other 2 doors are goats (which you don’t want!). 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 switch and instead pick door No. 2?”
What should you do? Should you stick with your original choice of door No. 1, or should you switch to door No. 2?
LOCK THE GATES!
But first let me tell you that the last part of this post (about SUSPICIONS) is really interesting. So now we begin for real…
I Recently ran across the “Monty Hall problem.” It’s a famous problem dealing with probabilities. If you google “Monty Hall problem” you will get over 500K hits. This is certainly an indication of something! Anyway, there’s a fair chance you’ve stumbled across it. And you may have even studied it and if so your interest in the rest of this post has (I hope) been piqued. Personally, I have run across it a handful of times but never paid it much attention. However, this last time I stumbled on it I spent some time studying the problem and thought that a “Monty Hall” simulation program in C# would be fun and interesting and there may even be something to learn from the exercise. It would a make a good recreational programming activity for a variety of reasons:
The problem is similar to the prior programming exercises in that it is conceptually straightforward and simple.
The UI fits on one screen (Window). It’s axiomatic that the most interesting programs have a UI that fits on one screen; even if it’s dense.
Before going further, you may want to watch the “Monty Hall problem” video on the Khan Academy web site. It’s good. And oh!! At about the 2 minute mark, when the video says “Pause the video now and I encourage you to think about it….” go ahead and pause the video and come back here and continue reading.
Oh good! You’re back. Below is a screen print from the Monty Hall Problem simulator program. As you can see it’s pretty simple. Here’s a description of its very simple UI:
Number Of Doors – In the Let’s Make A Deal game show there’s only 3 doors. However, this program has been “generalized” so that we can specify any number of doors.
Change Doors – When you run the simulation you can specify whether the contestant will change doors when given the chance or whether they will stick with their 1st choice.
Show Stats Only – When the simulation is run for more that a few hundred iterations it doesn’t really make sense to show the details of each iteration in the log. So if Show Stats Only is checked then only summary statistics are shown in the log. E.g., if we run the program for 10,000,000 iterations the summary stats are meaningful but the details are essentially useless.
Iterations – Here we specify how many times to run the simulation. On your PC you can probably expect about 5 million iterations per second when not showing details (when Show Stats Only is checked). I’m constantly amazed at how fast PCs are these days.
Go Button – Self explanatory.
Log – Where we print the details and/or summary statistics.
The above screen print is an example of what we might see for 10,000,000 iterations where we show the summary stats only for 3 doors and the contestant changes doors.
The following is a screen print for 100 iterations but we show the details for each iteration. And it’s for 4 doors and the contestant changes doors.
There was a need to be able to test/verify the simulations for many different number of doors. To do that I needed to find or come up with a “formula” calculating the probabilities for n Doors and then compare the simulation stats with the formula’s results. After an hour or so of trying to find a formula I decided to devote some time to arrive at one myself. Here’s the formula I arrived at for the probability of success (for when the contestant changes (switches) doors randomly):
( (#Doors – 1 ) / #Doors ) * ( 1 / (#Doors – 1 – 1) )
( (D – 1) / D ) * ( 1 / (D – 2) )
For 3 doors ( (2/3) * (1/1) ) == 2/3 == .66666
For 4 doors ( (3 / 4) * (1 / 2) ) == 3/8 == .375 and so on
I have not seen the above formula anywhere but I suspected others had come up with it before.
MORE ON MY SUSPICION LATER!
BUT FIRST… Here’s how formula works….
D == number of doors
If you will always switch doors, then in order to win you need to do 2 things, each of which has its own probability.
FIRST, your initial choice must be a non-prize door. Since there is only 1 prize door then
the odds of initially choosing a non-prize door == (D-1) / D
Let’s call this probability P1.
SECOND, of the doors you did NOT choose, Monty will show you 1 of them without the prize. That means that the SECOND thing you must do is switch to (choose) one of the (D – 2) remaining doors (-1 door for your initial choice PLUS -1 door for the non-prize door that Monty just showed you).
The odds of picking the PrizeDoor from one of those remaining doors is 1 / (D-2).
Lets call this probability P2.
The odds of winning is the odds of being able to do BOTH things and those odds are
P1 * P2 which is ( (D – 1) / D ) * ( 1 / (D ・ 2) )
Here is a simple chart that helped me to visualize the situation (the order does not really matter).
C P S X X … X
C is our initial choice
P is the prize door
S is the non-prize door that Monty shows us
X is the remaining non-prize doors
Developing this Monty Hall Simulator was fun and easy (no unforeseen difficulties). As it turned out, coming up with the formula was much more interesting. And btw, the simulated results did indeed match the formula (but we knew it would). But we’re not done yet!
MORE ON MY SUSPICION NOW!
The formula I arrived at (above) is
((D-1) / D ) * ( 1 / (D-2))
And as stated, I suspected that someone may have come up with this in the past. After all, with 500K google hits on “Monty Hall problem” it would seem to be likely. So off and on for a couple of days while writing this post I kept looking, using search terms like “monty hall problem generalized.” Some documents and even the Khan Academy page hinted at it but… no. But then Eureka! It had been right in front of me all along but I had missed it because it was camouflaged. Here’s a reprint of the pertinent portion from
D. L. Ferguson (1975 in a letter to Selvin cited in (Selvin 1975b)) suggests an N-door generalization of the original problem in which the host opens p losing doors and then offers the player the opportunity to switch; in this variant switching wins with probability (N−1)/[N(N−p−1)]. If the host opens even a single door, the player is better off switching, but, if the host opens only one door, the advantage approaches zero as N grows large (Granberg 1996:188). At the other extreme, if the host opens all but one losing door the advantage increases as N grows large (the probability of winning by switching approaches 1 as N grows very large).
It may not be obvious but on a hunch I discovered that, with a little arithmetic massaging, the “Ferguson formula” listed just above
(N−1)/[N(N−p−1)] for p == 1 is identical to ((D-1) / D ) * ( 1 / (D-2))
Do you see it?
Mystery solved! Done. Moving on. Oops! Wait a second. A couple of final things. First, don’t forget to finish the Khan video. And second, I forgot to mention that one does not necessarily need to write a program to simulate the Monty Hall problem. We can do it with pencil and paper and some dice, or playing cards, etc. However, to run a simulation millions or billions of times would be a little tough without a computer. Now I’m done.
OPEN THE GATES!