Birthday problem

From a permutations perspective, let the event {{math|A}} be the probability of finding a group of 23 people without any repeated birthdays. And let the event {{math|B}} be the probability of finding a group of 23 people with at least two people sharing same birthday, {{math|P(B) {{=}} 1 − P(A)}}. This is such that {{math|P(A)}} is the ratio of the total number of birthdays, $V\_\{nr\}$, without repetitions and order matters (e.g. for a group of 2 people, mm/dd birthday format, one possible outcome is $\backslash left\; \backslash \{\; \backslash left\; \backslash \{01/02,05/20\backslash right\; \backslash \},\backslash left\; \backslash \{05/20,01/02\backslash right\; \backslash \},\backslash left\; \backslash \{10/02,08/04\backslash right\backslash \},...\backslash right\; \backslash \}$) divided by the total number of birthdays with repetition and order matters, $V\_\{t\}$, as it is the total space of outcomes from the experiment (e.g. 2 people, one possible outcome is $\backslash left\; \backslash \{\; \backslash left\; \backslash \{01/02,01/02\backslash right\; \backslash \},\backslash left\; \backslash \{10/02,08/04\backslash right\; \backslash \},...\backslash right\; \backslash \}$). Therefore $V\_\{nr\}$ and $V\_\{t\}$ are permutations.

:

