Someone and Anyone

“I walk slowly, like one who comes from so far away he doesn’t expect to arrive.”

Posts Tagged ‘analysis

Analysis of Strategies for the n-Door Monty Hall Problem

with one comment

In an earlier post (see comments also), I had put forth a question about the winning strategy for the famous n-Door Monty Hall problem. Let me pose it again here, this time in a general way.

Of the following strategies, which has the highest chance of winning in the n-door problem (n > 3)?

  1. Stick with your initial choice till the very end without switching
  2. Stick with your initial choice till the end and switch only at the last stage
  3. Switch your choice at the very beginning and stick with this new door till the very end without switching again
  4. Switch at every possible stage

For those who are already familiar with the 3-door problem, strategy 4 might intuitively seem to be the best strategy. However, that is not the case!

Consider n doors as follows: C, G1, G2, …, Gn-1

Assertion 1: The door we choose at the first stage is C (the “car door”) with probability 1/n, while it is a Gx (one of the “goat doors”) with probability (n – 1)/n.

Strategy 1: Stick with your initial choice till the very end without switching

This strategy is equivalent to simply picking a door uniformly at random. Hence, it is trivially true that the probability of picking C (i.e. probability of winning the car) is 1/n.

Strategy 2: Stick with your initial choice till the end and switch only at the last stage

This strategy is interesting. At every stage except the last one, Monty Hall will go ahead and show us one of the goat doors. That is, out of a total of (n – 1) goat doors, we are shown (n – 2). Hence, the unopened door at the last stage and the door we chose at the first stage are the only two mystery doors to us! One of these contains the car, while the other contains a goat. As we can see, by waiting till the last stage, we maximized our own information content.

If the door we chose at the first stage is C, then according to this strategy, we definitely lose — because the other mystery door (to which we have to switch) then contains a goat.

However, if we chose a Gx at the first stage, then we always win! Because the other mystery door (to which we have to switch) then contains the car.

Therefore, the probability of winning with this strategy is (probability of choosing a Gx at the first stage) * 1. From Assertion 1, this equals (n – 1)/n.

Strategy 3: Switch your choice at the very beginning and stick with this new door till the very end without switching again

According to this strategy, we choose a door at the first stage and switch our choice at the second stage. Thereafter, we stick to the door that we chose at the second stage, till the end of the game.

If the door we chose at the first stage is C, then we definitely lose — because we would switch to a goat door at the second stage and stick with it thereafter.

So, we could win only if we chose a Gx at the first stage. However, merely choosing a Gx at the first stage does not mean we always win. After the first stage, Monty shows us one of the goat doors. This still leaves (n – 2) other doors (excluding our initial choice) as a mystery to us. So, we will switch to one of the remaining (n – 2) doors uniformly at random. So, the probability of switching to C is 1/(n – 2).

Therefore, the probability of winning with this strategy is (probability of choosing a Gx at the first stage) * 1/(n – 2). Hence, It follows (from Assertion 1) that the probability of winning with this strategy is (n – 1)/(n (n – 2)) or (n – 1)/(n2 – 2n).

Strategy 4: Switch at every possible stage

In this strategy, we keep hopping from one door to another door at every stage. In this approach, the only way to win is by switching to C at the (n – 1)th stage, no matter which doors we have switched to up until then. The only thing that matters is whether we are able to switch to C at the last stage. This can happen if and only if we are at a Gx at the (n – 2)th stage.

It is obvious that by the time we reach the last stage, Monty would have revealed all but one goat door. So, we’ll be left with two doors — one goat door (i.e. some Gx) and C. Hence, it is clear that we will win if we are at the solitary goat door at the end of the (n – 2)th stage.

Let us first see what is the probability (P) of making it to some Gx at the last-but-one stage, given that we start with C at the first stage. In other words, having started with C at the first stage, what is the probability that we will have reached some Gx after exactly (n – 3) transitions (or switches)?

