My birthday is upon me.
My birthday present was an
iPhone 4. Yeah, I got it early, but it was nice to have for my just-finished vacation drive. I noticed that when I'd reshuffle the 1763 songs on there, I'd more often than not hit a collision with a song I swear I'd heard during the previous shuffling. Time for some math...
The
Birthday Problem (or Birthday Paradox, not because it's a real paradox, but because it's counterintuitive) shows that it only takes 23 people to be in the same room before the chances that two of them share a birthday are equivalent to a coin flip. The link above shows how one derives this. Basically, as you keep adding people, the probability of there NOT being a shared birthday decreases. That probability hits near-enough to 50% at 23 people.
I figured if I would have listened/remembered 30 songs from a previous shuffle. That's 2-3 hours of music, not a lot when you're driving all day. So if I accidentally shook my iPhone and reshuffled the songs, how many would I need to hear until I had a coinflip's chance of hearing a repeat from the previous 30?
Basically, the probability of NOT hearing a previously-heard song was (1763-30) / 1763. If that wasn't a repeat, the probability of another non-collision would be (1762 - 30) / 1762. Note that unlike the birthday problem, I'm decrementing the denominator as well. This is because I'm not going to hear the same song twice in a random shuffle.
I wrote a C program (because I hack way too much ON code) to compute things. Here it is:
#include <stdio.h>
int
main(int argc, char *argv[])
{
double p;
int i, listened, total, tries;
if (argc != 4) {
fprintf(stderr,
"usage: ipod [listened-songs] [total-songs] [tries]\n");
return (1);
}
p = 1.0;
listened = atoi(argv[1]);
total = atoi(argv[2]);
tries = atoi(argv[3]);
for (i = 0; i < tries; i++)
p *= (double)(total - listened - i) / (double)(total - i);
printf("P(NO repeat for %d on the second playthough): %lf%%\n", tries,
p * 100.0);
printf("P(Repeat for %d on the second playthough): %lf%%\n", tries,
(1 - p) * 100.0);
return (0);
}
Turns out, I need to hear
40 songs to have a coinflip's chance of hearing one of the previous 30 songs I heard before reshuffling the 1763 total songs.
mactavish(~/sources)[0]% ./a.out 30 1763 40
P(NO repeat for 40 on the second playthough): 49.942794%
P(Repeat for 40 on the second playthough): 50.057206%
mactavish(~/sources)[0]%
The above program should work for any sized iPod/iPhone collection, or any sized song-memory/patience. I
really hope I got the math/derivation right. Any probability wizards in the audience can feel free to school me in the comments section.