A hundred prisoners and one shuffle

A warden numbers a hundred prisoners and places their numbers, one each, into a hundred closed boxes, shuffled at random. The prisoners go one at a time into the room. Each may open fifty boxes, and must find their own number. Each must leave the room exactly as it was found, and no communication is possible once the process starts, though they may agree on a plan beforehand. If every prisoner finds their number, all go free. If any one fails, all die.

If each prisoner opens fifty random boxes, each has a chance of one half, and the chance that all succeed is $2^{-100}$, about $8 \times 10^{-31}$. It seems as though no plan can help. A prisoner has no information about the arrangement of the boxes before opening any, and no way of passing on what they find. So nobody’s chance can be better than a half, whatever they do, and a plan cannot alter that.

That last sentence is true. Yet a plan exists under which they all go free 31% of the time. The puzzle was given in this form by Anna Gál and Peter Bro Miltersen in 2003, in a paper about data structures, and Peter Winkler then spread it through collections of mathematical puzzles. Its solution uses the structure of a random shuffle in a beautifully direct way.

The plan #

Each prisoner opens the box bearing their own number. Inside it is some number. They next open the box with that number, and so on, until they find their own or run out of openings.

The numbers in the boxes define a permutation: box $b$ points to the box named by the number inside. Every permutation breaks up into disjoint cycles. A prisoner who starts at box $k$ is starting on the cycle that contains $k$, and following the arrows, they must come back to box $k$ at the end of that cycle. The box just before returning to $k$ is the box containing the number $k$. So the prisoner finds their number exactly when their cycle has length at most fifty. Then everyone’s fate is decided by a single fact: whether the permutation has a cycle longer than fifty.

If it has none, then all prisoners succeed. If it has one, then all those on that cycle fail, at least 51 of them, and so everyone is executed. Their successes and failures are no longer independent at all, and they are as tightly linked as they could be.

In the figure, the shuffle of 24 has cycle lengths 11, 7, 5 and 1. The longest is below the allowance of 12, so in this room everyone would go free.

The arithmetic #

The chance that the plan fails is the chance of a cycle longer than half. This is a pleasant count. How many permutations of $n$ have a cycle of length exactly $k$, for $k$ above $n/2$? Choose its elements, $\binom{n}{k}$ ways, arrange them in a cycle, $(k - 1)!$ ways, and arrange the rest however one likes, $(n - k)!$ ways. The product is $n!/k$. So the chance is exactly $1/k$. And since two cycles longer than half cannot exist at once, the events for different $k$ exclude one another, and their chances simply add. There are no correction terms. That is the whole reason this counts so much more easily than the problem of nobody getting their own hat, with its alternating sums. So

$$P(\text{all succeed}) = 1 - \sum_{k = n/2 + 1}^{n} \frac{1}{k}.$$

For $n = 100$ this is 0.3118. The sum is a piece of the harmonic series, from $n/2 + 1$ to $n$, which tends to $\ln 2$. So as the number of prisoners grows, the chance falls towards $1 - \ln 2 = 0.3069$, and no lower. A thousand prisoners, or a million, would have nearly the same chance of 30.7% as a hundred do. Independent guessing would have the chance fall to nothing exponentially fast.

The simulation shows the distribution of the longest cycle in 40,000 shuffles, and above fifty it follows $1/k$. The region to the left of fifty is where the distribution is hard: at a length $k$ below half, there can be several cycles of that length, and the exact law has inclusion–exclusion terms that build up as $k$ falls below $n/2$, $n/3$, and so on. The curve changes shape at each of those points, though the figure shows it most clearly at 50. It is a characteristic feature of cycle statistics. The average longest cycle of a random permutation is about 0.6243 times its length, a number called the Golomb–Dickman constant.

What a shuffle’s cycles look like #

The count $n!/k$ is one instance of a much larger fact about the cycles of a random permutation. The expected number of cycles of length $k$ is exactly $1/k$, for every $k$ from 1 to $n$, not just for those above half. So the expected total number of cycles is the harmonic number $H_n$, which is about 5.19 for a hundred boxes. A typical shuffle of a hundred has one or two long cycles, a few of moderate length, and a handful of short ones, which is just what the opening figure’s shuffle of 24 looks like.

