Prisoner's paradox

The prisoners ' paradox, also known as the Three Prisoners Problem , appeared in Martin Gardner's Mathematical Games column in Scientific American in 1959 and is a paradox about conditional probabilities and Bayes' theorem . It is not to be confused with the prisoner's dilemma in game theory.

Formulation of the problem

Three prisoners sentenced to death - A nton, B ernd and C lemens - are in solitary cells when the governor decides to pardon one of them. He writes their names on three pieces of paper, shakes them up in a hat, pulls one out and gives the name of the lucky one to the prison guard over the phone, asking them to keep this information secret for several days. Rumors of it reach Anton. When the guard makes his morning round, Anton tries to persuade him to tell him who will be pardoned. The guard refuses.

“Then tell me,” says Anton, “the name of one of the others who will be executed. If Bernd is pardoned, tell me Clemens; if Clemens is pardoned, tell me Bernd. If I am pardoned, flip a coin to decide between Bernds and Clemens' mention. "

“But when you see me toss a coin,” replies the guard, “you will know that you are the pardoned. And when you see that I am not tossing a coin, then you know that the unnamed person will be pardoned. "

"Then don't tell me now," says Anton, "but tell me tomorrow."

The guard, who knows little about probability theory, thinks about it during the night and decides to follow the procedure suggested by Anton, assuming that he would give him no help in estimating his chances of survival if Anton did not know whether he had the coin threw. The next morning he informs Anton that Bernd will be executed.

After the guard disappears, Anton smiles at his stupidity: Either Clemens is pardoned or he himself, so that his chance of survival has increased from ¹ ⁄ ₃ to ¹ ⁄ ₂ .

The guard doesn't know that Anton can communicate with Clemens, who is sitting in the neighboring cell, by giving knock signals over a water pipe. He tells him exactly what he has discussed with the guard. Clemens is equally pleased with the news because, for the same reasons as Anton, he concludes that his chances of survival have also risen to ¹ ⁄ ₂ .

Do the two prisoners correctly assess their chances? If not, how should each calculate their chances of being pardoned?

The solution

At the beginning, the information given in the problem formulation is translated into a mathematical formalism. In general, a strict distinction must be made between the level of the persons acting in the text (e.g. Anton) and the level of the reader (meta level). The prior knowledge available to the various levels can be quite different.

First you place after the first letter of the actors, and then the random variable that represents the lottery and maps it to. Because the name was chosen randomly, you can start: ${\ displaystyle {\ mathcal {X}} = \ {A, B, C \}}$ ${\ displaystyle L}$ ${\ displaystyle {\ mathcal {X}}}$

{\ displaystyle P (L = A) = P (L = B) = P (L = C) = {\ frac {1} {3}}}

That is, is evenly distributed . ${\ displaystyle L}$

Furthermore, let it be a random variable that indicates who the keeper names. Although Anton, unlike the reader, does not know whether the guard followed the suggested procedure, he trusts the guard and then concludes for the conditional probabilities of the guard's mentioning: ${\ displaystyle G}$

{\ displaystyle P (G = B | L = A) = P (G = C | L = A) = {\ frac {1} {2}}}

{\ displaystyle P (G = B | L = B) = 0}

{\ displaystyle P (G = B | L = C) = 1}

The warden will name Bernd or Clemens with equal probability, should the lottery draw on Anton. He will not name Bernd if Bernd has been drawn and he will certainly name Bernd if Clemens has been drawn. The posterior survival probability for Anton is then, according to Bayes' theorem :

{\ displaystyle P (L = A | G = B) =}

{\ displaystyle = {P (L = A) P (G = B | L = A) \ over P (L = A) P (G = B | L = A) + P (L = B) P (G = B | L = B) + P (L = C) P (G = B | L = C)} =}

{\ displaystyle = {\ frac {{\ frac {1} {3}} \ cdot {\ frac {1} {2}}} {{\ frac {1} {3}} \ cdot {\ frac {1} {2}} + {\ frac {1} {3}} \ cdot 0 + {\ frac {1} {3}} \ cdot 1}} = {\ frac {1} {3}}}

The prisoners misjudge their chances of survival. The probability that Anton survives remains ¹ ⁄ ₃ . The probability that Clemens survives has increased to ² ⁄ ₃ .

The paradox

The paradox of the result is that Anton's chance of survival in the new situation, i.e. his conditional chance of survival , is still ¹ ⁄ ₃ , while Clemens' probability of survival doubles from ¹ ⁄ ₃ to ² ⁄ ₃ . Although now only he or Clemens can be pardoned, it is just as good as his chance of survival at the beginning. ${\ displaystyle P (L = A | G = B)}$ ${\ displaystyle P (L = A)}$

The paradox can be resolved by realizing that the warden's statement has no bearing on the likelihood of Anton's fate. Since Anton would not be named under any circumstances, his omission does not provide any additional information. Since, on the other hand, Bernd or Clemens can be named, the entire information gain from mentioning or not mentioning one of the two names is distributed antisymmetrically to exactly these two people. As soon as it is known that Bernd will die, Bernds survival probability drops from ¹ ⁄ ₃ to 0, and Clemens' survival probability increases from ¹ ⁄ ₃ to ² ⁄ ₃ . The overall probability that Bernd or Clemens will survive remains unchanged at ² ⁄ ₃ .

