08 November 2007

The birthday paradox

Finding the Odds of Synchronized Couples, from The Numbers Guy.

The problem is as follows: how many opposite-sex couples need to be in a room for the probability that there are couples Mr. and Mrs. A, and Mr. and Mrs. B, such that Mr. A and Mr. B have the same birthday and Mrs. A and Mrs. B have the same birthday, to be more than one half?

This is a variation on the classic "birthday problem", which asks this for individuals. The answer in the case of individuals is 23; for couples it's 431. This number 431 is given in the article without justification, so I wanted to explain it. For same-sex couples, the answer is about 304. (There are less possible pairs of birthdays for same-sex couples because you can no longer distinguish between the two members of the couple.)

Let's say there are n possible types of objects (say, birthdays that a person can have) and objects of these types (people with different birthdays) come along one by one. Their types (birthdays) are chosen uniformly at random. The probability that the first person is not the same type as any of the people before em is, of course, 1. The probability that the second person is not the same type as any of the people before em is 1-1/n. The probability that the third person is not the same type as either of the first two people -- given that the first two people are of different types -- is 1-2/n. And in general the probability that the kth person is not the same type as any of the people preceding em is
\left( 1 - {1 \over n} \right) \left( 1 - {2 \over n} \right) \cdots \left( 1 - {k-1 \over n} \right)

But recalling that (1-x) ≈ e-x, we can rewrite this approximately as
\exp \left( -\sum_{i=1}^{k-1} {i \over n} \right)

which is, again approximately, exp(-k2/2n).

To have this probability be less than one half, then, we need
k > \sqrt{n(2 \log 2)} \approx 1.18\sqrt{n}

For birthdays of ordinary Earth people, n = 365, and we get k > 22.49, that is, we need at least 23 people (since people come in integers) to have probability 1/2 that two of them have the same birthday. For birthdays of opposite-sex couples, n = 3652, and this gives k > 430; for birthdays of same-sex couples, n = 365(365+1)/2, and k > 305.

Incidentally, the birthday problem is often called the "birthday paradox" because a lot of people are surprised by the result -- if you have 23 people in a room then there's a fifty-fifty chance that two of them have the same birthday. I don't find it surprising any more, so I won't call it a paradox.

(Somewhat more surprisingly, I don't seem to have blogged about the birthday paradox before!)

It would be interesting to note whether the birthdays of couples are actually evenly distributed; having them not be evenly distributed might be evidence for something. The obvious thing is astrology -- but it wouldn't surprise me if there are earthly reasons why people born around the same time of year are more likely to be attracted to each other. (I have no idea what the mechanism for this would be, though, and I suspect this isn't the case.)

1 comment:

Max said...

You introductory paragraph leaves out the critical 'more than half' part of the sentence. :)