The Three Prisoners problem appeared in Martin Gardner's "Mathematical Games" column in Scientific
American in 1959.
It is mathematically equivalent to the Monty Hall problem with car and goat replaced with
freedom and execution respectively, and also equivalent to, and presumably based on, Bertrand's
box paradox.
Problem Three prisoners, A, B and C, are in separate
cells and sentenced to death.
The governor has selected one of them at random to be pardoned.
The warden knows which one is pardoned, but is not allowed to tell.
Prisoner A begs the warden to let him know the identity of one of the others who is going
to be executed.
"If B is to be pardoned, give me C's name.
If C is to be pardoned, give me B's name.
And if I'm to be pardoned, flip a coin to decide whether to name B or C."
The warden tells A that B is to be executed.
Prisoner A is pleased because he believes that his probability of surviving has gone
up from 1/3 to 1/2, as it is now between him and C. Prisoner A secretly tells C the news,
who is also pleased, because he reasons that A still has a chance of 1/3 to be the pardoned
one, but his chance has gone up to 2/3.
What is the correct answer?
Solution The answer is that prisoner A didn't gain
information about his own fate.
Prisoner A, prior to hearing from the warden, estimates his chances of being pardoned as
1/3, the same as both B and C. As the warden says B will be executed, it's either because
C will be pardoned, or A will be pardoned and the B/C coin the warden flipped came up
B. Hence, after hearing that B will be executed, the estimate of A's chance of being pardoned
is half that of C.
This means his chances of being pardoned, now knowing B isn't, again are 1/3, but C
has a 2/3 chance of being pardoned.
Table The explanation above may be summarised in
the following table.
As the warden is asked by A, he can only answer B or C to be executed.
As the warden has answered that B will not be pardoned, the solution comes from the second
column.
It appears that the odds for A to be pardoned are 1:2.
Mathematical formulation Call , and the events that the corresponding
prisoner will be pardoned, and the event that the warden mentions prisoner B as the one
not being pardoned, then, using Bayes' formula, the posterior probability of A being pardoned,
is:
An intuitive explanation Prisoner A only has a 1/3 chance of pardon.
Knowing whether "B" or "C" will be executed does not change his chance.
After he hears B will be executed, Prisoner A realizes that if he will not get the pardon
himself it must only be going to C. That means there is a 2/3 chance for C to get a pardon.
This is identical to the Monty Hall Problem.
Enumeration of possible cases The following scenarios may arise:
A is pardoned and the warden mentions B to be executed: 12=1/6 of the cases
A is pardoned and the warden mentions C to be executed: 12=1/6 of the cases
B is pardoned and the warden mentions C to be executed: 1/3 of the cases
C is pardoned and the warden mentions B to be executed: 1/3 of the cases
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, the warden will say B because A will
be pardoned, and 1/6 of the time he will say C because A is being pardoned.
This adds up to the total of 1/3 of the time A is being pardoned, which is accurate.
It is now clear that if the warden answers B to A, cases 1 and 4, which happens 1/2 of
the time, 1/3 of the time C is pardoned and A will still be executed, and only 1/6 of
the time A is pardoned.
Hence C's chances are2)=2/3 and A's are2)=1/3.
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.
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 pardoned, warden says: B executed
A pardoned, warden says: C executed B pardoned, warden says: B pardoned
B pardoned, warden says: C executed C pardoned, warden says: B executed
C pardoned, warden says: C pardoned 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 occurring.
However, the warden in that case may not reveal the fate of a pardoned 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.
Similarly, in case 6, the warden must say B instead of C. That leaves cases 4 and 5
with 1/3 probability of occurring and leaves us with the same probability as above.
Why the paradox?
The tendency of people to provide the answer 1/2 neglects to take into account that the
warden may have tossed a coin before he gave his answer.
The warden may have answered because is to be released and he tossed a coin.
Or, is to be released.
The probabilities of the two events are not equal.
Judea Pearl used a variant of this example to demonstrate that belief updates must depend
not merely on the facts observed but also on the experiment that led to those facts.
Related problems and applications Bertrand's box paradox
Boy or Girl paradox Monty Hall problem
Principle of restricted choice, an application in the card game bridge
Prisoner's dilemma, a game theory problem Sleeping Beauty problem
Two envelopes problem Notes
References Frederick Mosteller: Fifty Challenging Problems
in Probability.
Dover 1987, ISBN 0-486-65355-2, p. 28-29 Richard Isaac: Pleasures of Probability.
Springer 1995, ISBN 978-0-387-94415-9, p. 24-27