Probability · Expectation · Hard
A gift exchange of five
Five friends each draw one name from a hat holding their five names, to decide who buys a gift for whom. The whole draw is repeated until nobody has drawn their own name, so every assignment in which nobody draws their own name is equally likely. What is the expected number of pairs of friends who have drawn each other's names?
Answer and solution
Answer
5/11 ≈ 0.4545
Solution
Count the allowed assignments in which a given pair swap, divide by all allowed assignments, and add over the ten pairs.
Assignments of five names with nobody drawing their own: 44. If a given pair draw each other, the other three must draw among themselves with nobody drawing their own: 2 ways. So a pair swaps with probability 2/44 = 1/22, and the expected number of such pairs is 10 × 1/22 = 5/11 ≈ 0.45.
Expectation comes up in 10 firms' roundsJane Street · Hudson River Trading · Citadel Securities · +7
These 14 rounds ask this kind of problem live, with follow-ups. Every round on every track is in Premium.