prisoner puzzle: big hint
Previously I described a puzzle of prisoners and hats. Each of 100 prisoners had a 50-50 chance to pick his number from his 50 picks from hats. For any prisoner to survive (puzzles tend to be violent; it's true), every one of the 100 prisoners needed to succeed with his 50-50 chance. Simple probability says the chance of the prisoners surviving is essentially zero: you can't flip a fair coin 100 times and get heads every time. The key, it turns out, is to use a rigged coin.... Go to that link now if you don't want to see a really big hint.
Move below the cute kitten photos to proceed...
Okay, enough of that. Here's that big hint. For simplicity, I'll assume 8 (not 100) prisoners and 4 (not 50) hats. I show two sequences: one which wins, the other which loses.
The winning sequence:
4, 6, 3, 0, 2, 1, 5, 7
The losing sequence:
4, 2, 3, 0, 1, 6, 5, 7
These sequences are permutations: various orderings of the same elements. The key insight is that these permutations descibe loops. The probability distribution of the length of a loop associated with a random element is unifrom from one to the number of elements in the set. So for 100 prisoners, if I pick a given hat, then follow the sequence as shown, I will end up back at that hat in from one to 100 steps, each with equal probability. Complete the loop and you've found your number. If your loop has a length no more than half the number of elements, you win, or else you lose. If you win, because your loop is short enough, then everyone else in the same loop will win. And if you lose because your loop is too long, then everyone else in the loop will lose.
This is why the solution is like a weighted coin: you don't know if it's rigged to come up heads or tails, so the first flip is 50-50 chance of a win. But if you commit to picking either heads or tails every time, if you luck out and guess right on the first flip, every successive flip is in your favor. Same with the prisoners. If the loops are all length less than half the total, then every prisoner wins. If any loop is more than half, then every prisoner on that long loop will fail. It's impossible that less than half the prisoners will fail except that no prisoner fails.
So what's the probability of success? Consider the limit of a large number of prisoners. The first prisoner has the probability 50% of success. If he succeeds, then the length of his loop has any value from 0 to 50% the number of prisoners with equal probability. Eventually a prisoner will pick a hat which is in a different loop. The probability of success for that loop is better, since there's fewer remaining hats after the first loop, and the maximum length of the loop is still half of all of the hats together. Simple analysis shows the second loop has a 75% chance of success.
My fellow Caltrain passenger explains the theoretical chance of failure, in the limit of an infinite number of prisoners, is the natural logarithm of two, or 69.3%. That leaves a 30.7% chance for success. My 100 thousand trials had had a 29.919% success rate, with a standard error of 0.45%.
So I didn't explicitly describe the solution, but it should be fairly obvious from the diagrams.
Move below the cute kitten photos to proceed...
Okay, enough of that. Here's that big hint. For simplicity, I'll assume 8 (not 100) prisoners and 4 (not 50) hats. I show two sequences: one which wins, the other which loses.
The winning sequence:
4, 6, 3, 0, 2, 1, 5, 7
The losing sequence:
4, 2, 3, 0, 1, 6, 5, 7
These sequences are permutations: various orderings of the same elements. The key insight is that these permutations descibe loops. The probability distribution of the length of a loop associated with a random element is unifrom from one to the number of elements in the set. So for 100 prisoners, if I pick a given hat, then follow the sequence as shown, I will end up back at that hat in from one to 100 steps, each with equal probability. Complete the loop and you've found your number. If your loop has a length no more than half the number of elements, you win, or else you lose. If you win, because your loop is short enough, then everyone else in the same loop will win. And if you lose because your loop is too long, then everyone else in the loop will lose.
This is why the solution is like a weighted coin: you don't know if it's rigged to come up heads or tails, so the first flip is 50-50 chance of a win. But if you commit to picking either heads or tails every time, if you luck out and guess right on the first flip, every successive flip is in your favor. Same with the prisoners. If the loops are all length less than half the total, then every prisoner wins. If any loop is more than half, then every prisoner on that long loop will fail. It's impossible that less than half the prisoners will fail except that no prisoner fails.
So what's the probability of success? Consider the limit of a large number of prisoners. The first prisoner has the probability 50% of success. If he succeeds, then the length of his loop has any value from 0 to 50% the number of prisoners with equal probability. Eventually a prisoner will pick a hat which is in a different loop. The probability of success for that loop is better, since there's fewer remaining hats after the first loop, and the maximum length of the loop is still half of all of the hats together. Simple analysis shows the second loop has a 75% chance of success.
My fellow Caltrain passenger explains the theoretical chance of failure, in the limit of an infinite number of prisoners, is the natural logarithm of two, or 69.3%. That leaves a 30.7% chance for success. My 100 thousand trials had had a 29.919% success rate, with a standard error of 0.45%.
So I didn't explicitly describe the solution, but it should be fairly obvious from the diagrams.
Comments