Hacker News Reader

Comment by micaeked | Hacker News Reader

Since wikipedia doesn't explain why it works (or maybe I just didn't understand it), I found this explanation much better: http://datagenetics.com/blog/december42014/index.html

View on HN

This is a great explanation.

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.

It sounds like a parallelization algorithm. Spin up a hundred threads each whom does not need to communicate with anyone.

Thank you. This is a MUCH better resource.

This sentence did the trick:

> 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).

That's really the sentence that seems to be wrong, until you see the light shine through the problem.

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 prisoner starting with their own number box ensures that they are in the chain with their number ticket in it.

> 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.

And thats the part I still don't understand.

So, following your cycle looks like this:

    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?

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 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.

That was the shortest description that worked for me. Framed this way, its obvious - thanks, also to all the others!

Assuming that linked list is shorter than 50, you're guaranteed to find your own number.

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.

Maybe it helps to understand...

The goal isn't to maximize an individual's odds of finding their number, but maximizing the odds of the entire group finding their number.

> 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.

OK I'll give it another go :)

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)

I think this explanation makes the most sense, since it explains the non-independence of the player's actions. Another way I thought of it was this: imagine (despite the prisoners' knowledge) each prisoner actually had the same number. The "choose at random" strategy would still have a vanishingly small probably of success, while (any) deterministic strategy would yield a 50% rate of group success.

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.

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.

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.

This point was obvious once pointed out, and is definitely the reason this link clicked for me and the Wikipedia explanation did nothing.

As I pointed out in a sibling comment, this is also stated in the Wikipedia article.

Better graphics

> 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.

Random distribution of numbers is part of the problem statement:

> The director randomly puts one prisoner's number in each closed drawer.

From the problem description on Wikipedia.

The director _randomly_ puts one prisoner's number in each closed drawer.

Random does not mean independently chosen random number.

Consider, if you pick a completely random location then two numbers could end up in the same box so one prisoner's number implies there is some order.

Further, random does not mean even distribution. The logic is really based on a very specific kind of random distribution.

If you shuffle a deck of cards, do you ever get a 2/5 of heart/diamonds?

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...)

Colloquially, "random" does imply a uniform distribution.

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.

Even if the warden's assignment of numbers to boxes is not random (perhaps he knows the suggested winning strategy and wants to foil it), the players can make it random by randomly permuting the numbers on the outside of the boxes. This guarantees their 31% success rate even against an adversarial warden.

Players can't communicate. So, this comes down to what that means, but your suggestion is reasonable and might depending on how the problem was carried out apply.

aka, they can't all individually come up with the same random numbers without communicating. But, they could all independently come up with the same strategy if the all saw the same numbers on the outside of the boxes.

From the problem description on Wikipedia again.

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.

So they certainly could all use a pre-agreed random permutation to compensate for any insufficient or evil [non-]randomness introduced by the director.

I was not clear in my wording. They need to enter the room and know box one is this and thus I should treat that as box 22. But again without seeing the boxes they need a system to unambiguously order the boxes. That's not strictly a math problem as they are not say given exact x,y,z locations or precise measuring tools etc.

Or what if it is dark inside the room and they can not read the numbers in the drawers? Or what if there is no gravity in the room and they can not determine which drawers are at the top? Or what if the director used a script or number system none of the prisoners can read or understand? Or what if the numbers are only 100 nm tall inscribed with electron-beam lithography on small pieces of metal? Or what if there is no oxygen in the room? Or what if the room is 10,000 km long, wide, and high?

A Revolving Filing Cabinet or even just a two sided one is a not exactly a 10,000 km long room. But, I think your getting the argument.

If you assume something not explicitly as part of the puzzle it's not necessarily the correct solution.

They can communicate beforehand to come up with this scheme - it's clear they just can't communicate after looking at the boxes.

The generic version of the scheme is, after looking in box N, look in box f(N) where f is any bijective function from [1, 100], and all the prisoners agree on the same choice of f. The version described on the wikipedia page corresponds to f(N) := N, but any of the other 100! such functions would do so long as they agree on the same one.

You are treating this as a math problem not a puzzle. Is there anything written in the description that says they can all agree to an ordering that they can then apply their function to. Aka if they say box 1 maps to box 37 they need to agree what box 1 is and what box 2 is ...

From the page: '...Before the first prisoner enters the room, the prisoners may discuss strategy'

As I have pointed out in other comments discussing strategy without seeing the room makes finding a strict ordering difficult.

Picture them entering the room and the boxes are on a round filing cabinet. There is no obvious #1 to pick so some of the 100 would pick different #1's. Again, as a math problem it's reasonable to assume they can agree on an order, but it's not stated.

They can communicate, before they start. That's how they share the strategy with each other.

> 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

So they just write down a random permutation and give a copy to each prisoner while discussing strategy.

They need to communicate before seeing the boxes. You assume the can decide on a strict ordering before looking at the boxes. If they say box one is the highest box closest to the door their might be two boxes that satisfy that criteria. As a math problem it's assumed that such problems don't occur, as a riddle things are not so clear.

On the other hand, if they could communicate after getting a reasonable definition of the room and know they would not be moved then sure strict ordering is easy. But, nothing says they are given that.

Further, they need to pick random numbers without the warden deducing the scheme, but let's assume the can use a public key crypto to get around the need for privacy.

There are many strict orderings that can be used, but we just need one.

Since each number is in a physical draw in a physical room, and no two draws can occupy the exact same space, there is a strict ordering of the drawers given by each drawers distance from a fixed point in the room (say a specific corner agreed on beforehand) in each of the three orthogonal dimensions sideways (x), backwards (y), and up (z).

We say a drawer A is before a drawer B if A.x < B.x; or, if A.x = B.x then if A.y < B.y; or, if A.x = B.x and A.y = B.y then if A.z < B.z

If A.x = B.x and A.y = B.y and A.z = B.z then A = B.

This is a strict ordering that will number the drawers from 1-100, and can be determined beforehand.

Now the prisoners take that order, and shuffle it randomly, without telling the warden what they are doing.

As math that works fine, in practice it's a world of problems. A.x = B.x is a question of finite precision close enough and all prisoners will not agree if A.x = B.X or A > B or A < B. Adding precision tools does not help as you get into things like thermal expansion and the weight of prisoners deforming the floor etc.

So, while that works as a math problem, it may fail as an actual solution.

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.

Ah yes, that's where I first heard about this problem. Dategenetics is a great blog in general, with lots of interesting content.

Thanks for the compliment. </blush>

I'm curious, is there a better strategy?

Any better strategy would have to exhibit the cyclic behavior of the proposed strategy. I don't think there is any.

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.

Reply on news.ycombinator.com