Probability and the Prisoner Problem

Date: 07/04/2001 at 22:39:45
From: Nick Martin
Subject: Probability and the "Prisoner Problem"

Hi. This is a problem that was posed a few months ago at a lecture 
attended by a friend of mine. The lecturer didn't give the answer; she 
couldn't work it out and after putting our heads together with several 
others', we're still coming up empty. Maybe you can help.

Sixteen prisoners are assembled and told the following: Each will 
receive a hat that is either red or blue (the colour is selected 
randomly and each has a 1/2 probability.) Then, all the prisoners must 
simultaneously either:

- Try to guess the colour of their hats, or
- Pass.

The prisoners will be set free if

- at least one person guesses, AND
- nobody guesses wrong.

Otherwise, they will be executed.

The prisoners may consult beforehand to decide on a strategy, but they 
will be unable to communicate in any way after the hats are put on; 
and all must answer simultaneously.

Apparently, there exists some strategy that will give the prisoners 
a probability of survival greater than 90%.

We eventually discovered a solution for only three people: each 
person follows the following strategy:

- If both of the other people have the same colour hat, guess the 
  opposite colour.

- If the other two people have different-coloured hats, pass.

The prisoners will be set free unless they all wear the same colour 
hat (75%).

Attempts to extend this further to more people, however, only lowered 
the probability, and the best we can do with sixteen people is still 
75% (by having thirteen people all pass, and the other three simply 
follow the above strategy).

I've also been told that the situation is "best" when there are 
(2^n-1) prisoners, but work on a 7-person solution went nowhere 
either.

Help!

Date: 07/10/2001 at 13:18:35
From: Doctor Rick
Subject: Re: Probability and the "Prisoner Problem"

Hi, Nick, thanks for writing to Ask Dr. Math with a great problem!

This is an interesting problem! It is contrary to my (trained) 
intuition that one can do any better than a 50% probability of 
surviving. Given that the assignment of hat colors is completely 
independent, a prisoner's knowledge of other prisoners' hat colors 
cannot skew the probability of his own hat color away from 1 in 2. 
Part of the solution must be to explain where my intuition went wrong.

I have played with the problem quite a bit in the past 6 days. I 
haven't reached the end yet, but I have learned a lot. I wrote down my 
thoughts along the way, so you can see my problem-solving technique, 
as far as it goes.

Considering the scheme you present for 3 prisoners, which gives a 75% 
probability of survival, we can get a hint as to how the odds can be 
beaten. Here are the 8 cases, with the guesses each prisoner makes 
("-" means pass):

  R R R   B B B (all wrong)
  R R B   - - B (correct)
  R B R   - B - (correct)
  R B B   R - - (correct)
  B R R   B - - (correct)
  B R B   - R - (correct)
  B B R   - - R (correct)
  B B B   R R R (all wrong)

We see that a total of 12 guesses are made, and in fact half of them 
are wrong! There is nothing counterintuitive about the individual 
guesses. What skews the probability of survival is that all the wrong 
guesses are concentrated in only 1/4 of the possible states, while the 
correct guesses are distributed evenly among the remaining states.

Let's consider whether we have any hope for a strategy along these 
lines. What happens when we go to N prisoners? There are 2^N possible 
states. If we want the wrong guesses to occur in 2^N/10 or fewer 
states, then there can be at most N*2^N/5 guesses. This is because 
there are at most N*2^N/10 guesses in the 2^N/10 states, and the 
number of right guesses will equal the number of wrong guesses.

On the other hand, death also follows in a state for which *no* guess 
is made. Thus we want at least one guess in each state. Thus we have 
a lower limit on the number of guesses, namely (N+9)*2^N/10: the 
N*2^N/10 wrong guesses, and one each in the (9/10)*2^N other states. 
If the total number of guesses is G, then

  (N+9)*2^N/10 < G < N*2^N/5

There will be numbers in this range if 

  N+9 < 2N

Thus, I conclude that, if my scenario for "beating the odds" is the 
way to go, we can only possibly exceed 90% success if N > 9. Your 75% 
success is pretty good for only 3 prisoners. And this gives me a 
little hope that we may actually have a *better* chance the higher the 
number of prisoners ... if we can come up with a strategy.

Let the number of cases in which wrong guesses are made be M. Then 
each prisoner will make a guess in 2M states. M of these guesses will 
be correct, and the other M states will differ only by the color of 
the prisoner's own hat. The M states in which a prisoner makes a 
correct guess will be different for each prisoner, so that there are 
NM such states. The total number of states is thus NM+M, or M(N+1). We 
know there are 2^N states, so that

  2^N = M(N+1)

