Friday, November 22, 2013

Monty Hall, extended

The original Monty Hall problem is so famous that pretty much every soul knows the solution by heart (in case you don't: change to the other still closed door and double your winning probability!). Despite (or because of) the fame of this problem, some would learn the answer without really knowing how to solve it. Let's go through the problem in its original setting:

Classic Three Door Monty Hall
There are three doors A, B and C, and only one leads to a prize. After you picked door A, the host (who knows where the prize is) opens door C, which turns out to be not the prize door. What is the winning probabilities of you sticking to door A versus switching to door B?

And of course, the toolkit to invoke is Bayesian statistics:
$$ P(A|C_o) = \frac { P(C_o|A)P(A)}{P(C_o)} $$
where $P(X)$ is the unconditional probability of the prize being behind door X, and $P(Y_o)$ is the probability of door Y being opened by the host. In this case, the entities on the RHS are straightforward, except perhaps for $ P(C_o)$:
$$  P(C_o|A) = 1/2 $$
$$  P(A) = 1/3 $$
$$  P(C_o) = P(C_o|A)P(A) + P(C_o|B)P(B) + P(C_o|C)P(C) $$
$$= \frac 1 2 \times  \frac 1 3 + 1 \times \frac 1 3 + 0 = \frac 1 2$$
So $P(A|C_o) = 1/3$. One can in a similar fashion find that $P(B|C_o) = 2/3$. The reason $ P(C_o|B) = 1$ is of course that if the prize is really behind door B, the host has no choice but to open door C.

Extended Five Door Monty Hall
So far so good. Now we are invited to a "Monty Hall Deluxe" game with a bigger prize, but more doors and more rounds. In round one, you pick a door. The host would open one door, after which you may choose to switch to another. Then once you have decided and acted accordingly, we enter round two where the host would open one more door (so number of closed door drops to 3 at this point). Then you decide on whether to switch for a second time, and if so to which door. What should the optimal strategy be?

Suppose you first pick door A and the host opens door E. The first round of this game is really similar to the Classic version above. Namely,
$$ P(A|E_o) = \frac { P(E_o|A)P(A)}{P(E_o)} $$
with
$$  P(E_o|A) = 1/4$$
$$  P(A) = 1/5$$
$$  P(E_o) =\sum  P(E_o|X)P(X) $$
$$= \frac 1 4 \times  \frac 1 5 + \frac 1 3 \times \frac 1 5 + \frac 1 3 \times  \frac 1 5+ \frac 1 3 \times  \frac 1 5+0 = \frac 1 4$$
So $P(A|E_o) = 3/15$. Similarly, one can show that $P(B|E_o) = P(C|E_o) =P(D|E_o) =4/15$. So once again, it is better for you to switch (and due to symmetry, it doesn't matter to which).

Suppose you switch to door B. Now we are in round two. The host then open door D, which, surprise-surprise, turns out to have no prize behind it too. Now what do you do? What are the probabilities of staying versus switching?

One thing to be careful about is this: since at this point round one is already over, the conditional probabilities we calculated (i.e. $P(A|E_o)$, $P(B|E_o)$, ...) should now be considered unconditional:
$$ P(A)  = 3/15$$
$$ P(B)  = 4/15$$
$$ P(C)  = 4/15$$
We also have the followings:
$$ P(D_o|A) = 1/2$$
$$ P(D_o|B) = 1/3$$
$$ P(D_o|C) = 1/2$$
$$  P(D_o) =\sum  P(D_o|X)P(X) $$
$$= \frac 1 2 \times  \frac 3 {15} + \frac 1 3 \times \frac 4 {15} + \frac 1 2 \times  \frac 4 {15} +0 = \frac {29} {90}$$
Hence $P(A|D_o) = 9/29$, $P(B|D_o) = 8/29$ and $P(C|D_o) = 12/29$. So staying with door B is even worse than switching back to door A, and switching to the untouched door C is the best. Just keep switching!

No comments:

Post a Comment