3 ms·

One Hundred Prisoners Problem

• version_five 5y ago
  This is cool
  • luca3v 5y ago
    If one player picks 50 of boxes, the probability of finding a particular number will be 50% independently of the strategy. (Note that sum([1.0/(100-n) for n in range(70)]) is more than one: the probability is 1/100 + 99/100 * 1/99 + ... which adds 1/100 in each try) The point of the cycle strategy is that there is at least a 30% probability that all 100 people will succeed, while this should intuitively happen only with probability (1/2)^100 which is inconceivably small.
• jl2718 5y ago
  Here is a simulation I wrote: https://replit.com/@JohnLakness/100Prisoners https://replit.com/@JohnLakness/100Prisoners I have printed out the distributions of the number of successes in each instance of 10000 problems, for both a baseline random selection and this strategy. (Can’t copypasta here b/c ipad) Look at my results and notice that the strategy does not affect the likelihood of any one prisoner to be successful in any random implementation of the problem. But, for any given configuration, the likelihood that they will all end up the same, either successful or not, is greatly increased. This is an information thresholding transformation, much like Reed-Solomon or Gallagher coding. In fact, I think there may be a direct transformation of the problem to LDPC, but that’s just an idea in my head.