Another way the birthday problem can be solved is by asking for an approximate probability that in a group of {{mvar|n}} people at least two have the same birthday. For simplicity, leap years, twins, selection bias, and seasonal and weekly variations in birth rates{{refn|see Birthday#Distribution through the year}} 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.{{Harv|Bloom|1973}}{{cite book |author-first = J. Michael |author-last = Steele |title = The Cauchy‑Schwarz Master Class |url = https://archive.org/details/cauchyschwarzmas00stee_431 |url-access = limited | pages = [https://archive.org/details/cauchyschwarzmas00stee_431/page/n217 206], 277 |date=2004 |publisher = Cambridge University Press |location=Cambridge | isbn = 9780521546775 }} 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.{{cite journal |author1 = Mario Cortina Borja |author2 = John Haigh |title = The Birthday Problem |journal = Significance |date = September 2007 |volume = 4 |issue = 3 |pages = 124–127 |publisher = Royal Statistical Society |doi = 10.1111/j.1740-9713.2007.00246.x|doi-access = free }}

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

Here is the calculation of {{math|P(B)}} 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 {{sfrac|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 {{sfrac|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 {{sfrac|343|365}}. Finally, the principle of conditional probability implies that {{math|P(A′)}} is equal to the product of these individual probabilities:

{{NumBlk|:|$P(A\text{'})=\backslash frac\{365\}\{365\}\backslash times\backslash frac\{364\}\{365\}\backslash times\backslash frac\{363\}\{365\}\backslash times\backslash frac\{362\}\{365\}\backslash times\backslash cdots\backslash times\backslash frac\{343\}\{365\}$|{{EquationRef|1}}}}

The terms of equation ({{EquationNote|1}}) can be collected to arrive at:

{{NumBlk|:|$P(A\text{'})=\backslash left(\backslash frac\{1\}\{365\}\backslash right)^\{23\}\backslash times(365\backslash times364\backslash times363\backslash times\backslash cdots\backslash times343)$|{{EquationRef|2}}}}

Evaluating equation ({{EquationNote|2}}) gives {{math|P(A′) ≈ 0.492703}}

Therefore, {{math|P(B) ≈ 1 − 0.492703 {{=}} 0.507297}} (50.7297%).

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

:

where {{math|!}} is the factorial operator, {{math|{{pars|s=160%|{{su|p=365|b=n|a=c}}}}}} is the binomial coefficient and {{math|_kP_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 {{math|{{pars|s=160%|{{sfrac|364|365}}}}}}, the third cannot have the same birthday as either of the first two {{math|{{pars|s=160%|{{sfrac|363|365}}}}}}, and in general the {{mvar|n}}th birthday cannot be the same as any of the {{math|n − 1}} preceding birthdays.

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

:$p(n)\; =\; 1\; -\; \backslash bar\; p(n).$

The following table shows the probability for some other values of {{mvar|n}} (for this table, the existence of leap years is ignored, and each birthday is assumed to be equally likely):

Image:Birthdaymatch.svg

:

Image:Birthday paradox probability.svg

Image:Birthday paradox approximation.svg

The Taylor series expansion of the exponential function (the constant {{math|e ≈ {{val|2.718281828}}}})

:$e^x\; =\; 1\; +\; x\; +\; \backslash frac\{x^2\}\{2!\}+\backslash cdots$

provides a first-order approximation for {{math|e^x}} for $|x|\; \backslash ll\; 1$:

:$e^x\; \backslash approx\; 1\; +\; x.$

To apply this approximation to the first expression derived for {{math|{{overline|p}}(n)}}, set {{math|x {{=}} −{{sfrac|a|365}}}}. Thus,

:$e^\{-a/365\}\; \backslash approx\; 1\; -\; \backslash frac\{a\}\{365\}.$

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

: $e^\{-1/365\}\; \backslash approx\; 1\; -\; \backslash frac\{1\}\{365\}.$

The first expression derived for {{math|{{overline|p}}(n)}} can be approximated as

:$$

\begin{align}

\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{align}

Therefore,

:$p(n)\; =\; 1-\backslash bar\; p(n)\; \backslash approx\; 1\; -\; e^\{-\backslash frac\{n(n-1)\}\{730\}\}.$

An even coarser approximation is given by

:$p(n)\backslash approx\; 1-e^\{-\backslash 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 {{mvar|d}}, if there are {{mvar|n}} persons, and if {{math|n ≪ d}}, then using the same approach as above we achieve the result that if {{math|p(n, d)}} is the probability that at least two out of {{mvar|n}} people share the same birthday from a set of {{mvar|d}} available days, then:

:$\backslash begin\{align\}$

p(n, d) & \approx 1-e^{-\frac{n(n-1)}{2d}} \\[6pt]

& \approx 1-e^{-\frac{n^2}{2d}}.

\end{align}

The probability of any two people not having the same birthday is {{sfrac|364|365}}. In a room containing n people, there are {{math|{{pars|s=150%|{{su|p=n|b=2|a=c}}}} {{=}} {{sfrac|n(n − 1)|2}}}} pairs of people, i.e. {{math|{{pars|s=150%|{{su|p=n|b=2|a=c}}}}}} 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 {{sfrac|364|365}} can be multiplied by itself {{math|{{pars|s=150%|{{su|p=n|b=2|a=c}}}}}} times, which gives us

:$\backslash bar\; p(n)\; \backslash approx\; \backslash left(\backslash frac\{364\}\{365\}\backslash right)^\backslash 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)\; \backslash approx\; 1\; -\; \backslash left(\backslash frac\{364\}\{365\}\backslash right)^\backslash binom\{n\}\{2\}.$

And for the group of 23 people, the probability of sharing is

:$p(23)\; \backslash approx\; 1\; -\; \backslash left(\backslash frac\{364\}\{365\}\backslash right)^\backslash binom\{23\}\{2\}\; =\; 1\; -\; \backslash left(\backslash frac\{364\}\{365\}\backslash right)^\{253\}\; \backslash approx\; 0.500477\; .$

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

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

so

:$\backslash Pr(X>0)=1-\backslash Pr(X=0)\; \backslash approx\; 1-e^\{-0.6932\}\; \backslash 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 {{math|e^x ≈ 1 + x}}.

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

:$p(n,d)\; \backslash approx\; \backslash frac\{n^2\}\{2d\}$

which can also be written as

:$n\; \backslash approx\; \backslash sqrt\; \{\; 2d\; \backslash times\; p(n)\}$

which works well for probabilities less than or equal to {{sfrac|1|2}}. In these equations, {{mvar|d}} is the number of days in a year.

For instance, to estimate the number of people required for a {{sfrac|1|2}} chance of a shared birthday, we get

:$n\; \backslash approx\; \backslash sqrt\{\; 2\; \backslash times\; 365\; \backslash times\; \backslash tfrac12\}\; =\; \backslash sqrt\{365\}\; \backslash 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 {{sfrac|1|2}} chance of matching:

:$n\; \backslash geq\; \backslash tfrac\{1\}\{2\}\; +\; \backslash sqrt\{\backslash tfrac\{1\}\{4\}\; +\; 2\; \backslash times\; \backslash ln(2)\; \backslash times\; 365\}\; =\; 22.999943.$

This is a result of the good approximation that an event with {{math|{{sfrac|1|k}}}} probability will have a {{sfrac|1|2}} chance of occurring at least once if it is repeated {{math|k ln 2}} times.{{cite journal

| last = Mathis

| first = Frank H.

|date= June 1991

| title = A Generalized Birthday Problem

| journal = SIAM Review

| volume = 33

| issue = 2

| pages = 265–270

| issn = 0036-1445

| doi = 10.1137/1033051

| oclc = 37699182

| jstor = 2031144

| url = http://http.cs.berkeley.edu/~daw/papers/genbday-crypto02.ps

}}

{{Main|Birthday attack}}

:

[[File:birthday_attack_vs_paradox.svg|thumb|Comparison of the birthday problem (1) and birthday attack (2):{{parabreak}}

In (1), collisions are found within one set, in this case, 3 out of 276 pairings of the 24 lunar astronauts.{{parabreak}}

In (2), collisions are found between two sets, in this case, 1 out of 256 pairings of only the first bytes of SHA-256 hashes of 16 variants each of benign and harmful contracts.]]

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, {{val|e=-18}} to {{val|e=-15}} is the uncorrectable bit error rate of a typical hard disk.Jim Gray, Catharine van Ingen. [https://arxiv.org/abs/cs/0701166 Empirical Measurements of Disk Failure Rates and Error Rates] In theory, 128-bit hash functions, such as MD5, should stay within that range until about {{val|8.2|e=11}} documents, even if its possible outputs are many more.

The argument below is adapted from an argument of Paul Halmos.{{refn|group=nb|In his autobiography, Halmos criticized the form in which the birthday paradox is often presented, in terms of numerical computation. He believed that it should be used as an example in the use of more abstract mathematical concepts. He wrote:

The reasoning is based on important tools that all students of mathematics should have ready access to. The birthday problem used to be a splendid illustration of the advantages of pure thought over mechanical manipulation; the inequalities can be obtained in a minute or two, whereas the multiplications would take much longer, and be much more subject to error, whether the instrument is a pencil or an old-fashioned desk computer. What calculators do not yield is understanding, or mathematical facility, or a solid basis for more advanced, generalized theories.

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

:$1-p(n)\; =\; \backslash bar\; p(n)\; =\; \backslash prod\_\{k=1\}^\{n-1\}\backslash left(1-\backslash frac\{k\}\{365\}\backslash right)\; .$

As in earlier paragraphs, interest lies in the smallest {{mvar|n}} such that {{math|p(n) > {{sfrac|1|2}}}}; or equivalently, the smallest {{mvar|n}} such that {{math|{{overline|p}}(n) < {{sfrac|1|2}}}}.

Using the inequality {{math|1 − x < e^−x}} in the above expression we replace {{math|1 − {{sfrac|k|365}}}} with {{math|e^{{{frac|−k|365}}}}}. This yields

:

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

:

implies {{math|{{overline|p}}(n) < {{sfrac|1|2}}}}. Solving for {{mvar|n}} gives

:$n^2-n\; >\; 730\; \backslash ln\; 2\; .$

Now, {{math|730 ln 2}} is approximately 505.997, which is barely below 506, the value of {{math|n² − n}} attained when {{math|n {{=}} 23}}. Therefore, 23 people suffice. Incidentally, solving {{math|n² − 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 {{mvar|n}} is 22 or less could also work.

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

:$1-\backslash left(1-\backslash frac\{1\}\{d\}\backslash right)\backslash left(1-\backslash frac\{2\}\{d\}\backslash right)\backslash cdots\backslash left(1-\backslash frac\{n-1\}\{d\}\backslash right)\backslash geq\; \backslash frac\{1\}\{2\}.$

The classical birthday problem thus corresponds to determining {{math|n(365)}}. The first 99 values of {{math|n(d)}} are given here {{OEIS|id=A033810}}:

:

A similar calculation shows that {{math|n(d)}} = 23 when {{mvar|d}} is in the range 341–372.

A number of bounds and formulas for {{math|n(d)}} have been published.{{wikicite|ref={{Harvid|Brink|2012}}|reference=D. Brink, A (probably) exact solution to the Birthday Problem, Ramanujan Journal, 2012, [https://link.springer.com/article/10.1007/s11139-011-9343-9].}}

For any {{math|d ≥ 1}}, the number {{math|n(d)}} satisfies{{Harvard citations|author=Brink|year=2012|nb=yes|loc=Theorem 2}}

:

These bounds are optimal in the sense that the sequence {{math|n(d) − {{sqrt|2d ln 2}}}}

gets arbitrarily close to

:$\backslash frac\{3-2\backslash ln2\}\{6\}\; \backslash approx\; 0.27,$

while it has

:$9-\backslash sqrt\{86\backslash ln2\}\backslash approx\; 1.28$

as its maximum, taken for {{math|d {{=}} 43}}.

The bounds are sufficiently tight to give the exact value of {{math|n(d)}} in most of the cases. For example, for {{math|d {{=}}}} 365 these bounds imply that {{math|22.7633 < n(365) < 23.7736}} and 23 is the only integer in that range. In general, it follows from these bounds that {{math|n(d)}} always equals either

:$\backslash left\backslash lceil\backslash sqrt\{2d\backslash ln2\}\backslash ,\backslash right\backslash rceil\; \backslash quad\backslash text\{or\}\backslash quad\; \backslash left\backslash lceil\backslash sqrt\{2d\backslash ln2\}\backslash ,\backslash right\backslash rceil+1$

where {{math|⌈ · ⌉}} denotes the ceiling function.

The formula

:$n(d)\; =\; \backslash left\backslash lceil\backslash sqrt\{2d\backslash ln2\}\backslash ,\backslash right\backslash rceil$

holds for 73% of all integers {{mvar|d}}.{{Harvard citations|author=Brink|year=2012|nb=yes|loc=Theorem 3}} The formula

:$n(d)\; =\; \backslash left\backslash lceil\backslash sqrt\{2d\backslash ln2\}+\backslash frac\{3-2\backslash ln2\}\{6\}\backslash right\backslash rceil$

holds for almost all {{mvar|d}}, i.e., for a set of integers {{mvar|d}} with asymptotic density 1.

The formula

:$n(d)=\backslash left\backslash lceil\; \backslash sqrt\{2d\backslash ln2\}+\backslash frac\{3-2\backslash ln2\}\{6\}+\backslash frac\{9-4(\backslash ln2)^2\}\{72\backslash sqrt\{2d\backslash ln2\}\}\backslash right\backslash rceil$

holds for all {{math|d ≤ {{val|e=18}}}}, but it is conjectured that there are infinitely many counterexamples to this formula.{{Harvard citations|author=Brink|year=2012|nb=yes|loc=Table 3, Conjecture 1}}

The formula

:$n(d)=\backslash left\backslash lceil\; \backslash sqrt\{2d\backslash ln2\}+\backslash frac\{3-2\backslash ln2\}\{6\}+\backslash frac\{9-4(\backslash ln2)^2\}\{72\backslash sqrt\{2d\backslash ln2\}\}-\backslash frac\{2(\backslash ln2)^2\}\{135d\}\backslash right\backslash rceil$

holds for all {{math|d ≤ {{val|e=18}}}}, and it is conjectured that this formula holds for all {{mvar|d}}.

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 {{OEIS|A014088}}.{{cite web |title=Minimal number of people to give a 50% probability of having at least n coincident birthdays in one year. |url=https://oeis.org/A014088 |website=The On-line Encyclopedia of Integer Sequences |publisher=OEIS |access-date=17 February 2020}}

The strong birthday problem asks for the number of people that need to be gathered together before there is a 50% chance that everyone in the gathering shares their birthday with at least one other person. For d=365 days the answer is 3,064 people.DasGupta, Anirban. "The matching, birthday and the strong birthday problem: a contemporary review." Journal of Statistical Planning and Inference 130.1-2 (2005): 377-389.Mario Cortina Borja, The Strong Birthday Problem, Significance, Volume 10, Issue 6, December 2013, Pages 18–20, https://doi.org/10.1111/j.1740-9713.2013.00705.x

The number of people needed for arbitrary number of days is given by {{OEIS|A380129}}

The birthday problem can be generalized as follows:

:Given {{mvar|n}} random integers drawn from a discrete uniform distribution with range {{math|[1,d]}}, what is the probability {{math|p(n; d)}} that at least two numbers are the same? ({{math|d {{=}} 365}} gives the usual birthday problem.){{cite conference | title = Birthday Paradox for Multi-collisions| last1 = Suzuki| first1 = K.

| last2 = Tonien| first2 = D.|display-authors=et al| date = 2006| publisher = Springer| book-title = Lecture Notes in Computer Science, vol 4296 | location = Berlin

| id = Information Security and Cryptology – ICISC 2006| editor = Rhee M.S., Lee B. | doi = 10.1007/11927587_5}}

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

:$\backslash begin\{align\}$

p(n;d) &= \begin{cases} 1-\displaystyle\prod_{k=1}^{n-1}\left(1-\frac{k}{d}\right) & n\le 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{align}

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

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

The birthday problem in this more generic sense applies to hash functions: the expected number of {{math|N}}-bit hashes that can be generated before getting a collision is not {{math|2^N}}, but rather only {{math|2^{{frac|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 SchnabelZ. E. Schnabel (1938) The Estimation of the Total Fish Population of a Lake, American Mathematical Monthly 45, 348–352. under the name of capture-recapture statistics to estimate the size of fish population in lakes. The birthday problem and its generalizations are also useful tools for modelling coincidences.M. Pollanen (2024) A Double Birthday Paradox in the Study of Coincidences, Mathematics 23(24), 3882. https://doi.org/10.3390/math12243882

The classic birthday problem allows for more than two people to share a particular birthday or for there to be matches on multiple days. The probability that among {{mvar|n}} people there is exactly one pair of individuals with a matching birthday given {{mvar|d}} possible days is

: $p\_2(n;\; d)\; =\; \backslash frac\{\{n\; \backslash choose\; 2\}\}\{d-n+1\}\; (1-p(n;\; d))$

Unlike the standard birthday problem, as {{mvar|n}} increases the probability reaches a maximum value before decreasing. For example, for {{math|d {{=}} 365}}, the probability of a unique match has a maximum value of 0.3864 occurring when {{math|n {{=}} 28}}.

File:2d birthday.png

The basic problem considers all trials to be of one "type". The birthday problem has been generalized to consider an arbitrary number of types.M. C. Wendl (2003) [https://dx.doi.org/10.1016/S0167-7152(03)00168-8 Collision Probability Between Sets of Random Variables], Statistics and Probability Letters 64(3), 249–254. In the simplest extension there are two types of people, say {{mvar|m}} men and {{mvar|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

:$p\_0\; =\backslash frac\{1\}\{d^\{m+n\}\}\; \backslash sum\_\{i=1\}^m\; \backslash sum\_\{j=1\}^n\; S\_2(m,i)\; S\_2(n,j)\; \backslash prod\_\{k=0\}^\{i+j-1\}\; d\; -\; k$

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

This variation of the birthday problem is interesting because there is not a unique solution for the total number of people {{math|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 {{mvar|n}} is {{math|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.{{citation needed|date=September 2019}}

Image:Birthday paradox.svg

In the birthday problem, neither of the two people is chosen in advance. By contrast, the probability {{math|q(n)}} that at least one other person in a room of {{mvar|n}} other people has the same birthday as a particular person (for example, you) is given by

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

and for general {{mvar|d}} by

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

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

For any one person in a group of n people the probability that he or she shares his birthday with someone else is $q(n-1;d)$, as explained above. The expected number of people with a shared (non-unique) birthday can now be calculated easily by multiplying that probability by the number of people (n), so it is:

: $n\backslash left(1\; -\; \backslash left(\; \backslash frac\{d-1\}\{d\}\; \backslash right)^\{n-1\}\backslash right)$

(This multiplication can be done this way because of the linearity of the expected value of indicator variables). This implies that the expected number of people with a non-shared (unique) birthday is:

: $n\; \backslash left(\; \backslash frac\{d-1\}\{d\}\; \backslash right)^\{n-1\}$

Similar formulas can be derived for the expected number of people who share with three, four, etc. other people.

The expected number of people needed until every birthday is achieved is called the Coupon collector's problem. It can be calculated by {{math|nH_n}}, where {{math|H_n}} is the {{mvar|n}}th harmonic number. For 365 possible dates (the birthday problem), the answer is 2365.

Another generalization is to ask for the probability of finding at least one pair in a group of {{mvar|n}} people with birthdays within {{mvar|k}} calendar days of each other, if there are {{mvar|d}} equally likely birthdays.M. Abramson and W. O. J. Moser (1970) More Birthday Surprises, American Mathematical Monthly 77, 856–858

:

The number of people required so that the probability that some pair will have a birthday separated by {{mvar|k}} days or fewer will be higher than 50% is given in the following table:

:

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.

The expected number of different birthdays, i.e. the number of days that are at least one person's birthday, is:

:$d\; -\; d\; \backslash left\; (\backslash frac\; \{d-1\}\; \{d\}\; \backslash right\; )^n$

This follows from the expected number of days that are no one's birthday:

:$d\; \backslash left\; (\backslash frac\; \{d-1\}\; \{d\}\; \backslash right\; )^n$

which follows from the probability that a particular day is no one's birthday, {{math|{{pars|s=150%|{{sfrac|d − 1|d}}}}{{su|p=n|b= }}}}, easily summed because of the linearity of the expected value.

For instance, with {{math|1={{var|d}} = 365}}, you should expect about 21 different birthdays when there are 22 people, or 46 different birthdays when there are 50 people. When there are 1000 people, there will be around 341 different birthdays (24 unclaimed birthdays).

The above can be generalized from the distribution of the number of people with their birthday on any particular day, which is a Binomial distribution with probability {{math|{{sfrac|1|d}}}}. Multiplying the relevant probability by {{mvar|d}} will then give the expected number of days. For example, the expected number of days which are shared; i.e. which are at least two (i.e. not zero and not one) people's birthday is:

$$d\; -\; d\; \backslash left\; (\backslash frac\; \{d-1\}\; \{d\}\; \backslash right\; )^n\; -\; d\; \backslash cdot\; \backslash binom\{n\}\{1\}\; \backslash left\; (\backslash frac\; \{1\}\; \{d\}\; \backslash right\; )^1\backslash left\; (\backslash frac\; \{d-1\}\; \{d\}\; \backslash right\; )^\{n-1\}\; =\; d\; -\; d\; \backslash left\; (\backslash frac\; \{d-1\}\; \{d\}\; \backslash right\; )^n\; -\; n\; \backslash left\; (\backslash frac\; \{d-1\}\; \{d\}\; \backslash right\; )^\{n-1\}$$

The probability that the {{mvar|k}}th integer randomly chosen from {{math|[1,d]}} will repeat at least one previous choice equals {{math|q(k − 1; d)}} above. The expected total number of times a selection will repeat a previous selection as {{mvar|n}} such integers are chosen equals{{cite web|last1=Might|first1=Matt|title=Collision hash collisions with the birthday paradox|url=http://matt.might.net/articles/counting-hash-collisions/|website=Matt Might's blog|access-date=17 July 2015}}

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

This can be seen to equal the number of people minus the expected number of different birthdays.

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[{{mvar|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{{cite book |first=D. E. |last=Knuth |title=The Art of Computer Programming |volume=3, Sorting and Searching |publisher=Addison-Wesley |location=Reading, Massachusetts |year=1973 |isbn=978-0-201-03803-3 }}{{cite journal |first1=P. |last1=Flajolet |first2=P. J. |last2=Grabner |first3=P. |last3=Kirschenhofer |first4=H. |last4=Prodinger |year=1995 |title=On Ramanujan's Q-Function |journal=Journal of Computational and Applied Mathematics |volume=58 |pages=103–116 |doi=10.1016/0377-0427(93)E0258-N |doi-access=free }} that if one samples uniformly, with replacement, from a population of size {{math|M}}, the number of trials required for the first repeated sampling of some individual has expected value {{math|{{overline|n}} {{=}} 1 + Q(M)}}, where

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

The function

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

has been studied by Srinivasa Ramanujan and has asymptotic expansion:

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

With {{math|1=M = 365}} days in a year, the average number of people required to find a pair with the same birthday is {{math|1={{overline|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 {{math|1=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.{{Cite book|title=Introduction to Algorithms|last=Cormen |display-authors=etal }} For each pair (i, j) for k people in a room, we define the indicator random variable X_ij, for $1\backslash leq\; i\; \backslash leq\; j\backslash leq\; k$, by

$$\backslash begin\{alignat\}\{2\}$$

X_{ij} &

= I \{ \text{person }i\text{ and person }j\text{ have the same birthday} \} \\[10pt] &

= \begin{cases}

1, & \text{if person }i\text{ and person }j\text{ have the same birthday;} \\

0, & \text{otherwise.}

\end{cases}

\end{alignat}

$$\backslash begin\{alignat\}\{2\}$$

E[X_{ij}] &

= \Pr \{ \text{person }i\text{ and person }j\text{ have the same birthday} \} = \frac{1}{n}.

\end{alignat}

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

$$X\; =\backslash sum\_\{i=1\}^k\; \backslash sum\_\{j=i+1\}^k\; X\_\{ij\}$$

$$\backslash begin\{alignat\}\{3\}$$

E[X]

& = \sum_{i=1}^k \sum_{j=i+1}^k E[X_{ij}]\\[8pt]

& = \binom{k}{2} \frac{1}{n}\\[8pt]

& = \frac{k(k-1)}{2n}

\end{alignat}

For {{math|1=n = 365}}, if {{math|1=k = 28}}, the expected number of pairs of individuals with the same birthday is {{sfrac|28 × 27|2 × 365}} ≈ 1.0356. Therefore, we can expect at least one matching pair with at least 28 people.

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.{{cite web |url=https://www.bbc.co.uk/news/magazine-27835311 |title=The birthday paradox at the World Cup |last1=Fletcher |first1=James |date=16 June 2014 |website=bbc.com |publisher=BBC |access-date=27 August 2015 }}

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.{{cite journal |last1=Voracek |first1=M. |last2=Tran |first2=U. S. |last3=Formann |first3=A. K. |year=2008 |title=Birthday and birthmate problems: Misconceptions of probability among psychology undergraduates and casino visitors and personnel |journal=Perceptual and Motor Skills |volume=106 |issue=1 |pages=91–103 |doi=10.2466/pms.106.1.91-103 |pmid=18459359 |s2cid=22046399 }} Further results showed 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 {{mvar|p}},

the greatest {{mvar|n}} for which the probability {{math|p(n)}} is smaller than the given {{mvar|p}}, or the smallest {{mvar|n}} for which the probability {{math|p(n)}} is greater than the given {{mvar|p}}.{{citation needed|date=September 2019}}

Taking the above formula for {{math|d {{=}} 365}}, one has

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

The following table gives some sample calculations.

:

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

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 tonne). 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?

Often, people's intuition is that the answer is above {{val|100000}}. 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.{{Citation needed|date=December 2016}}

The reason is that the correct comparison is to the number of partitions of the weights into left and right. There are {{math|2^{N − 1}}} different partitions for {{math|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 {{math|{{val|500000}}N}} and width {{math|{{val|1000000}}{{sqrt|N}}}}, so that when {{math|2^{N − 1}}} is approximately equal to {{math|{{val|1000000}}{{sqrt|N}}}} the transition occurs. 2^{23 − 1} is about 4 million, while the width of the distribution is only 5 million.{{cite journal |first1=C. |last1=Borgs |first2=J. |last2=Chayes |first3=B. |last3=Pittel |s2cid=6819493 |year=2001 |title=Phase Transition and Finite Size Scaling in the Integer Partition Problem |journal=Random Structures and Algorithms |volume=19 |issue=3–4 |pages=247–288 |doi=10.1002/rsa.10004 }}

Arthur C. Clarke's 1961 novel A Fall of Moondust 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.

{{reflist|group=nb}}

{{Reflist|45em}}

• {{cite journal |first1=M. |last1=Abramson |first2=W. O. J. |last2=Moser |year=1970 |title=More Birthday Surprises |journal=American Mathematical Monthly |volume=77 |issue= 8|pages=856–858 |doi= 10.2307/2317022|jstor=2317022 |ref=none}}
• {{cite journal |first=D. |last=Bloom |year=1973 |title=A Birthday Problem |journal=American Mathematical Monthly |volume=80 |issue= 10|pages=1141–1142 |doi=10.2307/2318556 | jstor=2318556 }}
• {{cite book |first1=John G. |last1=Kemeny |first2=J. Laurie |last2=Snell |first3=Gerald |last3=Thompson |title=Introduction to Finite Mathematics |edition=First |year=1957 |ref=none}}
• {{cite journal |first=E. H. |last=McKinney |year=1966 |title=Generalized Birthday Problem |journal=American Mathematical Monthly |volume=73 |issue= 5|pages=385–387 |doi= 10.2307/2315408|jstor=2315408|ref=none }}
• {{cite journal |first=F.|last=Mosteller |title=Understanding the Birthday Problem |year=1962 |journal=The Mathematics Teacher |volume=55 |issue= 5|pages=322–325|doi=10.5951/MT.55.5.0322 |jstor=27956609}} Reprinted in {{cite book|title=Selected Papers of Frederick Mosteller|chapter=Understanding the Birthday Problem |series=Springer Series in Statistics|isbn=978-0-387-20271-6 |doi= 10.1007/978-0-387-44956-2_21|pages=349–353|year=2006 |last1=Mosteller |first1=Frederick }}
• {{cite book |author1-link=Leila Schneps |first1=Leila |last1=Schneps |author2-link=Coralie Colmez |first2=Coralie |last2=Colmez |title=Math on Trial. How Numbers Get Used and Abused in the Courtroom |publisher=Basic Books |year=2013 |isbn=978-0-465-03292-1 |chapter=Math error number 5. The case of Diana Sylvester: cold hit analysis |ref=none|title-link=Math on Trial}}
• {{cite book|author=Sy M. Blinder|title=Guide to Essential Math: A Review for Physics, Chemistry and Engineering Students|url=https://books.google.com/books?id=M7TCNAEACAAJ|year=2013|publisher=Elsevier|isbn=978-0-12-407163-6|pages=5–6|ref=none}}

• [http://www.efgh.com/math/birthday.htm The Birthday Paradox accounting for leap year birthdays]
• {{MathWorld | urlname=BirthdayProblem | title=Birthday Problem|ref=none}}
• [http://www.damninteresting.com/?p=402 A humorous article explaining the paradox]
• [http://wiki.stat.ucla.edu/socr/index.php/SOCR_EduMaterials_Activities_BirthdayExperiment SOCR EduMaterials activities birthday experiment]
• [http://betterexplained.com/articles/understanding-the-birthday-paradox/ Understanding the Birthday Problem (Better Explained)]
• [http://www.matifutbol.com/en/eurobirthdays.html Eurobirthdays 2012. A birthday problem.] A practical football example of the birthday paradox.
• {{cite web|last=Grime|first=James|title=23: Birthday Probability|url=http://www.numberphile.com/videos/23birthday.html|work=Numberphile|publisher=Brady Haran|access-date=2013-04-02|archive-url=https://web.archive.org/web/20170225140726/http://www.numberphile.com/videos/23birthday.html|archive-date=2017-02-25|url-status=dead|ref=none}}
• [https://www.wolframalpha.com/input/?i=birthday+paradox%2C+4+people%2C+100+possible+birthdays Computing the probabilities of the Birthday Problem at WolframAlpha]

{{Portal bar|Mathematics}}

{{DEFAULTSORT:Birthday Problem}}

Category:Probability theory paradoxes

Category:Probability problems

Category:Applied probability

Category:Birthdays

Category:Mathematical problems

Category:Coincidence