# The prisoner paradox

I am given an exercise, and I can't quite figure it out.

### The Prisoner Paradox

Three prisoners in solitary confinement, A, B and C, have been sentenced to death on the same day but, because there is a national holiday, the governor decides that one will be granted a pardon. The prisoners are informed of this but told that they will not know which one of them is to be spared until the day scheduled for the executions.

Prisoner A says to the jailer “I already know that at least one the other two prisoners will be executed, so if you tell me the name of one who will be executed, you won’t have given me any information about my own execution”.

The jailer accepts this and tells him that C will definitely die.

A then reasons “Before I knew C was to be executed I had a 1 in 3 chance of receiving a pardon. Now I know that either B or myself will be pardoned the odds have improved to 1 in 2.”.

But the jailer points out “You could have reached a similar conclusion if I had said B will die, and I was bound to answer either B or C, so why did you need to ask?”.

What are A’s chances of receiving a pardon and why? Construct an explanation that would convince others that you are right.

You could tackle this by Bayes theorem, by drawing a belief network, or by common sense. Whichever approach you choose should deepen your understanding of the deceptively simple concept of conditional probability.

Here's my analysis:

This looks like the the Monty Hall problem, but not quite. If A says I change my place with B after he is told C will die, he has 2/3 chances to be saved. If he doesn't, then I would say his chances are 1/3 to live, like when you don't change your choice in the Monty Hall problem. But at the same time, he is in a group of 2 guys, and one should die, so it is tempting to say that his chances are 1/2.

So the paradox is still here, how would you approach this. Also, I have no idea how i could make a belief network about this, so i'm interested to see that.

• "He is in a group of 2 guys" does not imply "his chances are 1/2" – Henry Oct 20 '11 at 23:51

Initially there are three possibilities with equal probabilities:

• A will be freed (prob $1/3$)
• B will be freed (prob $1/3$)
• C will be freed (prob $1/3$)

With the promise of the message, there are four possibilities with different probabilities:

• A will be freed and A is told B will be executed (prob $1/6$)
• A will be freed and A is told C will be executed (prob $1/6$)
• B will be freed and A is told C will be executed (prob $1/3$)
• C will be freed and A is told B will be executed (prob $1/3$)

Conditional on "A is told C will be executed" this becomes

• A will be freed and A is told C will be executed (prob $1/3$)
• B will be freed and A is told C will be executed (prob $2/3$)

So after the message A would like to swap with B (the Monty Hall problem) but cannot and so keeps the original $2/3$ probability of being executed.

• A would like to swap with B is the key. To take one of the common Monty Hall explanations: Imagine there are 1000 prisoners: A asks the jailer who gives him 998 names. Clearly we just learned a lot about the one guy who is not A and who is not named. But we didn't learn anything about A. – Ben Jackson Oct 21 '11 at 16:40
• I think in A's position its a very good strategy for him to ask the guard this. Then later, talk to B and ask if he wants to switch. If he agrees, you guys can ask the executioners if, if either of them is to be freed, then free the other one. From B's perspective, his odds don't change, so there's no reason for him to say no (or to say yes, so its a matter of pressure at that point) – Cruncher Mar 12 '14 at 12:54

I think you are over-thinking the problem - it is a Monty Hall problem and the same logic applies.

• Can you develop ? I am interested by the reasoning, not the answer – Benjamin Crouzier Oct 20 '11 at 21:00
• @pinouchon: The Jailer is Monty Hall and Prisoner A is the player. Dieing is analogous to getting a goat; being pardoned is analogous to getting a prize. Now you can directly translate any explanation of the Monty Hall problem you like: that covers a lot of reasoning. +1 to babelproofreader for pointing this out. – whuber Oct 20 '11 at 21:03
• How would you argue against this statement: But at the same time, he is in a group of 2 guys, and one should die, so it is tempting to say that his chances are 1/2.. And what about the belief network ? – Benjamin Crouzier Oct 20 '11 at 21:16
• @Pinouchon It would be constructive to edit your question to focus on the belief network aspect. The Monty Hall problem itself has been discussed to death in many, many places, so I see no point in rehashing that material here. – whuber Oct 20 '11 at 21:40
• I agree that the Monty Hall problem has been discussed to death but despite babelproof's and whuber's assertions, I don't see where Prisoner A gets to switch places. If the jailer had three sealed envelopes, one containing a pardon and two containing death sentences, A picked one envelope, and the jailer opened another (exact same rules as I gave in a separate answer) and showed that it contained a death sentence, and then asked A "Would you like to keep the envelope you picked or would you rather switch?" I can see the analogy – Dilip Sarwate Oct 20 '11 at 23:53

The answer depends on how the jailer chooses which prisoner to name when he knows that A is to be pardoned. Consider two rules:

1) The jailer chooses among B and C at random, and just happened to say C in this case. Then A's chance of being pardoned is 1/3.

2) The jailer always says C. Then A's chance of being pardoned is 1/2.

All we are told is that the jailer said C, so we don't know which of these rules he followed. In fact, there could be other rules -- perhaps the jailer rolls a die and only says C if he rolls a 6.

I am not quite sure that I agree with @babelproofreader that this is a Monty Hall problem and the same logic applies. In the Monty Hall problem, you go down and select one door. The rules are that Monty knows where the prize is, will never open a door that conceals the prize, and will always open one of the unchosen doors (i.e. if you have chosen a door without a prize, he will not open the door you have chosen and say, "Sorry, you lose!" and send you back to your seat), and he will always offer the choice to switch to the other (unchosen unopened) door (i.e. he will not offer the choice only when you have chosen the door with the prize.) In these circumstances, if $A$ denotes the event that your initial pick is the the door with the prize, then $P(A) = \frac{1}{3}$. If $B$ is the event that your final pick is the door with the prize, then

