Tom Moertel's Blog

The Bayesian meets Monty Hall

Posted by Tom Moertel Sat, 01 Jan 2011 23:15:00 GMT

The Monty Hall Problem is a probability-theory classic. Here’s how it goes.

You are on Monty’s game show, trying to find a car hidden behind one of three doors. Monty knows which one; you don’t. He asks you to choose a door, and you do. But he doesn’t open your door. Instead, he goes to the other two doors and, per the rules of the game, opens one that he knows does not contain the car. After making this revelation, he asks if you want to stay with your first choice or switch to the other remaining door.

Should you stay or switch?

The answer – spoiler alert! – is that you should switch: it doubles your chances of finding the car.

This conclusion, however, is hard for many people to believe. According to Wikipedia, “when the Monty Hall problem appeared in Parade, approximately 10,000 readers, including nearly 1,000 with PhDs, wrote to the magazine claiming the published solution – switch! – was wrong.” Because the problem seems to defy intuition, it has been the subject of much study.

But most explanations I’ve seen are unsatisfying because, at one point or another, they require an intuitive leap that many people can’t make. The reader either has the necessary spark of realization at the right moment, or is left behind.

I’m going to try to offer a more satisfying explanation by working through the problem using nothing but Bayesian probability theory and showing every step. Using this method, there are no leaps to be made: everything follows naturally from the theory itself and from the knowledge we have of the problem.

Ready? Let’s get started!

The Bayesian approach

To begin, let’s define some propositions to formalize our discussion of the problem:

• C=i: the car is behind door i (for i = 1, 2, or 3)
• Y=i: you first choose door i
• M=i: Monty reveals that the car is not behind door i
• K: Our prior knowledge about life, the universe, and everything, including the rules for the television game show and our understanding of Monty’s incentives

(For a refresher on propositions and probabilities and our notation, refer to our earlier discussion, More on the evidence of a single coin toss.)

Now let’s formalize our knowledge about these propositions.

Representing our initial knowledge

To represent our knowledge, we’ll use probability equations. First, given our prior knowledge K, we have no reason to believe the car is more likely to be hidden behind any of the three doors; therefore, we must consider each C=i proposition equally likely:

P(C=1|K) = P(C=2|K) = P(C=3|K).

Further, the car must be hidden behind one of the three doors:

P((C=1 ∨ C=2 ∨ C=3)|K) = 1,

and by the sum rule for mutually exclusive propositions:

P(C=1|K) + P(C=2|K) + P(C=3|K) = 1.

Therefore, solving for the individual probabilities, we must assign 1/3 to each:

P(C=1|K) = P(C=2|K) = P(C=3|K) = 1/3.

Adjusting our knowledge in light of you choosing a door

Now, let’s say you choose a door. We’ll call it door 1, which we are free to call it because, so far, we haven’t made any assignments between door numbers and physical doors. So, we make the first assignment now: the door you chose we will call door 1.

Therefore, we now know Y=1. Let’s adjust our probabilities in light of this new evidence.

The quick way is to realize, since you don’t know anything about where the car is hidden, that knowing which door you chose cannot provide us with any new knowledge about which door the car is behind. Therefore, this new evidence shouldn’t change the corresponding probabilities:

P(C=1|Y=1∧K) = P(C=2|Y=1∧K) = P(C=3|Y=1∧K) = 1/3.

But, if we want to do the math, we see that the Bayesian probability adjustments give the same result. Recall the formula for updating a probability in light of new evidence:

(new plausibility) = (old plausibility) × (evidence adjustment)

For door 1, then,

P(C=1|Y=1∧K)
= (old plausibility) × (evidence adjustment)
= P(C=1|K) × [ P(Y=1|C=1∧K) / P(Y=1|K) ]
= P(C=1|K) × [ P(Y=1|K) / P(Y=1|K) ] { since you don’t know C=1 }
= P(C=1|K) × 1
= P(C=1|K)
= 1/3.

The calculations for the other two doors work out identically.

Adjusting our knowledge in light of Monty’s revelation

Now Monty opens a door to show you that it wasn’t hiding the car. We’ll call it door 2. Thus, we now know M=2. Let’s update our beliefs in light of this new evidence.

First, in light of Monty’s revelation, we know that the car is not behind door 2:

P(C=2|M=2∧Y=1∧K) = 0.

But, for the remaining doors, 1 and 3, let’s turn to the adjustment formula for guidance. Before doing any calculations, however, let’s write the formulas for both doors:

P(C=1|M=2∧Y=1∧K) = P(C=1|Y=1∧K) × [ P(M=2|C=1∧Y=1∧K) / P(M=2|Y=1∧K) ]

