The 100 prisoner problem is considered one of the best examples of a game theory problem where a different stategy greatly changes the probability of success. In 2003 Danish computer scientist Peter Bro Miltersen published a paper that studied "time-space tradeoffs for static data structure problems". To demonstrate some results, he introduced a game in which one player randomly places one of two colored slips of paper in boxes. A second player opens some of the boxes and makes a best guess of the contents of the remaining boxes. He gave an upper bound for the probability of player 2 being correct that decreased very rapidly with the number of boxes.

He then conjectured that if player 2 was replaced by a team of players independently opening boxes, the results would be similar. His collegue Sven Skyum pointed out to him that this is not necessarily true and that the probability of team success could be much greater than expected.

The 100 prisoner problem evolved from Miltersen's problem to demonstrate Skyum's remarkable observation.

The director of a prison offers 100 death row prisoners, who are numbered from 1 to 100, a last chance. A room contains 100 boxes. The director randomly puts one prisoner's number in each closed box. The prisoners enter the room, one after another. Each prisoner may open and look into 50 boxes in any order. The boxes are closed again afterwards. If, during this search, every prisoner finds his number in one of the boxes, all prisoners are pardoned. If just one prisoner does not find his number, all prisoners die. Before the first prisoner enters the room, the prisoners may discuss strategy but may not communicate once the first prisoner enters to look in the boxes. What is the prisoners' best strategy?

Suppose that the prisoners follow the naive strategy of each prisoner randomly choosing 50 of the 100 boxes. Each has a probability of .5 of finding his own prisoner number and since they are choosing randomly, these events are independent. Thus the probability of all succeeding is .5 ¹⁰⁰ ≈ 7.9 × 10 ^-31 . This is a very small number that gives the prisoners no hope of success. Just to dramatize how small this number is, the number of seconds since the big bang is approximately 4.4 × 10 ¹⁷ . So if this process was repeated every second since the big bang the probability of even one success is on the order of 10 ^-13 .

No matter what strategy we use, the probabilty of any given prisoner succeeding is

50

100

= .5. Our only way to significantly improve their chances is to make the events highly dependent (despite the fact that the prisoners do not communicate).

The strategy we choose is the following. Let each prisoner go to the box labeled with his prisoner number. If the number inside that box is his prisoner number, then he was successful; otherwise, the prisoner goes to the box labeled with the number inside the first box. The process is repeated until he finds his prisoner number or he has opened 50 boxes. If he finds his box within 50 tries he is successful; otherwise, he has failed and the game is over. The prisoners win their freedom only if all 100 prisoners successfully find their number.

At first thought, this does not seem to be a better strategy than the previous one. But let's check it out.

Recall that the director randomly puts one prisoner's number in each box. So each box must contain one number and no two boxes can contain the same number. This greatly limits the paths that a prisoner can take through the boxes. For example the path 42, 26, 53, 82, 12, 26 looks like this. This path is impossible because both boxes 12 and 42 must contain 26.

The path 92, 31, 14, 82, 31, 12 looks like this. This path is also impossible. Box 12 must contain some number. That number cannot be 12 since both boxes 34 and 12 would contain 12. So the path must continue to 92 or somewhere it hasn't gone before. In either case, the path eventually comes back to 92 without revisiting any of the other boxes.

The only paths possible are cycles of length from 1 to 100. And no two cycles may intersect. The prisoners will succeed if and only if, no cycle has length greater than 50. Start

We know that the paths that the prisoners take through the boxes are cycles with lengths between 1 and 100 and that any two distinct cycles are disjoint. This tells us that the prisoners succeed if and only if the maximum cycle length in their permutation is less than or equal to 50.

Let's look at the simpler case of 4 prisoners. The following table gives the possible permutations of the numbers with the possible cycles.

	Permutation	Cycles	Cycle Length	Max Length
