A Youtube video discusses the 100 Prisoners Problem. At 9:40 he says that if there is only a single prisoner, their odds of finding the correct box containing the slip with his number will be 0.5, whether they use the "random method" or the "loop method". Wikipedia also says that the expected value of the single prisoner surviving is 0.5, regardless of method used. (If you're not familiar with the riddle and/or the solution, watch the video or see the wikipedia article. Ensure you understand that the loop method guarantees that you're on track to eventually hitting the box with your number slip. The only problem is when the loop's length is greater than the number of boxes you're allowed to open, then you definitely won't make it to the correct box and are guaranteed to fail.)
I have 2 questions regarding the single prisoner's probability.
1.This question discusses a single prisoner using the random method. To simplify this question, let's use a smaller case of 10 boxes, and a single prisoner (Bob) is allowed to pick and check the paper inside 5 boxes. When Bob picks his first box, the probability of him picking the box containing the slip with his number is 1/10. If he sees that it didn't have his number, he now sees 9 remaining boxes. When he makes his second choice, I would think that the probability of picking the correct box is now 1/9. Because he received new information that he didn't have before he picked the first box. So the probability would be expressed as P(Pick correct box | Box A is incorrect). If Box B is also incorrect, he is ready for his 3rd choice. He knows 2 are definitely wrong, and is hoping he makes a lucky choice out of the remaining 8. Therefore, the probability of that choice being correct is 1/8. If we follow this logic, then the probability of finding the correct box after having completed 5 successive choices would appear to be: 1/10 + 1/9 + 1/8 + 1/7 + 1/6 ~ 0.6456 . The only way I see the probability being 0.50 is if Bob had to make all of the choices before gaining any information, i.e. before he even opened the first box. So my question is: How is the probability only 0.5 if he gained information after each selection; shouldn't the probability of choosing the correct box increase with each successive choice?
2.This question discusses a single person using the loop method. Let's go back to the original setting of 100 boxes and being allowed to check 50 boxes. The above sources state that the probability for the longest cycle (loop) to be >50 is approximately 0.69. The probability of the longest cycle being <= 50 is approximately 0.31. On average, approximately 31 out of 100 cases will only contain loops of 50 or less. In those ~31 out of 100 cases, if Bob uses the loop method, he is guaranteed to successfully find the box containing the correct slip.
In the ~69 of 100 cases that have a loop > 50, what is the probability of the box with the prisoner's number being in that dreaded long loop? For example, if the longest loop is 65 boxes and a small loop (or loops) consist(s) of the remaining 35 boxes, it would appear that the probability of Bob's box being in the 65-box loop is 65/100 (longest loop length / 100) and being among the other 35 boxes is 35/100, $[100 - longest loop length] / 100$. So when longest loop = 65 and Bob uses the loop method, the probability of Bob finding the correct box is 0.35. So the probability of survival in each of these 50 scenarios (longest loop = 51, longest loop = 52, ...) is: $[100 - longest loop length] / 100$
Therefore the probability of survival using the loop method would be:
1, if longest loop <= 50
$[100 - longest loop length] / 100$, if longest loop > 50
Therefore, to calculate the expected value of survival using the loop method, we would need to take the probability of each longest chain length greater than 50 occurring and multiply by that scenario's survival probability, and add all of those plus ~0.31183 * 1.0 (i.e. the scenarios of <= 50 which all have 100% survival). I would greatly appreciate if someone can calculate that. If that number doesn't equal 0.5, then my question is which probably is correct.
Thank you
You need to look to your argument again for the first question the probability is:
$$\frac1{10} + \frac{9}{10}\times \frac19 + \frac9{10}\times\frac8{9}\times \frac17 + \ldots = \frac5{10} = \frac12$$
The second question you are not correctly dividing the cases. The problem with your argument that you don't look at the loop containing Bob number which can be other loop than the longest loop in the permutation.