The Prison Puzzle Where 31% Beats Almost Zero

Anna Gal and Peter Bro Miltersen posed the original version in 2003, in a paper called "The Cell Probe Complexity of Succinct Data Structures." The setup: 100 prisoners, 100 boxes, each box holding one prisoner's number in random order. Each prisoner gets to open 50 boxes. If every prisoner finds their own number, all are freed. If even one fails, everyone dies. No communication during the search.

Random guessing gives each prisoner a 1/2 chance and the group (1/2)^100 — one in a nonillion. Miltersen, by his own account, thought no strategy did meaningfully better. Then his colleague Sven Skyum mentioned one over lunch.

Here it is: prisoner k opens box k first. Inside is some number — say 37. Next, k opens box 37. Inside is 12. Then box 12. Keep following the chain. The boxes-and-numbers form a permutation of 1 to 100, and every permutation breaks into disjoint cycles. The prisoner is walking their own cycle. They find their number exactly when the cycle closes — and they find it within 50 steps if and only if their cycle has length at most 50.

So every prisoner succeeds when the random permutation has no cycle longer than 50. There's at most one such cycle, and you can count them. The chance of a long cycle is the harmonic sum H_100 minus H_50; the survival probability is 1 minus that, around 0.31183. As prisoner count grows, it tends to 1 minus the natural log of 2, roughly 0.30685.

The interesting part isn't that the strategy works. Eugene Curtin and Max Warshauer proved it's optimal — no protocol where prisoners can't share information beats 1 - ln 2 in the limit. The 30% wall is built into the structure of permutations, not the cleverness of the prisoners.