Let's Make A Deal - The Monty Hall Problem In ColdFusion
Posted April 1, 2010 at 9:48 AM by Ben Nadel
Right now, I'm in the middle of reading The Drunkard's Walk: How Randomness Rules Our Lives. It's an interesting book about how mathematics, statistics, and probability can be applied to everyday situations. While the book goes over my head on some of the more in-depth math explanations, there's definitely a lot of fascinating concepts. One of the topics author Leonard Mlodinow brings up is the "Let's Make a Deal" game show. On the game show, the contestant is presented with three closed doors. One of the three doors has a prize behind it and the other two have non-prizes, such as a goat.
| | | | | |
| | | |||
| | | |
The contestant starts out by picking one of the doors. After the first door is selected, Monty Hall opens a non-prize door from one of the other two, non-selected doors. At this point, the contestant can either stand by their original door selection or, they may elect to switch their choice of doors to the only other closed door. Once the final selection is made, all doors are opened and the contestant has either picked a winning or a losing door.
As it turns out, the best strategy in this game is to always switch to the remaining door. This insight created a ton of controversy in the math world; in fact, many mathematicians refused to believe it even after they saw the winning strategy demonstrated in a computer program. This got me thinking about ColdFusion (as most things in life do) and, I thought it would be fun to try and run the simulation myself.
To simulate the Monty Hall door game, I'm going to need to generate a lot of random numbers in a very small amount of time. To be honest, I've always been a little suspect of ColdFusion's random number generator; so, rather than relying on randRange() in order to generate random values, I'm going to use remote web content. Essentially, I'm going to be grabbing all the alpha character values from a target page and then using Java's Collections class to shuffle those alpha values. Then, I'm going to use the ASCII value of each letter and the Modulus operator to generate a "random" number.
- <!---
- Grab a page of content off of the web; we are going to use the
- ascii values to help produce a random number selector (since I
- don't much care for ColdFusion's ability to pick random numbers
- in very rapid succession.
- --->
- <cfhttp
- result="get"
- method="get"
- url="http://www.supertangas.com"
- useragent="Mozilla/BenNadel.com"
- />
-
- <!---
- Extract all the letters on the page into an array; we are using
- an array so that we can then shuffle this array to get rid of
- the patterns of the English language.
- --->
- <cfset letters = reMatch( "(?i)[a-z]", get.fileContent ) />
-
- <!--- Now, let's shuffle the letters to make it more random. --->
- <cfset createObject( "java", "java.util.Collections" ).shuffle(
- letters
- ) />
-
-
- <!--- ----------------------------------------------------- --->
- <!--- ----------------------------------------------------- --->
-
-
- <!--- Keep track of the number of trials. --->
- <cfset trialCount = 0 />
-
- <!---
- Before we begin, we need to keep track of the scores of the
- relative wins of the original guess and then the mandatory
- door switch.
- --->
- <cfset originalWinCount = 0 />
- <cfset switchWinCount = 0 />
-
-
- <!--- ----------------------------------------------------- --->
- <!--- ----------------------------------------------------- --->
-
-
- <!---
- Ok, now to get onto the actual "Let's Make A Deal" trial. As
- we loop over the letters in our random array, we are going to
- do so in incremnets of two. The first letter's ASCII values
- will give us the winning door. The second letter will give us
- the original door selection.
- --->
- <cfloop
- index="letterIndex"
- from="1"
- to="#(arrayLen( letters ) - 2)#"
- step="2">
-
-
- <!--- Increment the trial count. --->
- <cfset trialCount++ />
-
- <!---
- Get the door that has the prize behind it. This is based
- on the ascii value of the current letter.
- --->
- <cfset winningDoor = (
- (asc( letters[ letterIndex ] ) mod 3) + 1
- ) />
-
- <!---
- Get the original guess of the door. This is based on the
- ascii value of the next letter.
- --->
- <cfset originalDoor = (
- (asc( letters[ letterIndex + 1 ] ) mod 3) + 1
- ) />
-
-
- <!---
- Now that we have the original guess, we have to reveal the
- door that is NEITHER the winning door NOR the door that the
- contestant originally guessed.
- --->
- <cfswitch expression="#originalDoor#-#winningDoor#">
- <cfcase value="1-1,3-3,1-3,3-1">
- <cfset goatDoor = 2 />
- </cfcase>
- <cfcase value="1-2,2-1">
- <cfset goatDoor = 3 />
- </cfcase>
- <cfcase value="2-2,2-3,3-2">
- <cfset goatDoor = 1 />
- </cfcase>
- </cfswitch>
-
-
- <!---
- Now that we have revealed the Goat door, we are going to
- have the contestant switch their guess to be the only other
- available door.
- --->
- <cfswitch expression="#originalDoor#-#goatDoor#">
- <cfcase value="1-2,2-1">
- <cfset switchDoor = 3 />
- </cfcase>
- <cfcase value="1-3,3-1">
- <cfset switchDoor = 2 />
- </cfcase>
- <cfcase value="2-3,3-2">
- <cfset switchDoor = 1 />
- </cfcase>
- </cfswitch>
-
-
- <!---
- Now that we have gotten all of our doors selected, let's
- figure out if anyone won the game.
- --->
- <cfif (winningDoor eq originalDoor)>
-
- <!--- The original guess would have won. --->
- <cfset originalWinCount++ />
-
- <cfelseif (winningDoor eq switchDoor)>
-
- <!--- The final, switch door would have won. --->
- <cfset switchWinCount++ />
-
- </cfif>
-
- </cfloop>
-
-
- <!--- ----------------------------------------------------- --->
- <!--- ----------------------------------------------------- --->
-
-
- <!--- Reset the content buffer to get rid of white space. --->
- <cfcontent type="text/html" />
-
-
- <!---
- Now that we have ran a large number of tests, let's output
- the results of the guessing strategy.
- --->
- <cfoutput>
-
- Trials: #numberFormat( trialCount, "," )#<br />
- <br />
-
- Original Door Wins: #numberFormat( originalWinCount, "," )#
- (#numberFormat( (originalWinCount / trialCount * 100), "00" )#%)
- <br />
- <br />
-
- Switch Door Wins: #numberFormat( switchWinCount, "," )#
- (#numberFormat( (switchWinCount / trialCount * 100), "00" )#%)
-
- </cfoutput>
As you can see, I loop over the collection of letters to run my trials. For each trial, I select a random winning door and a random "guess" door. Then, I reveal one of the non-prize doors. At that point, I check to see if the user would have won with their original guess or, if they would have won by switching to the other closed door. After running the code above, simulating about 70,000 trials, I get the following output:
Trials: 71,898
Original Door Wins: 23,950 (33%)
Switch Door Wins: 47,948 (67%)
While these numbers change slightly with each simulation and with different remote URLs (for character data), the percentages stay pretty much the same. So, as you can see, you have a significantly better chance of winning the Monty Hall, Let's Make A Deal game if you switch doors once one of the doors has been revealed.
I'm not going to try and tell you why this is the case as probability and statistics has never been my strong suit. But, from what I think he was saying in the book, the chances become 2-in-3 that the prize is behind the "other" door. To make the situation more understandable, Mlodinow presented a slightly different game - one with 100 doors. In this version, after you pick your original door, 98 of the closed doors are opened, leaving only one other closed door. At first, the chances that your original door was a winner was simply 1-in-100. But, after the other 98 doors were opened, the author explains that the chances of the "other" door being the winner is now 99-in-100. So, it's like the probabilities of all the opened doors get rolled into the one remaining door.
Anyway, it was just a cool problem that gave me an excuse to play around with some ColdFusion.... and that choice is always a winner!
Reader Comments
Nice read Ben. I know what's gonna be my next book. The example with 100 doors really makes sense when you think about it.
@Alain,
It's an interesting book. It really does go over my head in a number of ways; and I think it gets a bit too "mathy" at parts. But, all in all, I am enjoying it.
@Ben,
Partition the doors into two subsets: the first subset includes the door you choose, and the second subset includes all the other doors. The first subset has a one-in-three probability of winning, and the second subset has a two-in-three probability of winning.
When one of the doors is opened (and you are offered the opportunity to switch doors), you discover new information about each of the other two doors individually, but no new information about the second subset as a whole. Because one of the rules of the game is that the door you chose will not be opened, no matter which door the prize is hidden behind, you do not gain any information about the door you chose and therefore no new information about the first subset.
So you know exactly as much as you did before about the first subset as a whole, and exactly as much as you did before about the second subset as a whole. The first subset continues to have a one-in-three shot, and the second subset continues to have a one-in-three shot. But now, there is only one door in each subset. So the door you chose continues to have a one-in-three shot, while the remaining door that you did not choose now has a two-in-three shot. Remember, you gained new information about each of the doors in the second subset on an individual basis, but no new information about the second subset as a whole.
Cheers,
Justice
There is a book called "the Montey hall problem" by Jason Rosenhouse, which reviews the history of the fun mind tease, and also a LOT of math. An interesting read so far, but I got distracted and never finished.
Like the mathematicians you described, even I was skeptical and had to run this code to believe it. Pretty amazing and @Justice's post makes sense. I remember the same concept described in the movie 21 (about blackjack) but never really looked into it.
This books sounds interesting - waiting to see what else you are going to test out.
I was having a discussion with a co-worker about this exact problem last week, thanks for running the simulations to back me up!
@Justice,
Yeah, thinking in terms of sets of doors makes the logic behind this a bit more tangible.
@Joshua,
This book also has a lot of math and also a lot of history about the people who discovered all of these patterns and laws and what not. It's interesting, but gets drawn out at points.
@Eapen,
I still have not seen 21. I need to add it to my movie queue.
@Ryan,
No problem :)
A little strange view:
In this problem, finally we are end up with 2 doors, just start thinking from this point of view. And we have not told about the previous cases.
Now the chance or probabilty of winning is 1/2 either we select any of them.
Now come back to previous case.
Among the two doors we unselected, one door is a loser that means the other door can be saviour.
Now also we are not clear about why we need to select the "unselected door" (as the monty hall strategy says), let this door be called "saviour".
Now lets try to elaborate this case:
Imagine if there are 10 doors (now totally 11 doors out of which one is selected by us) in which this "saviour" door is one among them and we are told that out of this 10 doors all the other 9 doors are loosers. that means the saviour door has got lot of chance among the 10, But still at this moment of time we are not sure it is a saviour or not. But still it has got lots of chance among the 10.
I think now you got a little idea about, why we accept, that solution
I am not sure whether my explanation is complicated or not. Hope it helps. thanks.
"probability and statistics has never been my strong suit". Not sure the pun was intended but that's pretty goddamn funny :-D
I believe I saw this author discuss his book on Barry Kibrick's excellent tv show. I knew the author, Leonard Mlodinow, is a physicist but I guess I'm a little surprised that depth of statistics would be necessary to prove his point(s) which I agree with.
I'm pretty sure he discussed the Let's Make a Deal scenario on his show. It's the same type of problem that genius columnist Marilyn vos Savant has written about a few time (although I'm a decade behind in my reading of the Parade magazine). These problems are tricky in part because I think it is easy to misunderstand the problem. And I had a bad statistics teacher who had such a conditional probability exam on a final and I believe his problem was not stated the way he intended and I lost a lot of points despite my contention that I answered the problem as stated.
However, Marilyn vos Savant brought up a scenario I think which had something to do with the number of boys versus girls in some (conditional) population and I could not believe what she stated was the right answer. I always wanted to go back and review that one to figure out what I didn't understand - someday I will. Conditional probability is not hard to understand and my Finite Math teacher defined and illustrated it simply, without any complicated math.
What I took away from Leonard Mlodinow is that dumb luck has everything to do with everything about us. (In my opinion, this isn't contrary to religious belief either.)
Another author I saw on Barry Kibrick's show was Dr. Jack Hokikian (The Science of Disorder). Included in his treatise was a discussion on economics. He uses as a basis the Second Law of Thermodynamics about entropy which stipulates that entropy increases in all processes irreversibly. Hmmm ... randomness and entropy tied together?
But what's happening with our economy right now doesn't seem random; it feels like a deliberate increase in entropy.
I'm not sure that this example takes such a deep understanding to figure out.
It just takes the skill to apply rigorous thinking, rather than intuition. I will assume, for the duration of this post, an at most rudimentary understanding of probability and statistics. I will then show how to take this basic understanding, apply a rigorous method of analysis to the problem, and come of up with the correct solution.
Let us conduct a thought-experiment. Suppose we set up the following scenario. We have three undifferentiated doors, behind one of which is a prize. Our contestant may choose a single door and open it, and he wins whatever (either nothing or the prize) is behind the door he opened. If we run the experiment 1,000 times, we can expect our contestant to win 333 times and to lose 667 times.
Now let us conduct a similar thought-experiment. In this thought-experiment, the scenario is as it was in the first thought-experiment, except that when the contestant chooses a door, the host of the contest opens one of the doors that the contestant did not choose and behind which the host knows there is no prize, and then the contestant opens the door he originally chose. In this scenario, he is not allowed to alter his choice. Once again, the contestant wins whatever is behind the door he opens. In this second scenario, because nothing about the doors in themselves changed, and because nothing changed about which door the contestant opens, we can once again expect our contestant to win 333 times out of 1,000.
Now let us conduct a similar thought-experiment. The scenario is again similar, except that after the host has opened his door, the contestant must open the door which he did not choose in the first round and which the host did not open. In this third scenario, we can expect the chance of the contestant winning to invert exactly, from 333 out of 1,000 to 667 out of 1,000. Because the only change in this scenario from the one before it is that the contestant opens the opposite door from the one he opened in the previous scenario, and we knew in that scenario the probability of winning with that door, we must also know the probability of winning with the opposite door, namely, that probability which makes the two of them sum to 100%.
We know from the second and third thought-experiments that the probability of winning, if the contestant remains with the first door, will remain at 333 out of 1,000. Correspondingly, the probability of winning, if the contestant switches door, rises to 667 out of 1,000.
The process I just went through above is the process of altering a single variable, or a single property of the system, at a time. By applying this process, I can analyze rigorously what otherwise seems to be quite an intractable problem.
Cheers,
Justice
That was an excellent post, Justice, as you illustrate our particular (conditional probability) problem in a simple elegant way that anyone can understand.
I think the first issue with these problems is in recognizing that a particular "problem" is a classic conditional probability problem. And I believe many think they are creating (or posing) a certain kind of conditional probably problem when they actually are not which leads to great confusion. Let me expain, and I'll follow your lead.
Let's alter the Monty Hall problem so the contestant (Fred) is competing with another contestant (Julie) for the prize behind one of the three doors. Fred decides to himself that he will pick door 1. Julie goes first and picks door 3 but gets the goat. Should Fred change his mind based on Julie's bad pick? It doesn't make any difference as both door 1 and door 2 now both have a 50% probably of having the prize. While the probabilities have changed, it's not what I think is the classic conditional probability problem.
So just because one knows some additional information, it must be clear how that information came about. Are you receiving what is effectively a tip, or just getting access to some information randomly? Many times when it's not stated, I think the default answer should be that the information gained is random even though the problem might not be useful depending on the particular information gained; for example, Julie picked first and won.
Key words: random, randomness
@Gary,
Yeah, Mlodinow definitely says that randomness plays a huge part in the outcome of things. In the final chapter of the book he makes a really good point - while there is so much about this that we cannot control, there is something we can control: the number of times we try something.
From this, he says that to increase your chances of success, you should double your failure rate; meaning, do whatever you are doing a LOT more and you might fail most of the time, but chances are, eventually you'll succeed by random chance.
The inventor of the Dyson vacuum cleaner takes a somewhat related approach. I was told that he spends the first 15 minutes of each day doing something that he knows he will fail at. Of course, I think this is less about random chance and more about freeing yourself mentally to not be afraid of failing (such that you may not have to the ability to innovate / think outside the box).
Anyway, just interesting the way you can use "Failure" as a tool for success in general.
@Gary,
Gary: Thank you for the wonderful comments about my show. Barry Kibrick