And for fixed $k$, as $n$ grows, the number of cycles of length $k$ becomes a Poisson variable with mean $1/k$, independently for different $k$. That is a theorem of Vasily Goncharov from 1944, and its case $k = 1$ is how many get their own hat: the fixed points of a random permutation are Poisson with mean 1. The hat problem and the prisoner problem are therefore two ends of one picture. The hats concern the shortest possible cycles, and the chance of having none of them is $1/e$, reached through a long alternating sum. The prisoners concern the longest cycles, and the chance of having none of those is $1 - \ln 2$, reached by a sum with no alternation at all. The frustration card game uses another piece of the same structure, avoiding a fixed offset rather than a fixed length.

So the picture of a random permutation is unusually complete. Short cycles behave independently, and long ones behave like a process in which a stick is broken at random, with the longest piece taking a random share, the next a random share of the rest, and so on. That description, called the Poisson–Dirichlet law, is why the Golomb–Dickman constant has the value it does, and why the same law shows up in the factorisation of numbers.

Why nobody’s individual chance has moved #

It is important to see that the plan does nothing to any individual’s chance. A prisoner following the plan succeeds if the shuffle has their number at a position reached within fifty steps. That chance is still exactly one half: the length of the cycle containing a given element is uniformly distributed on $\{1, \dots, 100\}$, so the chance it is at most 50 is exactly a half. Nobody has been given an advantage. All that has changed is the correlation.

This is the same phenomenon that makes some card tricks seem impossible, and it is an instance of a very general rule. When all prisoners succeed or fail together, the probability that all succeed equals what one of them has, adjusted for overlap. Under independence it is a half to the power 100. The plan arranges that a shuffle which is good for one prisoner tends to be good for all. Since the expected number of successful prisoners is fifty under any plan, a plan cannot change that count. It can only choose how it is distributed: under independence it clusters tightly around 50 and almost never reaches 100. Under the cycle plan it is often 100 and otherwise less than 50, sometimes much less. That is the whole trick. The same total of successes is spent on all-or-nothing.

A nice way of putting it: the rule makes failure come in a clump. If there is a long cycle, then more than half the prisoners fail together, and so the failures are concentrated in a few shuffles, which are the 69% of shuffles with a long cycle. The other 31% are left with no failure at all. Failure is being moved around, and it is not being reduced. In the same way the coupon collector’s last few coupons are costly because the waiting is concentrated at the end, whereas here the concentration is the prisoners’ own doing.

Nothing can do better #

It is one thing to find a good plan and another to prove that it is the best. Every prisoner’s chance is a half, so one might suspect that a cleverer correlation could do better, with a plan that succeeds, say, 40% of the time.

For four prisoners who may open two boxes each it is feasible to search exhaustively. A rule for a prisoner names a first box and, for each number found there, a second box. That is 324 rules for each prisoner. Trying all combinations against all 24 shuffles, with pruning, shows that the best combination wins exactly 10 of the 24 shuffles. That is the cycle plan’s value, since $1 - (1/3 + 1/4) = 5/12$. A pair-up plan, in which two prisoners search one half and two search the other, wins 4 of the 24. Nothing in between comes close.

Eugene Curtin and Max Warshauer gave the full proof in 2006, with a very pretty idea. Change the rules so the game is more generous to the prisoners. In the new game, the boxes opened by earlier prisoners stay open and everyone can see them. A prisoner enters, first checks whether their number is already showing, and if it is, walks out; if not, they open further boxes until they find it, stopping at the number of boxes allowed. Any plan in the original game can be simulated in the generous game, with at least as good a chance. But in the generous game, every strategy has the same chance of winning, because the only thing a prisoner can do is open a box not yet seen, and all unopened boxes are exchangeable given what has been seen. So the generous game has one value, which can be computed from any strategy, and the cycle plan in the original game happens to reach it. That is an argument with no calculation at all.

The value is the same as in other optimal results of this kind, where a game is made easier so that its solution becomes trivial, and the original is then found to match its solution exactly.

If the warden is not fair #

A real warden need not shuffle fairly. A hostile warden who knows the plan can arrange a single cycle of length 100 and execute everyone. The plan can be defended against that, and the defence is a nice trick. Before going in, the prisoners agree on a random relabelling of the boxes, a secret permutation of the labels chosen by them. Now each prisoner follows the cycle plan on the relabelled boxes. Whatever the warden placed, composing it with a uniformly random relabelling gives a uniformly random permutation. So the chance is again 31%, against any warden who does not see the relabelling.

It works for the same reason as the first shuffle of a pack: one good shuffle wipes out any structure in what came before, and the prisoners have one shared shuffle available in the plan they agree on. That matters for the analysis of worst-case randomised algorithms, of which this is a tiny example. The original paper by Gál and Miltersen arose from questions about the costs of data structures in that setting. A trade-off between how much a structure must store and how many places must be read for one query is limited by the same fact about permutations that this puzzle dramatises.

