Tuesday, June 7, 2011

The MontyHallProblem

The Monty Hall problem is as follows(stated in wikipedia):
The Monty Hall problem is a probability puzzle based on the American television game show Let's Make a Deal that was originally hosted by Monty Hall. The problem, also called the Monty Hall paradox, is a veridical paradox because the result appears odd but is demonstrably true. The Monty Hall problem, in its usual interpretation, is mathematically equivalent to the earlier Three Prisoners problem, and both bear some similarity to the much older Bertrand's box paradox.

In a few words
Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. 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 pick door No. 2?" Is it to your advantage to switch your choice?
 Furthermore the Monty Hall problem is briefly discussed in the movie "21 Blackjack".
The answer in the question switch or not is given but without a mathematical analysis.
The mathematical solution for this problem is based on Bayes' Theorem. This article, however, does not aim to explain Bayes' Theorem, but how we use it to create a program in java that will give us the best solution for N doors.
The steps is that you choose a door, and Monty Hall opens a door other that yours and the winning door. In each stage you choose to switch or stick to your choice. This process is until there's nothing left but two closed doors, yours and another one.

So let's say we have N doors. The prior probability of each door to have the car behind it is obviously 1/N

So, let's say D is the set of containing all closed doors, such that its initial value is
P(D) = 1
(That means that the car is behind of a closed door)
and card(D) = N
(that means that D has N elements)

         P(L) = 1/N
(this means that each door that is a closed door has probability be the right door of 1/N)

So now Monty Hall opens a door b other than your door you chose.
D = D-{b}
P(D) = 1

Now for every door that is closed the probability changes.
Let Oi be the event that Monty Hall opens a door i, and P(Oi | L) be the probability that
he opens door I by knowing that the right door is L.
so if L = "your door" ⇒ i is a door other than L

so P(Oi | L) = 1/(N-1)
Wonder why? think about it. He knows that you choosed the right door, so he has a range of N-1 doors to choose.
He wouldn't open the right door (that's the rules) and so if L = i ⇒ P(Oi | L) = 0
Now what happens if the door is not the door you chose?
if (L ≠ your door) and (L ≠ i) then
  P(L) = 1/(N-2)

If you still wonder why count how many doors left for Monty Hall to choose.

Now, we have to update our probabilities of belief for each door. We must forget the prior probabilities we begun because they have no meaning any more.

So we've found those probabilities of opening, how do we find the new probabilities for each door?

Using Bayes' theorem to find the probability that L is the right door under the event that Moonty Hall opened door i
P(L | Oi) = P(Oi | L)p(L) / (∑P(Oi | d)P(d))

So for each step you must do the same thing, and in the end you will have your probability.

You can ask for questions on facebook or below this article

If you find the solution in a language other than Java we would be glad to share it with us along with your name!

Solution is uploaded, you can find the source code here and the byte code there!

No comments:

Post a Comment