How many prisoners find their number on average?

Question

A hundred prisoners, a hundred boxes with their numbers inside in random order, each prisoner may open fifty boxes. With the famous follow-the-chain strategy, the probability that all hundred succeed is about 31 per cent, compared with essentially zero for random guessing.

Does the strategy also increase the average number of prisoners who find their own number? What is that average under random guessing, and under the chain strategy?

Accepted Answer

The average is 50 either way. The strategy does not change how many succeed on average; it changes when the successes happen. Random guessing. Each prisoner opens 50 of 100 boxes, so finds their number with probability 1/2. The expected number of successes is 100 × 1/2 = 50. Chain strategy. Pick any single prisoner. Her chain reaches her number within 50 openings exactly when the cycle containing her number has length at most 50. For a random arrangement, the cycle through a particular element has length L with probability 1/100 for every L from 1 to 100 (a classical fact about random permuta…

How many prisoners find their number on average?

Your answer

Discussion

Learn the concepts

Related questions