Sunday, May 04, 2008

The Three Prisoners Problem

One thing that can be both a blessing and a curse about my nature is that I am often able to find ways to keep myself awake almost all night long. It doesn’t matter how tired I am when I try to go to bed, if I think of something that gets my mind going then I’d much rather continue to think on it than sleep. This happened to me the other day as I was thinking of a few statistical quirks regarding Natural Selection, random mutations, and the like.

Unfortunately, I’m not yet able to write the blog post that I wanted to write, because while I know exactly what I’m talking about, it lacks sufficient groundwork for many other readers to be able to follow along! Since I am an apologist at heart (one who would love to preside over the complete destruction of ideological Darwinism, mind you) I do wish to expand on my thoughts and present them to others, so this leaves me with the necessary task of providing some starting groundwork before I get to the main point. And besides, although it’s tangential to my ultimate point, some of this stuff is just plain kewl :-)

In any case, since a great deal of what I will be focusing on in future posts will deal with statistical analysis, I thought it might be beneficial to give a quick overview of The Three Prisoners Problem in order to A) melt your brain if you’ve never heard of it and B) show how statistics can be logical and yet make no sense at first glance (mostly due to a wrong perspective).

The Three Prisoners Problem was originally mentioned by Martin Gardner in his “Mathematical Games” column in the October, 1959 edition of Scientific American, but under the Monty Hall guise (its mathematical equivalent) it has gathered more infamy, especially after Marilyn vos Savant’s article in Parade magazine in 1990. If this doesn’t make sense to you at first glance, you can take comfort in the fact that it has fooled Nobel laureates, professional mathematicians, and Mensa members countless times. Here I will give my own version of the problem.

There are three prisoners in the king’s dungeon: Adam, Bill, and Charlie. The Warden arrives at each cell and says, “The King has decided that two of you shall go free tomorrow.” At this, there is great rejoicing. But the Warden continues: “However, one of you will be executed.”

“Who will it be?” they all ask in turn.

The Warden responds: “The King has told me who will be executed, but he has also forbidden me telling you who will live and who will die.”

Each of the prisoners accepts this answer except for Charlie. Charlie is a shrewd character and because he knows the Warden is scrupulously honest, he asks: “I know you said that you cannot tell me who will be executed or who will be set free, and therefore you cannot tell me my fate. But will you instead give me one name of one of the other prisoners who will be set free?”

The Warden thinks about this for a moment. “Why would you want to know that?” he ponders. “If I don’t give you a name, you know that you have a 1/3 chance of being executed and a 2/3 chance of going free. If I tell you a name, then you will only have a 1/2 chance of going free! It is better for you if you do not know a name.”

“In that case,” Charlie responds, “why not tell me?”

The Warden relents and says, “Adam will go free tomorrow.”

At this, Charlie sits back and smiles because the Warden has inadvertently told him that it is twice as likely that Bill will be executed as it is that he will be executed…

The reason this is a “problem” is because for most of us we reason the way that the Warden did. Surely telling Charlie that Adam will go free has actually reduced Charlie’s odds of survival, hasn’t it? It used to be 2/3 because it could have been Adam, Bill, or Charlie who would be killed and 2 of them would have lived. But now it’s either Bill or Charlie who will be killed and only one of them would live, and that’s a 1/2 chance, isn’t it?

There are two ways to look at this. First, let’s look at the mathematical rule involved: fractional statistics must together add up to 1.

When the prisoners are first given information, there is a 1/3 chance for each of them that they will be killed. Thus, we have the odds of death being:

Adam = 1/3
Bill = 1/3
Charlie = 1/3

Now when Charlie asks which of the first two prisoners will go free, since the Warden is honest, he tells him that Adam is one who will go free. But this gives no new information to Charlie about whether or not Charlie will die. Charlie’s odds of being killed remain 1/3. However, Adam’s odds of being killed are reduced to 0. He will survive.

If Charlie has a 1/3 shot of dying and Adam has a 0 shot of dying, then because statistics must balance to 1 (it is a certainty that someone will die), this means that Bill’s odds of dying must be 2/3. As a result, Bill is twice as likely to be executed as Charlie.

Of course, this still doesn’t seem right at all! After all, how can telling Charlie that Adam will go free affect Bill’s odds of survival but not affect Charlie’s original odds of survival?

The second way of explaining this helps to flesh it out a bit better. As we stated, when the problem begins, each prisoner has a 1/3 chance of being killed. Therefore, there are three possible options. Let us examine these three options and what the Warden must respond under each option.

Option 1: Adam is killed. If Adam is the one to be executed, then when Charlie asks for the name of one of the two prisoners who will live, the Warden must respond “Bill.” If he says Adam lives, then he has lied (and we’ve stipulated that the Warden is honest). Conclusion: Charlie lives; the prisoner not named dies.

Option 2: Bill is killed. Like the above, the Warden’s choice is restricted to one answer. The Warden can only say that “Adam” will live. Conclusion: Charlie lives; the prisoner not named dies.