From C, we will always make a transition to some goat door other than the one that Monty reveals at the end of the first stage. So, we can make a transition to one of the remaining (n – 2) goat doors with probability 1. That leaves us with exactly (n – 4) transitions after which to reach some goat door. From here on, Monty is going to unveil one goat door at each stage except the last. So, the number of possible transitions at each stage, no matter what door we are at, keeps decreasing by 1. Also, note that there is a transition from every goat door to C.

Therefore, the probability of transition to a goat door for the third stage is ((n – 3) – 1)/(n – 3); the probability of transition to a goat door for the fourth stage is (n – 5)/(n – 4); … ; the probability of transition to a goat door for the (n – 3)th stage is 2/3; the probability of transition to a goat door for the (n – 2)th stage is 1/2.

Therefore, with C as the initial choice, the probability that we reach some Gx after exactly (n – 2) stages is given by

P = 1 * (n – 4)/(n – 3) * (n – 5)/(n – 4) * … * 2/3 * 1/2.

This implies P = 1/(n – 3).

However, this seems to hold only if we do not make any transitions to C up to the end of (n – 2) stages. But what if we do switch to C at some stage? Then, we switch back to one of the remaining (n – m – 1) instances of Gx with probability 1, where m is the stage number that took us to C. Therefore, switching to C at some intermediate stage does not affect our calculation of P.

Now, let us see what is the probability (Q) of making it to some Gx at the last-but-one stage, given that we start with a Gx at the first stage. In other words, having started with some Gx at the first stage, what is the probability that we will have reached another Gx after exactly (n – 3) transitions?

From a Gx, we will make a transition to either some Gx other than the one that Monty reveals at the end of the first stage or C. So, for the second stage, the probability that we make a transition to one of the remaining (n – 3) goat doors is (n – 3)/(n – 2); for the third stage, the probability that we make a transition to one of the remaining (n – 4) goat doors is (n – 4)/(n – 3); … ; for the (n – 3)th stage, the probability that we make a transition to one of the remaining 2 goat doors is 2/3; for the (n – 2)th stage, the probability that we make a transition to the remaining 1 goat door is 1/2.

Therefore, with some Gx as the initial choice, the probability that we reach another Gx after (n – 2) stages is given by

Q = (n – 3)/(n – 2) * (n – 4)/(n – 3) * … * 2/3 * 1/2

This implies Q = 1/(n – 2).

Again, at any stage, if we make a transition to C, then we make a transition to a Gx at the next stage with probability 1. Therefore, switching to C at some intermediate stage does not affect our calculation of Q.

Thus, the probability of winning with the strategy of always switching is (probability of choosing C at the first stage) * P + (probability of choosing a Gx at the first stage) * Q. From Assertion 1, it follows that the probability of winning with this strategy is given by 1/(n * (n – 3)) + (n – 1)/(n * (n – 2)). This equals (n2 – 3n + 1)/(n3 – 5n2 + 6n).

In the order of probability of winning, the above four strategies compare as follows:

Strategy 2 > Strategy 4 > Strategy 3 > Strategy 1.

There are many other strategies for playing this game, of course. For ex., you could switch and stick alternately (or with any other pattern, for that matter). However, intuitively, it seems that it would pretty much be impossible to beat Strategy 2 — as n increases, the probability of winning approaches 1. Perhaps, there exists a formal proof of the supremacy of Strategy 2. But I’ve not been able to find it on the Web. If you come across such a proof, please leave a comment.

PS: If you find any discrepancies in this article, please let me know. I am not too sure about the correctness of the proof for strategy 4.

Advertisements

Written by Anyone

May 21, 2008 at 1:42 am

Aargh! Hmmm…

leave a comment »

I saw “Aarghhhhh!” written as a friend’s IM status message, and wondered what could be some of the most frequent spellings of this expression. So I decided to google “aargh”. The top result for this query turned out to be pretty interesting.

Oliver Steele has an interesting post on this topic here.

Steele has an interesting analysis about the expression hmmm too.

Written by Anyone

September 16, 2007 at 8:22 pm