Birthday problem
73242
224424233
2008-07-08T19:59:03Z
Pimlottc
984771
/* Generalization to multiple types */ more resilient link
In [[probability theory]], the '''birthday problem''', or '''birthday [[paradox]]''',<ref>This is not a [[paradox]] in the sense of leading to a [[logic]]al contradiction, but is called a paradox because the mathematical truth contradicts naïve [[intuition (knowledge)|intuition]]: most people estimate that the chance is much lower than 50%.</ref> pertains to the [[probability]] that in a set of [[random]]ly chosen people some pair of them will have the same [[birthday]]. In a group of 23 (or more) randomly chosen people, there is more than 50% probability that some pair of them will have the same birthday. For 57 or more people, the probability is more than 99%, tending toward 100% as the pool of people grows.<ref> Note that birthdays are not evenly distributed throughout the year; not only does February 29 occur less than a quarter as often as any other day, but birth rates vary for the other 365 days.</ref> The mathematics behind this problem leads to a well-known cryptographic attack called the [[birthday attack]].
[[Image:Birthday_paradox.png|thumb|right|450px|A graph showing the probability of at least two people sharing a birthday amongst a certain number of people.]]
'''
== Understanding the problem ==
The birthday problem asks whether ''any'' of the 23 people have a matching birthday with ''any'' of the others — not one in particular. (See "[[#Same birthday as you|Same birthday as you]]" below for an analysis of this much less surprising alternative problem.)
In a list of 23 people, if you compare the birthday of the first person on the list to the others, you have 22 chances of success, but if you compare each to the others, you have 253 chances. This is because in a group of 23 people there are 23*22/2=253 pairs, which is more than half of the number of days in the year. So the chance that one of these pairs has a matching birthday is not small. For this reason (along with many others) we have the Birthday Paradox.
It is easier to figure the probability that the birthdays will be different, such as: with one person they have 365 opportunities to have a different birthday. The second person only has 364 possibilities to have a different birthday than the first person. The third person has 363 days, and so on. Thus when the group reaches 366 a clash is inevitable - all the days will have been used up, save for leap years.
== Calculating the probability ==
To compute the approximate probability that in a room of ''n'' people, at least two have the same birthday, we disregard variations in the distribution, such as [[leap year]]s, [[twin]]s, seasonal or weekday variations, and assume that the 365 possible birthdays are equally likely. Real-life birthday distributions are not uniform since not all dates are equally likely.<ref>In particular, many children are born in the summer, especially the months of August and September (for the northern hemisphere) [http://scienceworld.wolfram.com/astronomy/LeapDay.html], and in the U.S. it has been noted that many children are conceived around the holidays of [[Christmas]] and [[New Year's Day]]; and, in environments like classrooms where many people share a birth year, it becomes relevant that due to the way hospitals work, where C-sections and induced labor are not generally scheduled on the weekend, more children are born on Mondays and Tuesdays than on weekends. Both of these factors tend to increase the chance of identical birth dates, since a denser subset has more possible pairs (in the extreme case when everyone was born on three days, there would obviously be many identical birthdays). The birthday problem for such non-constant birthday probabilities was tackled by [[Murray Klamkin]] in 1967. A formal proof that the probability of two matching birthdays is least for a uniform distribution of birthdays was given by D. Bloom (1973)</ref>
It is easier to first calculate the probability ''<u style="text-decoration:overline">p</u>''(''n'') that all ''n'' birthdays are ''different''. If ''n'' > 365, by the [[pigeonhole principle]] this probability is 0. On the other hand, if ''n'' ≤ 365, it is
:<math>\bar p(n) = 1 \times \left(1-\frac{1}{365}\right) \times \left(1-\frac{2}{365}\right) \cdots \left(1-\frac{n-1}{365}\right) = { 365 \times 364 \cdots (365-n+1) \over 365^n } = { 365! \over 365^n (365-n)!}</math>
because the second person cannot have the same birthday as the first (364/365), the third cannot have the same birthday as the first two (363/365), etc.
The [[event (probability theory)|event]] of at least two of the ''n'' persons having the same birthday is [[complementary event|complementary]] to all ''n'' birthdays being different. Therefore, its probability ''p''(''n'') is
:<math> p(n) = 1 - \bar p(n) .</math>
This probability surpasses 1/2 for ''n'' = 23 (with value about 50.7%). The following table shows the probability for some other values of ''n'' (This table ignores the existence of leap years, as described above):
{| class="wikitable"
!''n''!!''p''(''n'')
|-
|10 || 11.7%
|-
|20 || 41.1%
|-
|23 || 50.7%
|-
|30 || 70.6%
|-
|50 || 97.0%
|-
|57 || 99.0%
|-
|100 || 99.99996%
|-
|200 || 99.9999999999999999999999999998%
|-
|300 || (100 − (6×10<sup>−80</sup>))%
|-
|350 || (100 − (3×10<sup>−129</sup>))%
|-
|366 || 100%
|}
== Approximations ==
The [[Taylor series]] expansion of the [[exponential function]]
:<math> e^x = 1 + x + \frac{x^2}{2!}+\cdots </math>
[[Image:050329-birthday2.png|thumb|right|290px|A graph showing the accuracy of the approximation <math>1-e^{-n^2/{2 \cdot 365}}</math>]]
provides a first-order approximation for <math>e^x</math>:
:<math> e^x \approx 1 + x </math>
The first expression derived for ''<u style="text-decoration:overline">p</u>''(''n'') can be approximated as
:<math>\bar p(n) \approx 1 \times e^{-1/365} \times e^{-2/365} \cdots e^{-(n-1)/365} </math>
::<math>= 1 \times e^{-(1+2+ \cdots +(n-1))/365}</math>
::<math>= e^{(-(n(n-1))/2) / 365}</math>
Therefore,
:<math> p(n) = 1-\bar p(n) \approx 1 - e^{- \frac{(n(n-1))}{2 \times 365}}</math>
An even coarser approximation is given by
:<math>p(n)\approx 1-e^{- \frac{n^2}{2 \times 365}},\,</math>
which, as the graph illustrates, is still fairly accurate.
=== A simple exponentiation ===
Very basically, the probability of any two people not having the same birthday is 364/365. In a room of people of size ''N'', there are ''C''(''N'', 2) pairs of people, i.e. ''C''(''N'', 2) events. We can approximate the probability of no two people sharing the same birthday by assuming that these events are independent and hence by multiplying their probability together. In short we multiply 364/365 by itself ''C''(''N'', 2) times, which gives us
:<math>\left(\frac{364}{365}\right)^{C(N,2)}</math>
And obviously if this is the probability of no one having the same birthday, then the probability of someone sharing a birthday is
:<math>p(n)\approx 1 - \left(\frac{364}{365}\right)^{C(N,2)}.</math>
=== Poisson approximation ===
Using the [[Poisson distribution|Poisson]] approximation for the binomial,
:<math>\mathrm{Poi}\left(\frac{C(23, 2)}{365}\right) \approx \mathrm{Poi}\left(\frac{253}{365}\right) \approx \mathrm{Poi}(0.6932)</math>
:<math>\Pr(X>0)=1-\Pr(X=0)=1-e^{-0.6932}=1-0.499998=0.500002.</math>
Again, this is over 50%.
=== Approximation of number of people ===
We can also approximate this using the following formula for the ''number'' of people necessary to have at least a 50% chance of matching:
:<math>N = \frac{1}{2} + \sqrt{\frac{1}{4} - 2 \times 365 \times \ln(0.5)} \approx 22.9999</math>
This is a result of the good approximation that an event with 1 in ''k'' probability will have a 50% chance of occurring at least once if it is repeated ''k'' ln 2 times.<ref>{{cite journal
| quotes =
| last = Mathis
| first = Frank H.
| authorlink =
| coauthors =
| date =
| year = 1991
| month = June
| title = A Generalized Birthday Problem
| journal = SIAM Review
| volume = 33
| issue = 2
| pages = 265-270
| publisher = [[Society for Industrial and Applied Mathematics]]
| location =
| issn = 00361445
| pmid =
| pmc =
| doi =
| bibcode =
| oclc = 37699182
| id =
| url = http://www.jstor.org/stable/2031144
| language =
| format =
| accessdate = 2008-07-08
| laysummary =
| laysource =
| laydate =
| quote =
}}</ref>
==An upper bound and a different perspective==
The argument below is adapted from an argument of [[Paul Halmos]].<ref>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:
<blockquote>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 [[calculator]]s do not yield is understanding, or mathematical facility, or a solid basis for more advanced, generalized theories.</blockquote></ref>
As stated above, the probability that no two birthdays coincide is
:<math>1-p(n) = \bar p(n) = \prod_{k=1}^{n-1}\left(1-{k \over 365}\right) .</math>
This can be seen by first counting the number of ways 365 birthdays can be distributed among ''n'' people in such a way that no two birthdays are the same, then dividing by the total number of ways 365 birthdays can be distributed among ''n'' people:
:<math>\bar p(n) = \dfrac{365\cdot364\cdots(365-n+1)}{365^n}.</math>
We are interested in the smallest ''n'' such that ''p''(''n'') > 1/2; or equivalently, the smallest ''n'' such that ''<u style="text-decoration:overline">p</u>''(''n'') < 1/2.
Replacing 1 − ''k''/365, as above, with ''e''<sup>−''k''/365</sup>, and using the inequality 1 − ''x'' < ''e''<sup>−''x''</sup>, we have
:<math>\bar p(n) = \prod_{k=1}^{n-1}\left(1-{k \over 365}\right) < \prod_{k=1}^{n-1}\left(e^{-k/365}\right) = e^{-(n(n-1))/(2\times 365)} .</math>
Therefore, the expression above is not only an approximation, but also an [[upper bound]] of ''<u style="text-decoration:overline">p</u>''(''n''). The inequality
:<math> e^{-(n(n-1))/(2\cdot 365)} < \frac{1}{2}</math>
implies ''<u style="text-decoration:overline">p</u>''(''n'') < 1/2. Solving for ''n'' we find
:<math>n^2-n > 2\times365\ln 2 \,\! .</math>
Now, 730 ln 2 is approximately 505.997, which is barely below 506, the value of ''n''² − ''n'' attained when ''n'' = 23. Therefore, 23 people suffice.
This derivation only shows that ''at most'' 23 people are needed to ensure a birthday match with even chance; it leaves open the possibility that, say, ''n'' = 22 could also work.
== Generalizations ==
==== Cast as a collision problem ====
The birthday problem can be generalized as follows: given ''n'' random integers drawn from a [[Uniform distribution (discrete)|discrete uniform distribution]] with range [1,''d''], what is the probability ''p''(''n'';''d'') that at least two numbers are the same?
The generic results can be derived using the same arguments given above.
:<math>p(n;d) = \begin{cases} 1-\prod_{k=1}^{n-1}\left(1-{k \over d}\right) & n\le d \\ 1 & n > d \end{cases}</math>
:<math>p(n;d) \approx 1 - e^{-(n(n-1))/2d}</math>
:<math>q(n;d) = 1 - \left( \frac{d-1}{d} \right)^n </math>
:<math>n(p;d)\approx \sqrt{2d\ln\left({1 \over 1-p}\right)}</math>
The birthday problem in this more generic sense applies to [[hash function]]s: the expected number of ''N''-[[bit]] hashes that can be generated before getting a collision is not 2<sup>''N''</sup>, but rather only 2<sup>''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.
==== Generalization to multiple types ====
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>M. C. Wendl (2003) ''[http://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 just two types, 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, say two women do not count.) The probability of ''no'' (i.e. zero) 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 we set <math>d = 365</math> and where <math>S_2</math> are [[Stirling number|Stirling numbers of the second kind]]. Consequently, the desired probability is <math>1 - p_0</math>.
This variation of the birthday problem is interesting because there is not a unique solution for the total number of people <math>m + n</math>. For example, the usual 0.5 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.
== Other birthday problems ==
=== Reverse problem ===
For a fixed probability ''p'':
* Find the greatest ''n'' for which the probability ''p''(''n'') is smaller than the given ''p'', or
* Find the smallest ''n'' for which the probability ''p''(''n'') is greater than the given ''p''.
An approximation to this can be derived by inverting the 'coarser' approximation above:
:<math>n(p)\approx \sqrt{2\times 365\ln\left({1 \over 1-p}\right)}.</math>
==== Sample calculations ====
{| class="wikitable"
|-----
| ''p'' || ''n''
| ''n''↓ || ''p''(''n''↓) || ''n''↑ || ''p''(''n''↑)
|-----
| <span style="color:magenta">0.01</span>
| 0.14178√365 = <span style="color:magenta">2.70864</span>
| align="right" | 2 || 0.00274 || align="right" | 3
| <span style="color:magenta">0.00820</span>
|-----
| 0.05 || 0.32029√365 = 6.11916
| align="right" | 6 || 0.04046 || align="right" | 7 || 0.05624
|-----
| <span style="color:magenta">0.1</span>
| 0.45904√365 = <span style="color:magenta"> 8.77002</span>
| align="right" | 8 || 0.07434 || align="right" | 9
| <span style="color:magenta">0.09462</span>
|-----
| <span style="color:magenta">0.2</span>
| 0.66805√365 = <span style="color:magenta">12.76302</span>
| align="right" | 12 || 0.16702 || align="right" | 13
| <span style="color:magenta">0.19441</span>
|-----
| 0.3 || 0.84460√365 = 16.13607
| align="right" | 16 || 0.28360 || align="right" | 17 || 0.31501
|-----
| 0.5 || 1.17741√365 = 22.49439
| align="right" | 22 || 0.47570 || align="right" | 23 || 0.50730
|-----
| 0.7 || 1.55176√365 = 29.64625
| align="right" | 29 || 0.68097 || align="right" | 30 || 0.70632
|-----
| 0.8 || 1.79412√365 = 34.27666
| align="right" | 34 || 0.79532 || align="right" | 35 || 0.81438
|-----
| 0.9 || 2.14597√365 = 40.99862
| align="right" | 40 || 0.89123 || align="right" | 41 || 0.90315
|-----
| 0.95 || 2.44775√365 = 46.76414
| align="right" | 46 || 0.94825 || align="right" | 47 || 0.95477
|-----
| <span style="color:magenta">0.99</span>
| 3.03485√365 = <span style="color:magenta">57.98081</span>
| align="right" | 57
| <span style="color:magenta">0.99012</span>
| align="right" | 58 || 0.99166
|}
Note: some values falling outside the bounds have been <span style="color:magenta">colored</span> to show that the approximation is '''not''' always exact.
=== First match ===
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's a prize for first match, the best position in line is 20th.
=== Same birthday as you ===
[[Image:Birthday paradox.svg|thumb|right|290px|Comparing ''p''(''n'') = probability of a birthday match with ''q''(''n'') = probability of matching ''your'' birthday]]
Note that in the birthday problem, neither of the two people is chosen in advance. By way of 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
: <math> q(n) = 1 - \left( \frac{365-1}{365} \right)^n </math>
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.<!-- Caution! Think twice before changing it to 23 ;-) --> Note that 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.
=== Near matches ===
Another generalization is to ask how many people are needed in order to have a better than 50% chance that two people have a birthday within one day of each other, or within two, three, etc., days of each other. This is a more difficult problem and requires use of the [[inclusion-exclusion principle]]. The number of people required so that the probability that some pair will have a birthday separated by fewer than <math>k</math> days will be higher than 50% is:
{| class="wikitable" style="text-align: center"
! k !! # people required
|-
|1 || 23
|-
|2 || 14
|-
|3 || 11
|-
|4 || 9
|-
|5 || 8
|-
|6 || 8
|-
|7 || 7
|-
|8 || 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.<ref name="abramson">M. Abramson and W. O. J. Moser (1970) ''More Birthday Surprises'', [[American Mathematical Monthly]] '''77''', 856-858</ref>
=== Collision counting ===
The probability that the ''k''th integer randomly chosen from [1, ''d''] will repeat at least one previous choice equals <math>q(k-1;d)</math> above. The expected total number of times a selection will repeat a previous selection as ''n'' such integers are chosen equals
:<math>\sum_{k=1}^n q(k-1;d) = n - d + d \left (\frac {d-1} {d} \right )^n.</math>
=== Average number of people ===
In an alternative formulation of the birthday problem, one asks the ''average'' number of people required to find a pair with the same birthday. The problem is relevant to several [[hash function|hashing algorithms]] analyzed by [[Donald Knuth]] in his monumental book ''[[The Art of Computer Programming]]''. It may be shown <ref name="knuth73">D. E. Knuth; ''[[The Art of Computer Programming]]. Vol. 3, Sorting and Searching'' (Addison-Wesley, Reading, Massachusetts, 1973)</ref>, <ref name="flajolet95">P. Flajolet, P. J. Grabner, P. Kirschenhofer, H. Prodinger (1995), ''On Ramanujan's Q-Function'', Journal of Computational and Applied Mathematics '''58''', 103-116</ref> that if one samples uniformly, with replacement, from a population of size <math>M</math>, the number of trials required for the first repeated sampling of ''some'' individual has [[expectation value]] <math>\overline{n}=1+Q(M)</math>, where <math>Q(M)=\sum_{k=1}^{M} \frac{M!}{(M-k)! M^k}</math>.
The function <math>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}}</math> has been studied by [[Srinivasa Ramanujan]] and has [[asymptotic expansion]]:
<math>Q(M)\sim\sqrt{\frac{\pi M}{2}}-\frac{1}{3}+\frac{1}{12}\sqrt{\frac{\pi}{2n}}-\frac{4}{135n}+\cdots.</math>
With <math>M=365</math> days in a year, the average number of people required to find a pair with the same birthday is <math>\overline{n}=1+Q(M)\approx24.61658</math>, slightly more than the number required for a 50% chance. In the best case, two people will suffice; at worst, the maximum possible number of <math>M+1=366</math> people is needed; but on [[average]], only 25 people are required.
An ''informal'' demonstration of the problem can be made from the [[List of Prime Ministers of Australia]], in which [[Paul Keating]], the 24th Prime Minister, is the first to share a birthday with another on the list.
== Partition problem ==
A related problem is the [[partition problem]], a variant of the [[knapsack problem]] from computer science. Some weights are put on a balance; each weight is an integer number of grams randomly chosen between one gram and one million grams (one metric ton). The question is whether you 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. 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 impossible?
Some people's intuition is that the answer is above 100,000. 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 approximately 23.
The reason is that the correct comparison is to the number of partitions of the weights into left and right. There are 2<sup>''N''−1</sup> different partitions for ''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 [[normal distribution|Gaussian]], with a peak at 1,000,000 ''N'' and width <math>\scriptstyle 1,000,000\sqrt{N}</math>, so that when 2<sup>''N''−1</sup> is approximately equal to <math>\scriptstyle 1,000,000\sqrt{N}</math> the transition occurs. 2<sup>23−1</sup> is about 4 million, while the width of the distribution is only 5 million<ref>C. Borgs, J. Chayes, and B. Pittel (2001) ''Phase Transition and Finite Size Scaling in the Integer Partition Problem'', Random Structures and Algorithms '''19'''(3-4), 247-288.</ref>.
== Notes ==
<references/>
==References==
*E. H. McKinney (1966) ''Generalized Birthday Problem'', [[American Mathematical Monthly]] '''73''', 385-387.
*M. Klamkin and D. Newman (1967) ''Extensions of the Birthday Surprise'', Journal of Combinatorial Theory '''3''', 279-282.
*M. Abramson and W. O. J. Moser (1970) ''More Birthday Surprises'', [[American Mathematical Monthly]] '''77''', 856-858
*D. Bloom (1973) ''A Birthday Problem'', [[American Mathematical Monthly]] '''80''', 1141-1142.
*[[Clay Shirky|Shirky, Clay]] ''Here Comes Everybody: The Power of Organizing Without Organizations'', (2008.) New York. 25-27.
==External links==
* http://www.efgh.com/math/birthday.htm
* http://planetmath.org/encyclopedia/BirthdayProblem.html
* {{MathWorld | urlname=BirthdayProblem | title=Birthday Problem}}
* [http://www.nestel.net/maple/bd/bd.html Maple vs. birthday paradox]
* [http://www.damninteresting.com/?p=402 A humorous article explaining the paradox]
* [http://www.excelexchange.com/Birthday%20Problem.xls The Birthday Problem Spreadsheet]
* [http://wiki.stat.ucla.edu/socr/index.php/SOCR_EduMaterials_Activities_BirthdayExperiment SOCR EduMaterials Activities BirthdayExperiment]
[[Category:Probability theory paradoxes]]
[[Category:Probability theory]]
[[Category:Applied probability]]
[[Category:Birthdays]]
[[cs:Narozeninový problém]]
[[de:Geburtstagsparadoxon]]
[[es:Paradoja del cumpleaños]]
[[fr:Paradoxe des anniversaires]]
[[gl:Paradoxo do aniversario]]
[[ko:생일 문제]]
[[it:Paradosso del compleanno]]
[[he:פרדוקס יום ההולדת]]
[[lt:Gimimo dienų paradoksas]]
[[hu:Születésnap-paradoxon]]
[[nl:Verjaardagenparadox]]
[[ja:誕生日のパラドックス]]
[[pl:Paradoks dnia urodzin]]
[[pt:Paradoxo do aniversário]]
[[ru:Парадокс дней рождения]]
[[fi:Syntymäpäiväongelma]]
[[sv:Födelsedagsparadoxen]]
[[zh:生日悖论]]