I thought of this question whilst loading mp3s onto my iPod. Suppose my iPod has N songs on it, and each song of average length 4 minutes. Also suppose a truly random shuffle (ie the same song may be repeated.) How long must it play continuously to have a .5 probability of having played each song at least once?
Just N/2*4, or 2N. Imagine you have 4 songs. If you listen for 8 minutes, after 4 minutes each song has a 1/4 chance of being played. In the second 4 minutes, they also have a 1/4 chance of being played, so the total probability is 1/2
This looks a lot like the collector’s problem, although the bit where you need every song twice makes it slightly more complicated.
After 20 minutes, is there a 5/4 chance of each song having been played twice?
Just plain wrong.
I agree that this does look similar to the problem you linked to. But when did I say anything about needing to play songs twice?
That’s a very good question. Chalk it up to the early morning.
If N = 1, the probability is 1 after just 1 song has played. (Clearly).
If N = 2, the probability is 1/2 after just 2 songs have played. (The calculation is pretty easy).
So this formula is invalid in at least 2 cases.
This problem has come up on the board before (different context, but essentially the same problem):
That thread asks how many people you need to have at least a 50% chance of having all 365 possible birthdays (ignore leap years) represented.
The answer I gave in post 3 can easily be modified for this question, given a specific number of songs N on your ipod.