100 Prisoners

[pzhon]

[ QUOTE ]
Prisoner i starts by searching box i. Then if his last opened box revealed the name of prisoner j, search box j next.

[/ QUOTE ]
A few comments:

[img]/images/graemlins/diamond.gif[/img] Nice. I didn't have the right interpretation of the problem. I found another, more awkward one which also led to the ln(2) answer, and didn't look further.

[img]/images/graemlins/diamond.gif[/img] The December 2006 IBM Ponder This challenge was to compute the asymptotic probability that a random permutation in S_n has no cycle of length longer than x*n for x>=1/2. For x=1/2, the probability equals the asymptotic probability that Marv's method succeeds.

[img]/images/graemlins/diamond.gif[/img] It's not obvious to me that throwing away the other information is optimal. If you have seen that Box 1 contains 5, and Box 5 contains 3, then at that point you only use the last piece of information. You don't use that you know how many boxes you have opened or the contents of the previous boxes. Is there a simple argument showing that this is optimal anyway?

[img]/images/graemlins/diamond.gif[/img] It looks to me like the probability that no stick is greater than x is the asymptotic probability that a random permutation from S_n will have no cycle of length greater than x*n. I didn't realize that while finding the lag differential equation for the generalized stick problem.

[img]/images/graemlins/diamond.gif[/img] Has anyone worked out the asymptotics in the other direction, as x decreases? For a fixed small x such as 1/100, what is the probability that a randomly chosen permutation no cycle has length greater than x*n? I think it's much clearer that the rough asymptotics should be something like x^(c/x) from the stick breaking description than the permutations, but I think it is a natural question to ask about permutations.

[img]/images/graemlins/diamond.gif[/img] I conjecture that there are similar functional equations for the probabilities that precisely k cycles are greater than x*n. We looked at k=0 here.

[jason1990]

[ QUOTE ]

[img]/images/graemlins/diamond.gif[/img] It's not obvious to me that throwing away the other information is optimal. If you have seen that Box 1 contains 5, and Box 5 contains 3, then at that point you only use the last piece of information. You don't use that you know how many boxes you have opened or the contents of the previous boxes. Is there a simple argument showing that this is optimal anyway?

[/ QUOTE ]
I too would like to know this. djames, do you have an answer for this?

[ QUOTE ]

[img]/images/graemlins/diamond.gif[/img] Has anyone worked out the asymptotics in the other direction, as x decreases? For a fixed small x such as 1/100, what is the probability that a randomly chosen permutation no cycle has length greater than x*n? I think it's much clearer that the rough asymptotics should be something like x^(c/x) from the stick breaking description than the permutations, but I think it is a natural question to ask about permutations.

[/ QUOTE ]
First, let me confess to not having thought about this at all, so the following comment is entirely heuristic. But if it is easy to see the asymptotics for the stick problem, then why should it not be easy to translate that into the asymptotics for the permutations? The prisoner puzzle with n prisoners is mathematically identical to the stick puzzle under the restriction that the breaks must occur at points of the form j/n. Some kind of dominated convergence argument ought to easily carry results back and forth between the two.

[djames]

[ QUOTE ]
[ QUOTE ]

[img]/images/graemlins/diamond.gif[/img] It's not obvious to me that throwing away the other information is optimal. If you have seen that Box 1 contains 5, and Box 5 contains 3, then at that point you only use the last piece of information. You don't use that you know how many boxes you have opened or the contents of the previous boxes. Is there a simple argument showing that this is optimal anyway?

[/ QUOTE ]
I too would like to know this. djames, do you have an answer for this?

[/ QUOTE ]

Unfortunately, no. But, a googling clue is that I read Eugene Curtain and/or Max Washauer have proven this result. Perhaps someone more skilled with this series of tubes can provide us all a link.

However, it appears that there is currently agreement that the stick problem and the prisoners problem are equivalent. Therefore, if the prisoners problem has a better solution, then wouldn't the stick problem's answer also be different? Either this would be the case, or the problems are not equivalent afterall.

[jason1990]

The probability of having a broken stick piece whose length is greater than 1/2 is equivalent in the limit to the probability of having a cycle of length greater than n/2. In other words, once you decide on the strategy in the prisoner problem, then it is equivalent to the stick problem after that. But the question about the optimality of the prisoner strategy has no analog in the stick problem. At least not one I can see. So I do not think the stick problem can shed light on whether or not the cycle strategy is optimal in the prisoner problem.