The following is the story of how I challenged the conventional academic wisdom regarding a known mathematical problem, resiliently tried it out ‘for real’ in the field, and discovered that – lo and behold – science was right, and I was wrong.
The reader (you) is probably familiar with ‘The Monty Hall Problem’. Most CS curricula approach it at some point, though usually as an amusing thought provoking exercise along the lines of “most probably two people in this class share the same birthday”. If you’re not familiar with it, the Internets are full of great explanations of it; I’d personally recommend YouTube for this one. For the rest of this text, let’s assume we all know what we’re talking about: Curtains, you choose, host opens all the rest but one, they’re empty – should you switch?
My own first encounter with said paradox was some years ago, in Cecil Adams’ excellent ‘The Straight Dope’, which in turn was commenting on Marilyn vos Savant (Guinness’s highest IQ!) approach to the paradox. Quite a confusing one indeed, as both Adams and vos Savant switched around their answers several times, not the least of which due to thousands of letters (from PhD-toters, no less!) claiming *both* sides of the argument. So, assuming you know what we’re talking about by now, just to make sure we’re all on the same page – the final score is it is decidedly better to switch. This is contrary to basic logic, and indeed I myself could (and have) make what I feel would be a compelling case to the contrary.
Since both Adams and vos Savant have been (by their own admission) confounded more than once on this issue, I did not feel as bad when this issue came up in data structures class (like I said, it was more going out on a tangent than any real relevance to CS material) and I simply could not fathom why switching is the preferred strategy, assuming the host has, as usual, opened all but one of the non-selected curtains, revealing them to be empty. I took it up with the lecturer (Prof. Dorit Aharonov), but to no avail – I could not be convinced, and science, science is rarely convinced. Her last piece of advice, by way of conjecture, was to write a program that performed ‘the game’, run it a thousand times, and see for myself what the results were. Words easily spoken than done – that is, for a first-year student, who would prefer to use his theoretically spare time for, say, breathing.
A couple years went by, and personal geopolitical motions have transpired – namely, my political ban on my favorite newspaper “Haaretz” (which is a matter for another post), which left me bored for meal-time reading material. A friend recommended and loaned a pop-sci book on game theory (in Hebrew, by Chaim Shapira, who is not perfect, but can certainly bring to life relatively difficult math theories. An poor Israeli man’s Malcolm Gladwell?), and over a Shabbat lunch I found myself rereading the same belated Monty Hall story, problem and solution – when given the choice, switch. Enough is enough, I decided – it’s time to do this right. No theories, let’s take this into the field; two years too late, I was going to settle this once and for all.
Having waited two years turned out, unsurprisingly, to at least considerably shorten the difficulty of the task of writing a software program to simulate such a Monty Hall game. Not the least of which due to having learnt Python, that quasi-magical programming language which, well, lets you do anything, easily.
So, basic program is:
1. Initialize array of X doors
2. Randomly ‘choose’ one door
3. Randomly ‘place prize’ in one door
4. Randomly open all doors but chosen one, and another one (with the prize, if chosen door != prize door)
5. Check to see if user should have switched, or not.
Bottom line – having written the (very simple) code myself, and having run it a few times, I am very proud (or rather, disappointed) to have discovered that indeed, the preferred strategy is simply to switch. Playing around with the parameters (namely, the number of doors) lets you easily see the expectancy how much more preferable switching is, and that is exactly 1/(# of doors). I.e., in the simple case of 3 doors, 1/3 of the time ‘not switching’ is better; 2/3 of the time you should switch. In the case of 1,000 doors – only 0.1 percent of the time ‘not switching’ is preferable. This is perhaps most intuitively explained as, instead of going through the farce of opening empty doors, just having the host let you choose between the one door you did choose and all the other doors together. In effect, of course, this is the exact same thing as the opening-then-suggest-to-switch routine.
Like I said, this is nothing new to science – the Monty Hall Problem has, for all it matters, been ‘solved’. It was, though, an interesting learning experience for myself – a see-for-yourself epiphany accessible only by toll & sweat.
I’ve shared my code here (http://sharetext.org/CZGS); you can (and I encourage you, if you feel the same about the MHP as I do). If you don’t have Python on your computer, you can also see, edit, and run the code here (http://codepad.org/lbh5VVHU) to get a feel-for-yourself.
Hooray for science!