You might have noticed that blogging has been a bit erratic lately, and I have fallen off my usual pace of updating every weekday. There’s a reason for that! Regular readers of this blog are aware that I have a small obsession with the Monty Hall problem. I managed to convince Oxford University Press that a book on the subject would be a good idea, and now I’m supposed to submit a manuscript to them by New Year’s. And since there is a limit to how many hours a day I can spend typing away at a computer, well, you get the idea.
I’ve also learned something else lately. Writing a book is hard! I always pictured it as just writing a long essay, and since I write long essays at this blog all the time, usually just making it up as I go along, I figured writing a book would be just like that, only more so. But it turns out you actually have to do reasearch in writing a book. That means not just obtaining copies of lots of obscure journal articles but also reading them! I even had to learn how to use a microfilm machine again (The New York Times had an informative front page story on the MHP back in 1991). They’ve gotten more sophisticated since the last time I used one back in high school.
And every time I think I’ve gotten all my references together, I discover a treasure trove of other references I need to go through. For example, the Monty Hall problem was living a parallel life in the technical literature in the form of something called the three prisoners problem. Suddenly all the time I spent typing “Monty Hall problem,” “game show problem,” “cars and goats,” and every other string I could think of into various search engines wasn’t good enough.
But maybe I should start at the beginning.
Chapter One of the book describes the history of the MHP. I originally envisioned this as a short little romp, but it currently stands at around ten thousand words and it is not finished yet. Here’s the super condensed version.
It is typically Blaise Pascal who is given credit for founding the modern theory of probability. In correspondence with Pierre de Fermat in the seventeenth century, the two hashed out the “Problem of Points”. Imagine that two players, A and B, are involved in the following game. A coin is tossed. If it comes up heads then A gets a point. If it comes up tails then B gets a point. The winner is the first to get to ten points, and the prize is a pool of money to which both players contributed equally. Let us suppose the action is interrupted at a moment when the score stands 8 to 7 in A’s favor. How should the prize money be distributed between the players?
Of course, this is not strictly speaking a problem in mathematics. Some standard of fair play will have to be used in judging the equity of a proposed solution, and math has little light to shed on what that standard ought to be. Nonetheless, if we simply assume that people know a fair division when they see one, we can still hope to arrive at a definitive answer.
Fermat got the ball rolling by pointing out that if A needs x points to win and B needs y points to win, then the game will be over in no more than x+y-1 further tosses. Since these tosses can come in 2x+y-1 equally likely ways, a fair division can be reached by counting up the number in which A wins and the number in which B wins. The money should then be divided in accordance with this ratio.
For instance, in the concrete example given above we have that A needs two more points and B needs three more points to win. The game will consequently end in no more than four more tosses, which can come up in 16 different ways. Since 11 of those ways lead to A victories, while 5 of those ways lead to B victories, the money should be divided up in the ratio 11:5.
Pascal agreed that this was a fine way of doing things, but observed that it quickly becomes unwieldy to write out all the possible scenarios. He developed some counting techniques based on his famous arithmetical triangle that provide a general method for working out problems of this sort.
By reasoning in this way, Pascal and Fermat realized some very important points that had eluded previous proposed solutions to this problem. They realized that what is important is not so much the current score, but rather how many further points were needed for each player to win. They realized the significance of the fact that all future outcomes were equally likely. And they, especially Pascal, recognized the importance of elementary combinatorics in solving these sorts of problems. Elementary considerations by modern standards, but several other mathematicians failed to realize their significance.
Pascal actually made another contribution to probability theory. I refer, of course, to Pascal’s wager. Pascal’s argument here was considerably more subtle than is sometimes presented (for example, he was not making an argument for the existence of God, but rather an argument for why one ought to behave as if there were a God), but for all of that was still unpersuasive. For our purposes the significance of the wager was that it represents the first time that probabilistic considerations were invoked in the context of making a decision in the face of uncertainty.
Enumerating sample spaces, recognizing equally likely scenarios, using probability as a guide to making decisions under uncertainty. The Monty Hall problem in a nutshell.
Of course, in crediting Pascal with founding modern probability, I don’t mean to slight the considerable achievments of other folks like Huygens and Liebniz. I am merely following the example of Ian Hacking, who wrote, in his book The Emergence of Probability:
Probability has two aspects. It is connected with the degree of belief warranted by evidence, and it is connected with the tendency, displayed by some chance devices, to produce stable relative frequencies. Neither of these aspects was self-consciously and deliberately apprehended by any substantial body of thinkers before the time of Pascal.
The next significant development would surely be the work of Thomas Bayes, of “Bayes’ Theorem” fame. He developed the most comprehensive solution up to that time to the problem of revising a probability assessment in the face of new data, and his theorem is of singular importance to solving certain versions of the Monty Hall problem. Nonetheless, in he interest of keeping this post to some sort of reasonable length, we will skip over it.
The first occurrence of a Monty Hall like problem of which I am aware came in 1889. In that year the French mathematician Joseph Bertrand published his book Calcul de Probabilites. On page one of this book he discusses the idea that a probability is the ratio of favorable occurrences to possible ooutcomes. On page two (literally!) he pondered a chest of three drawers, one of which contained two gold coins (literally “medallions” in the original text), one of which contained two silver coins, and one of which contained one gold and one silver. If we pick a drawer at random what is the probability that the drawer contains different coins? Obviously, the answer is one out of three.
But now suppose we pick a drawer at random and remove a coin. We do not look at it. What is the probability now that the drawer contains different coins? We might reason that regardless of whether the coin in our hand is gold or silver, there are still only two possibilities. The other coin is either the same or it is different. Thus, it would seem the probability is now 1/2.
Surely an absurd result. Our probability jumps from 1/3 to 1/2 just because we removed a coin? Ridiculous! Bertrand went on to explain what went wrong, that the two possibilities (same kind of coin, different kind of coin) were not equally likely. For example, if the coin in your hand is gold, then you might have reached into either the two golds drawer or the one gold one silver drawer, but it is more likely that you did the former than the latter. This was intended as a cautionary tale in what happens when you are too cavlier in listing your possible outcomes, without giving due consideration to the likelihood of each one.
This is nowadays described as the Bertrand Box Paradox, though what modern probability texts describe by that name is actually a bit different from what Bertrand wrote. Nowadays we usually ask, “Assuming that you reach into the drawer and pull out a gold coin, what is the probability that the other coin in the drawer is gold as well?” You want to say 1/2, because the silver/silver drawer has been eliminated and the remaining options are equally likely. But the correct answer is 2/3, because you are twice as likely to remove a gold coin from the gold/gold drawer as you are from the gold/silver drawer.
The relationship to the Monty Hall problem is clear. In both cases a counter intuitive result is obtained because in updating the probability of X in the face of new data Y, people tend to ignore the importance of assessing the probability of obtaining Y under the assumption of X.
We fast forward now to 1959. Martin Gardner, writing in Scientific American, asks us to consider the plight of three prisoners. One is to be freed, the others are to be executed. Each is equally likely to be the one freed. A asks the warden to tell him the name of one of the other prisoners who will be executed. The warden reasons that this information can’t possibly be of any use to A, so he says, “B will be executed.” A chuckles, Since it is now between himself and C to see who will be freed, his chances of survival have gone from 1/3 to 1/2. Has A reasoned correctly?
No, he hasn’t. This, now, is the Monty Hall problem in all but name. Gardner gave the correct solution, that A still has a mere 1/3 chance of being freed while C’s chances have now improved to 2/3, in the following issue. By doing so, he kicked off a steady trickle of professional papers discussing the glories of the three prisoner problem. In a small 1965 book called Fifty Challenging Problems in Probability and Their Solutions, the Harvard mathematician Fred Mosteller included the prisoner problem as number 13. Foreshdowing the Monty Hall wars to come, Mosteller commented that this problem more than any other attracted lots of mail wherever it was published. Throughout the seventies and eighties various technical papers appeared from mathematicians, philosophers and cognitive scientists discussing various aspects of the problem.
The game show Let’s Make a Deal premiered on American television in 1963, but it was not until 1975 that the phrase “Monty Hall problem” appears in print. A statistician named Steve Selvin published a letter to the editor about in The American Statistician, presenting the correct solution via an enumeration of the sample space. Predictably, many angry letters ensued claiming the solution was wrong. Selvin’s lucid analysis made short work of the critics. Had more mathematicians been aware of it, some later embarrassment could have been avoided.
Then came l’affaire Parade. Marily vos Savant tackled the question in 1990 when it was posed by a curious correspondent. She gave the correct answer that the contestant doubles his chances of winning by switching. Over the next few months some ten thousand letters would come in, many from professional mathematicians boasting of their credentials in the subject, lecturing her in snotty, condescending tones, about how she had gotten things wrong. Overall, vos Savant estimated that over ninety percent of the letters disagreed with her solution.
vos Savant devoted three subsequent columns to the problem. Things were later adjudicated in her favor when classrooms across the country did a simulation of the problem, thereby generating huge quantities of data to look at. (In math jargon we would say they used a Monte Carlo simulation to tackle the problem). The empirical data was unambiguous, and Marilyn was completely vindicated.
The whole spectacle reached the height of journalistic importance, page one of the Sunday New York Times, on June 21, 1991.
Thoughout the nineties and even into the current century, various professionals started turning out a stream of technical articles on the subject. Mathematicians and statisticians discussed the probabilistic issues. Philosophers found relationships between the Monty Hall problem and other philosophical questions such as the famous Doomsday Argument. Physicists developed quantum mechanical versions of the problem. And cognitive scientists and social psychologists undertook some studeis to figure out why people find this problem so darned confusing.
Cognitive scientist Massimo PIatelli-Palmarini aptly described the situation by writing, “…no other statistical puzzle comes so close to fooling all the people all the time…The phenomenon is particularly interesting precisely because of its specificity, its reproducibility, and its immunity to higher education.”
So there you go. Just a taste of what you will find in the book. Assuming I manage to finish it before driving myself crazy!