Probability · Waiting times · Medium
A song you have heard
A playlist holds four songs. Every time, the player picks the next song uniformly at random from all four, independently of what it has played before, so the same song can play twice running. You listen from the first song until a song plays that has already been played, and then stop. What is the expected number of songs played, counting the repeated one?
Answer and solution
Answer
103/32 ≈ 3.21875
Solution
Sum the probabilities that the first k songs are all different.
You hear more than k songs exactly when the first k are all different. That has probability 1 for k = 0 and 1, then 3/4, then 3/4 × 2/4 = 3/8, then 3/8 × 1/4 = 3/32, and 0 for k = 5. The expected count is 1 + 1 + 3/4 + 3/8 + 3/32 = 103/32 ≈ 3.22.
Waiting times comes up in 8 firms' roundsCitadel Securities · Goldman Sachs · Jump Trading · +5
These 9 rounds ask this kind of problem live, with follow-ups. Every round on every track is in Premium.