3 ms·
> I suspect the chances are still negligible for 100 prisoners though. I think from a probabilistic standpoint, they're equivalent as n increases. Think of it
by peeters 9y ago
> I suspect the chances are still negligible for 100 prisoners though.
I think from a probabilistic standpoint, they're equivalent as n increases. Think of it as the inverse; what's the probability each box is checked by its owner?
Pb = Nb / N, or number of people that checked that box divided by number of people total.
If there is perfect, premeditated overlap, then Nb / N is exactly 50/100, so we get the "(1/2) ^ 100" that was already cited in the article.
If prisoners choose randomly though, the expected value of Nb is still 50 though. You've maximized Nb in practice, but not really in theory.
- dmurray 9y ago> If prisoners choose randomly though, the expected value of Nb is still 50 though. The expected value of Nb would still be 50 if all the prisoners checked the same subset of boxes, but the chance of the prisoners surviving would clearly be 0. I think it's correct that if the prisoners don't get the see the contents of the boxes, then any arrangement where each box is opened by 50 prisoners is equally good and optimal - but I can't quite see a proof.
- peeters 9y ago> The expected value of Nb would still be 50 if all the prisoners checked the same subset of boxes, but the chance of the prisoners surviving would clearly be 0. Yes I should have expanded. The probability of escape is ∏ (i = 1..N) Ni / N So if some Ni is 0, the whole thing is 0. My point was that if you're choosing randomly, then as N goes to infinity, "Ni / N" already converges to 0.5 . So your strategy is ensuring optimality, but you'd get there if you took it to the limit anyway. As a quick test I did 1000 trials. The minimum overlap in those 1000 trials was 26. 95% of the time it was above 35. For N = 1000, 95% of the time it was above 440.