Equivalence with the goat problem

The prisoner paradox is based on the same facts as the standard variant of the goat problem . The event of the pardon is to be identified with the existence of the profit behind a gate, furthermore the opening of a gate with the naming of a victim and the guard with the moderator. The attendant's knowledge and behavior, along with the coin toss, is equivalent to that of the moderator. In the moderator or guard only the behavior of the probabilities is subsumed.

Solution with a larger base quantity

When looking at 100 prisoners, one of whom is to be pardoned, the probabilities are similar to those for three people. Anton's chances of survival as one of the hundred are 1%, and the chance someone else will survive is 99%. Anton asks the guard to name 98 of his fellow prisoners who have to die. After completing the list, Clemens and Anton remain themselves. Since Anton was excluded from the list from the start, Anton's chance of survival in the new situation, i.e. his conditional chance of survival, is still 1%. And because Clemens was the only one who was not named, it is very likely, 99% of the time, that he was pardoned.

By naming a victim, the guard gives the questioner new information. However, this information does not affect the questioner's probability of survival. The guard names a prisoner different from the questioner and the pardoned. This means that the prisoners are to be divided into two groups, the questioner's group and a remaining group. The information given by the keeper only affects the remaining quantity. With each named name, the survival probability drops to zero and the survival probability of the others increases accordingly, while that of the questioner remains the same.

It is assumed that the selection probability of every prisoner is initially the same. The probability that the pardoned person is an element of the questioner or the rest of the group is determined by the distribution of the random variables.

Addition to the above considerations

“So after Anton received the guard's answer, the guard visits Clemens. Clemens asks the guard what he did with Anton. The guard tells him the story, to which Clemens replies: 'Thank God I didn't ask first!' "

In fact, with the same answer “Bernd”, Anton's chances of winning would have risen to ² ⁄ ₃ , while with the questioning Clemens it would have remained ¹ ⁄ ₃ .

The paradox is that the chances of survival seem to increase for those who did not ask. However, the chances of survival remain the same regardless of the question, namely ¹ ⁄ ₃ (the answer to the question only increases the information about the chances of survival of the prisoners in the remaining quantity).

Consider the question: "What is the probability that Anton was pardoned, provided that Bernd was not pardoned?"

Initially, the following probabilities apply:

{\ displaystyle P \ left ({\ overline {B}} \ mid A \ right) = P \ left ({\ text {Bernd not pardoned}} \ mid {\ text {Anton pardoned}} \ right) = 1}

(If Anton is pardoned, Bernd cannot be pardoned)

{\ displaystyle P (A) = P ({\ text {Anton pardoned}}) = {\ frac {1} {3}}}

{\ displaystyle P \ left ({\ overline {B}} \ right) = P ({\ text {Bernd not pardoned}}) = {\ frac {2} {3}}}

The result then follows directly from the definition of the conditional probability:

{\ displaystyle P (A | {\ overline {B}}) = {\ frac {P (A \ cap {\ overline {B}})} {P ({\ overline {B}})}} = {\ frac {P ({\ overline {B}} | A) \ cdot P (A)} {P ({\ overline {B}})}} = {\ frac {1 \ cdot {\ frac {1} {3 }}} {\ frac {2} {3}}} = {\ frac {1} {2}}}

You now have two solutions that seem to contradict each other.

The reason is that the answers are given under different conditions. In the question, the attendant's answer is influenced by the selection made previously (above in the separation into questioner and remaining quantity). If this influence is not taken into account, information is lost, and this is reflected in the shift in probability (the groups are not separated in the last question, so the loss of Bernd's chance of survival benefits the chances of Anton and Clemens equally).

literature

Frederick Mosteller : Fifty Challenging Problems in Probability. Dover, 1987 (reprint), ISBN 0-486-65355-2 , pp. 28-29 ( excerpt (Google) ).
Richard Isaac: The Pleasures of Probability. Springer, 1995, ISBN 9780387944159 , pp. 24-27 ( excerpt (Google) ).
Jason Rosenhouse: the Monty Hall Problem. Oxford University Press, 2009, ISBN 978-0-19-536789-8 , pp. 16-19 ( online copy of chapter 1 ( memento of April 30, 2011 in the Internet Archive ). (PDF; 275 kB), Preprint, there pp. 27-32).

Individual evidence

↑ Jason Rosenhouse: The Monty Hall Problem. Oxford University Press, 2009, p. 17.
^ Martin Gardner : Mathematical Games. Column in: Scientific American . October 1959, pp. 180-182.
^ Martin Gardner: Mathematical Games. Column in: Scientific American. November 1959, p. 188.

Web links

Google Books: "A wonderfully confusing little problem ..."
The Three Prisoners Problem Revisited: Issues in the use of Bayesian networks for security applications. (PDF; 184 kB).

[1] Jason Rosenhouse: The Monty Hall Problem. Oxford University Press, 2009, p. 17.

[2] Martin Gardner : Mathematical Games. Column in: Scientific American . October 1959, pp. 180-182.

[3] Martin Gardner: Mathematical Games. Column in: Scientific American. November 1959, p. 188.