Birthday problem

The probability of any two people not having the same birthday is 364/365. In a room containing n people, there are (ⁿ
₂) = n(n − 1)/2 pairs of people, i.e. (ⁿ
₂) 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 (ⁿ
₂) times, which gives us

${\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

${\displaystyle p(n)\approx 1-\left({\frac {364}{365}}\right)^{\binom {n}{2}}.}$

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

${\displaystyle \operatorname {Poi} \left({\frac {\binom {23}{2}}{365}}\right)=\operatorname {Poi} \left({\frac {253}{365}}\right)\approx \operatorname {Poi} (0.6932)}$

so

${\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 ${\displaystyle e^{x}\approx 1+x}$.

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

${\displaystyle p(n)\approx {\frac {n^{2}}{2m}}}$

which can also be written as

${\displaystyle n\approx {\sqrt {2m\times p(n)}}}$

which works well for probabilities less than or equal to 1/2. In these equations, m 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

${\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.

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:

${\displaystyle n\approx {\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.[6]

length of hex string	no. of bits (b)	hash space size (2b)	Number of hashed elements such that probability of at least one hash collision ≥ p
			p = 10−18	p = 10−15	p = 10−12	p = 10−9	p = 10−6	p = 0.001	p = 0.01	p = 0.25	p = 0.50	p = 0.75
8	32	4.3×109	2	2	2	2.9	93	2.9×103	9.3×103	5.0×104	7.7×104	1.1×105
(10)	(40)	(1.1×1012)	2	2	2	47	1.5×103	4.7×104	1.5×105	8.0×105	1.2×106	1.7×106
(12)	(48)	(2.8×1014)	2	2	24	7.5×102	2.4×104	7.5×105	2.4×106	1.3×107	2.0×107	2.8×107
16	64	1.8×1019	6.1	1.9×102	6.1×103	1.9×105	6.1×106	1.9×108	6.1×108	3.3×109	5.1×109	7.2×109
(24)	(96)	(7.9×1028)	4.0×105	1.3×107	4.0×108	1.3×1010	4.0×1011	1.3×1013	4.0×1013	2.1×1014	3.3×1014	4.7×1014
32	128	3.4×1038	2.6×1010	8.2×1011	2.6×1013	8.2×1014	2.6×1016	8.3×1017	2.6×1018	1.4×1019	2.2×1019	3.1×1019
(48)	(192)	(6.3×1057)	1.1×1020	3.5×1021	1.1×1023	3.5×1024	1.1×1026	3.5×1027	1.1×1028	6.0×1028	9.3×1028	1.3×1029
64	256	1.2×1077	4.8×1029	1.5×1031	4.8×1032	1.5×1034	4.8×1035	1.5×1037	4.8×1037	2.6×1038	4.0×1038	5.7×1038
(96)	(384)	(3.9×10115)	8.9×1048	2.8×1050	8.9×1051	2.8×1053	8.9×1054	2.8×1056	8.9×1056	4.8×1057	7.4×1057	1.0×1058
128	512	1.3×10154	1.6×1068	5.2×1069	1.6×1071	5.2×1072	1.6×1074	5.2×1075	1.6×1076	8.8×1076	1.4×1077	1.9×1077

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⁻¹⁸ to 10⁻¹⁵ is the uncorrectable bit error rate of a typical hard disk.[7] In theory, 128-bit hash functions, such as MD5, should stay within that range until about 8.2×10¹¹ documents, even if its possible outputs are many more.

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

${\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):

d	1–2	3–5	6–9	10–16	17–23	24–32	33–42	43–54	55–68	69–82	83–99
n(d)	2	3	4	5	6	7	8	9	10	11	12

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.[8] For any d ≥ 1, the number n(d) satisfies[9]

${\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

${\displaystyle {\frac {3-2\ln 2}{6}}\approx 0.27,}$

while it has

${\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 99% of all cases, for example n(365) = 23. In general, it follows from these bounds that n(d) always equals either

${\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

${\displaystyle n(d)=\left\lceil {\sqrt {2d\ln 2}}\,\right\rceil }$

holds for 73% of all integers d.[10] The formula

${\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.[10]

The formula

${\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 ≤ 10¹⁸, but it is conjectured that there are infinitely many counterexamples to this formula.[11]

The formula

${\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}}}}-{\frac {2(\ln 2)^{2}}{135d}}\right\rceil }$

holds for all d ≤ 10¹⁸, and it is conjectured that this formula holds for all d.[11]

It is possible to extend the problem to ask how many people in a group are necessary for there to be a greater than 50% probability that at least 3/4/5/etc. of the group share the same birthday.

The first few values are as follows: >50% probability of 3 people sharing a birthday - 88 people; >50% probability of 4 people sharing a birthday - 187 people. The full list can be found as sequence A014088 of the Online Encyclopedia of Integer Sequences.[12]

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.)[13]

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

${\displaystyle {\begin{aligned}p(n;d)&={\begin{cases}1-\displaystyle \prod _{k=1}^{n-1}\left(1-{\frac {k}{d}}\right)&n\leq d\\1&n>d\end{cases}}\\[8px]&\approx 1-e^{-{\frac {n(n-1)}{2d}}}\\&\approx 1-\left({\frac {d-1}{d}}\right)^{\frac {n(n-1)}{2}}\end{aligned}}}$

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

${\displaystyle n(p;d)\approx {\sqrt {2d\cdot \ln \left({\frac {1}{1-p}}\right)}}.}$

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⁄₂. 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[14] under the name of capture-recapture statistics to estimate the size of fish population in lakes.

Plot of the probability of at least one shared birthday between at least one man and one woman

The basic problem considers all trials to be of one "type". The birthday problem has been generalized to consider an arbitrary number of types.[15] 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 two men or two women do not count.) The probability of no shared birthdays here is

${\displaystyle p_{0}={\frac {1}{d^{m+n}}}\sum _{i=1}^{m}\sum _{j=1}^{n}S_{2}(m,i)S_{2}(n,j)\prod _{k=0}^{i+j-1}d-k}$

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 50% 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.

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 is a prize for first match, the best position in line is 20th.

Comparing p(n) = probability of a birthday match with q(n) = probability of matching your birthday

In the birthday problem, neither of the two people is chosen in advance. By 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

${\displaystyle q(n)=1-\left({\frac {365-1}{365}}\right)^{n}}$

and for general d by

${\displaystyle q(n;d)=1-\left({\frac {d-1}{d}}\right)^{n}.}$

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. 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.

Another generalization is to ask for the probability of finding at least one pair in a group of n people with birthdays within k calendar days of each other, if there are d equally likely birthdays.[16]

${\displaystyle {\begin{aligned}p(n,k,d)&=1-{\frac {(d-nk-1)!}{d^{n-1}{\bigl (}d-n(k+1){\bigr )}!}}\end{aligned}}}$

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 given in the following table:

k	n for d = 365
0	23
1	14
2	11
3	9
4	8
5	8
6	7
7	7

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.[16]

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[17]

${\displaystyle \sum _{k=1}^{n}q(k-1;d)=n-d+d\left({\frac {d-1}{d}}\right)^{n}.}$

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 asks for 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[18][19] 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

${\displaystyle Q(M)=\sum _{k=1}^{M}{\frac {M!}{(M-k)!M^{k}}}.}$

The function

${\displaystyle Q(M)=1+{\frac {M-1}{M}}+{\frac {(M-1)(M-2)}{M^{2}}}+\cdots +{\frac {(M-1)(M-2)\cdots 1}{M^{M-1}}}}$

has been studied by Srinivasa Ramanujan and has asymptotic expansion:

${\displaystyle Q(M)\sim {\sqrt {\frac {\pi M}{2}}}-{\frac {1}{3}}+{\frac {1}{12}}{\sqrt {\frac {\pi }{2M}}}-{\frac {4}{135M}}+\cdots .}$

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 analysis using indicator random variables can provide a simpler but approximate analysis of this problem.[20] For each pair (i, j) for k people in a room, we define the indicator random variable X_ij, for ${\displaystyle 1\leq i\leq j\leq k}$, by

${\displaystyle {\begin{alignedat}{2}X_{ij}&=I\{{\text{person }}i{\text{ and person }}j{\text{ have the same birthday}}\}\\&={\begin{cases}1,&{\text{if person }}i{\text{ and person }}j{\text{ have the same birthday;}}\\0,&{\text{otherwise.}}\end{cases}}\end{alignedat}}}$

${\displaystyle {\begin{alignedat}{2}E[X_{ij}]&=\Pr\{{\text{person }}i{\text{ and person }}j{\text{ have the same birthday}}\}\\&=1/n\end{alignedat}}}$

Let X be a random variable counting the pairs of individuals with the same birthday.

${\displaystyle X=\sum _{i=1}^{k}\sum _{j=i+1}^{k}X_{ij}}$

${\displaystyle {\begin{alignedat}{3}E[X]&=\sum _{i=1}^{k}\sum _{j=i+1}^{k}E[X_{ij}]\\&={\binom {k}{2}}{\frac {1}{n}}\\&={\frac {k(k-1)}{2n}}\\\end{alignedat}}}$

For n = 365, if k = 28, the expected number of with the same birthday is ${\displaystyle (28\cdot 27)/(2\cdot 365)\approx 1.0356.}$ Therefore we can expect at least one matching pair with at least 28 people.

An informal demonstration of the problem can be made from the list of Prime Ministers of Australia, of which there have been 29 as of 2017, 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 and Herzegovina, Brazil, Cameroon, Colombia, Honduras, Netherlands, Nigeria, Russia, Spain and USA each with one pair.[21]

Voracek, Tran and Formann showed that the majority of people markedly overestimate the number of people that is necessary to achieve a given probability of people having the same birthday, and markedly underestimate the probability of people having the same birthday when a specific sample size is given.[22] Further results were that psychology students and women did better on the task than casino visitors/personnel or men, but were less confident about their estimates.

The reverse problem is to find, for a fixed probability p, the greatest n for which the probability p(n) is smaller than the given p, or the smallest n for which the probability p(n) is greater than the given p.

Taking the above formula for d = 365, one has

${\displaystyle n(p;365)\approx {\sqrt {730\ln \left({\frac {1}{1-p}}\right)}}.}$

The following table gives some sample calculations.

p	n	n↓	p(n↓)	n↑	p(n↑)
0.01	0.14178√365 = 2.70864	2	0.00274	3	0.00820
0.05	0.32029√365 = 6.11916	6	0.04046	7	0.05624
0.1	0.45904√365 = 8.77002	8	0.07434	9	0.09462
0.2	0.66805√365 = 12.76302	12	0.16702	13	0.19441
0.3	0.84460√365 = 16.13607	16	0.28360	17	0.31501
0.5	1.17741√365 = 22.49439	22	0.47570	23	0.50730
0.7	1.55176√365 = 29.64625	29	0.68097	30	0.70632
0.8	1.79412√365 = 34.27666	34	0.79532	35	0.81438
0.9	2.14597√365 = 40.99862	40	0.89123	41	0.90315
0.95	2.44775√365 = 46.76414	46	0.94825	47	0.95477
0.99	3.03485√365 = 57.98081	57	0.99012	58	0.99166

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