Английская Википедия:Birthday problem
Шаблон:Short description Шаблон:For multi
In probability theory, the birthday problem asks for the probability that, in a set of Шаблон:Mvar randomly chosen people, at least two will share a birthday. The birthday paradox refers to 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 = 253 pairs to consider, far more than half the number of days in a year.
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 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".[1][2] The first publication of a version of the birthday problem was by Richard von Mises in 1939.[3]
Calculating the probability
From a permutations perspective, let the event Шаблон:Math be the probability of finding a group of 23 people without any repeated birthdays. Where the event Шаблон:Math is the probability of finding a group of 23 people with at least two people sharing same birthday, Шаблон:Math. Шаблон:Math is the ratio of the total number of birthdays, <math>V_{nr}</math>, without repetitions and order matters (e.g. for a group of 2 people, mm/dd birthday format, one possible outcome is <math>\left \{ \left \{01/02,05/20\right \},\left \{05/20,01/02\right \},\left \{10/02,08/04\right\},...\right \}</math>) divided by the total number of birthdays with repetition and order matters, <math>V_{t}</math>, as it is the total space of outcomes from the experiment (e.g. 2 people, one possible outcome is <math>\left \{ \left \{01/02,01/02\right \},\left \{10/02,08/04\right \},...\right \}</math>). Therefore <math>V_{nr}</math> and <math>V_{t}</math> are permutations.
- <math>\begin{align} V_{nr} &= \frac{n!}{(n-k)!} = \frac{365!}{(365-23)!} \\[8pt] V_t &= n^k = 365^{23} \\[8pt] P(A) &= \frac{V_{nr}}{V_t} \approx 0.492703 \\[8pt] P(B) &= 1 - P(A) \approx 1 - 0.492703 \approx 0.507297 \quad (50.7297\%)\end{align}</math>
Another way the birthday problem can be solved is by asking for an approximate probability that in a group of Шаблон:Mvar people at least two have the same birthday. For simplicity, leap years, twins, selection bias, and seasonal and weekly variations in birth ratesШаблон:Refn 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, the uniform distribution on birthdays is the distribution that minimizes the probability of two people with the same birthday; any unevenness increases this probability.[4][5] The problem of a non-uniform number of births occurring during each day of the year was first addressed by Murray Klamkin in 1967.Шаблон:SfnШаблон:Fv As it happens, the real-world distribution yields a critical size of 23 to reach 50%.[6]
The goal is to compute Шаблон:Math, the probability that at least two people in the room have the same birthday. However, it is simpler to calculate Шаблон:Math, the probability that no two people in the room have the same birthday. Then, because Шаблон:Math and Шаблон:Math are the only two possibilities and are also mutually exclusive, Шаблон:Math
Here is the calculation of Шаблон:Math 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, 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, 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. Finally, the principle of conditional probability implies that Шаблон:Math is equal to the product of these individual probabilities: Шаблон:NumBlk
The terms of equation (Шаблон:EquationNote) can be collected to arrive at: Шаблон:NumBlk
Evaluating equation (Шаблон:EquationNote) gives Шаблон:Math
Therefore, Шаблон:Math (50.7297%).
This process can be generalized to a group of Шаблон:Mvar people, where Шаблон:Math is the probability of at least two of the Шаблон:Mvar people sharing a birthday. It is easier to first calculate the probability Шаблон:Math that all Шаблон:Mvar birthdays are different. According to the pigeonhole principle, Шаблон:Math is zero when Шаблон:Math. When Шаблон:Math:
- <math> \begin{align} \bar p(n) &= 1 \times \left(1-\frac{1}{365}\right) \times \left(1-\frac{2}{365}\right) \times \cdots \times \left(1-\frac{n-1}{365}\right) \\[6pt] &= \frac{ 365 \times 364 \times \cdots \times (365-n+1) }{ 365^n } \\[6pt] &= \frac{ 365! }{ 365^n (365-n)!} = \frac{n!\cdot\binom{365}{n}}{365^n} = \frac{_{365}P_n}{365^n}\end{align} </math>
where Шаблон:Math is the factorial operator, Шаблон:Math is the binomial coefficient and Шаблон:Math 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, the third cannot have the same birthday as either of the first two Шаблон:Math, and in general the Шаблон:Mvarth birthday cannot be the same as any of the Шаблон:Math preceding birthdays.
The event of at least two of the Шаблон:Mvar persons having the same birthday is complementary to all Шаблон:Mvar birthdays being different. Therefore, its probability Шаблон:Math is
- <math> p(n) = 1 - \bar p(n). </math>
The following table shows the probability for some other values of Шаблон:Mvar (for this table, the existence of leap years is ignored, and each birthday is assumed to be equally likely):
Шаблон:Mvar Шаблон:Math 1 Шаблон:00.0% 5 Шаблон:02.7% 10 11.7% 20 41.1% 23 50.7% 30 70.6% 40 89.1% 50 97.0% 60 99.4% 70 99.9% 75 99.97% 100 Шаблон:Val% 200 Шаблон:Val% 300 (100 − Шаблон:Val)% 350 (100 − Шаблон:Val)% 365 (100 − Шаблон:Val)% ≥ 366 100%
Approximations
The Taylor series expansion of the exponential function (the constant Шаблон:Math)
- <math> e^x = 1 + x + \frac{x^2}{2!}+\cdots </math>
provides a first-order approximation for Шаблон:Math for <math>|x| \ll 1</math>:
- <math> e^x \approx 1 + x.</math>
To apply this approximation to the first expression derived for Шаблон:Math, set Шаблон:Math. Thus,
- <math> e^{-a/365} \approx 1 - \frac{a}{365}. </math>
Then, replace Шаблон:Mvar with non-negative integers for each term in the formula of Шаблон:Math until Шаблон:Math, for example, when Шаблон:Math,
- <math> e^{-1/365} \approx 1 - \frac{1}{365}. </math>
The first expression derived for Шаблон:Math can be approximated as
- <math>
\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} </math>
Therefore,
- <math> p(n) = 1-\bar p(n) \approx 1 - e^{-\frac{n(n-1)}{730}}.</math>
An even coarser approximation is given by
- <math>p(n)\approx 1-e^{-\frac{n^2}{730}},</math>
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, if there are Шаблон:Mvar persons, and if Шаблон:Math, then using the same approach as above we achieve the result that if Шаблон:Math is the probability that at least two out of Шаблон:Mvar people share the same birthday from a set of Шаблон:Mvar available days, then:
- <math>\begin{align}
p(n, d) & \approx 1-e^{-\frac{n(n-1)}{2d}} \\[6pt]
& \approx 1-e^{-\frac{n^2}{2d}}. \end{align}</math>
Simple exponentiation
The probability of any two people not having the same birthday is Шаблон:Sfrac. In a room containing n people, there are Шаблон:Math pairs of people, i.e. Шаблон:Math 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 can be multiplied by itself Шаблон:Math times, which gives us
- <math>\bar p(n) \approx \left(\frac{364}{365}\right)^\binom{n}{2}.</math>
Since 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)^\binom{n}{2}.</math>
And for the group of 23 people, the probability of sharing is
- <math>p(23) \approx 1 - \left(\frac{364}{365}\right)^\binom{23}{2} = 1 - \left(\frac{364}{365}\right)^{253} \approx 0.500477 .</math>
Poisson approximation
Applying the Poisson approximation for the binomial on the group of 23 people,
- <math>\operatorname{Poi}\left(\frac{\binom{23}{2}}{365}\right) =\operatorname{Poi}\left(\frac{253}{365}\right) \approx \operatorname{Poi}(0.6932)</math>
so
- <math>\Pr(X>0)=1-\Pr(X=0) \approx 1-e^{-0.6932} \approx 1-0.499998=0.500002.</math>
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.
Square approximation
A good rule of thumb which can be used for mental calculation is the relation
- <math>p(n) \approx \frac{n^2}{2m}</math>
which can also be written as
- <math>n \approx \sqrt { 2m \times p(n)}</math>
which works well for probabilities less than or equal to Шаблон:Sfrac. In these equations, Шаблон:Mvar is the number of days in a year.
For instance, to estimate the number of people required for a Шаблон:Sfrac chance of a shared birthday, we get
- <math>n \approx \sqrt{ 2 \times 365 \times \tfrac12} = \sqrt{365} \approx 19</math>
Which is not too far from the correct answer of 23.
Approximation of number of people
This can also be approximated using the following formula for the number of people necessary to have at least a Шаблон:Sfrac chance of matching:
- <math>n \geq \tfrac{1}{2} + \sqrt{\tfrac{1}{4} + 2 \times \ln(2) \times 365} = 22.999943.</math>
This is a result of the good approximation that an event with Шаблон:Math probability will have a Шаблон:Sfrac chance of occurring at least once if it is repeated Шаблон:Math times.[7]
Probability table
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 to Шаблон:Val is the uncorrectable bit error rate of a typical hard disk.[8] In theory, 128-bit hash functions, such as MD5, should stay within that range until about Шаблон:Val documents, even if its possible outputs are many more.
An upper bound on the probability and a lower bound on the number of people
The argument below is adapted from an argument of Paul Halmos.Шаблон:Refn
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-\frac{k}{365}\right) .</math>
As in earlier paragraphs, interest lies in the smallest Шаблон:Mvar such that Шаблон:Math; or equivalently, the smallest Шаблон:Mvar such that Шаблон:Math.
Using the inequality Шаблон:Math in the above expression we replace Шаблон:Math with Шаблон:Math. This yields
- <math>\bar p(n) = \prod_{k=1}^{n-1}\left(1-\frac{k}{365}\right) < \prod_{k=1}^{n-1}\left(e^{-\frac{k}{365}}\right) = e^{-\frac{n(n-1)}{730}} .</math>
Therefore, the expression above is not only an approximation, but also an upper bound of Шаблон:Math. The inequality
- <math> e^{-\frac{n(n-1)}{730}} < \frac{1}{2}</math>
implies Шаблон:Math. Solving for Шаблон:Mvar gives
- <math>n^2-n > 730 \ln 2 .</math>
Now, Шаблон:Math is approximately 505.997, which is barely below 506, the value of Шаблон:Math attained when Шаблон:Math. Therefore, 23 people suffice. Incidentally, solving Шаблон:Math 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 a birthday match with even chance; it leaves open the possibility that Шаблон:Mvar is 22 or less could also work.
Generalizations
Arbitrary number of days
Given a year with Шаблон:Mvar days, the generalized birthday problem asks for the minimal number Шаблон:Math such that, in a set of Шаблон:Mvar randomly chosen people, the probability of a birthday coincidence is at least 50%. In other words, Шаблон:Math is the minimal integer Шаблон:Mvar 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. The first 99 values of Шаблон:Math are given here Шаблон:OEIS:
Шаблон:Mvar 1–2 3–5 6–9 10–16 17–23 24–32 33–42 43–54 55–68 69–82 83–99 Шаблон:Math 2 3 4 5 6 7 8 9 10 11 12
A similar calculation shows that Шаблон:Math = 23 when Шаблон:Mvar is in the range 341–372.
A number of bounds and formulas for Шаблон:Math have been published.[9] For any Шаблон:Math, the number Шаблон:Math satisfies[10]
- <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 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.
The bounds are sufficiently tight to give the exact value of Шаблон:Math in most of the cases. For example, for Шаблон:Math 365 these bounds imply that Шаблон:Math and 23 is the only integer in that range. In general, it follows from these bounds that Шаблон:Math 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 ceiling function. The formula
- <math>n(d) = \left\lceil\sqrt{2d\ln2}\,\right\rceil</math>
holds for 73% of all integers Шаблон:Mvar.[11] The formula
- <math>n(d) = \left\lceil\sqrt{2d\ln2}+\frac{3-2\ln2}{6}\right\rceil</math>
holds for almost all Шаблон:Mvar, i.e., for a set of integers Шаблон:Mvar with asymptotic density 1.[11]
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, but it is conjectured that there are infinitely many counterexamples to this formula.[12]
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, and it is conjectured that this formula holds for all Шаблон:Mvar.[12]
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.[13]
The birthday problem can be generalized as follows:
- Given Шаблон:Mvar random integers drawn from a discrete uniform distribution with range Шаблон:Math, what is the probability Шаблон:Math that at least two numbers are the same? (Шаблон:Math gives the usual birthday problem.)[14]
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 denotes the number of random integers drawn from Шаблон:Math to obtain a probability Шаблон:Mvar 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 functions: the expected number of Шаблон:Math-bit hashes that can be generated before getting a collision is not Шаблон:Math, but rather only Шаблон:Math. 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[15] under the name of capture-recapture statistics to estimate the size of fish population in lakes.
Generalization to multiple types of people
The basic problem considers all trials to be of one "type". The birthday problem has been generalized to consider an arbitrary number of types.[16] In the simplest extension there are two types of people, say Шаблон:Mvar men and Шаблон:Mvar 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 and Шаблон:Math are Stirling numbers of the second kind. Consequently, the desired probability is Шаблон:Math.
This variation of the birthday problem is interesting because there is not a unique solution for the total number of people Шаблон:Math. 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.
Other birthday problems
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 Шаблон:Mvar is Шаблон:Math maximum? The answer is 20—if there is a prize for first match, the best position in line is 20th.Шаблон:Citation needed
Same birthday as you
In the birthday problem, neither of the two people is chosen in advance. By contrast, the probability Шаблон:Math that someone in a room of Шаблон:Mvar 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>
and for general Шаблон:Mvar by
- <math> q(n;d) = 1 - \left( \frac{d-1}{d} \right)^n. </math>
In the standard case of Шаблон:Math, substituting Шаблон:Math 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 Шаблон:Mvar people has the same birthday as you, Шаблон:Mvar would need to be at least 253. This number is significantly higher than Шаблон:Math: 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 <math> q(n-1;d) </math>, 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:
- <math> n\left(1 - \left( \frac{d-1}{d} \right)^{n-1}\right) </math>
(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:
- <math> n \left( \frac{d-1}{d} \right)^{n-1} </math>
Similar formulas can be derived for the expected number of people who share with three, four, etc. other people.
Number of people until every birthday is achieved
The expected number of people needed until every birthday is achieved is called the Coupon collector's problem. It can be calculated by Шаблон:Math, where Шаблон:Math is the Шаблон:Mvarth harmonic number. For 365 possible dates (the birthday problem), the answer is 2365.
Near matches
Another generalization is to ask for the probability of finding at least one pair in a group of Шаблон:Mvar people with birthdays within Шаблон:Mvar calendar days of each other, if there are Шаблон:Mvar equally likely birthdays.[17]
- <math> \begin{align} p(n,k,d) &= 1 - \frac{ (d - nk -1)! }{ d^{n-1} \bigl(d - n(k+1)\bigr)!}\end{align} </math>
The number of people required so that the probability that some pair will have a birthday separated by Шаблон:Mvar days or fewer will be higher than 50% is given in the following table:
Шаблон:Mvar Шаблон:Mvar
for Шаблон:Math0 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.[17]
Number of days with a certain number of birthdays
Number of days with at least one birthday
The expected number of different birthdays, i.e. the number of days that are at least one person's birthday, is:
- <math>d - d \left (\frac {d-1} {d} \right )^n </math>
This follows from the expected number of days that are no one's birthday:
- <math>d \left (\frac {d-1} {d} \right )^n </math>
which follows from the probability that a particular day is no one's birthday, Шаблон:Math, easily summed because of the linearity of the expected value.
For instance, with Шаблон:Math, 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).
Number of days with at least two 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. Multiplying the relevant probability by Шаблон:Mvar 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:
<math display="block">d - d \left (\frac {d-1} {d} \right )^n - d \cdot \binom{n}{1} \left (\frac {1} {d} \right )^1\left (\frac {d-1} {d} \right )^{n-1} = d - d \left (\frac {d-1} {d} \right )^n - n \left (\frac {d-1} {d} \right )^{n-1} </math>
Number of people who repeat a birthday
The probability that the Шаблон:Mvarth integer randomly chosen from Шаблон:Math will repeat at least one previous choice equals Шаблон:Math above. The expected total number of times a selection will repeat a previous selection as Шаблон:Mvar such integers are chosen equals[18]
- <math>\sum_{k=1}^n q(k-1;d) = n - d + d \left (\frac {d-1} {d} \right )^n</math>
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]] 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[19][20] that if one samples uniformly, with replacement, from a population of size Шаблон:Math, the number of trials required for the first repeated sampling of some individual has expected value Шаблон: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}{2M}}-\frac{4}{135M}+\cdots.</math>
With Шаблон:Math days in a year, the average number of people required to find a pair with the same birthday is Шаблон:Math, 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 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.[21] For each pair (i, j) for k people in a room, we define the indicator random variable Xij, for <math>1\leq i \leq j\leq k</math>, by
<math display="block">\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}</math>
<math display="block">\begin{alignat}{2} E[X_{ij}] & = \Pr \{ \text{person }i\text{ and person }j\text{ have the same birthday} \} = \frac{1}{n}. \end{alignat}</math>
Let X be a random variable counting the pairs of individuals with the same birthday.
<math display="block">X =\sum_{i=1}^k \sum_{j=i+1}^k X_{ij}</math>
<math display="block">\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}</math>
For Шаблон:Math, if Шаблон:Math, the expected number of pairs of individuals with the same birthday is Шаблон:Sfrac ≈ 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, 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.[22]
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.[23] 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.
Reverse problem
The reverse problem is to find, for a fixed probability Шаблон:Mvar, the greatest Шаблон:Mvar for which the probability Шаблон:Math is smaller than the given Шаблон:Mvar, or the smallest Шаблон:Mvar for which the probability Шаблон:Math is greater than the given Шаблон:Mvar.Шаблон:Citation needed
Taking the above formula for Шаблон:Math, one has
- <math>n(p;365)\approx \sqrt{730\ln\left(\frac{1}{1-p}\right)}.</math>
The following table gives some sample calculations.
Шаблон:Mvar Шаблон:Mvar Шаблон:Math Шаблон:Math Шаблон:Math Шаблон:Math 0.01 0.14178Шаблон:Sqrt = 2.70864 2 0.00274 3 0.00820 0.05 0.32029Шаблон:Sqrt = 6.11916 6 0.04046 7 0.05624 0.1 0.45904Шаблон:Sqrt = 8.77002 8 0.07434 9 0.09462 0.2 0.66805Шаблон:Sqrt = 12.76302 12 0.16702 13 0.19441 0.3 0.84460Шаблон:Sqrt = 16.13607 16 0.28360 17 0.31501 0.5 1.17741Шаблон:Sqrt = 22.49439 22 0.47570 23 0.50730 0.7 1.55176Шаблон:Sqrt = 29.64625 29 0.68097 30 0.70632 0.8 1.79412Шаблон:Sqrt = 34.27666 34 0.79532 35 0.81438 0.9 2.14597Шаблон:Sqrt = 40.99862 40 0.89123 41 0.90315 0.95 2.44775Шаблон:Sqrt = 46.76414 46 0.94825 47 0.95477 0.99 3.03485Шаблон:Sqrt = 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.
Partition problem
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. 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
The reason is that the correct comparison is to the number of partitions of the weights into left and right. There are Шаблон:Math different partitions for Шаблон:Math 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 and width Шаблон:Math, so that when Шаблон:Math is approximately equal to Шаблон:Math the transition occurs. 223 − 1 is about 4 million, while the width of the distribution is only 5 million.[24]
In fiction
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.
Notes
References
Bibliography
- Шаблон:Cite journal
- Шаблон:Cite journal
- Шаблон:Cite book
- Шаблон:Cite journal
- Шаблон:Cite journal
- Шаблон:Cite journal
- Шаблон:Cite book
- Шаблон:Cite book
External links
- The Birthday Paradox accounting for leap year birthdays
- Шаблон:MathWorld
- A humorous article explaining the paradox
- SOCR EduMaterials activities birthday experiment
- Understanding the Birthday Problem (Better Explained)
- Eurobirthdays 2012. A birthday problem. A practical football example of the birthday paradox.
- Шаблон:Cite web
- Computing the probabilities of the Birthday Problem at WolframAlpha
- ↑ David Singmaster, Sources in Recreational Mathematics: An Annotated Bibliography, Eighth Preliminary Edition, 2004, section 8.B
- ↑ 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, p. 38
- ↑ 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
- ↑ Шаблон:Harv
- ↑ Шаблон:Cite book
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite journal
- ↑ Jim Gray, Catharine van Ingen. Empirical Measurements of Disk Failure Rates and Error Rates
- ↑ Шаблон:Wikicite
- ↑ Шаблон:Harvard citations
- ↑ 11,0 11,1 Шаблон:Harvard citations
- ↑ 12,0 12,1 Шаблон:Harvard citations
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite conference
- ↑ Z. E. Schnabel (1938) The Estimation of the Total Fish Population of a Lake, American Mathematical Monthly 45, 348–352.
- ↑ M. C. Wendl (2003) Collision Probability Between Sets of Random Variables, Statistics and Probability Letters 64(3), 249–254.
- ↑ 17,0 17,1 M. Abramson and W. O. J. Moser (1970) More Birthday Surprises, American Mathematical Monthly 77, 856–858
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite book
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite book
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite journal
- Английская Википедия
- Страницы с неработающими файловыми ссылками
- Probability theory paradoxes
- Probability problems
- Applied probability
- Birthdays
- Mathematical problems
- Coincidence
- Страницы, где используется шаблон "Навигационная таблица/Телепорт"
- Страницы с телепортом
- Википедия
- Статья из Википедии
- Статья из Английской Википедии