We cannot achieve equality in general. We must choose the smallest M 
greater than 2^N/(N+1) so that all states are covered.

  N   2^N/(N+1)            M
------------------------------
  3   8/4                  2 (exact)
  4   16/5 = 3.2           4
  5   32/6 = 5.3           6
  6   64/7 = 9.1          10
  7   128/8 = 16          16 (exact)
  8   256/9 = 28.4        29
...
 15   32768/16 = 2048   2048 (exact)
 16   65536/17 = 3855.1 3856

I'm feeling good about this - the values of N that yield exact matches 
(so that we might actually have exactly one prisoner guess in each of 
the NM correct states) are just those that the hint said were best!

Now perhaps we can try a particular case - the next "exact" case, 
N = 7. We want to pick 16 out of the 2^7 = 128 "sacrificial" states, 
in which all will guess wrong. Each of the other 112 states should 
differ from one of the 16 in just one hat color. The 16 states must 
differ from each other in two or more hat colors.

I'll start by picking RRRRRRR and BBBBBBB to be two of the 16. No 
state with exactly one R or one B can then be among the 16. Let's try 
states that are nearly evenly divided, having 3 or 4 Red hats. How 
many of these are there? There are 7!/(3! 4!) = 35 states of each 
type. That's too many. 

Let's try a set of states that is closed under rotation among the 
prisoners. Here's what I mean: If the prisoners stand in a circle and 
their hats are in the set of 16, then if each gave his hat to the 
prisoner to his left, the set would again be in the set. 

RRRRRRR and BBBBBBB have this property themselves: if you rotate the 
state RRRRRRR, you get RRRRRRR again. Any other state is part of a 
closed set of 7 states, generated by rotating the state successively 
6 times. Thus the closed set of 16 states that we need can be formed 
of RRRRRRR, BBBBBBB, and two 7-member closed sets, such as:

RRRRRRR  RRBBBBB  BBRRRRR  BBBBBBB
         BRRBBBB  RBBRRRR
         BBRRBBB  RRBBRRR
         BBBRRBB  RRRBBRR
         BBBBRRB  RRRRBBR
         BBBBBRR  RRRRRBB
         RBBBBBR  BRRRRRB

Since none of these states differs from another by only one hat color, 
this set should work. All we need now is a set of rules such that each 
prisoner will guess incorrectly in these states. These rules do the 
trick:

  If you see all the same color hat, guess the opposite color.
  If you see only one hat of one color, guess the other color.
  If you see two hats of the same color together and the rest the
    other color, guess the same color as the two hats.

Take any one prisoner. If the hats are in any of the 12 states listed 
above, he will guess incorrectly. For each of these states, there is 
another in which he will make the same guess, but it will be correct; 
and he will be the only one who guesses, so all will be freed. In the 
12 states listed, all 7 prisoners will simultaneously guess wrong, so 
they will be executed. The deadly states are 16/128 = 1/8 of the 
states, so with 7 prisoners we have a probability of 7/8 = 87.5% that 
the prisoners will be freed if they use my strategy.

We don't yet have a general strategy that will work with any number of 
prisoners. Before thinking about "inexact" numbers, let's consider the 
next "exact" number, N = 15. In this case, M = 2^15/16 = 2^11 = 2048. 
We need to choose a set of 2048 states that is closed under rotation, 
so that all 15 prisoners, using the same rules, will guess wrong in 
these states. 

This is where I bogged down. I tried endless approaches to identifying 
subsets of hat states that total 2048, without complete success yet. 
Here is one approach that came closest so far.

What I did with N = 7 was to take the states with 0 red or 0 blue 
hats, and a subset of the states with 2 red or 2 blue hats. Let's take 
a look at the numbers of states with K red hats:

 0      1
 1     15
 2    105
 3    455
 4   1365
 5   3003
 6   5005
 7   6435
 8   6435
 9   5005
10   3003
11   1365
12    455
13    105
14     15
15      1
    -----
    32768

Perhaps we can find a subset of the 3003 states with 5 red hats that 
will come close in size to the 2048 we need. One way to create subsets 
while maintaining the closure under rotation is to restrict the 
pattern of adjacent red hats around the circle. For instance, we could 
require 2 red hats together, and another 3 red hats together but not 
adjacent to the two.

