The 100 Prisoner problem could explain the origin of life (and disprove a Creationist argument)
A winning strategy among proteins could make the improbable kickstart of evolution far more likely.
The 100 Prisoner problem, first proposed in 2003 and featured in a number of mathematics magazines, with variants appearing in the literature, is the weirdest, wildest, and most amazing math problem I’ve ever encountered. And I’m a mathematician. It’s not the hardest to understand by far nor is it the hardest to prove. It is incredibly counterintuitive what the solution is yet when explained, you understand why instantly.
Here is the problem (quoting from Flajolet and Sedgewick):
The director of a prison offers 100 death row prisoners, who are numbered from 1 to 100, a last chance. A room contains a cupboard with 100 drawers. The director randomly puts one prisoner’s number in each closed drawer. The prisoners enter the room, one after another. Each prisoner may open and look into 50 drawers in any order. The drawers are closed again afterwards. If, during this search, every prisoner finds their number in one of the drawers, all prisoners are pardoned. If just one prisoner does not find their number, all prisoners die. Before the first prisoner enters the room, the prisoners may discuss strategy — but may not communicate once the first prisoner enters to look in the drawers. What is the prisoners’ best strategy?
I imagine a dystopian world where this is a sadistic game show (a theme of at least one episode of Doctor Who).
Opening drawers randomly is one of the worst strategies. In this case, the probability of success is vanishingly small since each prisoner only has a 50% chance of succeeding. For all of them to succeed, this would be like each prisoner flipping a coin and for them all to land heads up randomly. The chances of that happening are 1/2 x 1/2 x 1/2 x … x 1/2, with 100 halves in the multiplication.
This is a really, really small number. As an example, you are vastly more likely to win the Mega Millions main jackpot (a 1 in 300 million chance) three times in a row than the prisoners here succeed. In fact, the probability is about the same as winning a lottery with a 1 in 33 million chance four times in a row.
It turns out, however, that there is a strategy that will ensure that the prisoners have a 31% chance of all being freed.
It works like this. First, the prisoners agree on a numbering for the drawers themselves. For example, starting from the top left corner and going across and then down in the way that we read in English.
When the first prisoner goes in, they find the drawer with their number and open it. They take out the slip of paper and find the drawer that corresponds to that number and open it. They keep doing this until they have either found their number or opened 50 drawers.
The next prisoner goes in and does the same thing and so on until either all have found their numbers or they fail. By doing this, they will succeed 31% of the time.
Why?
The reason has to do with cycles. If you think about it, the sequence of drawers that a prisoner opens forms a cycle that ultimately must point back to the first drawer they opened. This is because they opened a drawer that corresponded to their number, and they are looking for the drawer that contains their number. Thus, the drawer they are looking for points back to the first drawer they opened.
Let’s look at an example. Suppose prisoner 1 goes in. They open the topmost, leftmost drawer. In it they find a paper with the number 35 on it. They count out 35 from the 1st drawer and open that drawer. Now they get the number 8. They count out to the eighth drawer and open that. They get 4. They look in the fourth drawer and in there is the lucky number 1.
If the prisoner were to continue for one more pick, they would have to open drawer 1 which would lead them back to opening all the same drawers again in an endless loop, but since they found their number they can stop.
Prisoners 35, 8, and 4 will also end up on this loop and eventually they will all find their numbers as well since the cycle is shorter than 50.
This is true for all the prisoners. As long as all the cycles are shorter than 51, they will all find their numbers on their respective loops.
This means that the probability that all prisoners will find their numbers is the probability that none of the cycles are 51 drawers or longer. The probability that at least one is 51 drawers or longer turns out to be 69%, so the probability they will succeed is 31%.
This problem has appeared in numerous magazines both academic and recreational. It has inspired youtube videos including one by Veritasium that has garnered 7.4M views. Some derivative works on Tiktok have even more.
I haven’t seen much in the way of practical applications of the problem and so I began to ponder a question that is an obsession for some (American) Christians. It involves trying to disprove an idea using very, very small probabilities: evolution and the origin of life.
Now, we know for a fact that evolution occurs. It has not only been verified in the fossil record but also been observed to occur over small time scales. Likewise, we observe flaws in the design of the body that show that it evolved in a different environment and was adapted to a new one. A common example is the eye which works better in water than air since it mostly evolved under the sea. Clues can be found in our DNA that point to how long ago our species split off from others.
Yet one of the common Creationist arguments against evolution is that it has an extremely small probability of being successful in producing self-sustaining life. In particular, how could a complex molecule such as DNA or its likely predecessor RNA come to be and to be present in all life on Earth?
Creationists argue that even the simplest life supporting protein has a vanishingly small chance of assembling, pointing the way to a Designer who hand crafted it.
Now anyone who understands how evolution works knows that, once you have complex organisms, especially if you add sexual reproduction, they simply exchange and mutate traits in their genes and these produce either beneficial or usually harmful traits in their offspring. Offspring with harmful traits either die off or fail to reproduce. The effect is natural selection which vastly raises the probability that beneficial traits will be retained and carried forward to the next generation. Hence, once natural selection gets started, you can’t help but arrive at complexity.
But how could all that have begun? The chances of anything assembling to kick off evolution seems vanishingly small even with the right conditions. Even with trillions of attempts, the probability is still too small to ever happen in the history of the universe. But that assumes that all this is happening randomly.
One possible solution comes from the 100 prisoners problem.
Imagine that each of the prisoners is an amino acid or, more likely, a small protein and finding the box with their number is equivalent to finding a place in a long protein chain that leads to evolutionary success, the beginnings of the natural selection process.
The prisoners don’t have to communicate to strategize. They simply have to follow the strategy blindly, connecting together via peptide or hydrophobic bonds, but not randomly. Rather, they must connect in such a way that the configuration of amino acids or small proteins leads to another configuration, via reconnection and folding, on a cycle that ultimately leads to a successful configuration.
While the chances of this happening for a large collection of amino acids or protein sections randomly is vanishingly small, if each follows a reconfiguration strategy similar to the prisoner’s problem, then they have a good chance of success.
So far so good, but how would this occur naturally?
Let’s look at our analogy.
If the prisoners are amino acids or small proteins and the drawers are protein configurations, what are the slips of paper that tell you what drawer to go to next? How do the proteins “know” where to go next without having a mind to direct them there?
To answer this question, we have to grok the strategy. At its core, the strategy follows a cycle, but why is the cycle there in the first place? The cycle is there because the slips of paper represent a permutation of the drawer numbers. A permutation can be thought of as a sequence of exchanges between an ordering of numbers. Thus, any permutation contains a cycle representing the sequence of exchanges that occurred or would need to occur to reproduce that permutation.
You can think of it like this. If no permutation had been done, each drawer would contain a slip with its own number on it and point to itself. The cycles would have one element. If I exchange the slips of paper between two drawers, say 1 and 2, this single permutation creates a cycle of length two. Drawer 1 points to 2 and 2 back to 1.
If I then permute one of them with another drawer such as exchanging the slips in drawers 2 and 3, the cycle grows, now 1 to 2 to 3 and back to 1. Thus, there is a direct relationship between the length of the cycle and the number of exchanges.
Going back to proteins, suppose we consider that there exists a successful protein configuration, the one that represents all the prisoners finding their own numbers, i.e., starting natural selection going. Permutations of this configuration are on average failed configurations. Randomly assembling a protein in the right configuration is unlikely to succeed. But if that protein builds itself up with each segment following a permutation cycle, it is far more likely to succeed.
Now, suppose that the successful protein configuration is precisely that, a configuration that builds itself up according to permutation cycles. That is, we aren’t trying to find some magical, natural selection configuration but, rather, the natural selection configuration is precisely the one that satisfies the strategy! That is enough.
The reason is that a protein that follows this strategy would have a property that all life possesses: the ability to reproduce. It has this ability because it constructs itself (copies itself) with high probability despite its structure being very complex. Each segment finds its place by following a permutation cycle rather than encouraging random configurations.
Now I’m not a biologist and I don’t know if this is how life got started. I also don’t know if this is a property that can be found to exist among proteins. I just say that if this property were to exist among proteins, even one amid trillions, it would be able to kickstart natural selection even if the protein had no other characteristics of life and there were nothing otherwise special about it. It would be the beginnings, indeed, of the transcription ability that we see in DNA and RNA.
It also suggests that arguments that assume that proteins would be configuring themselves randomly are flawed. Proteins do not configure themselves randomly at all but connect to one another via exposed bonds. These bonds are exposed based on the way the protein folds. Thus to construct a successful, permutation cycle following protein only requires that each of the segments have this special property, via how they fold and expose their bonds, so that they connect in the right way to reproduce.
Likely this would work via a sequence of proteins (rather than one self-reconfiguring protein) with each segment following a predictable pattern of where in the chain it is positioned. You can think of this as if all the prisoners go into identical rooms at the same time rather than one after another. It is mathematically equivalent. Each iteration of the prisoners opening a drawer would be a new generation for the protein, but, since the cycles are all closed, the resulting proteins would all be part of a related family of proteins that would continuously reproduce in a never ending cycle that nevertheless is far from random.
These sequences, by following permutation cycles, would guarantee reproduction. This might be a simple enough way for life to be far more probable than you would think.
Unlike most of my articles which are based on peer reviewed research, this is a novel idea. As far as I know, no one has investigated it, so if any computational biologists would like to have at it, let me know how it goes!
If you like this article, don’t forget to click the email subscribe button below so you never miss when I publish.
If you aren’t a medium member and would like to subscribe, please click on my referral link and get access to all my articles and thousands more by other creators. I’ll receive a small commission every month you are a member. You can also support me directly on patreon.