0

Trying to understand the solution for a single prisoner in the 100 prisoner puzzle if he chooses randomly it is pretty straight forward 1/2

but if he uses the method described in solution (following permutation cycle) it is still 1/2

looking into the wiki page the explanation for this is as follows

$$ {\displaystyle (1-\ln(2))\cdot 1+\sum _{k=\lfloor n/2\rfloor +1}^{N}{\frac {1}{k}}\left(1-{\frac {k}{n}}\right)=1-\ln(2)+\sum _{\lfloor n/2\rfloor +1}^{N}{\frac {1}{k}}-\sum _{k=\lfloor n/2\rfloor +1}^{N}{\frac {1}{n}}=1-\ln(2)+\ln(2)-{\frac {1}{2}}={\frac {1}{2}}} $$

how did they derive this formula ? or why is it still 1/2 ?

Mike
  • 351
  • 2
    It is still $\frac{1}{2}$ because considering an isolated prisoner opening fifty of 100 boxes without any extra information will always have a $50%$ chance of picking the right one. The reason the permutation cycle increases the probability for all of them to get the right answer by making their guesses dependent in a smart way. – ItsMe Jul 29 '22 at 02:40

1 Answers1

1

This is (suppose to be) the probability that the cycle of a randomly chosen point within a random permutation (of N=100 points) is less or equal N/2=n=50. Which is exactly the probability that a prisoner survives according to the cycle strategy in the modified problem where each prisoner's survival doesn't depend on the survival of other prisoners.

You can try to simplify it by computing the probability that the cycle of 0 within a random (uniform) permutation of the numbers 0 ... 99 is longer than 50. You can write:

$$ P(\textrm{prisoner doesn't survive} ) = P(\textrm{cycle of 0 is longer than n} ) = \sum_{k=n+1}^{N}P(\textrm{exists a cycle of length k and 0 is in that cycle}) = \sum_{k=n+1}^{N}\frac{k}{N}P(\textrm{exists a cycle of length k}) = \sum_{k=n+1}^{N}\frac{k}{N} \frac{1}{k} = \sum_{k=n+1}^{N}\frac{1}{N} = \frac{N-n}{N}=\frac{100-50}{100}=\frac{1}{2}. $$

Note that if there exists a cycle of length $k>n$, then it needs to be the unique cycle that is longer than n (all other cycles can be at most N-k long), hence the k/N probability for 0 to be in there. In the step of the probability of existence of a k-cycle being equal 1/k we used this: Probability of a m-long cycle

The presentation on the Wikipedia page is not clear, I am not sure why it's like that. Probably someone copied a more general formula from somewhere.

Alexisz
  • 501
  • 1
    for the puzzle to work does the original arrangement of notes boxes have to stay the same between each prisoner ? i.e. can we randomize notes placement after each prisoner ? – Mike Jul 30 '22 at 18:12
  • In the original problem, the opening choices of the prisoners are not independent, because their boxes are not independent and the arrangement stays the same (e.g. two prisoners cannot have the same box). Therefore, when considering N prisoners together, having distinct boxes and each following the permutation strategy, and not changing the permutation every time, the probability of all succeeding is not (1/2)^N because of the dependent events of a single prisoner finding it's number. – Alexisz Jul 31 '22 at 19:28
  • Between prisoners the outcome of the experiment is independent if their starting number and the permutations are independent across prisoners. But in this problem we really just look at one prisoner. We still need to consider whether having for this single prisoner a random box, or one fixed box (e.g. 0) makes any difference when computing the probability. It turns out, there is no difference as each choice of fixed box results in the same probability of 1/2. So, now using law of total probability you can conclude that it's still 1/2 with a randomly chosen box for the single prisoner's number. – Alexisz Jul 31 '22 at 19:36
  • Now for the dependence structure in the original problem. (1) assuming all prisoners have a distinct fixed number, but the permutation changes independently across prisoners. (2) assuming the permutation is fixed, but the starting numbers are independent we get different problems to solve. For (1) you get (1/2)^N for the same reason as in my answer. For (2) everyone finds the number if there is no cycle of length > 50. The probability of this is still bounded below by P(there is no cycle with lenght > 50) >= 30.68% , as you can see in the linked answer about "Probability of a m-long cycle". – Alexisz Jul 31 '22 at 19:47