Place the 10 blue hats in a row, creating 11 sites (between the blue 
hats and at the ends) where we can put a cluster of red hats. We find 
the following numbers of states with the possible clustering patterns:

  5 R together:      P(11,1) =     11
  4 + 1:             P(11,2) =    110
  3 + 2:             P(11,2) =    110
  3 + 1 + 1:         P(11,3)/2 =  495
  2 + 2 + 1:         P(11,3)/2 =  495
  2 + 1 + 1 + 1:     P(11,4)/6 = 1320
  1 + 1 + 1 + 1 + 1: C(11,5) =    462
                                 ----
                                 3003

The total is correct, but the subsets need some tweaking. Some of our 
states have a cluster of red hats at both ends, which (when the 
prisoners form a circle) will become a single cluster. Thus, some 
states must be moved up to another subset. We need to move two of the 
4+1 states (those with 4 R's at the left and 1 at the right, and vice 
versa) and two of the 3+2 states up to the 5-R subset, making the 15 
states that we knew there should have been. Likewise, we must move

   - two 3+1+1 states (3-1, 1-3) and one 2+2+1 state (2-2) to the 
     4+1 subset,
   - a 3+1+1 state (1-1) and two 2+2+1 states (1-2, 2-1) to the 
     3+2 subset,
   - two 2+1+1+1 states (2-1 and 1-2) to the 3+1+1 subset,
   - one 2+1+1+1 state (1-1) to the 2+2+1 subset,
   - and one 1+1+1+1+1 state to the 2+1+1+1 subset.

Our counts become

  5 R together:        11 + 2 + 2 =   15
  4 + 1:              110 - 2 + 3 =  111
  3 + 2:              110 - 2 + 3 =  111
  3 + 1 + 1:          495 - 3 + 2 =  494
  2 + 2 + 1:          495 - 3 + 1 =  493
  2 + 1 + 1 + 1:     1320 - 3 + 1 = 1318
  1 + 1 + 1 + 1 + 1:  462 - 1     =  461
                                    ----
                                    3003

We can do the same analysis on the sets with other numbers of red hats 
if necessary. Then we look for a small number of subsets whose counts 
add to 2048. One solution is 

  4 red hats            1365
  5 R, none together     461
  5 R, in two clusters   222 (3+2 or 4+1)
                        ----
                        2048

To generate this set of "sacrificial" states, we can write the first 
rule for those who have a blue hat:

  If you see 4 red hats, or 5 red hats with no two neighbors having 
  red hats, or 5 red hats in two clusters, then guess that you have a 
  red hat. 

This guess will be wrong if it is one of the "sacrificial" states 
listed above. A prisoner who is wearing a red hat must also make a 
guess. What rule will achieve this? 

  If you see 3 red hats, or 4 red hats that (supposing that you also
  have a red hat) are all separated by blue hats, or 4 red hats all in
  a group (not including your neighbors), or 4 red hats in two groups
  (one of which may include one or both neighbors), then guess that 
  you have a blue hat.

What a mess! There must be a better way - can you find one?

Before I end this report, let's think a bit about solutions when N is 
not one less than a power of 2. You came up with a method for these 
cases: the prisoners select 2^K-1 of their number to do the guessing, 
based on the hats they see on the others of this same set, while the 
other N-(2^K-1) prisoners sit it out. Using this method, 16 to 30 
prisoners have the same probability of freedom as 15 prisoners, namely 
1/16. Is this the best that can be done? Going back to my early 
calculations, I found that for N = 16, the optimal number of 
"sacrificial" states M is 3856. The optimal probability is thus 
3856/65536 = 0.058838 = 1/16.996. We should be able to do a little 
better than 1/16. Still, we've done significantly better than 90% 
success, even with the less-than-optimal solution.

I'd like to close this out by finding a really good solution to the 
puzzle. If you can come up with one, please write back and let us 
know. Also, the contents of the lecture in which this puzzle was 
presented might provide a clue to the solution, so perhaps you could 
let me know more about it.

- Doctor Rick, The Math Forum
  http://mathforum.org/dr.math/   

Date: 07/12/2001 at 09:34:38
From: Doctor Rick
Subject: Re: Probability and the "Prisoner Problem"

Hi again, Nick.

I have more to report on your "Prisoner Problem." Another Math Doctor, 
finding the problem intriguing, searched the Web to see if it was a 
hot topic in the math community. Indeed it is! It even made the New 
York Times science section on April 10, 2001. Here is an article by 
Todd Ebert of the University of California at Irvine, who says he 
invented the puzzle.

  The Colored Hats Puzzle
  http://www.ics.uci.edu/~ebert/teaching/spring2001/ics151/puzzles.html   

