Three Prisoners problem Information & Three Prisoners problem Links at HealthHaven.com

The Three Prisoners problem appeared in Martin Gardner's Mathematical Games column in Scientific American in 1959.^[1]^[2] It is mathematically equivalent to the Monty Hall problem with car and goat replaced with freedom and execution respectively, and also equivalent to, and assumedly based on, Bertrand's box paradox.

Out of three prisoners scheduled to be executed, A, B, and C, one of them will be pardoned. A asks the warden to tell him the name of one of the others who will be executed. As the question is not directly about A's fate, the warden obliges — either naming the other prisoner to be executed, if A is the one, or secretly flipping a coin to decide which of the remaining names to give A if A is the one being pardoned. Assuming the warden's truthfulness, there are now only two possibilities for who will be pardoned: A, and whichever of B or C the warden did not name. Did A gain any information as to his own fate, that is, does he change his estimate of the chances he will be pardoned? To make the analogy to the Monty Hall problem more explicit: if the warden says "B will be executed" and A could switch fates with C, should he?

[edit] Solution

The answer is he didn't gain information about his own fate, but he should switch with C if he can. Prisoner A, prior to hearing from the warden, estimates his chances of being pardoned as 1/3, the same as both B and C. If the warden says B will be executed, it's either because C will be pardoned (1/3 chance) or A will be pardoned (1/3 chance) and the B/C coin the warden flipped came up B (1/2 chance; for a total of a 1/6 chance B was named because A will be pardonned). Hence, after hearing who will be executed, A estimates his own chances of being pardoned as half that of whoever the warden didn't name. This means his chances of being pardoned, now knowing B isn't, again are 1/3, but whoever between B and C is not being executed has a 2/3 chance of being pardoned. Concerning switching fates, if the warden says "B will be executed" and A wants to live, he's better off switching fates with C.

Some may argue that this is not equivalent to the Monty Hall problem, pointing to the fact that the player in that game decides for himself which door to initially select and is given a subsequent opportunity to switch, whereas the prisoner to be pardoned has already been selected and cannot affect his fate.

However this criticism depends on A's expectations. Should he be more or less worried about his future after hearing the warden? Or, putting it another way, if he had to choose between keeping his fate the way it is after hearing the warden's response, or try to switch it with that of the other prisoner whose destiny is still unknown, should he?

[edit] Aids to understanding

As with the Monty Hall Problem, it may be useful to see this problem from alternative viewpoints for better understanding.

[edit] Bayesian analysis

An analysis using Bayesian probability theory begins by expressing the problem in terms of statements, or propositions, that may be true or false. Its goal is to compute the probability of these propositions, a number P in $[0,1]\,$ measuring our confidence in their truth in light of all the background information available to us. The problem at hand concerns propositions of the form:

$F_x\,$ : "x will be pardoned", for x equal to one of A, B or C.

$W_{yz}\,$ : "Replying to y, the warden states that z is executed", for y and z equal to any of A, B or C.

For example, $\!\,F_A$ denotes the proposition "A will be pardoned", and $W_{AB}\,$ denotes the proposition "Replying to A, the warden states that B is executed". In this context, "being pardoned" is the negative of "to be executed".

The background information consists of the rules of the game, henceforth denoted by $I\,$ . They impose the following constraints on the probability of such propositions. First, the three prisoners have, a-priori, the same chance of being pardoned, hence the prior probability of $\!\,F_x$ is:

$P(F_x|I) = \tfrac13\,$ .

Second, the warden is truthful, and will always name as executed a prisoner other than the one questioning him. If he has a choice of two such prisoners, they are equally likely to be named in his response. This rule concerns the conditional probability of a proposition $W_{yz}\,$ , conditioned on a proposition $F_x\,$ and $I\,$ :

$P(W_{yz} \| F_x, I)\,\, =\,\begin{cases} \, \\ \, \\ \, \\ \, \end{cases}$	$\!\,0$	if y = z, (the warden shall not reveal the asking prisoner that he is executed)
	$\!\,0$	if z = x, (the warden shall not lie, by indicating as executed a prisoner that, in fact, is to be pardoned)
	$\!\,\tfrac 12$	if y = x, (the prisoner who asks is to be pardoned, and the warden names either one of the others as executed)
	$\!\,1$	if y ≠x and y ≠ z, (prisoner z is the only one the warden can mention in reply)

Now assume, by renaming the prisoners if necessary, that A is the one questioning the warden, and B the one the warden names as executed. After the warden's reply, A's opinion about his chances of being pardoned are expressed by the posterior probability $P(F_A | W_{AB}, I)\,$ . Using Bayes' theorem this is expressed as:

$P(F_A|W_{AB}\,, I) = \frac{P(W_{AB}| F_A\,, I) \, P(F_A | I)}{P(W_{AB} | I)}$ .

By the rules stated above, the numerator of the right-hand side is:

$P(W_{AB}| F_A\,, I) \, P(F_A | I) = \tfrac12 \times \tfrac13 = \tfrac16$ .

The normalizing constant at the denominator can be evaluated by expanding it using the Law of total probability:

$\begin{array}{lcl} P(W_{AB}|I) &{}= &P(W_{AB}\,,\,F_A|I) + P(W_{AB},\,F_B|I) + P(W_{AB},\,F_C|I) \\ &{}= &P(W_{AB}|F_A\,,I) \, P(F_A|I)\, + \\ &&P(W_{AB}|F_B\,,I) \, P(F_B|I)\, + \\ &&P(W_{AB}|F_C\,,I) \, P(F_C|I) \\ &{}= &{\displaystyle \tfrac12 \times \tfrac13 + 0 \times \tfrac13 + 1 \times \tfrac13} = \ {\displaystyle\tfrac12\ .} \end{array}$