1	1, 2, 3, 4	1;  2;  3;  4	4, 0, 0, 0	1
2	1, 2, 4, 3	1;  2;  4,3	2, 1, 0, 0	2
3	1, 3, 2, 4	1;  3,2;  4	2, 1, 0, 0	2
4	1, 3, 4, 2	1;  3,4,2	1, 0, 1, 0	3
5	1, 4, 2, 3	1;  4,3,2	1, 0, 1, 0	3
6	1, 4, 3, 2	1;  4,2;  3	2, 1, 0, 0	2
7	2, 1, 3, 4	2,1;  3;  4	2, 1, 0, 0	2
8	2, 1, 4, 3	2,1;  4,3	0, 2, 0, 0	2
9	2, 3, 1, 4	2,3,1;  4	1, 0, 1, 0	3
10	2, 3, 4, 1	2,3,4,1	0, 0, 0, 1	4
11	2, 4, 1, 3	2,4,3,1	0, 0, 0, 1	4
12	2, 4, 3, 1	2,4,1;  3	1, 0, 1, 0	3
13	3, 1, 2, 4	3,2,1;  4	1, 0, 1, 0	3
14	3, 1, 4, 2	3,4,2,1	0, 0, 0, 1	4
15	3, 2, 1, 4	3,1;  2;  4	2, 1, 0, 0	2
16	3, 2, 4, 1	3,4,1;  2	1, 0, 1, 0	3
17	3, 4, 1, 2	3,1;  4,2	0, 2, 0, 0	2
18	3, 4, 2, 1	3,2,4,1	0, 0, 0, 1	4
19	4, 1, 2, 3	4,3,2,1	0, 0, 0, 1	4
20	4, 1, 3, 2	4,2,1;  3	1, 0, 1, 0	3
21	4, 2, 1, 3	4,3,1;  2	1, 0, 1, 0	3
22	4, 2, 3, 1	4,1;  2;  3	2, 1, 0, 0	2
23	4, 3, 1, 2	4,2,3,1	0, 0, 0, 1	4
24	4, 3, 2, 1	4,1;  3,2	0, 2, 0, 0	2
			24, 12, 8, 6

We count the number of permuations with a given maximum length and get 1, 9, 8, and 6 respectively. This tells us that the probability of longest cycles of length k is ¹/₂₄ , ⁹/₂₄ , ⁸/₂₄ , and ⁶/₂₄ respectively. The probability that the prisoners succeed is ¹/₂₄ + ⁹/₂₄ = ¹⁰/₂₄ ≈ .4167.

Note for future reference that a given number appears in a cycle of length k (not necessarily of maximum length k) exactly 6 times.

 

 

We consider the general case of n boxes. Let N(n,k) denote the number of cycles of length k. We can choose the numbers in the cycles ways. We can arrange the k boxes in the cycle ways and we can arrange the remaining boxes ways. Then by the counting principle,

N(n,k) = C(n,k)(k-1)!(n-k)! =

n! (k-1)! (n-k)!

k! (n-k)!

=

n! (k-1)!

k !

=

n!

k

.

Notice that when n=4, this gives the 24, 12, 8, and 6 on the previous page.

However, this tells us the number of cycles of a given length but not necessarily the number of cycles with k as the maximum length. But, if each of the k cycles must be of maximum length since the remaining boxes could not have a cycle of length greater than or equal to k.

It follows for the probability of a maximal cycle of length k is Note that this is independent of n. For n = 4, P(k ≤ 2) = 1 - [1/3 + 1/4] ≈ 1 - .5833 = .4167. And for 100 prisoners,

Wow! While the odds are still against them, the prisoners went from no chance of success to a reasonable chance with this simple change in strategy.

The case where is much more difficult. We discuss this case for completeness but it is not needed to solve the problem as stated.

Let L(n,k) denote the number of times that k is the maximum cycle length for n boxes. The following recursive formula gives the number of partitions of n that have a maximum length of k and is presented with the derivation discussed later.

L(n,k) =

⌊ n/k ⌋

∑

j=1

n!

j! kj (n-jk)!

min(k-1,n-kj)

∑

t=1

L(n-kj,t)
where

0

∑

t=1

is interpreted as 1^a. To use a recursive formula, you must know some "base" values. In this case it is sufficient to know for all n. We use this formula when k ≤ ⁿ/₂. Note that we already have the formula when

Of course once is computed, the probability that k is a maximum cycle length can be found by dividing by n!.

We give an example of using the recursive formula:
L(n,k) =

⌊ n/k ⌋

∑

j=1

n!

j! kj (n-jk)!

min(k-1,n-kj)

∑

t=1

L(n-kj,t) .

We calculate L(7,3).

