| Home | About |
The n-Prisoners Riddle is a problem in probability theory in which a group (of size n, where n is a positive and even integer) of numbered prisoners is given the prospect of clemency if each prisoner can find a slip of paper containing their number in one of n randomly-sorted drawers within n/2 tries. However, if even one prisoner fails, all of the prisoners will be executed. The prisoners are allowed to communicate before the first prisoner opens a drawer, but communication is barred afterward.
The naive approach to this problem assumes that each prisoner has a 50% chance of opening the correct drawer. The probability of success for this approach is
,
a dismal probability for any value of n.
A more intelligent approach to this problem involves starting at the drawer that matches the prisoner's number and selecting the next drawer based on the contents of the current drawer. This strategy relies on the fact that the assignment of the prisoners' numbers to the drawers is a one-to-one permutation that contains cycles, and starting with the prisoner's own number guarantees that they are on the correct cycle.
This strategy is effective if there exists no cycle longer than n/2. The probability that a uniformly distributed random permutation contains no cycles longer than n/2 is given by
,
giving the prisoners a significantly better probability of survival than the naive approach.
The Law of Large Numbers is a law in probability theory that states that given a sample of independent and identically distributed values, the sample mean converges to the true mean as the sample size increases. This law is important because it guarantees stable long-term results for the averages of some random events.
In the case of the n-Prisoners Riddle, we should expect the rate of success for a sample of randomly-generated simulations to converge to the probability that a uniformly distributed random permutation containing values [1...n] contains no cycles greater than n/2 as more simulations are run.