If more or fewer boxes may be opened #

The same plan can be evaluated for any allowance of $m$ boxes, and the chance is then the probability that every cycle has length at most $m$. For $m$ above $n/2$ this is the plain sum: 0.4925 at 60 boxes, 0.714 at 75, 0.895 at 90. Below half the events no longer exclude one another, and a recursion counts the permutations with short cycles: the probability $f_N$ for $N$ elements satisfies $N f_N = \sum_{k \le m} f_{N-k}$. It agrees exactly with the plain sum above half, and for smaller $m$ it gives 0.135 at 40 boxes and 0.026 at 30.

The curve is a function that has already been met in another form. As $n$ grows, with $m = n/u$, the probability tends to Dickman’s function $\rho(u)$, the one that also gives the chance a random number has all its prime factors less than its $u$-th root. The largest prime in a typical number is the same distribution. This is not a loose analogy. The cycle lengths of a random permutation and the logarithms of the prime factors of a random number have very nearly the same joint law, a correspondence studied by Patrick Billingsley and many others. The prisoners’ chance of $1 - \ln 2$ is then the same number as the chance that a random large number has no prime factor above its own square root. So about 31% of numbers are made only of primes below their square root, for the same reason that 31% of shuffles have no long cycle. Those are two very different settings, and the formula is the same integral.

Simulations #

The four independent simulations end at 0.3126, 0.3135, 0.3109 and 0.3115, around the exact value of 0.3118. Each simulated room requires only a pass through the permutation to find its longest cycle. The result is not in doubt, but the fact that a simulation gives the same answer is a useful check on the logic of the plan, in a problem where intuition firmly says the answer ought to be near nought. In the classroom this is the first thing to do, since nobody believes it at first, and then the convergence of the running shares is hard to argue with.

What has been checked #

The exact chance has been computed from the formula in exact rational arithmetic, and the count at $n = 6$, 276 permutations of 720, was verified by listing them. The law $1/k$ above half is an exact count with a two-line proof; the simulation in the figure is only an illustration of it. The strategy search for four prisoners is complete only for deterministic rules, but randomising cannot beat the best deterministic plan, since a random plan is a mixture of deterministic plans. Curtin and Warshauer’s general proof is sketched in outline above, and the sketch has been verified only by the search at four. Beyond that it has not been reproduced computationally.

The connection with Dickman’s function is cited, and the recursion was checked against the plain sum at five values of $m$. The relabelling defence applies under the assumption that the warden does not see the prisoners’ private plan. The value 0.6243 for the mean longest cycle is quoted. The claim that about 31% of large numbers have no prime factor above their square root is the same integral, and its numerical side is treated in the essay on the largest prime factor.

Still open: variations with less shared information #

The basic puzzle is closed, and its neighbours are less so. What can be done if prisoners may not all use the same arrangement, or if a few prisoners are allowed to fail? If up to $f$ failures are allowed, the question becomes one about the length of the second-longest cycle and so on, and what the optimal plan looks like is not always clear. In the opposite direction, one might let a single prisoner look at the whole room and rearrange a small number of boxes. It has been shown that one swap is enough to make a win certain: the first prisoner finds any long cycle and splits it in two, and no prisoner then fails. Variants allowing partial rearrangement or limited signalling have been studied for their own sake, and exact values for partial signalling have only been worked out in a few small cases.

A separate question lies behind Gál and Miltersen’s original context. What are the true trade-offs in the data-structure problem? How many bits must a table store for one query to need only a few probes, on inputs drawn from a hard distribution? Their lower bound is based on a family of hard questions of this kind, and in many settings the gap between the upper and lower bounds is still open.

The same total, spent all at once #

Following the cycle makes every prisoner’s success depend on one fact about the shuffle, whether it has a cycle longer than half, and that has chance $\sum_{k > n/2} 1/k$, tending to $\ln 2$. So the prisoners survive with chance $1 - \ln 2$ however many they are, each with an individual chance of a half that the plan cannot change. No plan does better: a search confirms it at four prisoners and a short argument does so in general. And a shared relabelling makes this hold against any warden.

Independence is an expensive default. The expected number of successes is the same under every plan, and the probability that all succeed is a function only of how they overlap, which goes from $10^{-30}$ to $0.31$ through one change of rule. A fact about the cycles of permutations makes the whole difference, and it turns out to be the same fact that describes the prime factors of a number.