.. index:: Monty Hall Puzzle Example

.. _Monty_Hall_Puzzle:

Monty Hall Puzzle
=================

Describing the Monty Hall Puzzle
--------------------------------

The Monty Hall puzzle gets its name from an American TV game show, "Let's make a deal", hosted by Monty Hall. In this show, you have the chance to win some prize if you are lucky enough to find the prize behind one of three doors. The game goes like this:

* You are asked to select one of the three doors.
* Monty Hall (who knows where the prize is) opens another door behind which there is no prize.
* You are asked if you want to alter your selection (select the other closed door).
* You get the prize if it is behind the door you selected.

The problem of the puzzle is: What should you do at your second selection? Some would say that it does not matter because it is equally likely that the prize is behind the two remaining doors. This, however, is not quite true. The right answer is that you have the best chance of winning if you alter your selection - odds 2/3 in stead of 1/3. In the following, the solution is computed through the use of a simple :ref:`Bayesian network<introduction_to_bayesian_networks>`.

Finding the Solution Using a Bayesian Network
---------------------------------------------

The Monty Hall puzzle can be modeled with three random variables: Prize, First Selection, and Monty Opens.

* Prize represents the information about which door hides the prize. This means that it has three states: "Door 1", "Door 2", and "Door 3".
* First Selection represents your first selection. This variable also has the three states: "Door 1", "Door 2", and "Door 3".
* Monty Opens represents Monty Halls choice of door when you have made your first selection. Again, we have the three states: "Door 1", "Door 2", and "Door 3".

The door hiding the prize is known to Monty and thus Prize has an influence on Monty Opens. Monty will never choose to open the door of your first selection, so also First Selection has an influence on Monty Opens. This give us the network shown in Figure 1.

.. figure:: images/montyhall.png

	Figure 1: Bayesian network of the Monty Hall puzzle. The causal links describe that both Prize and First Selection have an influence on Monty Opens.

The conditional probability table (CPT) of Prize is shown in Table 1 (indicating ignorance about where the prize is hidden).

.. figure:: images/montyhalltabel.png

	Table 1: P(Prize).

The CPT of First Selection is shown in Table 2 (the probabilities of this table are unimportant, as you will always select a specific state of this variable when you use the network).

.. figure:: images/montyhalltabel1.png

	Table 2: P(First Selection).

Table 3 shows the CPT of Monty Opens. This table states that if the prize is behind Door 1 and you have chosen Door 3, then Monty will open Door 2 for sure, since this door is the only possible door he can open. If you have selected the right door in your first selection, he will randomly choose one of the two other doors.

.. figure:: images/montyhalltabel2.png

	Table 3: P(Monty Opens | Prize, First Selection).

The network shown in Figure 1 with nodes having the CPTs of Table 1, 2, and 3 can be constructed very quickly using the Hugin Graphical User Interface. Right after compilation, the Node List Pane of the Hugin Graphical User Interface will appear as in Figure 2, which is an interactive Java applet allowing you to select first your own first selection and then the door opened by Monty. After this, the solution appears from the probabilities of Prize. The functionality of this applet is very similar to the functionality of the Hugin Graphical User Interface.

.. figure:: images/montyhall1.png

	Figure 2: Showing the list of nodes (variables) of the Monty Hall puzzle domain. 

Figure 2 shows that it will always be best for you to alter your selection when Monty has opened a door (gives you 66.67% chance of winning the prize).


An easy way to convince yourself that this is true goes like this: At first you have 33.33% chance of choosing the right door and there is 66.67% chance of the prize being somewhere else. You know that Monty is going to open an empty door so when he does, this should not change a thing about your belief of your door being the right one. You still have 33.33% chance of having selected the right door. Thus there must be 66.67% chance of the prize being somewhere else (behind the last door).