Thursday, August 19, 2010

Thinking about the Birthday Problem on my Birthday, as it applies to my Birthday Present

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>

main(int argc, char *argv[])
double p;
int i, listened, total, tries;

if (argc != 4) {
"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%

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.