The Clapham omnibus is now too small for our needs so we resume the argument in a large room. 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 minuscule. 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 ½ and for 22 people the probability that a birthday is shared is just less than ½. The number 23 is the critical value. While the answer to the classic birthday problem is surprising it is not a paradox.

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 of 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 sharing 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 ½.

If n = 22, the probability of two people sharing a birthday is 0.4757, which is less than ½. 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 Mr Trevor Thomson whose birthday is on 8 March is in the room, a different question might be asked.

How many birthdays coincide with Mr Thomson’s?

For this question, the calculation is different. The probability of Mr Thomson not sharing his birthday with another person is 364/365 so that the probability that he does not share his birthday with any of the other n – 1 people in the room is (364/365)ⁿ – 1. Therefore the probability that Mr Thomson does share his 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 only a 6% chance that someone else will have their birthday on 8 March, the same date as Mr Thomson’s birthday. If we increase the value of n, this probability will increase. But we have to go as far n = 254 (which includes Mr Thomson in the count) for the probability to be greater than ½. For n = 254, its value is 0.5005. This is the cutoff point because n = 253 will give the value 0.4991 which is less than ½. There will have to be a gathering of 254 people in the room for a chance greater than ½ that Mr Thomson shares his birthday with someone else. 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 would 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 Bob Dylan concert and people join it 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 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 Mr Trevor Thomson (8 March)?

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.

the condensed idea

Calculating coincidences