In one of my classes, we were given the following problem.
Three prisoners, A, B, C are in their cells. They are told that one of them will be executed the next day and the others will be pardoned. Only the governor knows who will be executed. Prisoner A asks the guard a favor. “Please ask the governor who will be executed, and then tell either prisoner B or C that they will be pardoned.” The guard does as was asked and then comes back and tells prisoner A that he has told prisoner B that he (B) will be pardoned. What are prisoner A’s chances of being executed, given this message? Is there more information than before his request to the guard?
At first glance, it probably seems that prisoner A would have a 50/50 chance of pardon. That seems obvious since Prisoner A knows that Prisoner B or C has one of the pardons and the other would go to him or the remaining prisoner. But let's take a look at the math.
In this case, there are four possible cases.
Case 1: Prisoner A is to be executed, Prisoner B was told by the guard he was to be pardoned.
Case 2: Prisoner A is to be executed, Prisoner C was told by the guard he was to be pardoned.
Case 3: Prisoner B is to be executed, Prisoner C was told by the guard he was to be pardoned.
Case 4: Prisoner C is to be executed, Prisoner B was told by the guard he was to be pardoned.
There are no other possible valid cases.
So given those 4 possibilities, we find the following probabilities:
p(Btold | A) = 1/2, p(Btold | B) = 0, and p(Btold | C) = 1.
And from the problem statement, we know that p(A) = p(B) = p(C) = 1/3.
However, we are trying to calculate p(A | Btold). Let's use Bayes Theorem.
p(A | Btold) = ( p(Btold | A) * p(A) ) / ( p(Btold | A) * p(A) + p(Btold | B) * p(B) + p(Btold | C) * p(C) )
p(A | Btold) = ( 1/2 * 1/3 ) / ( 1/2 * 1/3 + 0 * 1/3 + 1 * 1/3) = (1/6) / ( 1/6 + 2/6) = 1/3
So we find that the probability of Prisoner A being executed given that Prisoner B was told he will be pardoned is 1/3, the same as before he know of Prisoner B being pardoned. However, for Prisoner C, since we know that the probability of p(B | Btold) must be 0, that is that Prisoner B cannot be executed if he is told he will be pardoned and p(Btold | B) * p(B) = 0, and the probability of p(A | Btold) + p(B | Btold) + p(C | Btold) = 1, that is that one of the 3 prisoners must be executed, we find that the probability of Prisoner C being pardoned is now 1 - 1/3 = 2/3.
Alternatively,
p(C | Btold) = ( p(Btold | C) * p(C) ) / ( p(Btold | A) * p(A) + p(Btold | B) * p(B) + p(Btold | C) * p(C) )
p(C | Btold) = ( 1 * 1/3 ) / ( 1/2 * 1/3 + 0 * 1/3 + 1 * 1/3) = (1/3) / ( 1/6 + 2/6) = 2/3
Additionally, I wrote a python program that allows execution of the 3 prisoner problem.
https://drive.google.com/file/d/0B9EB3hdj0VV9ZkdZTDR4UkpwbEU/edit?usp=sharing
The best strategy though might just be to stay out of jail.
Three prisoners, A, B, C are in their cells. They are told that one of them will be executed the next day and the others will be pardoned. Only the governor knows who will be executed. Prisoner A asks the guard a favor. “Please ask the governor who will be executed, and then tell either prisoner B or C that they will be pardoned.” The guard does as was asked and then comes back and tells prisoner A that he has told prisoner B that he (B) will be pardoned. What are prisoner A’s chances of being executed, given this message? Is there more information than before his request to the guard?
At first glance, it probably seems that prisoner A would have a 50/50 chance of pardon. That seems obvious since Prisoner A knows that Prisoner B or C has one of the pardons and the other would go to him or the remaining prisoner. But let's take a look at the math.
In this case, there are four possible cases.
Case 1: Prisoner A is to be executed, Prisoner B was told by the guard he was to be pardoned.
Case 2: Prisoner A is to be executed, Prisoner C was told by the guard he was to be pardoned.
Case 3: Prisoner B is to be executed, Prisoner C was told by the guard he was to be pardoned.
Case 4: Prisoner C is to be executed, Prisoner B was told by the guard he was to be pardoned.
There are no other possible valid cases.
So given those 4 possibilities, we find the following probabilities:
p(Btold | A) = 1/2, p(Btold | B) = 0, and p(Btold | C) = 1.
And from the problem statement, we know that p(A) = p(B) = p(C) = 1/3.
However, we are trying to calculate p(A | Btold). Let's use Bayes Theorem.
p(A | Btold) = ( p(Btold | A) * p(A) ) / ( p(Btold | A) * p(A) + p(Btold | B) * p(B) + p(Btold | C) * p(C) )
p(A | Btold) = ( 1/2 * 1/3 ) / ( 1/2 * 1/3 + 0 * 1/3 + 1 * 1/3) = (1/6) / ( 1/6 + 2/6) = 1/3
So we find that the probability of Prisoner A being executed given that Prisoner B was told he will be pardoned is 1/3, the same as before he know of Prisoner B being pardoned. However, for Prisoner C, since we know that the probability of p(B | Btold) must be 0, that is that Prisoner B cannot be executed if he is told he will be pardoned and p(Btold | B) * p(B) = 0, and the probability of p(A | Btold) + p(B | Btold) + p(C | Btold) = 1, that is that one of the 3 prisoners must be executed, we find that the probability of Prisoner C being pardoned is now 1 - 1/3 = 2/3.
Alternatively,
p(C | Btold) = ( p(Btold | C) * p(C) ) / ( p(Btold | A) * p(A) + p(Btold | B) * p(B) + p(Btold | C) * p(C) )
p(C | Btold) = ( 1 * 1/3 ) / ( 1/2 * 1/3 + 0 * 1/3 + 1 * 1/3) = (1/3) / ( 1/6 + 2/6) = 2/3
Additionally, I wrote a python program that allows execution of the 3 prisoner problem.
https://drive.google.com/file/d/0B9EB3hdj0VV9ZkdZTDR4UkpwbEU/edit?usp=sharing
The best strategy though might just be to stay out of jail.
No comments:
Post a Comment