Birthday pairings

Here’s two classic birthday puzzles:

1. How many people do you need in a room to have a better than 50% chance of finding at least one shared birthday among them?
2. How many people do you need in a room with you to have a better than 50% chance of finding someone who shares your birthday?

Finding a solution to these is conceptually quite straightforward, but also quite instructive on various useful probabilistic calculation techniques.

Let’s take these one at a time.

1. How many people do you need in a room to have a better than 50% chance of finding at least one shared birthday among them?

Like a lot of these kinds of problems, it can be easier to first find the chances of the proposition not happening. In this case, finding the chances of not finding a shared birthday.

I have a tendency to think of card decks in these situation – so in this case I think of having a bunch of 365-card decks. I deal one card from each deck. What are the chances that I haven’t dealt the same card after after dealing from r decks? You can see that this is an analogy for our problem. Looking back at the previous post on dealing a perfect hand may be a good primer for what follows.

The answer to our card analogy is to take the number of ways I can deal the cards (one from each deck) and get no duplicates divided by the total number of ways I can deal the cards.

From the first deck, I have 365 ways to deal one card. From the second deck, I have 364 ways to deal one card and not have duplicates. From the third deck, there are 363 ways, and so on until I get to 365-r+1 ways. So the number of ways I can deal cards without duplicates is:

= 365 * 364 * ... * (365-r+1)
= 365! / (365-r)!

Now lets work out how many ways there are to deal the cards without restrictions. The answer is simply:

= 365 ^ r

So now, the probability of not dealing any duplicate cards (and also the chances of not finding anyone with a shared birthday) is:

= (365! / (365-r)!) / (365 ^ r)

I was a little stumped at how to solve this as 365! will make any calculator blow up. But we can use Sterling’s approximation to find that:

ln(365!) = 1792.33142
ln((365-22)!) = 1663.17935
ln((365-23)!) = 1657.34162

So for r=22, our probability of no shared birthdays:

= e ^ (1 792.33142 - 1 663.17935) / (365 ^ 22) 
= 0.524310203

For r=23:

= e ^ (1792.33142 - 1657.34162) / (365 ^ 23) 
= 0.492707724

Now remember that this is for finding no shared birthdays. To have at least 1 shared birthday, we need to subract from 1.

So for r=22, the chances of finding at least 1 shared birthday are:

= 1 - 0.524310203 
= 0.475689797

For r=23, the chances are:

= 1 - 0.492707724 
= 0.507292276

So you can see that it takes at least 23 people in a room to have a greater than 50/50 chance of finding a shared birthday.

By the way, to get the Stirling approximation of ln(365!) I typed the following into google:

365 * ln(365) - (365) + ln(365)/2 + ln (2*pi) / 2)

Ok so let’s move on to our second problem:

2. How many people do you need in a room with you to have a better than 50% chance of finding someone who shares your birthday?

This one’s a little simpler than the first. Again, it’s easier to first find the probability of no one having your birthday. Let’s imagine people walking in to a room where you are. The first person has a 364/365 chance of not having your birthday. And it’s the same for all subsequent people who walk into the room. So the chances of no one sharing your birthday after r people have walked in are:

= (364/365)^r

So the chance that at least one person shares your birthday is:

= 1 - (364/365) ^ r

Let’s find r when the equation is 1/2, representing the at least 50% chance we were looking for:

1/2 = 1 - (364/365) ^ r
(364/365) ^ r = 1/2
r * log (364/365) = log (1/2)
r = log (1/2) / log (364/365)
r = 252.651989

So you need to have at least 253 people with you in a room to have a better than 50/50 chance of finding someone sharing your birthday. It’s quite amazing how different this answer is to the answer for the first part.