4 ms·

Let's make the game harder by not letting the prisoners see what's inside the opened drawers. Is it hopeless now?

by jwilk 9y ago

jrq 9y ago
Yes
majewsky 9y ago
That's just a game of chance. The point of a skill game, even one that involves randomness, is that information you get can influence your actions. If you cannot look inside the drawers, you do not gain any information about the particular setup and thus cannot execute anything that would resemble a strategy.
- dmurray 9y ago
  They can still do slightly better than chance by ensuring their guesses have the right amount of overlaps. For example, if there were only two prisoners, the right strategy would be for one to pick box 1 and the other one to pick box 2, improving their odds of survival from 25% to 50%. I suspect the chances are still negligible for 100 prisoners though.
  - deleted 9y ago
    [deleted]
  - 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.

Let's make the game harder by not letting the prisoners see what's inside the opened drawers. Is it hopeless now?

by jwilk 9y ago

Let's make the game harder by not letting the prisoners see what's inside the opened drawers. Is it hopeless now?

jrq 9y ago

Yes

majewsky 9y ago

That's just a game of chance. The point of a skill game, even one that involves randomness, is that information you get can influence your actions. If you cannot look inside the drawers, you do not gain any information about the particular setup and thus cannot execute anything that would resemble a strategy.

dmurray 9y ago
They can still do slightly better than chance by ensuring their guesses have the right amount of overlaps. For example, if there were only two prisoners, the right strategy would be for one to pick box 1 and the other one to pick box 2, improving their odds of survival from 25% to 50%. I suspect the chances are still negligible for 100 prisoners though.
- deleted 9y ago
  [deleted]
- 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.