I ended a recent overlong post—”Frequentists Use Bayes’ Theorem Too“—with a challenging probability problem I’ll call the 100 Prisoners and 100 Boxes problem.
Here’s more about that. I won’t include my own explanation. Were I to, I’d go at it by picking apart in greater detail the first explanation I myself encountered, from Peter Winkler. I’ll share his explanation in a moment, along with links to some others.
Here’s Winkler’s statement of the problem:
The names of 100 prisoners are placed in 100 wooden boxes, one name to a box, and the boxes are lined up on a table in a room. One by one, the prisoners are led into the room; each may look in at most 50 boxes, but must leave the room exactly as he found it and is permitted no further communication with the others.
The prisoners have a chance to plot their strategy in advance, and they are going to need it, because unless every single prisoner finds his own name all will subsequently be executed. Find a strategy for them which which has probability of success exceeding 30%.
Comment: If each prisoner examines a random set of 50 boxes, their probability of survival is an unenviable 1/2100 ≈ 0.0000000000000000000000000000008. They could do worse—if they all look in the same 50 boxes, their chances drop to zero. 30% seems ridiculously out of reach—but yes, you heard the problem correctly.
This is a hard problem whose solution may take work to intuitively understand (as it did for me). Winkler notes:
Devised by Danish computer scientist Peter Bro Miltersen, a version [of this puzzle] appeared in a prize-winning paper of his and Anna Gal’s.1 But Miltersen didn’t think there was a solution until one was pointed out to him over lunch by colleague Sven Skyum.
In another paper (linked below), mathematician Peter Taylor writes:
But simple as it is, the solution is not, I think, easily found. For me as a mathematician, the absorbing problem is not one of finding the solution (I had to be told the answer) but of understanding it. Having been given the solution, understand how it works. That already is a wonderful little project.
That nicely encapsulates my love for math as a whole.
How to solve 100 Prisoners and 100 Boxes?
On seeing such a problem, my first thoughts are about figuring out how many ways things can go favorably, which I aim to set in ratio to how many ways they can go favorably or not favorably. At least that’s the basic starting place (you might need, for example, to do this for specific ways of things going favorably or not and then add it all up while taking care not to over-count).
Two burning questions, then: How many ways can what go favorably or not? Once you figure out what that is, how do you count it?
Once you know what to count, if you’re lucky, you can run a computer simulation or physically perform 100 or 100,000 trials to draw out theoretical frequencies. Or, if you’re even luckier, the phenomena in question are naturally beholden to such regularities that you can use math. For this problem, some fairly straightforward math is the most precise and illuminating (and I think fun) way to go.
Here’s Winkler’s explanation, my favorite. It’s short but contains enough to pick the problem apart. Notice that the what we are counting is determined by this cruel and unusual game’s most promising strategy. Figuring out the strategy, which is to say the solution, is the hardest part. The rest—bearing out and explaining that solution—is counting (not easy either, but easier than counting the nanoseconds of every sneeze in Brooklyn two Tuesdays ago).
From Winkler’s paper:
To solve it, the prisoners must first agree on a random labeling of the boxes by their own names. (The point of making it random is that it makes it impossible for the warden to place names in boxes in such a way as to foil the protocol described next.) When admitted to the room, each prisoner inspects his own box (that is, the box with which his own name has been associated). He then looks into the box belonging to the name he just found, and then into the box belonging to the name he found in the second box, etc. until he either finds his own name, or has opened 50 boxes.
That’s the strategy; now, why on earth should it work? Well, the process which assigns to a box’s owner the name found in his box is a permutation of the 100 names, chosen uniformly at random from the set of all such permutations. Each prisoner is following a cycle of the permutation, beginning with his box and (if he doesn’t run over the 50-box limit) ending with his name on a piece of paper. If it happens that the permutation has no cycles of length greater than 50, this process will work every time and the prisoners will be spared.
In fact, the probability that a uniformly random permutation of the numbers from 1 to 2n contains no cycle of length greater than n is at least 1 minus the natural logarithm of 2—about 30.6853%.
To see this, let k > n and count the permutations having a cycle C of length exactly k. There are
ways to pick the entries in C, (k−1)! ways to order them, and (2n−k)! ways to permute the rest; the product of these numbers is (2n)!/k. Since at most one k-cycle can exist in a given permutation, the probability that there is one is exactly 1/k.
It follows that the probability that there is no long cycle is
where Hm is the sum of the reciprocals of the first m positive integers, approximately ln m. Thus our probability is about 1 − ln 2n + ln n = 1 − ln 2, and in fact is always a bit larger. For n = 50 we get that the prisoners survive with probability 31.1827821%.
Eugene Curtain and Max Washauer have recently proved that this solution cannot be improved upon.
Lovely!
Here are three papers with explanations, listed in order from easiest to hardest (according to me):
“The Condemned Prisoners and the Boxes” (2012) by Peter Taylor.
“Seven Puzzles You Think You Must Not Have Heard Correctly” (2006) by Peter Winkler.
“Introduction to the General Case of the 100 Prisoners Problem” (2018) by Timothee Schoen.
And here are two web pages with explanations:
“100 Prisoners Problem” at Wikipedia.
“100 Prisoners Escape Puzzle” by Nick Berry. The illustrations and clear language make this a good one to start with (with one correction; Berry writes: “For everyone to succeed, the maximum chain length needs to less than fifty boxes long”; should be “less than or equal to fifty” [it’s also missing a “be”]).
Thanks to Winkler and everyone else for their explanations.
If those don’t get you there and you’d like to see mine, let me know. It’ll likely be long and err towards over-explaining in an obsessive (though not guaranteed to be successful) effort to make it intuitive.
Enjoy or find this post useful? Please consider pitching in a dollar or three to help me do a better job of populating this website with worthwhile words and music. Let me know what you'd like to see more of while you're at it. Transaction handled by PayPal.Or click the banner to shop at Amazon (at no extra cost: it just gives me some of what would have gone to Amazon).