Editing Birthday problem (section)

{{Short description|Probability of shared birthdays}}
{{for-multi|yearly variation in mortality rates|Birthday effect|the mathematical brain teaser that was asked in the Math Olympiad|Cheryl's Birthday}}

[[Image:Birthday Paradox.svg|thumb|upright=1.3|The computed probability of at least two people sharing the same birthday versus the number of people]]

In [[probability theory]], the '''birthday problem''' asks for the probability that, in a set of {{mvar|n}} [[random]]ly 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, 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 {{sfrac|23&nbsp;×&nbsp;22|2}}&nbsp;=&nbsp;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 attack|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".<ref>[[David Singmaster]], ''Sources in Recreational Mathematics: An Annotated Bibliography'', Eighth Preliminary Edition, 2004, [https://www.puzzlemuseum.com/singma/singma6/SOURCES/singma-sources-edn8-2004-03-19.htm#_Toc69534221 section 8.B]</ref><ref>[[H.S.M. Coxeter]], "Mathematical Recreations and Essays, 11th edition", 1940, p 45, as reported in [[I. J. Good]], ''Probability and the weighing of evidence'', 1950, [https://archive.org/details/probabilityweigh0000good/page/38/mode/2up?q=same%20birthday p. 38]</ref> The first publication of a version of the birthday problem was by [[Richard von Mises]] in 1939.<ref>Richard Von Mises, "Über Aufteilungs- und Besetzungswahrscheinlichkeiten", ''Revue de la faculté des sciences de l'Université d'Istanbul'' '''4''':145-163, 1939, reprinted in {{cite book |editor-first1 = P. |editor-last1 = Frank |editor-first2 = S. |editor-last2 = Goldstein |editor-first3 = M. |editor-last3 = Kac |editor-first4 = W. |editor-last4 = Prager |editor-first5 = G. |editor-last5 = Szegö |editor-first6 = G. |editor-last6 = Birkhoff |title = Selected Papers of Richard von Mises |volume = 2 | pages = 313–334 |date=1964 |publisher = Amer. Math. Soc. |location=Providence, Rhode Island}}</ref>