Birthday problem

Calculating the probability

The problem is to compute the approximate probability that, in a group of n people, at least two have the same birthday. For simplicity, disregard variations in the distribution, such as leap years, twins, seasonal or weekday variations, and assume that the 365 possible birthdays are equally likely. (Real-life birthday distributions are not uniform, since not all dates are equally likely, but these irregularities have little effect on the analysis.)

The goal is to compute P(A), the probability that at least two people in the room have the same birthday. However, it is simpler to calculate P(A'), the probability that no two people in the room have the same birthday. Then, because A and A' are the only two possibilities and are also mutually exclusive, P(A) = 1 − P(A').

In deference to widely published solutions concluding that 23 is the minimum number of people necessary to have a P(A) that is greater than 50%, the following calculation of P(A) will use 23 people as an example. If one numbers the 23 people from 1 to 23, the event that all 23 people have different birthdays is the same as the event that person 2 does not have the same birthday as person 1, and that person 3 does not have the same birthday as either person 1 or person 2, and so on, and finally that person 23 does not have the same birthday as any of persons 1 through 22. Let these events respectively be called "Event 2", "Event 3", and so on. One may also add an "Event 1", corresponding to the event of person 1 having a birthday, which occurs with probability 1. This conjunction of events may be computed using conditional probability: the probability of Event 2 is 364/365, as person 2 may have any birthday other than the birthday of person 1. Similarly, the probability of Event 3 given that Event 2 occurred is 363/365, as person 3 may have any of the birthdays not already taken by persons 1 and 2. This continues until finally the probability of Event 23 given that all preceding events occurred is 343/365. Finally, the principle of conditional probability implies that P(A') is equal to the product of these individual probabilities:

The terms of equation (1) can be collected to arrive at:

Evaluating equation (2) gives P(A') ≈ 0.492703

Therefore, P(A) ≈ 1 − 0.492703 = 0.507297 (50.7297%)

This process can be generalized to a group of n people, where p(n) is the probability of at least two of the n people sharing a birthday. It is easier to first calculate the probability p(n) that all n birthdays are different. According to the pigeonhole principle, p(n) is zero when n > 365. When n ≤ 365:

where '!' is the factorial operator, ( 365 n ) is the binomial coefficient and k P r denotes permutation.

The equation expresses the fact that the first person has no one to share a birthday, the second person cannot have the same birthday as the first (364/365), the third cannot have the same birthday as either of the first two (363/365), and in general the n^th birthday cannot be the same as any of the n − 1 preceding birthdays.

The event of at least two of the n persons having the same birthday is complementary to all n birthdays being different. Therefore, its probability p(n) is

The following table shows the probability for some other values of n (this table ignores the existence of leap years, as described above, as well as assuming that each birthday is equally likely):

Approximations

The Taylor series expansion of the exponential function (the constant e ≈ 2.718281828)

provides a first-order approximation for e^x for x ≪ 1:

To apply this approximation to the first expression derived for p(n), set x = − a / 365   . Thus,

Then, replace a with non-negative integers for each term in the formula of p(n) until a = n − 1, for example, when a = 1,

The first expression derived for p(n) can be approximated as

Therefore,

An even coarser approximation is given by

which, as the graph illustrates, is still fairly accurate.

According to the approximation, the same approach can be applied to any number of "people" and "days". If rather than 365 days there are d, if there are n persons, and if n ≪ d, then using the same approach as above we achieve the result that if p(n, d) is the probability that at least two out of n people share the same birthday from a set of d available days, then:

A simple exponentiation

The probability of any two people not having the same birthday is 364/365. In a room containing n people, there are C(n, 2) = n(n − 1)/2 pairs of people, i.e. C(n, 2) events. The probability of no two people sharing the same birthday can be approximated by assuming that these events are independent and hence by multiplying their probability together. In short 364/365 can be multiplied by itself C(n, 2) times, which gives us

Since this is the probability of no one having the same birthday, then the probability of someone sharing a birthday is

Poisson approximation

Applying the Poisson approximation for the binomial on the group of 23 people,

The result is over 50% as previous descriptions.

Square approximation

A good rule of thumb which can be used for mental calculation is the relation

which can also be written as

which works well for probabilities less than or equal to 0.5. In these equations, m is the number of days in a year.

For instance, to estimate the number of people required for a 0.5 chance of a shared birthday, we get

Which is not too far from the correct answer of 23.

Approximation of number of people

This can also be approximated using the following formula for the number of people necessary to have at least a 50% chance of matching:

This is a result of the good approximation that an event with 1 in k probability will have a 50% chance of occurring at least once if it is repeated k ln 2 times.

The white fields in this table show the number of hashes needed to achieve the given probability of collision (column) given a hash space of a certain size in bits (row). Using the birthday analogy: the "hash space size" resembles the "available days", the "probability of collision" resembles the "probability of shared birthday", and the "required number of hashed elements" resembles the "required number of people in a group". One could of course also use this chart to determine the minimum hash size required (given upper bounds on the hashes and probability of error), or the probability of collision (for fixed number of hashes and probability of error).

For comparison, 10⁻¹⁸ to 10⁻¹⁵ is the uncorrectable bit error rate of a typical hard disk. In theory, 128-bit hash functions, such as MD5, should stay within that range until about 820 billion documents, even if its possible outputs are many more.

An upper bound

The argument below is adapted from an argument of Paul Halmos.

As stated above, the probability that no two birthdays coincide is

As in earlier paragraphs, interest lies in the smallest n such that p(n) > 1/2; or equivalently, the smallest n such that p(n) < 1/2.

Using the inequality 1 − x < e^−x in the above expression we replace 1 − k/365 with e^−k/365. This yields

Therefore, the expression above is not only an approximation, but also an upper bound of p(n). The inequality

implies p(n) < 1/2. Solving for n gives

Now, 730 ln 2 is approximately 505.997, which is barely below 506, the value of n² − n attained when n = 23. Therefore, 23 people suffice. Solving n² − n = 2 · 365 · ln 2 for n gives, by the way, the approximate formula of Frank H. Mathis cited above.

This derivation only shows that at most 23 people are needed to ensure a birthday match with even chance; it leaves open the possibility that n is 22 or less could also work.

The generalized birthday problem

Given a year with d days, the generalized birthday problem asks for the minimal number n(d) such that, in a set of n randomly chosen people, the probability of a birthday coincidence is at least 50%. In other words, n(d) is the minimal integer n such that

The classical birthday problem thus corresponds to determining n(365). The first 99 values of n(d) are given here:

A number of bounds and formulas for n(d) have been published. For any d≥1, the number n(d) satisfies

These bounds are optimal in the sense that the sequence n ( d ) − 2 d ln ⁡ 2 gets arbitrarily close to ( 3 − 2 ln ⁡ 2 ) / 6 ≈ 0.27 , while it has 9 − 86 ln ⁡ 2 ≈ 1.28 as its maximum, taken for d=43. The bounds are sufficiently tight to give the exact value of n(d) in 99% of all cases, for example n(365)=23. In general, it follows from these bounds that n(d) always equals either ⌈ 2 d ln ⁡ 2 ⌉ or ⌈ 2 d ln ⁡ 2 ⌉ + 1 where ⌈ x ⌉ denotes the ceiling function. The formula

holds for 73% of all integers d. The formula

holds for almost all d, i.e., for a set of integers d with asymptotic density 1. The formula

holds for all d up to 10¹⁸, but it is conjectured that there are infinitely many counter-examples to this formula. The formula

holds for all d up to 10¹⁸, and it is conjectured that this formula holds for all d.

Cast as a collision problem

The birthday problem can be generalized as follows: given n random integers drawn from a discrete uniform distribution with range [1,d], what is the probability p(n;d) that at least two numbers are the same? (d=365 gives the usual birthday problem.)

The generic results can be derived using the same arguments given above.

Conversely, if n(p;d) denotes the number of random integers drawn from [1,d] to obtain a probability p that at least two numbers are the same, then

The birthday problem in this more generic sense applies to hash functions: the expected number of N-bit hashes that can be generated before getting a collision is not 2^N, but rather only 2^N/2. This is exploited by birthday attacks on cryptographic hash functions and is the reason why a small number of collisions in a hash table are, for all practical purposes, inevitable.

The theory behind the birthday problem was used by Zoe Schnabel under the name of capture-recapture statistics to estimate the size of fish population in lakes.

Generalization to multiple types

The basic problem considers all trials to be of one "type". The birthday problem has been generalized to consider an arbitrary number of types. In the simplest extension there are two types of people, say m men and n women, and the problem becomes characterizing the probability of a shared birthday between at least one man and one woman. (Shared birthdays between, say, two women do not count.) The probability of no (i.e. zero) shared birthdays here is

where d = 365 and S₂ are Stirling numbers of the second kind. Consequently, the desired probability is 1 − p₀.

This variation of the birthday problem is interesting because there is not a unique solution for the total number of people m + n. For example, the usual 0.5 probability value is realized for both a 32-member group of 16 men and 16 women and a 49-member group of 43 women and 6 men.

Reverse problem

For a fixed probability p:

Taking the above formula for d = 365 we have:

Sample calculations

Note: some values falling outside the bounds have been colored to show that the approximation is not always exact.

First match

A related question is, as people enter a room one at a time, which one is most likely to be the first to have the same birthday as someone already in the room? That is, for what n is p(n) − p(n − 1) maximum? The answer is 20—if there's a prize for first match, the best position in line is 20th.

Same birthday as you

Note that in the birthday problem, neither of the two people is chosen in advance. By way of contrast, the probability q(n) that someone in a room of n other people has the same birthday as a particular person (for example, you), is given by

and for general d by

In the standard case of d = 365 substituting n = 23 gives about 6.1%, which is less than 1 chance in 16. For a greater than 50% chance that one person in a roomful of n people has the same birthday as you, n would need to be at least 253. Note that this number is significantly higher than 365/2 = 182.5: the reason is that it is likely that there are some birthday matches among the other people in the room.

It is not a coincidence that 253 = 23 × ( 23 − 1 ) 2 ; a similar approximate pattern can be found using a number of possibilities different from 365, or a target probability different from 50%.

Near matches

Another generalization is to ask what is the probability of finding at least one pair in a group of n people with birthdays within k calendar days of each other's, if there are m equally likely birthdays.

The number of people required so that the probability that some pair will have a birthday separated by k days or fewer will be higher than 50% is:

Thus in a group of just seven random people, it is more likely than not that two of them will have a birthday within a week of each other.

Collision counting

The probability that the kth integer randomly chosen from [1, d] will repeat at least one previous choice equals q(k − 1; d) above. The expected total number of times a selection will repeat a previous selection as n such integers are chosen equals

Average number of people

In an alternative formulation of the birthday problem, one asks the average number of people required to find a pair with the same birthday. If we consider the probability function Pr[n people have at least one shared birthday], this average is determining the Mean of the distribution, as opposed to the customary formulation which determines the Median. The problem is relevant to several hashing algorithms analyzed by Donald Knuth in his book The Art of Computer Programming. It may be shown that if one samples uniformly, with replacement, from a population of size M, the number of trials required for the first repeated sampling of some individual has expected value n ¯ = 1 + Q ( M ) , where

The function

has been studied by Srinivasa Ramanujan and has asymptotic expansion:

With M = 365 days in a year, the average number of people required to find a pair with the same birthday is n ¯ = 1 + Q ( M ) ≈ 24.61659 , somewhat more than 23, the number required for a 50% chance. In the best case, two people will suffice; at worst, the maximum possible number of M + 1 = 366 people is needed; but on average, only 25 people are required.

An informal demonstration of the problem can be made from the list of Prime Ministers of Australia, of which there have been 27 as of 2010, in which Paul Keating, the 24th Prime Minister, and Edmund Barton, the first Prime Minister, share the same birthday, 18 January.

In the 2014 FIFA World Cup, each of the 32 squads had 23 players. An analysis of the official squad lists suggested that 16 squads had pairs of players sharing birthdays, and of these 5 squads had two pairs: Argentina, France, Iran, South Korea and Switzerland each had two pairs, and Australia, Bosnia Herzegovina, Brazil, Cameroon, Colombia, Honduras, Netherlands, Nigeria, Russia, Spain and USA each with one pair.

Partition problem

A related problem is the partition problem, a variant of the knapsack problem from operations research. Some weights are put on a balance scale; each weight is an integer number of grams randomly chosen between one gram and one million grams (one metric ton). The question is whether one can usually (that is, with probability close to 1) transfer the weights between the left and right arms to balance the scale. (In case the sum of all the weights is an odd number of grams, a discrepancy of one gram is allowed.) If there are only two or three weights, the answer is very clearly no; although there are some combinations which work, the majority of randomly selected combinations of three weights do not. If there are very many weights, the answer is clearly yes. The question is, how many are just sufficient? That is, what is the number of weights such that it is equally likely for it to be possible to balance them as it is to be impossible?

Some people's intuition is that the answer is above 100,000. Most people's intuition is that it is in the thousands or tens of thousands, while others feel it should at least be in the hundreds. The correct answer is 23.

The reason is that the correct comparison is to the number of partitions of the weights into left and right. There are 2^N−1 different partitions for N weights, and the left sum minus the right sum can be thought of as a new random quantity for each partition. The distribution of the sum of weights is approximately Gaussian, with a peak at 1,000,000 N and width 1 , 000 , 000 N , so that when 2^N−1 is approximately equal to 1 , 000 , 000 N the transition occurs. 2²³⁻¹ is about 4 million, while the width of the distribution is only 5 million.

In fiction

Arthur C. Clarke's novel A Fall of Moondust, published in 1961, contains a section where the main characters, trapped underground for an indefinite amount of time, are celebrating a birthday and find themselves discussing the validity of the Birthday problem. As stated by a physicist passenger: "If you have a group of more than twenty-four people, the odds are better than even that two of them have the same birthday." Eventually, out of 22 present, it is revealed that two characters share the same birthday, May 23.