Option 3: Charlie is killed. Here is the only instance where the Warden has freedom. Since Charlie will be killed, then he can name either Adam or Bill. Conclusion: Charlie dies; the prisoner not named lives.

As we see in the above, Charlie’s chances of being killed remain 1/3 because only under option 3 does he die. Further, 2/3 of the time the Warden is forced to name a specific prisoner because the one not named is the one who will die. Therefore, 2/3 of the time the prisoner not named is the prisoner who will be executed.

This is also easier to see if we use bigger numbers. Suppose that there are instead 1,000 prisoners and all but one of them will be set free while the remaining prisoner is executed. Under these circumstances, the Warden reveals 998 prisoners who will be set free, leaving only Charlie and prisoner number 473 behind. Which is more likely, that the Warden was forced to leave prisoner number 473 as an option or that Charlie is going to be killed and prisoner 473 was a random selection? Obviously, there is only a 1/1000 chance that prisoner 473 was a random selection, but there is a 999/1000 chance that prisoner 473 was the forced choice. So in this case, the reason it is counterintuitive has more to do with the fact that we do not realize the Warden is excluding all but one prisoner from his answer. If there were 1,000 prisoners total and Charlie asked for the list of 998 of them that would go free, the Warden would immediately spot this error.

Note, however, that even under the circumstance that Charlie only asked for the name of one prisoner out of the 1000 who would go free, that would decrease the odds of all the other unnamed prisoners surviving, although in this instance the amount the odds change would be negligible. Charlie would remain with a 1/1000 chance of dying, while the 998 unnamed prisoners would have just over a 1.001/1000 chance of dying and the one named one would have a no (0) chance of dying. This equates to 998 prisoners splitting a 999/1000 odds, so you still end up with 1/1000 + 999/1000 + 0 = 1. (1.001 x 998 rounds to 999.)

As I mentioned at the top of this post, this is mathematically equivalent to the Monty Hall Problem. That can be demonstrated while keeping with the prisoner motif in the following manner. Suppose that instead of the Warden talking to the prisoners, the King summons the Warden to his throne room. The King, who enjoys tormenting the Warden, says:

“Warden, I am going to execute two prisoners tomorrow, but I am going to free one of them. I have written his name down and locked it in this chest beside me along with one thousand gold pieces. If you can guess who will go free, you can have all the gold in the chest. If you do not guess who goes free, you will have to join the prisoners being executed!”

The Warden realizes he has a 1/3 chance of gaining riches and a 2/3 chance of dying. Nevertheless, the King has given him no option. So he says, “I pick Adam to live.”

The King smiles and says, “Let us make this more interesting. Before you open the chest and see the name, I will tell you that Charlie is going to die. Now, do you still want to choose Adam to live, or do you want to switch your choice to Bill?”

At this point, what should the Warden decide?

Again, mathematically this is equivalent to the Three Prisoners Problem above. Therefore, we know that when the Warden picked Adam to live, he had a 1/3 chance of being right. The King has now informed the Warden that Charlie will die: therefore, Charlie has a 0 chance of living. Once again, because the numbers have to add up to 1, this means that Bill now has a 2/3 chance of living and Adam only has a 1/3 chance of living. Therefore, the Warden should switch his choice.

And to demonstrate this in the similar manner as above, look at the three options of what would happen after the Warden picks Adam but before the King (who already know who will die) responds:

Option 1: Adam lives. In this case, the King can name either Bill or Charlie as dying. Therefore, the Warden should not switch his choice because whomever the King does not name of the other two prisoners will die.

Option 2: Bill lives. In this case, the King MUST name Charlie as dying. The Warden should change his pick to the prisoner not mentioned (Bill).

Option 3: Charlie lives. In this case, the King MUST name Bill as dying. The Warden should change his pick to the prisoner not mentioned (Charlie).

Again we see that 2/3 of the time, the Warden should change his selection.

So here we see that sometimes statistics can be perfectly logical and rational, yet the result is so counterintuitive that they feel wrong. In my next post, I’ll give an example of the opposite: when statistics are irrational and yet seem to make sense. After that, I will look at a few examples statistics in action with Darwinism.

3 comments:

  1. If anyone disbelieves and needs to see a sign:

    http://www.shodor.org/interactivate/activities/SimpleMontyHall/?version=1.6.0_05&browser=MSIE&vendor=Sun_Microsystems_Inc.

    Try switchin enough times and you'll see it levels out to around 2/3rds.

    On a side note, it probably helps to have an understanding of the nature of CONDITIONAL probability when thinking about this problem...

    ReplyDelete
  2. Thanks Mike :-)

    I've actually made my own Monty Hall simulator too:

    http://www.calvindude.com/montyhall.php

    Mine has no frills or even instructions...but if you've read this post you should be able to figure it out :-D

    ReplyDelete
  3. At this, Charlie sits back and smiles because the Warden has inadvertently told him that it is twice as likely that Bill will be executed as it is that he will be executed…

    ha thats true. But Charlie didnt do anything to increase his odds, he just put the sweats on Bill...and whose to say the warden did it inadvertently? Charlie gained no new information about his lot, just Bills.

    ReplyDelete