Dividing the numerator by the normalizing constant yields:

$P(F_A|W_{AB}\,,I) = \tfrac16\,/\,\tfrac12 = \tfrac13$ .

As the value of the posterior probability is equal to the prior one, this shows that the warden has given no additional information concerning As fate . Further, since B is executed, it is $P(F_B | W_{AB}\,,I) = 0$ . Hence the chances that C is to be pardoned are, in As opinion,

$P(F_C | W_{AB}\,,I) = 1 - P(F_B | W_{AB}\,,I) - P(F_A|W_{AB}\,,I) = 1 - 0 - \tfrac13 = \tfrac23$ .

Therefore A must judge it safer to try switch his fate with C 's.

[edit] Enumeration of possible cases

Consider the following three scenarios:

a B C [B/C] (1/3)
A b C [C] (1/3)
A B c [B] (1/3)

This diagram is to be read as follows: Lowercase is for the prisoner being pardoned, while a capital letter means capital punishment. Between brackets is the name of the prisoner revealed as being executed by the warden when A asks. It is straightforward: each prisoner has a 1/3 chance of being pardoned. If either prisoner B or C is to be pardoned, there is 100% probability the warden will say the name of the other (he must). However, if prisoner A is to be pardoned, the warden may answer either B or C. He has a choice to make. This leaves us with four cases:

a B C [B] (1/3 * 1/2 = 1/6)
a B C [C] (1/3 * 1/2 = 1/6)
A b C [C] (1/3)
A B c [B] (1/3)

With the stipulation that the warden will choose randomly, in the 1/3 of the time that A is to be pardoned, there is a 1/2 chance he will say B and 1/2 chance he will say C. This means that taken overall, 1/6 of the time (1/3 [that A is pardoned] * 1/2 [that warden says B]), the warden will say B because A will be pardoned, and 1/6 of the time (1/3 [that A is pardoned] * 1/2 [that warden says C]) he will say C because A is being pardoned. This adds up to the total of 1/3 of the time (1/6 + 1/6) A is being pardoned, which is accurate.

It is now clear that if the warden answers B to A, 1/3 of the time C is pardoned and A will still be executed (case 3 above); But only 1/6 of the time A is pardoned and the warden randomly chose to say the name B.

It is important to note that this problem is intended to denote a one-time situation. If this problem is repeated many times, we can see that in the long run, the probabilities balance out. For example, instead of executions, consider that the prisoners will be tortured, with one randomly selected prisoner exempted each day. In the cases where the warden named B to be tortured, there is a 2/3 chance for C to avoid torture and a 1/3 chance for A (just as in the previous problem). There is also the unstated 0 possiblity for B to avoid torture. In the opposite case, where the warden names C, B has a 2/3 chance of avoiding torture, and A has a 1/3 chance, with 0 chance for C. The average for both situations (since each has a 1/2 probability of occuring) is that each of A, B and C end up with a 1/3 chance of avoiding torture each day.

The key to this problem is that the warden may not reveal the name of a prisoner who will be pardoned. If we eliminate this requirement, it can demonstrate the original problem in another way. The only change in this example is that prisoner A asks the warden to reveal the fate of one of the other prisoners (not specifying one that will be executed). In this case, the warden flips a coin chooses one of B and C to reveal the fate of. The cases are as follows:

a B C [B - executed] (1/6)
a B C [C - executed] (1/6)
A b C [B - pardonned] (1/6)
A b C [C - executed] (1/6)
A B c [B - executed] (1/6)
A B c [C - pardonned] (1/6)

The square brackets represent which prisoner whose fate is revealed and what that fate is. Each scenario has a 1/6 probability. The original Three Prisoners problem can be seen in this light: The warden in that problem still has these six cases, each with a 1/6 probability of occuring. However, the warden in that case may not reveal the fate of a pardonned prisoner. Therefore, in the 1/6 of the time that case 3 occurs, since saying B is not an option, the warden says C instead (making it the same as case 4). Similarly, in case 6, the warden must say B instead of C (the same as case 5). That leaves cases 4 and 5 with 1/3 probability of occuring and leaves us with the same probability as above.

[edit] Why the paradox?

The tendency of people to provide the answer 1/2 neglects to take into account the query that the warden was asked. Had the query been: "Will $B$ be executed?" then the warden's answer "Yes, $B$ will be executed" would indeed result in a probability 1/2 for $A$ 's death. Judea Pearl (1988)^[3] used a variant of this example to demonstrate that belief updates must depend not merely on the facts observed but also on the experiment (i.e., query) that led to those facts.

[edit] References

^ Gardner, Martin (1959a). "Mathematical Games" column, Scientific American, October 1959, pp. 180–182.
^ Gardner, Martin (1959b). "Mathematical Games" column, Scientific American, November 1959, p. 188.
^ Pearl, J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, San Mateo, CA: Morgan Kaufmann Publishers, Inc., First Edition, 1988.

[edit] Also see

Prisoner's dilemma, a game theory problem

[0] Gardner, Martin (1959a). "Mathematical Games" column, Scientific American, October 1959, pp. 180–182.

[1] Gardner, Martin (1959b). "Mathematical Games" column, Scientific American, November 1959, p. 188.

[2] Pearl, J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, San Mateo, CA: Morgan Kaufmann Publishers, Inc., First Edition, 1988.

[1]

[2]

[3]

Contents