Editing Birthday problem (section)

==Generalizations==

===Arbitrary number of days===
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

:<math>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}.</math>

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}}:

:{| class="wikitable" style="text-align:center;"
|-
! scope="row" | {{mvar|d}}
| 1–2 || 3–5 || 6–9 || 10–16 || 17–23 || 24–32 || 33–42 || 43–54 || 55–68 || 69–82 || 83–99
|-
! scope="row" | {{math|''n''(''d'')}}
| 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12
|}

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.<ref>{{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].}}</ref>
For any {{math|''d'' ≥ 1}}, the number {{math|''n''(''d'')}} satisfies<ref>{{Harvard citations|author=Brink|year=2012|nb=yes|loc=Theorem 2}}</ref>

:<math>\frac{3-2\ln2}{6}<n(d)-\sqrt{2d\ln2}\leq 9-\sqrt{86\ln2}.</math>

These bounds are optimal in the sense that the sequence {{math|''n''(''d'') − {{sqrt|2''d'' ln 2}}}}
gets arbitrarily close to
:<math>\frac{3-2\ln2}{6} \approx 0.27,</math>
while it has
:<math>9-\sqrt{86\ln2}\approx 1.28</math>
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
:<math>\left\lceil\sqrt{2d\ln2}\,\right\rceil \quad\text{or}\quad \left\lceil\sqrt{2d\ln2}\,\right\rceil+1</math>
where {{math|⌈ · ⌉}} denotes the [[Floor and ceiling functions|ceiling function]].
The formula

:<math>n(d) = \left\lceil\sqrt{2d\ln2}\,\right\rceil</math>

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

:<math>n(d) = \left\lceil\sqrt{2d\ln2}+\frac{3-2\ln2}{6}\right\rceil</math>

holds for [[almost all]] {{mvar|d}}, i.e., for a set of integers {{mvar|d}} with [[asymptotic density]] 1.<ref name=Brink/>

The formula

:<math>n(d)=\left\lceil \sqrt{2d\ln2}+\frac{3-2\ln2}{6}+\frac{9-4(\ln2)^2}{72\sqrt{2d\ln2}}\right\rceil</math>

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

The formula

:<math>n(d)=\left\lceil \sqrt{2d\ln2}+\frac{3-2\ln2}{6}+\frac{9-4(\ln2)^2}{72\sqrt{2d\ln2}}-\frac{2(\ln2)^2}{135d}\right\rceil</math>

holds for all {{math|''d'' ≤ {{val|e=18}}}}, and it is conjectured that this formula holds for all {{mvar|d}}.<ref name="ReferenceA"/>

===More than two people sharing a birthday===
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}}.<ref>{{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}}</ref>

===Everyone shares a birthday===
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.<ref>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.</ref><ref>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</ref>

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

===Probability of a shared birthday (collision)===
The birthday problem can be generalized as follows:
:Given {{mvar|n}} random integers drawn from a [[Uniform distribution (discrete)|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.)<ref>{{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}}</ref>

The generic results can be derived using the same arguments given above.
:<math>\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}</math>

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
:<math>n(p;d)\approx \sqrt{2d \cdot \ln\left(\frac{1}{1-p}\right)}.</math>

The birthday problem in this more generic sense applies to [[hash function]]s: the expected number of {{math|''N''}}-[[bit]] hashes that can be generated before getting a collision is not {{math|2<sup>''N''</sup>}}, but rather only {{math|2<sup>{{frac|''N''|2}}</sup>}}. This is exploited by [[birthday attack]]s on [[cryptographic hash function]]s 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<ref>Z. E. Schnabel (1938) ''The Estimation of the Total Fish Population of a Lake'', [[American Mathematical Monthly]] '''45''', 348–352.</ref> under the name of [[mark and recapture|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.<ref name="Pollanen">M. Pollanen (2024) ''A Double Birthday Paradox in the Study of Coincidences'', [[Mathematics]] '''23'''(24), 3882. https://doi.org/10.3390/math12243882</ref>

====Probability of a unique collision====

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<ref name="Pollanen"/>

: <math> p_2(n; d) =   \frac{{n \choose 2}}{d-n+1} (1-p(n; d)) </math>

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

====Generalization to multiple types of people====
[[File:2d birthday.png|thumb|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.<ref>[[Michael Christopher Wendl|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.</ref> 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

:<math>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</math>

where {{math|''d'' {{=}} 365}} and {{math|''S''<sub>2</sub>}} are [[Stirling numbers of the second kind]]. Consequently, the desired probability is {{math|1 − ''p''<sub>0</sub>}}.

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.