Question

a group of n people are trying to find their umbrellas after leaving a party (all n umbrellas are mixed together). each grabs a random umbrella at the same time (so the umbrellas are randomly permuted among the people). those who obtained the correct umbrella leave, while everyone else picks again randomly. this process continues until everyone has gotten his or her umbrella. what is the expected number of rounds needed?

Answer 1

The expected number of rounds for everyone to find their umbrellas in the given process, where each person grabs randomly until getting their own, is
`\( n \).`

Initially, each person grabs an umbrella randomly, which means the probability of anyone getting their own umbrella is
`\( (1)/(n) \)` since there are
`\( n \)` umbrellas randomly distributed among
`\( n \)`people.

Now, for each round, the probability that someone doesn't get their own umbrella (and thus has to pick again) is
`\( (n-1)/(n) \)` because they didn't get their own umbrella on the previous attempt. This also means that the probability of someone getting their own umbrella in one round is
`\( (1)/(n) \).`

Let
`\( X \)` be the number of rounds needed for everyone to find their own umbrella.

The probability of getting the correct umbrella in one round is
`\( (1)/(n) \)`. The probability of not getting it in one round is
`\( 1 - (1)/(n) \)`.

Therefore, the probability of needing exactly \( k \) rounds until someone gets their own umbrella is
`\( \left(1 - (1)/(n)\right)^(k-1) * (1)/(n) \)`because they need
`\( k-1 \)` failures (not getting their own umbrella) and then one success (getting their own umbrella) in the \( k \)th round.

The expected value of \( X \) is the sum of the products of the number of rounds (\( k \)) with their respective probabilities, i.e.,

`\[ E(X) = 1 * \left(1 - (1)/(n)\right)^(0) * (1)/(n) + 2 * \left(1 - (1)/(n)\right)^(1) * (1)/(n) + 3 * \left(1 - (1)/(n)\right)^(2) * (1)/(n) + \dots \]`

This is an infinite geometric series, and the formula to sum it up is \( E(X) =
`(1)/(1 - (1 - (1)/(n))) = (1)/((1)/(n)) = n \).`

Hence, the expected number of rounds needed for everyone to find their own umbrella is
`\( n \)`.