• if your strategy is to always stay put, then $P(B \mid A) = 1$ (since you made the right choice in the beginning and are sticking with it) and $P(B \mid A^c) = 0$ (because you made a wrong choice in the beginning and are sticking with it). So by the law of total probability, $$P(B) = P(B \mid A)P(A) + P(B \mid A^c)P(A^c) = 1 \times \frac{1}{3} + 0\times \frac{2}{3} = \frac{1}{3}$$
• if your strategy is to always switch, then $P(B \mid A) = 0$ (since you made the right choice in the beginning and then switched) and $P(B \mid A^c) = 1$ (because you made a wrong choice in the beginning and so the remaining (unchosen unopened) door is guaranteed to have the prize). So by the law of total probability, $$P(B) = P(B \mid A)P(A) + P(B \mid A^c)P(A^c) = 0 \times \frac{1}{3} + 1\times \frac{2}{3} = \frac{2}{3}$$

Here, the situation is different. There is no changing places with $B$ as in "If A says I change my place with B after he is told C will die, he has 2/3 chances to be saved."

Added comments: Another difference is that A has no information as to whether the jailer knows who is going to be pardoned or whether the jailer is speaking the truth when he says that C will be executed. On the other hand, the jailer is perfectly correct when he remarks that his telling A that C will be executed has conveyed no useful information to A. The closest analogy to the Monty Hall problem is that after A has chosen a door, Monty opens an unchosen door to reveal a goat and says to A "Open your door and let's see what you got", that is, no offer of a switch. So A's chance of winning the prize (Monty Hall) or being pardoned (prisoner problem) are the same: $1$ out of $3$ regardless of whether Monty opens an unchosen door to reveal a goat or not, or the jailer tells A that C is going to be executed, or not, exactly as Henry computed in detail.

• I think we can assume that the jailer does have that information, otherwise the problem is not worth reasoning about (if the jailer has an unknown probability of lying, then they might as well not have said anything). As for your first point: sure, the outcome is different than in the Monty Hall problem because there is no option to switch. But the logic is the same: by revealing one option that isn't a winner, information is provided about another option that the jailer/Monty could have picked. – Ruben van Bergen Feb 11 '18 at 10:45

As pointed by others, the three prisoners problem is a rephrasing of Monty Hall. For more information, take a look at section 1.7 of this paper http://faculty.winthrop.edu/abernathyk/Monty%20Hall%20Problem.pdf

Imagine that the jailer tells A that C will definitely die. And then he tells B that C will definitely die. It is clear in this case that A and B has 50% each to be pardonned. But what is the difference between the two versions?

Three prisoners problem is different from Monty Hall. The probability to be pardoned is actually $1/2$ for Alice, not $2/3$, but only if jailer follows "always name Bob when possible" strategy.

Events: $A$ - Alice is pardoned. Same for $B$ and $C$. $J$ - jailer tells Alice the name "Bob" (as an answer to the "who will be executed"). $J^c$ - he tells name "Carl". He can't name Alice herself because of the rules.

We're interested in $P(A|J) = P(J|A)P(A)/P(J)$. Now there are two scenarios:

1. Jailer tosses a coin before telling B or C: $P(J|A) = \frac{1}{2}$.

$$P(A|J) = \frac{1}{2} \times \frac{1}{3} / \frac{1}{2} = \frac{1}{3}$$

1. Jailer tells Bob's name whenever possible: $P(J|A) = 1$, also $P(J|C) = 1$ and $P(J|B) = 0$.

$$P(J) = P(J|B)P(B) + P(J|B^c)P(B^c) = 0\times\frac{1}{3} + 1\times\frac{2}{3} = \frac{2}{3}$$

$$P(A|J) = 1 \times \frac{1}{3} / \frac{2}{3} = \frac{1}{2}$$

• Wouldn't "always name Carl when possible" be as plausible as "always name Bob when possible"? – Juho Kokkala Feb 11 '18 at 10:31
• Yes, the S' = "always name Carl if possible" strategy must be completely equivalent if we redefine J accordingly. If we leave J as it is and force jailer to follow S', it'll make everything pre-determined: whenever J (jailer says Bob), we know that it wasn't possible to say "Carl", thus Carl was pardoned. – Mikhail Volkhov Feb 11 '18 at 14:08

After receiving the information, that Prisoner C will die, his chances do change to 1/2, but only, because the chances that he gets that information is already 2/3 (the 1/3 possibility of prisoner C getting the pardon is eliminated)

And 2/3*1/2 is the original probability for getting freed.

More convincing is the oppositional approach:

Assume, that he is told prisoner C will get the pardon.
What are his chances not to be killed?
Everybody will acknowledge that his chances are zero, assuming the jailer doesn't lie and there is only one pardon.

This time, he has the chance of 1/1, because the chance for that information was already 1/3.

• This is not correct; see the calculation in Henry's answer which shows that after hearing the jailer's information, prisoner A has a 2/3 chance of dying (not 1/2). This is the same probability he had before, so the jailer is right: what he told A didn't change anything for A's odds of living. If B were listening in though, he would now know his chance of dying was reduced to 1/3. – Ruben van Bergen Feb 11 '18 at 10:50