Prisoners problems are usually violent stories involving life and death.
This beautiful problem, which I believe is a relatively uncommon one, is no different except it also has an interesting mathematical angle.
Here is the problem statement:
As incredible as it may sound there is a strategy which enables the prisoners to survive with a probability greater than 30%!
To put this into perspective, consider the default strategy where every prisoner chooses 50 of the 100 boxes uniformly at random.
In such case each prisoner finds their number with probability and since the selections are independent this implies their collective probability of surviving is .
The chance of that happening is like a gazillion times less than winning the jackpot on national lottery whilst getting fatally struck by lightning. It therefore seems intuitively astonishing that there would exist a strategy guaranteeing survival with a probability of over 30%.
As it turns out the strategy described in this post is optimal for this problem, however I will omit the proof and simply quantify the survival probability. The proof due to Curtin and Warshauer may be found in the Mathematical Intelligencer.
To describe the strategy in the most effective manner it seems easiest to use the language of permutations.
Formally a permutation of a set is a bijective function .
We commonly write them as compositions of permutation cycles.
A permutation cycle is denoted where .
According to a standard result (Cycle Decomposition Theorem) every permutation may be written as a composition of disjoint cycles.
We can think of the numbers as having been distributed into the boxes according to an unknown permutation (all equally likely).
For instance if we only had 6 boxes then below picture would translate into the following permutation in disjoint cycle form :
Essentially this says:
If I open box number 1 I will find number 4.
Opening box number 4 I find number 2.
Finally opening box number 2 I find number 1 and hence I get back where I started.
This is a cycle of length 3 and is written sending
Going back to the problem the proposed strategy will work similarly to the above example:
- Prisoner always begins by opening box .
- Suppose box contains number .
- If then the prisoner is done.
- Otherwise he opens box to find number .
- Recursively the prisoner will open box to find number .
- If then the prisoner is done.
- Otherwise the prisoner will continue doing step 5 until he is done or have exhausted his 50 boxes, in which case everyone dies.
So the question is why this strategy should work any better than the random strategy?
After all we know nothing about what is in each box so why would the choice matter?
The answer of course is that probability of success can be made conditional upon the characteristics of the permutation. As we will see certain types of permutations work especially well with the strategy, and will guarantee collective success as long as everyone sticks to the plan. While their individual chance of success is still 50% (which btw is a trivial upper bound on any strategy) their collective chance of survival can vary wildly depending on how they organize themselves, this is the key distinction. All this problem is doing is drawing the disparity between independent and conditional probability to the extreme.
Question is now how we can quantify how well our proposed strategy ought to work?
We notice that if there is a cycle of length greater than 50 boxes then the strategy is guaranteed to fail, since any prisoner belonging to the cycle will have to open more than 50 boxes to get back where he started.
Similarly we see that if there are no cycles of length greater than 50 then the strategy is guaranteed to succeed since every prisoner will be able to complete their cycle and get back to where they started (i.e finding their own number in the last box of the cycle).
Hence the strategy will fail iff a permutation contains a cycle of length greater than 50.
In other words by the partitioning rule:
Lets count up the number of permutations failing the strategy among the possible permutations.
Since there can be no other cycle of length (because there are only 100 distinct numbers).
To count the number of -cycles we first count the number of ways to choose numbers among 100. That number is .
Out of chosen numbers we can form distinct -cycles.
From the remaining numbers we can construct permutations.
In total there are therefore permutations including a -cycle.
The probability of finding a -cycle in a random permutation is thus: .
Since no two cycles of length greater than 50 can occur together we get that the probability of strategy failure is given by .
Hence the probability of survival is approximately .
It may also be interesting to look at what limit the probability tends to as the number of boxes and prisoners tend to infinity.
Generalizing our previous argument in the obvious way we find that the probability of failure using boxes equals .
The last step follows from the fact that the integral is the limit of the upper Riemann sum.
Hence the probability of survival as the number of boxes and prisoners tend to infinity is approximately .