Of birthdays and probabilities!

Here’s a (rather useless) trivia — the reason I study mathematics is because sometimes the remarkability of results that are “arrived” at, are just utterly astonishing. While most of the times they are intuitive, sometimes, the results are beyond what most people shall call “common-sense.” Probability is one such field — you would expect something, but the actual expectation would be completely different (pun intended)! In this article I shall elaborate upon one of the famous puzzles in mathematics — the birthday paradox and some of it’s variations.

So, let’s dive in!

The birthday paradox

What is the least number of people needed, such that the probability that atleast two people have the same birthday exceeds 1/2 (50%)?

Suppose in a room there are N people. We need N such that,

P(atleast 2 out of N people have the same birthday) ≥ 0.5

Let us for simplicity not consider leap years, then there are 365 different possible birthdays. We shall try to compute the simpler probability that of the N people, no two have the same birthday.

Consider the persons are numbered as A₁, A₂ …… so on. Then A₁ can be paired with A₂, A₃… so on ie, N-1 people. A₂ can be paired with (N-2) different people (Since A₁ and A₂ have already been counted as a separate pair previously.) Continuing the same way, total possible pairs is — the sum, N-1 + N-2 + …+1,

Equation 1

The above can be arrived at by using combinations as well — total possible ways of selecting two people (i.e. a pair) from N people is simply NC2. That is the same result as arrived at above.

Now, in a pair, one person has a given birthday, then the other person should have his birthday on the rest of the 364 days — for them to not have the same birthday. So 364\365 is the probability that the pair does NOT have a common birthday. From equation 1 we have N(N-1)/2 pairs, so the total probability that no two people have the same birthday is,

Equation 2

(the RHS is 1–0.5 = 0.5, since it is “opposite” to our problem statement, the LHS can be arrived at by using the multiplication theorem.)

Taking logarithm on both sides of equation 2,

Equation 3

Solving (on a calculator ofcourse) we have,

Equation 4

If we set N = 23, we have the LHS as 253. So the possible value of N that answers our question is 23. Just 23.

Let that sink in.

Now, a few assumptions made for the above calculation is,

1. The N people we sampled were randomly chosen.
2. All the days of the year (except Feb 29th) are equal-likely to be a birthday.
3. If N is 23, there is 0.5 probability that atleast two people shall have the same birthday.

I wrote a python program (basic, couple lines) to vary the value of N and find the probability that two people share a birthday for each N, and plotted the results on a graph. We get the following figure:

Plot of number of people vs the chance of having the same birthday

Now it is intuitive, if we consider 366 people, two people must have the same birthday (pegion-hole principle — since there are only 365 different days). But from the above plot, we can conclude, if 70 people are randomly chosen, there is a 100% chance of two people sharing the same birthday!

Mind == blown

Finding your birthmate

Now, let’s discuss a slightly different problem.

You want to find a person with the same birthday as yours (that’s how you make new friends apparently). How many people you have to ask, to have a 50% chance of finding that person?

In this problem, we don’t care anymore if any random pair has the same birthday (like we did in the previous problem), afterall your birthday is fixed (say, 12th December). Suppose, you ask N people, let us calculate the probability none of these N people have their birthday on 12th December.

There are 364 other days these N people can have their birthdays on (if two people amongst these N have the same birthday, it does not really help you in your search). So each person has 364/365 probability of NOT having a birthday on 12th December, by using multiplication theorem of probability,

equation 5

(Again RHS is 1–0.5 = 0.5, we forulated the problem as “opposite” to the given statement.)

Taking log on both sides, we got,

equation 6

Again, solving 6, we get N = 253.

You need to ask 253 people to find your birthmate!

If we compare the above two problems, the relationship between them becomes rather intuitive.

In the birthday paradox, we wanted no two persons to have the same birthday, in the birthmate problem we wanted no one to have the birthday on one given date. In other words, if N is the number considered for the former and n for the latter, the number of pairs formed in the former shall be the total number of people considered in the latter, or,

equation 7

As can be proved by looking at equations — 2 and 5.

Hence Proved!

Thank you for reading! Let me know — what you think!