Zubair Idris
Mathematics has always fascinated me. I came across the birthday problem when I was in middle school. Today I share it with you.
Imagine you are on the top deck of a double-decker bus with nothing in particular to do but count your fellow passengers going off to work or university in the early morning. As it is likely that all the passengers are independent of each other, we may safely assume that their birthdays are randomly scattered throughout the year. Including you there are only 23 passengers on board. It is not many, but enough to claim there is a better than even chance that two passengers share a birthday. Do you believe it? Millions do not but it is absolutely true!Let us leave the double-decker bus for now and resume the argument in a large room for our next experiment. How many people must gather in the room so that it is certain that two people share the same birthday? There are 365 days in a standard year (and we’ll ignore leap years just to make things simpler) so if there were 366 people in the room, at least one pair would definitely have the same birthday. It cannot be the case that they all have different ones.
This is the pigeonhole principle: if there are n+1 pigeons who occupy n pigeonholes, one hole must contain more than one pigeon. If there were 365 people we could not be certain there would be a common birthday because the birthdays could each be on different days of the year. However, if you take 365 people at random this would be extremely unlikely and the probability of two people not sharing a birthday would be miniscule. Even if there are only 50 people in the room there is a 96.5% chance that two people share a birthday. If the number of people is reduced still further the probability of two sharing a birthday reduces. We find that 23 people is the number for which the probability is just greater than half and for 22 people the probability that a birthday is shared is just less than half. The number 23 is the critical value. While the answer to the classic birthday problem is surprising it is not a paradox.
Well, can we prove it? How can we be convinced? Let’s select a person at random. The probability that another person has the same birthday as this person is 1/365 and so the probability these two do not share a birthday is one minus this (or 364/365). The probability that yet another person selected at random shares a birthday with the first two is 2/365 so the probability this person does not share a birthday with either the first two is one minus this (or 363/365). The probability of none of these three sharing a birthday is the multiplication of these two probabilities, or (364/365) × (363/365) which is 0.9918.
Continuing this line of thought for 4,5,6,… people unravels the birthday problem paradox. When we get as far as 23 people with our pocket calculator we get the answer 0.4927 as the probability that none of them shares a birthday. The negation of ‘none of them shares a birthday’ is ‘at least two people share a birthday’ and the probability of this is 1 – 0.4927 = 0.5073, just greater than the crucial half.
If n=22, the probability of two people sharing a birthday is 0.4757, which is less than half. The apparent paradoxical nature of the birthday problem is bound up with language. The birthday result makes a statement about two people sharing a birthday, but it does not tell us which two people they are. We do not know where the matches will fall. If I am in the room, and my birthday is on 19 December, a different question might be asked.
How many birthdays coincide with mine? For this question, the calculation is different. The probability of my birthday not being shared with another person is 364/365 so that the probability that I do not share a birthday with any of the other n-1 people in the room is (364/365)n-1. Therefore the probability that I do share a birthday with someone will be one minus this value.
If we compute this for n=23 this probability is only 0.061151 so there is a 6% chance that someone else will have their birthday on 19 December, the same date as my birthday. If we increase the value of n, this probability will increase. But we have to go as far as n=254 (which includes me in the count) for the probability to be greater than half. For n=254, its value is 0.5005. This is the cut-off point because n=253 will give the value 0.4991 which is less than half. There has to be a gathering of 254 people in the room for a chance greater than half that I share a birthday with someone else there. This is perhaps more in tune with our intuition than with the startling solution of the classic birthday problem.
Other birthday problems? The birthday problem has been generalized in many ways. One approach is to consider three people sharing a birthday. In this case 88 people will be required before there is a better than even chance that three people will share the same birthday. There are correspondingly larger groups if four people, five people,… are required to share a birthday. In a gathering of 1000 people, for example, there is a better than even chance that nine of them share a birthday.
Other forays into the birthday problem have inquired into near birthdays. In this problem a match is considered to have occurred if one birthday is within a certain number of days of another birthday. It turns out that a mere 14 people in a room will give a greater than even chance of two people having a birthday in common or having a birthday within a day of each other.
A variant of the birthday problem which requires more sophisticated mathematical tools is the birthday problem for boys and girls: if a class consists of an equal number of boys and girls, what would be the minimum group that would give a better than even chance that a boy and a girl shared a birthday?
The result is that a class of 32 (16 girls and 16 boys) would yield the minimum group. This can be compared with 23 in the classic birthday problem.
By changing the question slightly we can get other novelties (but they are not easy to answer). Suppose we have a long queue forming outside a Zain Bhikha concert and people join in randomly. As we are interested in birthdays we may discount the possibility of twins or triplets arriving together. As the fans enter they are asked for their birthdays. The mathematical question is this: how many people would you expect to be admitted before two consecutive people have the same birthday? Another question: How many people go into the concert hall before a person turns up with the same birthday as mine (19 December)?
The birthday calculation makes the assumption that birthdays are uniformly distributed and that each birthday has an equal chance of occurring for a person selected at random. Experimental results show this is not exactly true (more are born during the summer months) but it is close enough for the solution to be applicable.
Birthday problems are examples of occupancy problems, in which mathematicians think about placing balls in cells. In the birthday problem, the number of cells is 365 (these are identified with possible birthdays) and the balls to be placed at random in the cells are the people. The problem can be simplified to investigate the probability of two balls falling in the same cell. For the boys-and-girls problem, the balls are of two colours.
It is not only mathematicians who are interested in the birthday problem. Satyendra Nath Bose was attracted to Albert Einstein’s theory of light based on photons. He stepped out of the traditional lines of research and considered the physical setup in terms of an occupancy problem. For him, the cells were not days of the year as in the birthday problem but energy levels of the photons. Instead of people being put into cells as in the birthday problem he distributed numbers of photons. There are many applications of occupancy problems in other sciences. In biology, for instance, the spread of epidemics can be modelled as an occupancy problem – the cells in this case are geographical areas, the balls are diseases and the problem is to figure out how the diseases are clustered.
The world is full of amazing coincidences but only mathematics gives us the way of calculating their probability. The classical birthday problem is just the tip of the iceberg in this respect and it is a great entry into serious mathematics with important applications.