L(7,3)	=	2 ∑ j=1 7! j! 3j (7-3j)! min(2,7-3j) ∑ t=1 L(7-3j,t)	1
	=	7! 1! 31 4! [ L(4,1) +L(4,2) ] + 7! 2! 32 1! [ L(1,1) ]	2
	=	70[1 + L(4,2)] + 280 • 1	3

We now calculate L(4,2).

L(4,2)	=	2 ∑ j=1 4! j! 2j (4-2j)! min(1,4-2j) ∑ t=1 L(4-2j,t)	4
	=	4! 1! 21 2! [ L(2,1) ] + 4! 2! 22 0! • 1	5
	=	6 + 3 = 9	6

We plug 9 into line 3 and get = 700 + 280 = 980.

This recursive formula is difficult to use by hand but is easy to program into a computer.

 

 

In 1997, S. W. Golomb and P. Gaal of the University of Southern California, published a paper in Probabilistic Methods in Discrete Mathematics entitled On The Number of Permutations of n Objects With Greatest Cycle Length k in which they derived the general formula where k ≤ ⁿ/₂. Their method involved building up to the result by considering cases ⁿ/₃ < k ≤ ⁿ/₂, ⁿ/₄ < k ≤ ⁿ/₃, and so on. The computation was long and nasty.

With the benefit of hindsight from the formula, a perhaps more esthically pleasing method of deriving the formula has evolved. If we let

L_j(n,k) = , then it turns out that the formula gives the number of permutations of n things with maximum cycle length k where cycles of length k occur exactly j times.

Each L_j(n,k) can be generated by decomposing previous values of L(n,k). While this method is beyond the scope of this page, we will give a simple example of decomposing a value of L(4,3) to get a corresponding value of L(7,3). Consider the permutaion 2,1,4,3. This gives two cycles of length 2; namely 2,1; 4,3. We could add three elements, 5, 6, and 7, to this permuation like following: 2,5,1; 4,6,3; 8 to get two cycles of length 3 and one of length 1. Of course there are many rearrangements of this permutation that produce the same pattern of two cycles of length 3 and one of length 1.

By decomposing earlier permutations in a very carefull way, it is possible to generate each L_j(n,k). Perhaps the biggest obstacle is to guarantee that each permulation is generated only once.

 

 

We estimate the probability distribution by creating random permutations of the numbers in the boxes.

It seems intuitively obvious that as the number of prisoners increases, the likelyhood of success should decline.

n	P(x ≤ n/2 )	value
10		.3544
100		.3118
1000		.3074
10000		.3069

The prisoners, being mainly politicians and lawyers, decide to negotiate with the director to be allowed to open more than 50 boxes before failing. How many boxes should they seek in order for the group to have at least a 50% chance of success?

---

Prisoner 13 has a mentor who is on death row in a much larger prison. This mentor is trying to get his prison director to offer the same chance at release. With 100 prisoners, opening 61% of the boxes gives at least a 50% chance of success. What percentage of the number of boxes should the mentor ask to open in order to have at least a 50% chance of success?

---

In this case, the prison director does not have to distribute the numbers into the boxes randomly, and realizes that the prisoners may apply strategy given here, so he creates a cycle of length greater than 50. Can the prisoners still succeed?

---

In this case, one prisoner may enter the room first, inspect all boxes, and then switch the contents of two boxes. What is the probabilty that the prisoners succeed?

---

After a given prisoner has taken his turn in the room, then if his cycle length is greater than 50, he knows that all prisoners are doomed. If his cycle length is less than or equal to 50, what is the probability of success given his cycle length?

---

Suppose that after the first prisoner leaves the room, the remaining prisoners can see by where he was lead afterwards whether his cycle length is less than or equal to 50. Given that it was, what is the probability of success for the prisoners?

---

Suppose that the director changes his mind about all prisoners needing to succeed and instead lets any prisoner go free who finds his number by opening at most 50 boxes. How much advantage will the cycle method give over opening 50 random boxes?

---

On the previous page, we saw that the probability of a prisoner being in a cycle of a given length k is no matter the value of k. So the probability of a given prisoner being in a cycle of length at most 50 is = .5. Wow! This is the same value as opening 50 random boxes. While the cycle method greatly increases the probability for group success, it provides no advantage for individual success.