Random Permutation Statistics - One Hundred Prisoners

One Hundred Prisoners

A prison warden wants to make room in his prison and is considering liberating one hundred prisoners, thereby freeing one hundred cells. He therefore assembles one hundred prisoners and asks them to play the following game: he lines up one hundred urns in a row, each containing the name of one prisoner, where every prisoner's name occurs exactly once. The game is played as follows: every prisoner is allowed to look inside fifty urns. If he or she does not find his or her name in one of the fifty urns, all prisoners will immediately be executed, otherwise the game continues. The prisoners have a few moments to decide on a strategy, knowing that once the game has begun, they will not be able to communicate with each other, mark the urns in any way or move the urns or the names inside them. Choosing urns at random, their chances of survival are almost zero, but there is a strategy giving them a 30% chance of survival, assuming that the names are assigned to urns randomly – what is it?

First of all, the survival probability using random choices is

so this is definitely not a practical strategy.

The 30% survival strategy is to consider the contents of the urns to be a permutation of the prisoners, and traverse cycles. To keep the notation simple, assign a number to each prisoner, for example by sorting their names alphabetically. The urns may thereafter be considered to contain numbers rather than names. Now clearly the contents of the urns define a permutation. The first prisoner opens the first urn. If he finds his name, he has finished and survives. Otherwise he opens the urn with the number he found in the first urn. The process repeats: the prisoner opens an urn and survives if he finds his name, otherwise he opens the urn with the number just retrieved, up to a limit of fifty urns. The second prisoner starts with urn number two, the third with urn number three, and so on. This strategy is precisely equivalent to a traversal of the cycles of the permutation represented by the urns. Every prisoner starts with the urn bearing his number and keeps on traversing his cycle up to a limit of fifty urns. The number of the urn that contains his number is the pre-image of that number under the permutation. Hence the prisoners survive if all cycles of the permutation contain at most fifty elements. We have to show that this probability is at least 30%.

Note that this assumes that the warden chooses the permutation randomly; if the warden anticipates this strategy, he can simply choose a permutation with a cycle of length 51. To overcome this, the prisoners may agree in advance on a random permutation of their names.

We consider the general case of prisoners and urns being opened. We first calculate the complementary probability, i.e. that there is a cycle of more than elements. With this in mind, we introduce

or

so that the desired probability is

because the cycle of more than elements will necessarily be unique. Using the fact that, we find that

which yields

Finally, using an integral estimate such as Euler–MacLaurin summation, or the asymptotic expansion of the nth harmonic number, we obtain

so that

or at least 30%, as claimed.

A related result is that asymptotically, the expected length of the longest cycle is λn, where λ is the Golomb–Dickman constant, approximately 0.62.

This example is due to Anna Gál and Peter Bro Miltersen; consult the paper by Peter Winkler for more information, and see the discussion on Les-Mathematiques.net. Consult the references on 100 prisoners for links to these references.

The above computation may be performed in a more simple and direct way, as follows: first note that a permutation of elements contains at most one cycle of length strictly greater than . Thus, if we denote

then

For, the number of permutations that contain a cycle of length exactly is

Explanation: is the number of ways of choosing the elements that comprise the cycle; is the number of ways of arranging items in a cycle; and is the number of ways to permute the remaining elements. Thus,

We conclude that