The 100 Prisoner Problem

November 21, 2023

Share this article:

[supsystic-social-sharing id='1']

Written by

Imagine if tomorrow you were abducted, and before you knew it, you were trapped in a room with 99 other people who seemed to know nothing more about what was happening than you. You notice that everyone is wearing an orange jumpsuit, which is uniquely numbered. You also notice a door, and you can not help but wonder what is behind it. At this moment, a voice can be heard telling you the rules of the game you are about to play.

Your circumstance is referred to as the “100 Prisoners Problem.” This issue was first proposed in 2003 by the Danish computer scientist Peter Bro Miltersen. In this problem, 100 prisoners, numbered from 1 to 100, are given the same task. They are required to find their corresponding number in 1 of 100 drawers. But here is the catch: everyone is limited to opening 50 drawers. Additionally, after the first prisoner begins its attempt of finding its number, no form of communication between the prisoners is allowed. 

At first glance, it appears that the chances of winning this game are slim. Every inmate possesses a probability of 50 in a 100 equal to 50% of locating their own identification number. Since we have a hundred prisoners who all need to find their own number, this gives us a chance of ½^100  = 0.00000000000000000000000000008%. However, this is under the assumption that every prisoner opens their drawers randomly, independently of each other. 

Suppose you had 100 attempts instead of 50 and opened your drawers in the following way: You start by opening the drawer of your own number; let us assume it is one. Upon opening your drawer, you will discover the number seven. Now, proceed to open drawer seven and discover number thirteen. After this, you open drawer thirteen. You can continue this approach until you find your own number. To realize this, it is important to note that every number is only hidden once. Hence, in our example, it is impossible to find number seven again after opening drawer thirteen. Hence, starting at number one, we are guaranteed to create a loop of numbers eventually containing one. To be more exact, one will be the final number we find to complete this loop. Since if you would continue opening drawers after finding your number, you would start opening the drawers you opened when you started. 

Now let us return to the original example, where you are limited to opening 50 drawers. Using the same approach, we know that we will find our own number as long as the loop we create does not contain more than 50 numbers (since, again, the final number in the loop is one). Assuming that this is the case, then not only will you find your own number, but all other people with a number contained in your loop will also find their own number. Since their number is also contained in this loop, and this loop is still not bigger than 50. To see this, assume that after you have found your number, number seven enters the room. This prisoner will open drawer seven, again find number thirteen, and start following the same loop as you, eventually arriving at drawer one, where it will find its own number. Notice that it will take number seven the same amount of attempts to find its number as you. 

We have now created an approach where the rate of success of a prisoner is correlated to that of the other prisoners. Instead of the success of the total group being determined by individual independent trials, the success is now dependent on the size of the loops that are created. To be more specific, the group is successful if there exists no loop with more than 50 numbers. Let us look at the chances of that happening. Let us start with the case that every number is used in one big loop; hence, we have a loop of a hundred numbers. For a loop, there are a hundred options for the first number, 99 for the second, 98 for the third, etc. Hence, we can create 100! Different number loops. Now for our hundred number loop, this is also the case; however, note that the loop 1,2,…,100 is the same as 2,3,…,100,1 and also the same as 3,4,…,100,1,2 etc. Hence, to find the probability of a hundred-number loop, we have: (100!/100)/100! = 1/100. Calculating these probabilities gives 1/99 for the 99 number loop, 1/98 for the 98 number loop, etc. Now adding up all probabilities of cases with loops bigger than 50, we get a total chance of roughly 69%. Hence, our rate of success is roughly 31%. Not perfect by a long shot, but much better odds than our previous calculation of a 0.00000000000000000000000000008% chance of success.

After the rules are explained, you recognize The 100 Prisoner Problem and tell all other people the strategy that they should use. Now, let us hope you are lucky.

Read more

Introduction Weekend Impression

Every year VESTING organizes an introduction weekend for the freshmen, including myself. The general theme of this weekend is getting to know your new fellow students. It is also a perfect opportunity to get a glimpse of the new world as a student. This was done by a...

The importance of statistics in sport

The importance of statistics in sport

“In terms of merit, sports have mathematical statistics. That is how you know who the best player is”. (Norm MacDonald) Until thirty/forty years ago people would most likely not believe in this statement, but the situation has changed since the end of the 90s when...

Does 1 in 3 econometricians become a millionaire?

Does 1 in 3 econometricians become a millionaire?

If you are a student in the discipline called Econometrics then you must have heard something along the lines of ‘Oh wow, that’s difficult’, followed by ‘I have heard that 1 in every 3 econometrics students will become a millionaire’. While I have since learned to...