Is this problem useful for anything? I've seen multiple variations of these prisoner problems now, and I can never remember any being useful in other contexts.
Well, first of all it's a puzzle so it's useful as something fun to think about. Math is kinda like science though, you never know exactly how or if a particular discovery will be useful. In this case maybe you could find some graph traversal scenario where this would be applicable. In the Wikipedia article under variants they mention
> If the number of team members and the fraction of boxes which are opened is fixed, the winning probability stays strictly larger than zero when more empty boxes are added
Replace boxes with nodes and now you have some math to determine graph traversals. Maybe a bit more math and you can expand it for multiple paths. I don't know though, I'm not a mathematician and I don't normally have to do more than DFS and BFS in coding interviews, but sure I can see some way that this might be useful.
Genetics for one. If a DNA primer-pair is looking for it's complement [0], then this strategy could be useful. Here the prisoners are the complementary primers and the DNA-sequence-to-be-matched-to is the cabinet. Shepherding proteins/histones could restrict in a nucleic bottleneck of some sort, such that only one primer gets to go at once without repeating [1]. Only when the primers are all set-up is the DNA 'free' to be transcribed or some such thing.
[0] For a sequence like ATGC, the primer is the opposite nucleotide, therefore the 'matching number' would be not ATGC as well, but TACG.
[1] Look, bio is weird, like, jumping genes are actually a thing. This set-up, though strange, is not as unreasonable as a lot of stuff that goes on.
> Because the prisoner starts on the box of their own number they are, by definition, on the chain that contains their ticket (there is only one ticket that points to that box).
Wikipedia provides exactly the same explanation that your link does:
> The prison director's assignment of prisoner numbers to drawers can mathematically be described as a permutation of the numbers 1 to 100.
> Every permutation can be decomposed into disjoint cycles, that is, cycles which have no common elements.
> In the initial problem, the 100 prisoners are successful if the longest cycle of the permutation has a length of at most 50. Their survival probability is therefore equal to the probability that a random permutation of the numbers 1 to 100 contains no cycle of length greater than 50.
What did you think was missing from the Wikipedia article?
> The cycle notation is not unique since a cycle of length l can be written in l different ways depending on the starting number of the cycle. During the opening the drawers in the above strategy, each prisoner follows a single cycle which always ends with his own number.
Think of it this way: you are always in a chain. It can be between 1 and 100 boxes long. But it can’t be a dead end or not include the 1-note. Worse case it visits all boxes and gets back to 1.
Try forming a scenario that doesn’t. E.g a “loop”:
Prisoner #1 opens box 1. Finds the number 2. Opens box 2 finds the number 3. Opens box 3...
Could he now find the “2” that would lead to him being stuck in the 2-3 loop? No. He already found the 2. It can’t appear again. In the third box he’ll find a number he hasn’t seen. The loop cannot form in any other way than to come to where he started - which it will do when he finds the note with “1” on it.
So by starting with box 1, he is on a loop of length 1..100 including the pointer TO box 1 (which is what he is looking for).
Ok, so I‘m walking a linked list that will lead to my number. But I still don’t get why the odds are better than just opening the first 50 boxes and hope for the best? What changes because I‘m on the chain?
The chance of you finding your number with 50 random opens is 50%. But you don't live jusr because you find your number. You only live if everyone finds their number. And that chance is slim: it's .5^100 which is a very small number.
The chance of finding your number using the chain algo is the same as the chance that your number is found before the 50th step of your chain. That probability is still 50% because you are opening at most 50 boxes of a 100, the order doesn't matter. This is why you feel nothing will change, that the order shouldn't matter. That is correct: each prisoner opens 50 boxes without any prior information.
But the key is what changes for the probability of success for the group.
All prisoners use the same shuffling (it's only randomized once). Everyone will succeed when walking their chains, if the longest chain is shorter than 50. That is, if there are two chains of 60,40 then the group will fail. Because some of the prisoners who are unlucky and have numbers in the 60 loop will to reach their number in 50 steps.
But if there are two chains of 50,50 or 3 chains 30,30,40 etc., then everyone will succeed.
So the difference is that with random choice, YOUR chance of finding YOUR number is 50%. The chance that all 100 does so you live, is .5^100.
With the chain walk, YOUR chance is still 50%, as is everyone elses. Yet the risk that someone fails is now just 70% instead 99.9999999...% (Now is no multiplication - the probabilities are not independent - the probability of success for the group is now a property of the loops rather than the product of 100 independent events)
Imagine Strategy A, where everyone started at box 1 and checked 1-50. Half of the prisoners would succeed, guaranteed, but half would fail, guaranteed, and prisoners would never win.
A slightly better Strategy B is to start at their own box and all subsequnt ones, wrapping around at 100. Now you have at least a small chance, but each prisoner winning independently is low.
What cycle method Strategy C does is group up failures. When prisoners fail because there's a cycle of size 51+, 51 fail. When there's a cycle of 99 boxes, all prisoners fail. But in exchange, there's more possibilities where there aren't cycles that long.
So it's not that the odds are better for an individual as much as the odds are better that the individual's successes coincide. In Strategy A, the success of an individual prisoner decreases the estimated success probability for subsequent prisoners. In Strategy B, that decreased probability is nullified by incrementing the starting location by one step. In strategy C, a prisoner's success or failure amplifies the estimated success probability for others. Not by changing any state, but revealing the state itself.
The success criteria goes from the prisoners randomly picking correctly to the warden not randomly creating a loop larger than 50. If the warden creates no loop greater than 50 then the prisoners win. If he creates one of 51 or more then the prisoners lose because the 51st number wont be found.
Think of it this way - if all the boxes are sorted then everyone finds their own number in their box.
But let's say that everything is sorted except your's and some other prisoner's number. Then it makes sense to follow the chain, because there is only one chain of two nodes.
Basically any number that is in its place is sorted and thus not part of a chain. Any number that is not in its place is not sorted and part of a chain.
There can be many different chains, but only one chain that leads to your number. By starting from your own box, you guarantee that you follow your own chain thus reducing the search space.
> If just one prisoner does not find his number, all prisoners die.
You're trying to find a strategy that is successful for all prisoners. Following the chain reduces the problem to "is there a cycle of length >50", which can be calculated easier.
Opening boxes randomly (or arbitrarily, as in "50 boxes starting with my number), by all prisoners, is 50%100 which as mentioned is vanishingly small. The trick is that chain-following actually gives information to each prisoner as they go, which helps leverage into a better win chance.
Opening 50 boxes at random gives you a 50% chance to hit the right box. But everybody else also has a 50% chance that’s independent from yours, so you just multiply the probabilities together to figure out the overall probability. This makes it vanishingly unlikely to get it right with a lot of people.
This strategy instead has you all collectively betting that the structure of the permutation is favourable, which doesn’t have that multiplicative problem.
This strategy weeds out chains that don't contain your number.
If there are 3 chains, one contains your number, and two are loops that don't contain your number, this strategy necessarily starts you in the chain that contains your number.
Open box 7, find number 2
Open box 2, find number 2700
Open box 2700, find number -16
Open box -16, find number 0.9
Open box 0.9, find number ℵ
Open box ℵ, find number 赢
Open box 赢, find number two
...
As you can see, it's not necessary to use numeric digits to identify the boxes; any identifier at all will do.
But this is a cycle; if we had started by opening box 0.9, it would look like this:
Open box 0.9, find number ℵ
Open box ℵ, find number 赢
Open box 赢, find number two
...
Open box 7, find number 2
Open box 2, find number 2700
Open box 2700, find number -16
Open box -16, find number 0.9
Exercise: given that this cycle starts with "open box 7", how does it end? (Or in other words, what is the second half of the line before "Open box 7"?) If this cycle instead started with "Open box ᚠ", how would it end in that case?
If you consider that each box only has one box that "points" to it, and that last box must necessarily be part of the box's cycle (by definition, there's no way to avoid it as if you hypothetically swapped the last box to point somewhere else then all you're doing is linking the cycles and you'll end up in the same place but later)
For me it helped to think of it as a collection of linked lists. At most, there can be 100 lists of length 1, where each number points to itself. On the other extreme, there are many ways to create a list of length 100.
The strategy takes advantage of the fact that randomly permuting the numbers is less likely to create one or two long lists, and more likely to create a bunch of shorter lists.
Since each prisoner knows which list he belongs to, he can use that information to reduce his search space from all of the boxes to just the boxes in his list.
> What did you think was missing from the Wikipedia article?
Oddly enough as stated the problem fails. It essentially assumes an evenly distributed random placement of numbers. However if the warden simply adds the same random number to every single box it ends up as a very long cycle and they all fail.
Worse, they have to communicate which order to count from. Is box 1 the top left or bottom left box?
PS: The problem shows up in many such puzzles because 'the problem' was based on the math rather than the math being chosen to solve the problem.
Depends on context, I randomly tossed it does not imply all locations it might end up are equally likely. As it rolls after impact it's more likely to end up in a dip than on top of a hill etc. At best the direction is random but not necessarily the angle with respect to the ground.
Basically, even distributions are very rare in the real world.
One operation to shuffle a deck of cards is to cut it creating a random offset.
So, I have seen someone just move the top few cards when asked to shuffle the deck. This makes a small offset more likely than you might assume. Remember the odds should be evenly spread across 52! which means in all of human history each deck should be unique, but in practice people have played with a default deck. (http://www.philly.com/philly/news/new_jersey/20120904_A_C__s...)
Funny thing: if that added number isn't relatively prime to 100 - and 60% of random numbers would share a factor - then they've just made a lot of smaller cycles.
And it's easy to break if you can swap two. Say the warden adds one. If you swap 50 and 100, you have two cycles of 50.
Again assuming the uniform random distribution. Select from (1, 3, 6, 7, 9, 11) is just as random as selecting from 1-100.
I would argue that not specifying the boxes have a specific order is a much larger problem, but saying 'random' does not nessiarly mean what you might think. As to moving the cards, they are specifically excluded from communication.
There is not, actually! You can show this strategy does as well as the case where prisoners have full information of each other's moves.[0] So any other strategy where each prisoner is blind to others' actions can always be executed in the full-information case above; so this bound is tight and this strategy is optimal: if there was a strategy that did better in the blind case, you could execute it in the full-information case to get a better outcome, but this is impossible.
For a nice exposition of this, see Curtin and Warshauer's article "The Locker Puzzle."
---
[0] More specifically, a game where all lockers are left open, so every strategy has the same probability of winning.
To be precise, the strategy is shown to be optimal as well in a modified game where all lockers are left open and you cannot open any more lockers if you find your own number.
Is this problem useful for anything? I've seen multiple variations of these prisoner problems now, and I can never remember any being useful in other contexts.