P(C=3|M=2∧Y=1∧K) = P(C=3|Y=1∧K) × [ P(M=2|C=3∧Y=1∧K) / P(M=2|Y=1∧K) ]

Note that the prior probabilities are equal: P(C=1|Y=1∧K) = P(C=3|Y=1∧K) = 1/3. Also, the evidence-adjustment factors have the same denominator, P(M=2|Y=1∧K). Thus, we can cancel these terms if we divide the second equation by the first, to arrive at the ratio of our adjusted probabilities. This ratio will tell us how strongly we should prefer door 3 to door 1.

After canceling those terms, the calculations are straightforward, in light of our knowledge of the game. We take particular advantage of the knowledge that, after you make your choice, Monty must reveal to you that one of the remaining doors does not hide the car. That is, he must open one of the other two doors, but if one of them is hiding the car, he cannot open that one.

P(C=3|M=2∧Y=1∧K) / P(C=1|M=2∧Y=1∧K)
= P(M=2|C=3∧Y=1∧K) / P(M=2|C=1∧Y=1∧K) { by the adjustment formula and canceling }
= 1 / P(M=2|C=1∧Y=1∧K) { given K, we know Monty must open 2 if C=3 ∧ Y=1 }
= 1 / (1/2) { given K, we know of no reason for Monty to prefer 2 to 3 if C=1 ∧ Y=1 }
= 2.

Therefore, our final belief that the car is behind door 3 should be twice as strong as our belief that it is behind door 1. Switch!

Tags bayesian, hall, monty, probability, problem
11 comments
no trackbacks
 

If unit testing can't keep Rails safe from string-escaping problems, what makes you think it will keep your projects safe?

Posted by Tom Moertel Thu, 12 Oct 2006 20:06:00 GMT

Recently I wrote about unit testing being a tool, not a goal in itself. I argued that unit testing was not a reliable way to fight certain kinds of common coding errors and, therefore, that unit testing ought to be supplemented with other tools.

To support my argument, I gave an example of a common, important coding error that unit testing does a bad job of helping programmers control. That error is failing to manage and escape strings properly: the “strings problem.” It is the mother of XSS and SQL-injection security vulnerabilities, not to mention the cause of legions of broken links and bad HTML on the web.

If you think I’m overstating the problem, or if you think that unit testing is a good way of solving it, let me show you how easy it is for even smart developers to get it wrong.

Consider Ruby on Rails, a great framework for developing web applications. Rails has an extensive suite of unit tests, and the Rails development guidelines require that changes to Rails be accompanied by unit tests that “prove [the] change works.”

Now consider that one of Rails’s most-used and most-scrutinized methods – the venerable link_to helper – contains a fundamental string-escaping error:

require 'rubygems'
require_gem 'rails'
include ActionView::Helpers::UrlHelper

url = "http://example.com?ohms_law?volt=1&amp=3" 
puts link_to("TEST", url)

The code, when executed, prints the following HTML snippet:

<a href="http://example.com?ohms_law?volt=1&amp=3">TEST</a>

The HTML snippet represents a hypertext link. The link should point to the URL given in the code, but because the URL was not properly escaped when it was converted into HTML by the link_to helper, the link is broken:

CORRECT:  http://example.com?ohms_law?volt=1&amp=3
LINK_TO:  http://example.com?ohms_law?volt=1&=3
                                             ^ oops

Here’s what’s going on. Because the URL was not escaped, web browsers misinterpret its “amp” parameter as a character-entity reference, which gets gobbled up when the link’s href attribute is parsed. (To see this for yourself, save the output of the Ruby code into an HTML file, open the file with your favorite web browser, and see where the link points.)

Now, how come the unit tests didn’t catch this problem? It turns out, the tests got it wrong, too, by expecting broken output:

# in url_helper_test.rb

def test_link_tag_with_query
  assert_dom_equal \
    "<a href=\"http://www.example.com?q1=v1&amp;q2=v2\">Hello</a>",
    link_to("Hello", "http://www.example.com?q1=v1&amp;q2=v2")
end

The point isn’t that the Rails developers are dumb. The point is that the Rails developers are smart. If they can’t get the strings problem right, even with all their brains and all their unit testing, what reason does any programmer have to think that unit testing is going to solve this problem reliably?

If, then, you want to solve the strings problem – and you really, seriously ought to want to solve the strings problem – you should consider options beyond unit testing.

Posted in programming, testing, rails
Tags escaping, problem, rails, strings, testing
5 comments
no trackbacks