The Birthday Problem

I was watching Law and Order: Special Victims Unit the other day (great show!) and I noticed a highly improbable outcome when the SVU team was struggling to find the twin brother of a detained suspect. The following is a summary of what occurs in the episode:

“Fin says he is already looking for Brian Smith and Munch comments about how many have that name. Benson wonders how many follow their twin to New York. Fin says there are 126 Brian Smiths [the twin of interest] in New York City. Rollins comments that as they are twins to look at their birthdates. Fin finds a match.” [1]

Probabilistically speaking, there is an approximate 2.097\times10^{-9}\% = 0.000000002097\% chance that Fin finds exactly one Brian Smith with the same birthday as the detained suspect [2]; that is a very low probability that luckily works out for our SVU team!

How did I get to this number?

Well, this is an application of the birthday problem: Given n randomly chosen people, what is the probability that some pair of them will have the same birthday?

Denote this desired probability as p(n). Then, letting p'(n) equal the probability that all of the persons’ birthdays are distinct, it follows that p(n) = 1 – p'(n).

We can actually come up with a formula for p'(n): If n is greater than 365, then p'(n) = 0.

Proof: If the first 365 people are found to all have different birthdays, since there is at least one person left over whose birthday still needs to be known, that person’s birthday must be the same of one of the other 365 already known people.

If n is less than or equal to 365, then p'(n) = 1 x (1 – 1/365) x (1 – 2/365) x … x (1 – (n-1)/365).

Proof: The probability that the first person observed has a distinct birthday from everyone else already observed is 1 (since no one else has yet been observed). The probability that the second person observed has a distinct birthday from everyone else already observed (the first person) is 1 – 1/365, or in other words 364/365, since there are 364 days remaining that will make the second person’s birthday distinct. The probability that the third person observed has a distinct birthday from everyone else already observed is 1 – 2/365, or 363/365, since there are 363 days remaining that will make the third person’s birthday distinct. It is easy to see that this pattern continues until we get to the last person such that the probability that person i has a distinct birthday from the i-1 already observed people is known to be 1-(i-1)/365, for 1\leq i \leq n.

Now, given person A and person B, the probabilities of person A having birthday x and person B having birthday y are independent of each other. Therefore, the probabilities described above must be all independent events. As such, p'(n) is just the product of all of the above probabilities (since for two independent events A and B, p(A*B) = p(A) * p(B)). Thus, p'(n) = 1 * (1 – 1/365) * (1 – 2/365) * … * (1 – (n-1)/365) = \frac{365 * 364 * 363 * ... (365 - (n-1))}{365^n}. Notice that 365 * 364 * 363 * ... (365 - (n-1)) = n!\binom{365}{n}. Therefore,

p'(n) = \frac{n!\binom{365}{n}}{365^n}.

So, back to what we are really interested in, we see that p(n) = 1 - p'(n) = 1 -\frac{n!\binom{365}{n}}{365^n}.

Therefore, to calculate the probability that an event like the one in SVU actually happens, let n=126 and solve for p'(n) : p'(n) = \frac{126!\binom{365}{126}}{365^{126}} = 2.097\times 10^{-11}.

Pretty cool! Now, if you didn’t notice the second footnote link above, I want to mention that there is a slight assumption violation in this application/computation. Can you find out what it is? Leave your answer in the Comments below!

EDIT: View Tanner’s comment below to see what went wrong in this SVU application! (the Birthday problem proof is still all fine though)

[1] http://allthingslawandorder.blogspot.com/2011/10/law-order-svu-double-strands-recap.html

[2] Actually, there is a slight assumption violation in this application/computation. Can you find out what it is? Leave your answer in the Comments below!

Advertisements

4 thoughts on “The Birthday Problem

  1. Isn’t the problem in the SVU case a little different. The probability for SVU is probability more than 1 people share birthday x, not that any two of them share a birthday. They know the birthday of the detained suspect, who cares if other pairs exist.

  2. Just to put this post to rest, the real answer is as follows:

    The probability, p(126), that at least one of the 126 Brian Smiths in New York has the same birthday as the twin in custody (whose birthday we know) is equal to 1 – p'(126), where p'(126) is the probability that none of the 126 Brian Smiths in New York have the same birthday as the twin in custody. p'(126) = (364/365)^(126).

    Reasoning: There are 364 days available for Brian Smith’s birthday, since all we know is that he does not have the same birthday as the twin in custody. As such, the probability that he does not have the same birthday as the twin is 364/365. This probability is the same for each of the 126 Mr. Smiths. Since birthdays are independent events, we multiply this probability together to get p'(126).

    So, the real probability? p(126) = 1 – (364/365)^(126) = 30%.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s