YAPP (Yet Another Prisoners Problem)

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:

Problem:
100 condemned prisoners awaiting execution are offered a chance to live.
The prison administration has labelled each prisoner with a unique number id from 1 to 100.
Each of the prisoners are led alone into a room with 100 closed boxes each containing a number from 1 to 100 in some (uniformly) random rearrangement.

Each prisoner is allowed to open 50 of the 100 boxes.

The deal is: If all 100 prisoners manage to find their number id in some box after opening 50 boxes each then they all live. Otherwise they will all die.

The prisoners may communicate a strategy with each other before they enter the room, but not after.
They are not allowed to manipulate the boxes nor leave messages to following prisoners.
All boxes are closed when a prisoner enters the room.

The question is: What strategy should the prisoners choose to maximize their chance of surviving?

 
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 \frac{1}{2} and since the selections are independent this implies their collective probability of surviving is (\frac{1}{2})^{100}.
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 \Omega is a bijective function \sigma:\Omega\rightarrow\Omega.
We commonly write them as compositions of permutation cycles.
A permutation cycle is denoted \sigma = (a_{1}\;a_{2}\;...\;a_{k-1}\;a_{k}) where \sigma(a_{i}) = a_{i+1},\;\;\sigma(a_{k}) = a_{1}.
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 \Omega=\{1,...,100\} 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 (1\;4\;2)(3\;6)(5):

boxes

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 (1\;4\;2) sending 1 \rightarrow 4,\;4 \rightarrow 2,\;2 \rightarrow 1

Going back to the problem the proposed strategy will work similarly to the above example:

  1. Prisoner k always begins by opening box a_{1} = k.
  2. Suppose box a_{1} contains number a_{2}.
  3. If a_{2} = a_{1} then the prisoner is done.
  4. Otherwise he opens box  a_{2} to find number a_{3}.
  5. Recursively the prisoner will open box a_{i} to find number a_{i+1}.
  6. If a_{i+1} = a_{1} then the prisoner is done.
  7. 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:
\mathbb{P}(Survival) =
\mathbb{P}(Survival|No\;Cycle\; Of \;Length > 50).\mathbb{P}(No\;Cycle\; Of \;Length > 50) +
\mathbb{P}(Survival|Cycle\; of\; length > 50).\mathbb{P}(Cycle\; of\; length > 50) =
1.\mathbb{P}(No\;Cycle\; Of \;Length > 50) + 0.\mathbb{P}(Cycle\; Of \;Length > 50) = \mathbb{P}(No\;Cycle\; Of \;Length > 50) =
1 - \mathbb{P}(Cycle\; Of \;Length > 50).

Lets count up the number of permutations failing the strategy among the 100! possible permutations.

Let k > 50.
Since k > 50 there can be no other cycle of length >50 (because there are only 100 distinct numbers).
To count the number of k-cycles we first count the number of ways to choose k numbers among 100. That number is \left( \begin{array}{c} 100 \\ k \end{array} \right).
Out of k chosen numbers we can form \frac{k!}{k}=(k-1)! distinct k-cycles.
From the remaining 100-k numbers we can construct (100-k)! permutations.
In total there are therefore \left( \begin{array}{c} 100 \\ k \end{array} \right)(k-1)!(100-k)! permutations including a k-cycle.

The probability of finding a k-cycle in a random permutation is thus: \frac{\left( \begin{array}{c} 100 \\ k \end{array} \right)(k-1)!(100-k)!}{100!} = \frac{1}{k}.

Since no two cycles of length greater than 50 can occur together we get that the probability of strategy failure is given by \frac{1}{51} + \frac{1}{52} + ...+\frac{1}{100} \thickapprox 0.688.

Hence the probability of survival is approximately 1 - 0.688 = 0.312 = 31.2\%.

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 2n boxes equals \frac{1}{n+1} + ... + \frac{1}{2n}.

Now

\lim_{n \to \infty} \left(\frac{1}{n+1} + ... + \frac{1}{2n}\right) =

\lim_{n \to \infty} \left(\frac{\frac{1}{n}}{1+\frac{1}{n}} + \frac{\frac{1}{n}}{1+\frac{2}{n}}+... + \frac{\frac{1}{n}}{1+\frac{n}{n}}\right) =

\lim_{n \to \infty} \frac{1}{n}\sum_{k=1}^n \frac{1}{1+\frac{k}{n}} = \int_0^1 \frac{1}{1+x} \;dx \;= ln(2) - ln(1) = ln(2) \thickapprox 0.693.

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 1 - 0.693 = 0.307 = 30.7\%.

 

Exercise 1 (Fair Game – Easy):

What is the smallest number of boxes the 100 prisoners should be the allowed to open in order to have at least 50% chance at survival?

 

Advertisements
This entry was posted in Probability, Uncategorized and tagged , , , , , , , . Bookmark the permalink.