Every day a group of friends play a strange game. Everyone writes their name on a slip of paper, folds it, and drops it into a hat. The slips are thoroughly shaken up, and then each player pulls a slip out of the hat. Anyone who draws a slip with their own name on wins a prize.
My question is: over a long series of games, what is the average number of players per game who win a prize?
Euler played this game too. (I know it as the sock pairing in the dark game)
This is related but not quite the same as the problem I asked about. I'm noy asking for e.g. the probability that at least one person pulls out their own name, but what is the mean number that pull out their own name, over a long series of repetitions of the game.
This could be answered by calculating derangements but that's a hard way to do it.
Ah, yes, much easier to answer the right question!
For n players. By symmetry,
p(1 draws 1) = p(2 draws 2) = ... p(n draws n) = 1/n
So surprisingly the expectation is 1 and is independent of the number of players.
Yes very nice, quite surprising, and follows easily from linearity of expectation.