100 Prisoners Problem: The Loop Strategy That Yields About a 31% Chance

Overview

This Veritasium video revisits the famous 100 prisoners problem and reveals a loop based strategy that delivers a surprisingly high chance of all prisoners finding their numbers.

• Loop strategy relies on permutation cycles
• Outcomes are not independent; all-or-nothing probability
• With 100 prisoners the success rate is about 31%
• Intuition and math behind the solution

Introduction

In this video, Veritasium tackles a well known probability puzzle often called the 100 prisoners problem. A group of 100 prisoners is separated from a room containing 100 slips of paper, each slip numbered from 1 to 100. The slips are placed randomly into 100 boxes. Each prisoner, in turn, may open up to 50 boxes in an attempt to locate the box containing their own number. After exploring, they must leave the room exactly as they found it. If every prisoner locates their own number, they all go free; if any one prisoner fails, they all face execution. Before their turns begin, they may coordinate a strategy, but they cannot communicate during the process.

The obvious approach is to have each prisoner pick 50 boxes at random. In that case the probability that all 100 prisoners succeed is (1/2) raised to the 100th power, which is vanishingly small. However, the video presents a powerful and counterintuitive strategy that drastically changes the odds and raises the collective success probability to about 31 percent. The strategy hinges on a deep and elegant property of permutations known as loops or cycles. Veritasium walks through the logic step by step, explaining why the arrangement of slips inside boxes forms loops and how following a loop guarantees success for prisoners whose numbers lie on loops no longer than 50 boxes.

The Loop Strategy in Action

The core idea is to treat the random placement of slips in boxes as a permutation of the numbers 1 through 100. When a prisoner enters the room and begins with the box labeled with their own number, they do not necessarily find their slip there. Instead, the slip points to another box, which contains a slip that points to another box, and so on. This sequence forms a closed loop. Each prisoner, by starting at their own box and following the chain, will traverse the loop that contains their number. If the loop length is L, the prisoner will find their number if L ≤ 50, because they only search 50 boxes. If the loop is longer than 50, they will miss their number on that run.

Thus, the prisoners all succeed if and only if the permutation decomposes entirely into cycles of length 50 or less. The remarkable fact is that, for a large group, the probability that the longest cycle length is at most 50 converges to a constant around 0.31. In other words, about a 31 percent chance that all 100 prisoners succeed, and a 69 percent chance of failure, when the loops are longer than 50 exist. This is a dramatic departure from the intuition that each prisoner has a 50 percent chance independently, since here the prisoners’ outcomes are linked through the permutation structure.

Why Loops and Permutations Create a Collective Win

To understand why the loop strategy works, it helps to visualize the random permutation as a collection of disjoint cycles. Each cycle represents a loop of boxes that eventually leads back to the starting box. If a prisoner’s number belongs to a cycle whose length is 50 or shorter, that prisoner will definitely locate their slip by following the cycle, because they can travel along the entire loop within the 50-box limit. Conversely, if a number belongs to a cycle longer than 50, that prisoner cannot complete the loop within the allowed number of boxes and will miss their slip. The key observation is that the event “no cycle longer than 50 exists” completely determines the group’s fate, and this event has a probability around 0.31 for 100 prisoners.

The warden scenario is a fun way to frame it: the loop structure ties every prisoner’s fate together. If the arrangement yields a short longest loop, everyone wins; if there is a long loop, the prisoners fail together. This all or nothing feature makes the probability non trivial and surprisingly high relative to the naive independent 50-50 guess.

Probability Calculation and the 30.7% Limit

Early in the explanation, the video notes that the probability of a loop of length 100 is 1/100 and the probability of a loop of length 99 is 1/99, and so on. The probability that there exists a loop longer than 50 is the sum of these 1/k terms from k = 51 to 100, which numerically approaches about 0.69. Therefore the probability that the longest loop is at most 50 is about 0.31. This calculation illustrates the counterintuitive result that a random permutation often has a longest cycle not exceeding half the size of the set, despite not obvious from first principles. As the number of prisoners grows, the probability of success converges to a constant value, equal to 1 minus the natural logarithm of 2, which is approximately 0.3069 or 30.7 percent.

Extensions and Real World Nuances

The video also explores several thought experiments that show the robustness of the loop strategy. If someone tries to cheat by swapping content in a few boxes, the core loop principle can still hold under certain modifications. Renumbering the boxes, for instance, preserves the randomness of the loop lengths and keeps the problem within the same probabilistic framework. If the number of prisoners increases, numerical calculations reveal that the probability of success remains around 30.7 percent, approaching the same limit even as the scale grows very large. This reveals a deep and somewhat surprising invariance in the problem's structure, an outcome that is not obvious from the outset.

Takeaways and Implications

The loop strategy demonstrates how global properties of a random permutation—the cycle structure—govern the collective outcome of the prisoners. It shows that dependencies among individuals can be harnessed to achieve a higher-than-expected probability of success as a group. It also provides a concrete example of how a nonintuitive mathematical insight, here the role of permutation cycles, can dramatically alter the odds in a classic probability puzzle. In addition to the theoretical value, the video plugs Brilliant.org as a resource for similar probability puzzles and teaches how such puzzles can sharpen reasoning, logic, and quantitative intuition.

Conclusion

The loop strategy for the 100 prisoners problem is a striking demonstration of how simple rules applied to a structured object, like a permutation, yield unexpectedly favorable results. The problem, once believed to be almost unwinnable under random strategies, has a robust 31 percent chance of success with a coordinated loop approach. As the numbers scale, the probability subtly stabilizes around 30.7 percent, a result tied to fundamental aspects of harmonic sums and logarithms. The video concludes by pointing viewers toward further probability puzzles and educational resources that cultivate mathematical thinking.