As it turns out, in order to come up with a truly satisfying and 
general solution to the problem on my own, I would have had to 
reinvent a mathematical concept called the Hamming code. This is a 
technique used to encode data (being transmitted from a space probe to 
earth, for example) in such a way that an error in a single bit out of 
N bits can be detected and corrected automatically. Here is an 
explanation of how a Hamming code works.

  Error Correction and the Hamming Code (University of New Brunswick)
  http://www.ee.unb.ca/tervo/ee4253/hamming.htm   

This page details the (7,4) Hamming code, which uses 7 bits to encode 
4 data bits. The other 3 bits are used to determine whether the 7 bits 
were transmitted correctly, or if not, which of the 7 bits is in 
error. (If more than one bit is in error, the code will not be 
corrected correctly.) Out of the 128 possible 7-bit codewords, 16 are 
valid. Sound familiar? 

When there are 7 prisoners, the winning strategy is to guess one's hat 
color such that the hats on all the prisoners' hats (letting red be a 
0 bit and blue be a 1 bit) represent a Hamming code with an error. 
Then if the hats represent a valid Hamming code, all will guess wrong; 
but if not, then the prisoner corresponding to the erroneous bit will 
guess correctly.

The rule for 7 prisoners thus is (see the link for more details):

Put the prisoners in a pre-determined order, 1 to 7. Assume that you 
have a red hat, and generate a 3-bit binary number as follows:

The ones bit is 1 if among prisoners 1, 3, 5, and 7 there is an odd 
number of blue hats (1).

The 2s bits is 1 if among prisoners 2, 3, 6, and 7 there is an odd 
number of blue hats.

The 4s bit is 1 if among prisoners 4, 5, 6, and 7 there is an odd 
number of blue hats.

Generate a second 3-bit number using the same rules but assuming that 
you have a blue hat. Then look at the two numbers. If neither is zero, 
PASS. IF one is zero, then that is the valid Hamming code. You want to 
guess that the code has an error, so guess the hat color that led to 
the non-zero number.

This rule looks much more complicated than my rule for 7 prisoners! 
The great thing about it is that it is extensible to any number of 
prisoners of the form 2^k-1. The numbers you generate will have k bits 
in general.

Here are the 16 valid (7,4) Hamming codes -- the hat patterns for 
which all prisoners guess incorrectly:

  0 0 0 0 0 0 0
  0 0 0 1 1 1 1
  0 0 1 0 1 1 0
  0 0 1 1 0 0 1
  0 1 0 0 1 0 1
  0 1 0 1 0 1 0
  0 1 1 0 0 1 1
  0 1 1 1 1 0 0
  1 0 0 0 0 1 1
  1 0 0 1 1 0 0
  1 0 1 0 1 0 1
  1 0 1 1 0 1 0
  1 1 0 0 1 1 0
  1 1 0 1 0 0 1
  1 1 1 0 0 0 0
  1 1 1 1 1 1 1

The bits are numbered 1-7 left to right. The valid codes have an even 
number of 1's (0 parity) in each of the three groups of bits listed in 
the rule.

The incorrectly guessed codes in my solution, for comparison, look 
like this:

  0 0 0 0 0 0 0
  1 1 0 0 0 0 0
  0 1 1 0 0 0 0
  0 0 1 1 0 0 0
  0 0 0 1 1 0 0
  0 0 0 0 1 1 0
  0 0 0 0 0 1 1
  1 0 0 0 0 0 1
  0 0 1 1 1 1 1
  1 0 0 1 1 1 1
  1 1 0 0 1 1 1
  1 1 1 0 0 1 1
  1 1 1 1 0 0 1
  1 1 1 1 1 0 0
  0 1 1 1 1 1 0
  1 1 1 1 1 1 1

I believe this solution is equally valid; the problem with it is that 
it is not extensible. It gave me no clue as to how to deal with 15 
prisoners.

This certainly is a fascinating problem. It starts out looking 
paradoxical: how can the prisoners possibly do better than 50-50? It 
ends up teaching us something about a very practical application of 
mathematics in this information age: error-correcting codes. I hope 
you will explore this field further! For one thing, I have not touched 
the question of how to handle the 16 prisoners in your version of the 
problem. I have ideas, but I'll leave it to you.

- Doctor Rick, The Math Forum
  http://mathforum.org/dr.math/