Thursday, September 19, 2013

The Monty Hall Problem via Bayes' Rule

The Monty Hall Problem is a puzzle presented in the context of a gameshow. Behind one of three doors is a prize, and behind the other two doors are goats. Here we assume that the prize is not a goat. You pick a door at random. The game's host, Monty Hall, knows which door the prize is behind. He opens one of the remaining two doors to reveal a goat and asks you if you'd like to switch your choice to the other unopened door. Should you switch?

Many people assume that there is no particular impetus to switch, because now the prize is behind each of the remaining two doors with equal probability. This is equivalent to the assumption that Monty's revelation is moot. While there are many other ways to rigorously prove that you should switch, we can use Bayes' rule as a natural way to account for the updating that occurs after Monty's reveal. Let $A$ be the door you have chosen, $B$ the other unopened door, and $C$ the door that Monty opened. We wish to calculate the probability that $B$ contains the prize given that Monty opened door $C$. By Bayes' rule, \begin{align*} P( B \text{ has prize} \mid C \text{ opened} ) &= \frac{ P( B \text{ has prize})P(C \text{ opened} \mid B \text{ has prize} )}{P( C \text{ opened})} \\ &= \frac{(1/3)(1)}{(1/2)}=2/3. \end{align*} This of course implies that $P( A \text{ has prize} \mid C \text{ opened} ) =1/3$, but we can calculate this explicitly: \begin{align*} P( A \text{ has prize} \mid C \text{ opened} ) &= \frac{ P( A \text{ has prize})P(C \text{ opened} \mid A \text{ has prize} )}{P( C \text{ opened})} \\ &= \frac{(1/3)(1/2)}{(1/2)}=1/3. \end{align*} This proves that you're twice as likely to win the prize if you switch doors.

It's not too difficult to arrive at an enumerative solution. Suppose more generally that there are $n$ doors, where $n$ is some natural number, but still only one prize. If you initially chose the winning door, then Monty can reveal all but one door in $n-1$ ways. Only in this scenario do you win by sticking with your original choice. On the other hand, for each of the $n-1$ doors not hiding a prize, Monty can reveal all but one door in $n-2$ ways, so there are a total of $(n-1) + (n-1)(n-2)=(n-1)^2$ ways the game can play out, $n-1$ of which result in a prize if you don't switch. So the probability of winning if you switch is $(n-1)(n-2)/(n-1)^2 = (n-2)/(n-1)$, opposed to just $(n-1)/(n-1)^2 = 1/(n-1)$ if you don't switch.

Another way of viewing the problem is to realize that by switching your are actually betting that your initial choice was incorrect, and this is indeed a good bet!