In probability theory, the birthday problem asks for the probability that, in a set of n randomly chosen people, at least two will share the same birthday. The birthday paradox is the counterintuitive fact that only 23 people are needed for that probability to exceed 50%. The birthday paradox is a veridical paradox: it seems wrong at first glance but is, in fact, true. While it may seem surprising that only 23 individuals are required to reach a 50% probability of a shared birthday (the number being less than 1/15th of the number of days in a year), this result is made more intuitive by considering that the birthday comparisons will be made between every possible pair of individuals. With 23 individuals, there are 23 × 22 2 = 253 {\displaystyle {\frac {23\times 22}{2}}=253} pairs to consider. Real-world applications for the birthday problem include a cryptographic attack called the birthday attack, which uses this probabilistic model to reduce the complexity of finding a collision for a hash function, as well as calculating the approximate risk of a hash collision existing within the hashes of a given size of population. The problem is generally attributed to Harold Davenport in about 1927, though he did not publish it at the time. Davenport did not claim to be its discoverer "because he could not believe that it had not been stated earlier". The first publication of a version of the birthday problem was by Richard von Mises in 1939.
Calculating the probability
Consider the event A that a group of k people does not have any repeated birthdays, and let the complementary event B be that of a group of k people contains at least two people who share a birthday. Then the probabilities P(A) and P(B) of the two events are related by the equation P(B) = 1 − P(A). The probability P(A) can be computed using the perspective of permutations, as follows. Let V n r {\displaystyle V_{nr}} be the total number of ways that k people can have distinct birthdays, and let V t {\displaystyle V_{t}} be the total number of ways k people can have birthdays arranged, including possibly repeated birthdays. The probability P(A) is the ratio of these two quantities, V n r {\displaystyle V_{nr}} divided by V t {\displaystyle V_{t}} . When k = 23 {\displaystyle k=23} , the two counts are given by
V n r = 365 ⋅ 364 ⋅ 363 ⋯ ( 365 − 22 ) = 365 ! ( 365 − 23 ) ! {\displaystyle V_{nr}=365\cdot 364\cdot 363\cdots (365-22)={\frac {365!}{(365-23)!}}}
and
V t = 365 ⋅ 365 ⋅ 365 ⋯ 365 = 365 23 , {\displaystyle V_{t}=365\cdot 365\cdot 365\cdots 365=365^{23},}
their ratio is P ( A ) = V n r V t ≈ 0.492703 {\displaystyle P(A)={\frac {V_{nr}}{V_{t}}}\approx 0.492703} , and so
P ( B ) = 1 − P ( A ) ≈ 1 − 0.492703 = 0.507297 ( 50.7297 % ) . {\displaystyle P(B)=1-P(A)\approx 1-0.492703=0.507297\quad (50.7297\%).}
Another way the birthday problem can be solved is by asking for an approximate probability that in a group of n people at least two have the same birthday. For simplicity, leap years, twins, selection bias, and seasonal and weekly variations in birth rates are generally disregarded, and instead it is assumed that there are 365 possible birthdays, and that each person's birthday is equally likely to be any of these days, independent of the other people in the group. For independent birthdays, a uniform distribution of birthdays minimizes the probability of two people in a group having the same birthday. Any unevenness increases the likelihood of two people sharing a birthday. However, real-world birthdays are not sufficiently uneven to make much change: the real-world group size necessary to have a greater than 50% chance of a shared birthday is 23, as in the theoretical uniform distribution. The goal is to compute P(B), 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 B and A′ are the only two possibilities and are also mutually exclusive, P(B) = 1 − P(A′). Here is the calculation of P(A) for 23 people. Let the 23 people be numbered 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 be called Event 2, Event 3, and so on. Event 1 is 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(B) ≈ 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:
p ¯ ( n ) = 1 × ( 1 − 1 365 ) × ( 1 − 2 365 ) × ⋯ × ( 1 − n − 1 365 ) = 365 × 364 × ⋯ × ( 365 − n + 1 ) 365 n = 365 ! 365 n ( 365 − n ) ! = n ! ⋅ ( 365 n ) 365 n = 365 P n 365 n {\displaystyle {\begin{aligned}{\bar {p}}(n)&=1\times \left(1-{\frac {1}{365}}\right)\times \left(1-{\frac {2}{365}}\right)\times \cdots \times \left(1-{\frac {n-1}{365}}\right)\\[6pt]&={\frac {365\times 364\times \cdots \times (365-n+1)}{365^{n}}}\\[6pt]&={\frac {365!}{365^{n}(365-n)!}}={\frac {n!\cdot {\binom {365}{n}}}{365^{n}}}={\frac {_{365}P_{n}}{365^{n}}}\end{aligned}}}
where ! is the factorial operator, (365n) is the binomial coefficient and kPr 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 nth 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
p ( n ) = 1 − p ¯ ( n ) . {\displaystyle p(n)=1-{\bar {p}}(n).}
The following table shows the probability for some other values of n (for this table, the existence of leap years is ignored, and each birthday is assumed to be equally likely):
Approximations
The Taylor series expansion of the exponential function (the constant e ≈ 2.718281828)
e x = 1 + x + x 2 2 ! + ⋯ {\displaystyle e^{x}=1+x+{\frac {x^{2}}{2!}}+\cdots }
provides a first-order approximation for ex for | x | ≪ 1 {\displaystyle |x|\ll 1} :
e x ≈ 1 + x . {\displaystyle e^{x}\approx 1+x.}
To apply this approximation to the first expression derived for p(n), set x = −a/365. Thus,
e − a / 365 ≈ 1 − a 365 . {\displaystyle e^{-a/365}\approx 1-{\frac {a}{365}}.}
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,
e − 1 / 365 ≈ 1 − 1 365 . {\displaystyle e^{-1/365}\approx 1-{\frac {1}{365}}.}
The first expression derived for p(n) can be approximated as
p ¯ ( n ) ≈ 1 ⋅ e − 1 / 365 ⋅ e − 2 / 365 ⋯ e − ( n − 1 ) / 365 = e − ( 1 + 2 + ⋯ + ( n − 1 ) ) / 365 = e − n ( n − 1 ) / 2 365 = e − n ( n − 1 ) 730 . {\displaystyle {\begin{aligned}{\bar {p}}(n)&\approx 1\cdot e^{-1/365}\cdot e^{-2/365}\cdots e^{-(n-1)/365}\\[6pt]&=e^{-{\big (}1+2+\,\cdots \,+(n-1){\big )}/365}\\[6pt]&=e^{-{\frac {n(n-1)/2}{365}}}=e^{-{\frac {n(n-1)}{730}}}.\end{aligned}}}
Therefore,
p ( n ) = 1 − p ¯ ( n ) ≈ 1 − e − n ( n − 1 ) 730 . {\displaystyle p(n)=1-{\bar {p}}(n)\approx 1-e^{-{\frac {n(n-1)}{730}}}.}
An even coarser approximation is given by
p ( n ) ≈ 1 − e − n 2 730 , {\displaystyle p(n)\approx 1-e^{-{\frac {n^{2}}{730}}},}
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:
p ( n , d ) ≈ 1 − e − n ( n − 1 ) 2 d ≈ 1 − e − n 2 2 d . {\displaystyle {\begin{aligned}p(n,d)&\approx 1-e^{-{\frac {n(n-1)}{2d}}}\\[6pt]&\approx 1-e^{-{\frac {n^{2}}{2d}}}.\end{aligned}}}
Simple exponentiation The probability of any two people not having the same birthday is 364/365. In a room containing n people, there are (n2) = n(n − 1)/2 pairs of people, i.e. (n2) 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. Being independent would be equivalent to picking with replacement, any pair of people in the world, not just in a room. In short 364/365 can be multiplied by itself (n2) times, which gives us
p ¯ ( n ) ≈ ( 364 365 ) ( n 2 ) . {\displaystyle {\bar {p}}(n)\approx \left({\frac {364}{365}}\right)^{\binom {n}{2}}.}
Since this is the probability of no one having the same birthday, then the probability of someone sharing a birthday is
p ( n ) ≈ 1 − ( 364 365 ) ( n 2 ) . {\displaystyle p(n)\approx 1-\left({\frac {364}{365}}\right)^{\binom {n}{2}}.}
And for the group of 23 people, the probability of sharing is
p ( 23 ) ≈ 1 − ( 364 365 ) ( 23 2 ) = 1 − ( 364 365 ) 253 ≈ 0.500477. {\displaystyle p(23)\approx 1-\left({\frac {364}{365}}\right)^{\binom {23}{2}}=1-\left({\frac {364}{365}}\right)^{253}\approx 0.500477.}
Poisson approximation Applying the Poisson approximation for the binomial on the group of 23 people,
Poi ( ( 23 2 ) 365 ) = Poi ( 253 365 ) ≈ Poi ( 0.6932 ) {\displaystyle \operatorname {Poi} \left({\frac {\binom {23}{2}}{365}}\right)=\operatorname {Poi} \left({\frac {253}{365}}\right)\approx \operatorname {Poi} (0.6932)}
so
Pr ( X > 0 ) = 1 − Pr ( X = 0 ) ≈ 1 − e − 0.6932 ≈ 1 − 0.499998 = 0.500002. {\displaystyle \Pr(X>0)=1-\Pr(X=0)\approx 1-e^{-0.6932}\approx 1-0.499998=0.500002.}
The result is over 50% as previous descriptions. This approximation is the same as the one above based on the Taylor expansion that uses ex ≈ 1 + x.
Square approximation A good rule of thumb which can be used for mental calculation is the relation
p ( n , d ) ≈ n 2 2 d {\displaystyle p(n,d)\approx {\frac {n^{2}}{2d}}}
which can also be written as
n ≈ 2 d × p ( n ) {\displaystyle n\approx {\sqrt {2d\times p(n)}}}
which works well for probabilities less than or equal to 1/2. In these equations, d is the number of days in a year. For instance, to estimate the number of people required for a 1/2 chance of a shared birthday, we get
n ≈ 2 × 365 × 1 2 = 365 ≈ 19 {\displaystyle n\approx {\sqrt {2\times 365\times {\tfrac {1}{2}}}}={\sqrt {365}}\approx 19}
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 1/2 chance of matching:
n ≥ 1 2 + 1 4 + 2 × ln ( 2 ) × 365 = 22.999943. {\displaystyle n\geq {\tfrac {1}{2}}+{\sqrt {{\tfrac {1}{4}}+2\times \ln(2)\times 365}}=22.999943.}
This is a result of the good approximation that an event with 1/k probability will have a 1/2 chance of occurring at least once if it is repeated k ln 2 times.
Probability table
The lighter 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 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−18 to 10−15 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 8.2×1011 documents, even if its possible outputs are many more.
An upper bound on the probability and a lower bound on the number of people The argument below is adapted from an argument of Paul Halmos. As stated above, the probability that no two birthdays coincide is
1 − p ( n ) = p ¯ ( n ) = ∏ k = 1 n − 1 ( 1 − k 365 ) . {\displaystyle 1-p(n)={\bar {p}}(n)=\prod _{k=1}^{n-1}\left(1-{\frac {k}{365}}\right).}
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
p ¯ ( n ) = ∏ k = 1 n − 1 ( 1 − k 365 ) < ∏ k = 1 n − 1 ( e − k 365 ) = e − n ( n − 1 ) 730 . {\displaystyle {\bar {p}}(n)=\prod _{k=1}^{n-1}\left(1-{\frac {k}{365}}\right)<\prod _{k=1}^{n-1}\left(e^{-{\frac {k}{365}}}\right)=e^{-{\frac {n(n-1)}{730}}}.}
Therefore, the expression above is not only an approximation, but also an upper bound of p(n). The inequality
e − n ( n − 1 ) 730 < 1 2 {\displaystyle e^{-{\frac {n(n-1)}{730}}}<{\frac {1}{2}}}
implies p(n) < 1/2. Solving for n gives
n 2 − n > 730 ln 2. {\displaystyle n^{2}-n>730\ln 2.}
Now, 730 ln 2 is approximately 505.997, which is barely below 506, the value of n2 − n attained when n = 23. Therefore, 23 people suffice. Incidentally, solving n2 − n = 730 ln 2 for n gives the approximate formula of Frank H. Mathis cited above. This derivation only shows that at most 23 people are needed to ensure the chances of a birthday match are at least even; it leaves open the possibility that n is 22 or less could also work.
Generalizations
Arbitrary number of days 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
1 − ( 1 − 1 d ) ( 1 − 2 d ) ⋯ ( 1 − n − 1 d ) ≥ 1 2 . {\displaystyle 1-\left(1-{\frac {1}{d}}\right)\left(1-{\frac {2}{d}}\right)\cdots \left(1-{\frac {n-1}{d}}\right)\geq {\frac {1}{2}}.}
The classical birthday problem thus corresponds to determining n(365). The first 99 values of n(d) are given here (sequence A033810 in the OEIS):
A similar calculation shows that n(d) = 23 when d is in the range 341–372. A number of bounds and formulas for n(d) have been published. For any d ≥ 1, the number n(d) satisfies
3 − 2 ln 2 6 < n ( d ) − 2 d ln 2 ≤ 9 − 86 ln 2 . {\displaystyle {\frac {3-2\ln 2}{6}}<n(d)-{\sqrt {2d\ln 2}}\leq 9-{\sqrt {86\ln 2}}.}
These bounds are optimal in the sense that the sequence n(d) − √2d ln 2 gets arbitrarily close to
3 − 2 ln 2 6 ≈ 0.27 , {\displaystyle {\frac {3-2\ln 2}{6}}\approx 0.27,}
while it has
9 − 86 ln 2 ≈ 1.28 {\displaystyle 9-{\sqrt {86\ln 2}}\approx 1.28}
as its maximum, taken for d = 43. The bounds are sufficiently tight to give the exact value of n(d) in most of the cases. For example, for d = 365 these bounds imply that 22.7633 < n(365) < 23.7736 and 23 is the only integer in that range. In general, it follows from these bounds that n(d) always equals either
⌈ 2 d ln 2 ⌉ or ⌈ 2 d ln 2 ⌉ + 1 {\displaystyle \left\lceil {\sqrt {2d\ln 2}}\,\right\rceil \quad {\text{or}}\quad \left\lceil {\sqrt {2d\ln 2}}\,\right\rceil +1}
where ⌈ · ⌉ denotes the ceiling function. The formula
n ( d ) = ⌈ 2 d ln 2 ⌉ {\displaystyle n(d)=\left\lceil {\sqrt {2d\ln 2}}\,\right\rceil }
holds for 73% of all integers d. The formula
n ( d ) = ⌈ 2 d ln 2 + 3 − 2 ln 2 6 ⌉ {\displaystyle n(d)=\left\lceil {\sqrt {2d\ln 2}}+{\frac {3-2\ln 2}{6}}\right\rceil }
holds for almost all d, i.e., for a set of integers d with asymptotic density 1. The formula
n ( d ) = ⌈ 2 d ln 2 + 3 − 2 ln 2 6 + 9 − 4 ( ln 2 ) 2 72 2 d ln 2 ⌉ {\displaystyle n(d)=\left\lceil {\sqrt {2d\ln 2}}+{\frac {3-2\ln 2}{6}}+{\frac {9-4(\ln 2)^{2}}{72{\sqrt {2d\ln 2}}}}\right\rceil }
holds for all d ≤ 1018, but it is conjectured that there are infinitely many counterexamples to this formula. The formula
n ( d ) = ⌈ 2 d ln 2 + 3 − 2 ln 2 6 + 9 − 4