Probability · Expectation · Medium
A reshuffle of desks
Eight traders each have their own desk. Overnight the desks are reassigned, one to each trader, with all 8! assignments equally likely, so a trader may keep their own desk. Your chain is made up of you, the trader whose old desk you now have, the trader whose old desk that trader now has, and so on, until the chain comes back to you; if you keep your own desk, your chain is you alone. What is the expected number of traders in your chain, counting yourself?
Answer and solution
Answer
9/2 ≈ 4.5
Solution
The length of your chain is equally likely to be each of 1, 2, …, 8.
For the chain to have exactly k traders, each of the first k − 1 desks followed must not be your old desk and the k-th must be: 7/8 × 6/7 × … × (8 − k + 1)/(8 − k + 2) × 1/(8 − k + 1) = 1/8. The expected length is (1 + 2 + … + 8)/8 = 4.5.
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.