Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Birthday problem

From Wikipedia, the free encyclopedia
(Redirected fromBirthday paradox)
Probability of shared birthdays
For yearly variation in mortality rates, seeBirthday effect. For the mathematical brain teaser that was asked in the Math Olympiad, seeCheryl's Birthday.
The computed probability of at least two people sharing the same birthday versus the number of people

Inprobability theory, thebirthday problem asks for the probability that, in a set ofnrandomly chosen people, at least two will share the samebirthday. Thebirthday paradox is the counterintuitive fact that only 23 people are needed for that probability to exceed 50%.

The birthday paradox is averidical 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⁠23 × 22/2⁠ = 253 pairs to consider.

Real-world applications for the birthday problem include a cryptographic attack called thebirthday attack, which uses this probabilistic model to reduce the complexity of finding acollision for ahash 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 toHarold 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 byRichard von Mises in 1939.[3]

Calculating the probability

[edit]

From apermutations perspective, let the eventA be the probability of finding a group of 23 people without any repeated birthdays. Where the eventB is the probability of finding a group of 23 people with at least two people sharing same birthday,P(B) = 1 −P(A). This is such thatP(A) is the ratio of the total number of birthdays,Vnr{\displaystyle V_{nr}}, without repetitions and order matters (e.g. for a group of 2 people, mm/dd birthday format, one possible outcome is{{01/02,05/20},{05/20,01/02},{10/02,08/04},...}{\displaystyle \left\{\left\{01/02,05/20\right\},\left\{05/20,01/02\right\},\left\{10/02,08/04\right\},...\right\}}) divided by the total number of birthdays with repetition and order matters,Vt{\displaystyle V_{t}}, as it is the total space of outcomes from the experiment (e.g. 2 people, one possible outcome is{{01/02,01/02},{10/02,08/04},...}{\displaystyle \left\{\left\{01/02,01/02\right\},\left\{10/02,08/04\right\},...\right\}}). ThereforeVnr{\displaystyle V_{nr}} andVt{\displaystyle V_{t}} arepermutations.

Vnr=n!(n−k)!=365!(365−23)!Vt=nk=36523P(A)=VnrVt≈0.492703P(B)=1−P(A)≈1−0.492703≈0.507297(50.7297%){\displaystyle {\begin{aligned}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{aligned}}}

Another way the birthday problem can be solved is by asking for an approximate probability that in a group ofn people at least two have the same birthday. For simplicity,leap years,twins,selection bias, and seasonal and weekly variations in birth rates[4] 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, auniform 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.[5][6] 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.[7]

The goal is to computeP(B), the probability that at least two people in the room have the same birthday. However, it is simpler to calculateP(A′), the probability that no two people in the room have the same birthday. Then, becauseB andA′ are the only two possibilities and are alsomutually exclusive,P(B) = 1 −P(A′).

Here is the calculation ofP(B) for 23 people. Let the 23 people be numbered 1 to 23. Theevent 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 usingconditional probability: the probability of Event 2 is⁠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⁠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⁠343/365⁠. Finally, the principle of conditional probability implies thatP(A′) is equal to the product of these individual probabilities:

P(A′)=365365×364365×363365×362365×⋯×343365{\displaystyle P(A')={\frac {365}{365}}\times {\frac {364}{365}}\times {\frac {363}{365}}\times {\frac {362}{365}}\times \cdots \times {\frac {343}{365}}}1

The terms of equation (1) can be collected to arrive at:

P(A′)=(1365)23×(365×364×363×⋯×343){\displaystyle P(A')=\left({\frac {1}{365}}\right)^{23}\times (365\times 364\times 363\times \cdots \times 343)}2

Evaluating equation (2) givesP(A′) ≈ 0.492703

Therefore,P(B) ≈ 1 − 0.492703 = 0.507297 (50.7297%).

This process can be generalized to a group ofn people, wherep(n) is the probability of at least two of then people sharing a birthday. It is easier to first calculate the probabilityp(n) that alln birthdays aredifferent. According to thepigeonhole principle,p(n) is zero whenn > 365. Whenn ≤ 365:

p¯(n)=1×(1−1365)×(1−2365)×⋯×(1−n−1365)=365×364×⋯×(365−n+1)365n=365!365n(365−n)!=n!⋅(365n)365n=365Pn365n{\displaystyle {\begin{aligned}{\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{aligned}}}

where! is thefactorial operator,(365
n) is thebinomial coefficient andkPr denotespermutation.

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(⁠364/365⁠), the third cannot have the same birthday as either of the first two(⁠363/365⁠), and in general thenth birthday cannot be the same as any of then − 1 preceding birthdays.

Theevent of at least two of then persons having the same birthday iscomplementary to alln birthdays being different. Therefore, its probabilityp(n) is

p(n)=1−p¯(n).{\displaystyle p(n)=1-{\bar {p}}(n).}

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

The probability that no two people share a birthday in a group ofn people. Note that the vertical scale is logarithmic (each step down is 1020 times less likely).
np(n)
10.0%
52.7%
1011.7%
2041.1%
2350.7%
3070.6%
4089.1%
5097.0%
6099.4%
7099.9%
7599.97%
10099.99997%
20099.9999999999999999999999999998%
300(100 −6×10−80)%
350(100 −3×10−129)%
365(100 −1.45×10−155)%
≥ 366100%

Approximations

[edit]
Graphs showing the approximate probabilities of at least two people sharing a birthday (red) and its complementary event (blue)
A graph showing the accuracy of the approximation 1 −e−n2/730 (red)

TheTaylor series expansion of theexponential function (the constante ≈2.718281828)

ex=1+x+x22!+⋯{\displaystyle e^{x}=1+x+{\frac {x^{2}}{2!}}+\cdots }

provides a first-order approximation forex for|x|≪1{\displaystyle |x|\ll 1}:

ex≈1+x.{\displaystyle e^{x}\approx 1+x.}

To apply this approximation to the first expression derived forp(n), setx = −⁠a/365⁠. Thus,

e−a/365≈1−a365.{\displaystyle e^{-a/365}\approx 1-{\frac {a}{365}}.}

Then, replacea with non-negative integers for each term in the formula ofp(n) untila =n − 1, for example, whena = 1,

e−1/365≈1−1365.{\displaystyle e^{-1/365}\approx 1-{\frac {1}{365}}.}

The first expression derived forp(n) can be approximated as

p¯(n)≈1⋅e−1/365⋅e−2/365⋯e−(n−1)/365=e−(1+2+⋯+(n−1))/365=e−n(n−1)/2365=e−n(n−1)730.{\displaystyle {\begin{aligned}{\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{aligned}}}

Therefore,

p(n)=1−p¯(n)≈1−e−n(n−1)730.{\displaystyle p(n)=1-{\bar {p}}(n)\approx 1-e^{-{\frac {n(n-1)}{730}}}.}

An even coarser approximation is given by

p(n)≈1−e−n2730,{\displaystyle p(n)\approx 1-e^{-{\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 ared, if there aren persons, and ifn ≪d, then using the same approach as above we achieve the result that ifp(n,d) is the probability that at least two out ofn people share the same birthday from a set ofd available days, then:

p(n,d)≈1−e−n(n−1)2d≈1−e−n22d.{\displaystyle {\begin{aligned}p(n,d)&\approx 1-e^{-{\frac {n(n-1)}{2d}}}\\[6pt]&\approx 1-e^{-{\frac {n^{2}}{2d}}}.\end{aligned}}}

Simple exponentiation

[edit]

The probability of any two people not having the same birthday is⁠364/365⁠. In a room containingn people, there are(n
2) =⁠n(n − 1)/2⁠ pairs of people, i.e.(n
2) 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 pickingwith replacement, any pair of people in the world, not just in a room. In short⁠364/365⁠ can be multiplied by itself(n
2) times, which gives us

p¯(n)≈(364365)(n2).{\displaystyle {\bar {p}}(n)\approx \left({\frac {364}{365}}\right)^{\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)≈1−(364365)(n2).{\displaystyle p(n)\approx 1-\left({\frac {364}{365}}\right)^{\binom {n}{2}}.}

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

p(23)≈1−(364365)(232)=1−(364365)253≈0.500477.{\displaystyle p(23)\approx 1-\left({\frac {364}{365}}\right)^{\binom {23}{2}}=1-\left({\frac {364}{365}}\right)^{253}\approx 0.500477.}

Poisson approximation

[edit]

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

Poi⁡((232)365)=Poi⁡(253365)≈Poi⁡(0.6932){\displaystyle \operatorname {Poi} \left({\frac {\binom {23}{2}}{365}}\right)=\operatorname {Poi} \left({\frac {253}{365}}\right)\approx \operatorname {Poi} (0.6932)}

so

Pr(X>0)=1−Pr(X=0)≈1−e−0.6932≈1−0.499998=0.500002.{\displaystyle \Pr(X>0)=1-\Pr(X=0)\approx 1-e^{-0.6932}\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 usesex ≈ 1 +x.

Square approximation

[edit]

A goodrule of thumb which can be used formental calculation is the relation

p(n,d)≈n22d{\displaystyle p(n,d)\approx {\frac {n^{2}}{2d}}}

which can also be written as

n≈2d×p(n){\displaystyle n\approx {\sqrt {2d\times p(n)}}}

which works well for probabilities less than or equal to⁠1/2⁠. In these equations,d is the number of days in a year.

For instance, to estimate the number of people required for a⁠1/2⁠ chance of a shared birthday, we get

n≈2×365×12=365≈19{\displaystyle n\approx {\sqrt {2\times 365\times {\tfrac {1}{2}}}}={\sqrt {365}}\approx 19}

Which is not too far from the correct answer of 23.

Approximation of number of people

[edit]

This can also be approximated using the following formula for thenumber of people necessary to have at least a⁠1/2⁠ chance of matching:

n≥12+14+2×ln⁡(2)×365=22.999943.{\displaystyle n\geq {\tfrac {1}{2}}+{\sqrt {{\tfrac {1}{4}}+2\times \ln(2)\times 365}}=22.999943.}

This is a result of the good approximation that an event with⁠1/k⁠ probability will have a⁠1/2⁠ chance of occurring at least once if it is repeatedkln 2 times.[8]

Probability table

[edit]
Main article:Birthday attack
length of
hex string		no. of
bits
(b)		hash space
size
(2b)		Number of hashed elements such that probability of at least one hash collision ≥ p
p =10−18p =10−15p =10−12p =10−9p =10−6p = 0.001p = 0.01p = 0.25p = 0.50p = 0.75
8324.3×1092222.9932.9×1039.3×1035.0×1047.7×1041.1×105
(10)(40)(1.1×1012)222471.5×1034.7×1041.5×1058.0×1051.2×1061.7×106
(12)(48)(2.8×1014)22247.5×1022.4×1047.5×1052.4×1061.3×1072.0×1072.8×107
16641.8×10196.11.9×1026.1×1031.9×1056.1×1061.9×1086.1×1083.3×1095.1×1097.2×109
(24)(96)(7.9×1028)4.0×1051.3×1074.0×1081.3×10104.0×10111.3×10134.0×10132.1×10143.3×10144.7×1014
321283.4×10382.6×10108.2×10112.6×10138.2×10142.6×10168.3×10172.6×10181.4×10192.2×10193.1×1019
(48)(192)(6.3×1057)1.1×10203.5×10211.1×10233.5×10241.1×10263.5×10271.1×10286.0×10289.3×10281.3×1029
642561.2×10774.8×10291.5×10314.8×10321.5×10344.8×10351.5×10374.8×10372.6×10384.0×10385.7×1038
(96)(384)(3.9×10115)8.9×10482.8×10508.9×10512.8×10538.9×10542.8×10568.9×10564.8×10577.4×10571.0×1058
1285121.3×101541.6×10685.2×10691.6×10715.2×10721.6×10745.2×10751.6×10768.8×10761.4×10771.9×1077
Comparison of the birthday problem (1) and birthday attack (2):
In (1), collisions are found within one set, in this case, 3 out of 276 pairings of the 24 lunar astronauts.
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,10−18 to10−15 is the uncorrectable bit error rate of a typical hard disk.[9] In theory, 128-bit hash functions, such asMD5, should stay within that range until about8.2×1011 documents, even if its possible outputs are many more.

An upper bound on the probability and a lower bound on the number of people

[edit]

The argument below is adapted from an argument ofPaul Halmos.[nb 1]

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

1−p(n)=p¯(n)=∏k=1n−1(1−k365).{\displaystyle 1-p(n)={\bar {p}}(n)=\prod _{k=1}^{n-1}\left(1-{\frac {k}{365}}\right).}

As in earlier paragraphs, interest lies in the smallestn such thatp(n) >⁠1/2⁠; or equivalently, the smallestn such thatp(n) <⁠1/2⁠.

Using the inequality1 −x <e−x in the above expression we replace1 −⁠k/365⁠ withe−k⁄365. This yields

p¯(n)=∏k=1n−1(1−k365)<∏k=1n−1(e−k365)=e−n(n−1)730.{\displaystyle {\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}}}.}

Therefore, the expression above is not only an approximation, but also anupper bound ofp(n). The inequality

e−n(n−1)730<12{\displaystyle e^{-{\frac {n(n-1)}{730}}}<{\frac {1}{2}}}

impliesp(n) <⁠1/2⁠. Solving forn gives

n2−n>730ln⁡2.{\displaystyle n^{2}-n>730\ln 2.}

Now,730 ln 2 is approximately 505.997, which is barely below 506, the value ofn2 −n attained whenn = 23. Therefore, 23 people suffice. Incidentally, solvingn2 −n = 730 ln 2 forn gives the approximate formula of Frank H. Mathis cited above.

This derivation only shows thatat most 23 people are needed to ensure the chances of a birthday match are at least even; it leaves open the possibility thatn is 22 or less could also work.

Generalizations

[edit]

Arbitrary number of days

[edit]

Given a year withd days, thegeneralized birthday problem asks for the minimal numbern(d) such that, in a set ofn randomly chosen people, the probability of a birthday coincidence is at least 50%. In other words,n(d) is the minimal integern such that

1−(1−1d)(1−2d)⋯(1−n−1d)≥12.{\displaystyle 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}}.}

The classical birthday problem thus corresponds to determiningn(365). The first 99 values ofn(d) are given here (sequenceA033810 in theOEIS):

d1–23–56–910–1617–2324–3233–4243–5455–6869–8283–99
n(d)23456789101112

A similar calculation shows thatn(d) = 23 whend is in the range 341–372.

A number of bounds and formulas forn(d) have been published.[10]For anyd ≥ 1, the numbern(d) satisfies[11]

3−2ln⁡26<n(d)−2dln⁡2≤9−86ln⁡2.{\displaystyle {\frac {3-2\ln 2}{6}}<n(d)-{\sqrt {2d\ln 2}}\leq 9-{\sqrt {86\ln 2}}.}

These bounds are optimal in the sense that the sequencen(d) −√2d ln 2gets arbitrarily close to

3−2ln⁡26≈0.27,{\displaystyle {\frac {3-2\ln 2}{6}}\approx 0.27,}

while it has

9−86ln⁡2≈1.28{\displaystyle 9-{\sqrt {86\ln 2}}\approx 1.28}

as its maximum, taken ford = 43.

The bounds are sufficiently tight to give the exact value ofn(d) in most of the cases. For example, ford = 365 these bounds imply that22.7633 <n(365) < 23.7736 and 23 is the only integer in that range. In general, it follows from these bounds thatn(d) always equals either

⌈2dln⁡2⌉or⌈2dln⁡2⌉+1{\displaystyle \left\lceil {\sqrt {2d\ln 2}}\,\right\rceil \quad {\text{or}}\quad \left\lceil {\sqrt {2d\ln 2}}\,\right\rceil +1}

where⌈ · ⌉ denotes theceiling function.The formula

n(d)=⌈2dln⁡2⌉{\displaystyle n(d)=\left\lceil {\sqrt {2d\ln 2}}\,\right\rceil }

holds for 73% of all integersd.[12] The formula

n(d)=⌈2dln⁡2+3−2ln⁡26⌉{\displaystyle n(d)=\left\lceil {\sqrt {2d\ln 2}}+{\frac {3-2\ln 2}{6}}\right\rceil }

holds foralmost alld, i.e., for a set of integersd withasymptotic density 1.[12]

The formula

n(d)=⌈2dln⁡2+3−2ln⁡26+9−4(ln⁡2)2722dln⁡2⌉{\displaystyle n(d)=\left\lceil {\sqrt {2d\ln 2}}+{\frac {3-2\ln 2}{6}}+{\frac {9-4(\ln 2)^{2}}{72{\sqrt {2d\ln 2}}}}\right\rceil }

holds for alld ≤1018, but it is conjectured that there are infinitely many counterexamples to this formula.[13]

The formula

n(d)=⌈2dln⁡2+3−2ln⁡26+9−4(ln⁡2)2722dln⁡2−2(ln⁡2)2135d⌉{\displaystyle n(d)=\left\lceil {\sqrt {2d\ln 2}}+{\frac {3-2\ln 2}{6}}+{\frac {9-4(\ln 2)^{2}}{72{\sqrt {2d\ln 2}}}}-{\frac {2(\ln 2)^{2}}{135d}}\right\rceil }

holds for alld ≤1018, and it is conjectured that this formula holds for alld.[13]

More than two people sharing a birthday

[edit]

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 (sequenceA014088 in theOEIS).[14]

Everyone shares a birthday

[edit]

The strong birthday problem asks for the number of people that need to be gathered together before there is a 50% chance thateveryone in the gathering shares their birthday with at least one other person. For d=365 days the answer is 3,064 people.[15][16]

The number of people needed for arbitrary number of days is given by (sequenceA380129 in theOEIS)

Probability of a shared birthday (collision)

[edit]

The birthday problem can be generalized as follows:

Givenn random integers drawn from adiscrete uniform distribution with range[1,d], what is the probabilityp(n;d) that at least two numbers are the same? (d = 365 gives the usual birthday problem.)[17]

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

p(n;d)={1−∏k=1n−1(1−kd)n≤d1n>d≈1−e−n(n−1)2d≈1−(d−1d)n(n−1)2{\displaystyle {\begin{aligned}p(n;d)&={\begin{cases}1-\displaystyle \prod _{k=1}^{n-1}\left(1-{\frac {k}{d}}\right)&n\leq 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{aligned}}}

Conversely, ifn(p;d) denotes the number of random integers drawn from[1,d] to obtain a probabilityp that at least two numbers are the same, then

n(p;d)≈2d⋅ln⁡(11−p).{\displaystyle n(p;d)\approx {\sqrt {2d\cdot \ln \left({\frac {1}{1-p}}\right)}}.}

The birthday problem in this more generic sense applies tohash functions: the expected number ofN-bit hashes that can be generated before getting a collision is not2N, but rather only2N⁄2. This is exploited bybirthday attacks oncryptographic hash functions and is the reason why a small number of collisions in ahash table are, for all practical purposes, inevitable.

The theory behind the birthday problem was used by Zoe Schnabel[18] under the name ofcapture-recapture statistics to estimate the size of fish population in lakes. The birthday problem and its generalizations are also useful tools for modelling coincidences.[19]

Probability of a unique collision

[edit]

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 amongn people there is exactly one pair of individuals with a matching birthday givend possible days is[19]

p2(n;d)=(n2)d−n+1(1−p(n;d)){\displaystyle p_{2}(n;d)={\frac {n \choose 2}{d-n+1}}(1-p(n;d))}

Unlike the standard birthday problem, asn increases the probability reaches a maximum value before decreasing. For example, ford = 365, the probability of a unique match has a maximum value of 0.3864 occurring whenn = 28.

Generalization to multiple types of people

[edit]
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.[20] In the simplest extension there are two types of people, saym men andn 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

p0=1dm+n∑i=1m∑j=1nS2(m,i)S2(n,j)∏k=0i+j−1d−k{\displaystyle 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}

whered = 365 andS2 areStirling numbers of the second kind. Consequently, the desired probability is1 −p0.

This variation of the birthday problem is interesting because there is not a unique solution for the total number of peoplem +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.

Other birthday problems

[edit]

First match

[edit]

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 whatn isp(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]

Same birthday as you

[edit]
Comparingp(n) = probability of a birthday match withq(n) = probability of matchingyour birthday

In the birthday problem, neither of the two people is chosen in advance. By contrast, the probabilityq(n) thatat least one other person in a room ofn other people has the same birthday as aparticular person (for example, you) is given by

q(n)=1−(365−1365)n{\displaystyle q(n)=1-\left({\frac {365-1}{365}}\right)^{n}}

and for generald by

q(n;d)=1−(d−1d)n.{\displaystyle q(n;d)=1-\left({\frac {d-1}{d}}\right)^{n}.}

In the standard case ofd = 365, substitutingn = 23 gives about 6.1%, which is less than 1 chance in 16. For a greater than 50% chance thatat least one other person in a roomful ofn people has the same birthday asyou,n would need to be at least 253. 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.

Number of people with a shared birthday

[edit]

For any one person in a group ofn people the probability that he or she shares his birthday with someone else isq(n−1;d){\displaystyle 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(1−(d−1d)n−1){\displaystyle n\left(1-\left({\frac {d-1}{d}}\right)^{n-1}\right)}

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

n(d−1d)n−1{\displaystyle n\left({\frac {d-1}{d}}\right)^{n-1}}

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

[edit]

The expected number of people needed until every birthday is achieved is called theCoupon collector's problem. It can be calculated bynHn, whereHn is thenthharmonic number. For 365 possible dates (the birthday problem), the answer is 2365.

Near matches

[edit]

Another generalization is to ask for the probability of finding at least one pair in a group ofn people with birthdays withink calendar days of each other, if there ared equally likely birthdays.[21]

p(n,k,d)=1−(d−nk−1)!dn−1(d−n(k+1))!{\displaystyle {\begin{aligned}p(n,k,d)&=1-{\frac {(d-nk-1)!}{d^{n-1}{\bigl (}d-n(k+1){\bigr )}!}}\end{aligned}}}

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

kn
ford = 365
023
114
211
39
48
58
67
77

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.[21]

Number of days with a certain number of birthdays

[edit]

Number of days with at least one birthday

[edit]

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

d−d(d−1d)n{\displaystyle d-d\left({\frac {d-1}{d}}\right)^{n}}

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

d(d−1d)n{\displaystyle d\left({\frac {d-1}{d}}\right)^{n}}

which follows from the probability that a particular day is no one's birthday,(⁠d − 1/d⁠)n
 , easily summed because of the linearity of the expected value.

For instance, withd = 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).

Number of days with at least two birthdays

[edit]

The above can be generalized from the distribution of the number of people with their birthday on any particular day, which is aBinomial distribution with probability⁠1/d⁠. Multiplying the relevant probability byd 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(d−1d)n−d⋅(n1)(1d)1(d−1d)n−1=d−d(d−1d)n−n(d−1d)n−1{\displaystyle 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}}

Number of people who repeat a birthday

[edit]

The probability that thekth integer randomly chosen from[1,d] will repeat at least one previous choice equalsq(k − 1;d) above. The expected total number of times a selection will repeat a previous selection asn such integers are chosen equals[22]

∑k=1nq(k−1;d)=n−d+d(d−1d)n{\displaystyle \sum _{k=1}^{n}q(k-1;d)=n-d+d\left({\frac {d-1}{d}}\right)^{n}}

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

Average number of people to get at least one shared birthday

[edit]

In an alternative formulation of the birthday problem, one asks theaverage number of people required to find a pair with the same birthday. If we consider the probability function Pr[n people have at least one shared birthday], thisaverage is determining themean of the distribution, as opposed to the customary formulation, which asks for themedian. The problem is relevant to severalhashing algorithms analyzed byDonald Knuth in his bookThe Art of Computer Programming. It may be shown[23][24] that if one samples uniformly, with replacement, from a population of sizeM, the number of trials required for the first repeated sampling ofsome individual hasexpected valuen = 1 +Q(M), where

Q(M)=∑k=1MM!(M−k)!Mk.{\displaystyle Q(M)=\sum _{k=1}^{M}{\frac {M!}{(M-k)!M^{k}}}.}

The function

Q(M)=1+M−1M+(M−1)(M−2)M2+⋯+(M−1)(M−2)⋯1MM−1{\displaystyle 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}}}}

has been studied bySrinivasa Ramanujan and hasasymptotic expansion:

Q(M)∼πM2−13+112π2M−4135M+⋯.{\displaystyle Q(M)\sim {\sqrt {\frac {\pi M}{2}}}-{\frac {1}{3}}+{\frac {1}{12}}{\sqrt {\frac {\pi }{2M}}}-{\frac {4}{135M}}+\cdots .}

WithM = 365 days in a year, the average number of people required to find a pair with the same birthday isn = 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 ofM + 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.[25] For each pair (i,j) for k people in a room, we define the indicator random variableXij, for1≤i≤j≤k{\displaystyle 1\leq i\leq j\leq k}, by

Xij=I{person i and person j have the same birthday}={1,if person i and person j have the same birthday;0,otherwise.{\displaystyle {\begin{alignedat}{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{alignedat}}}

E[Xij]=Pr{person i and person j have the same birthday}=1n.{\displaystyle {\begin{alignedat}{2}E[X_{ij}]&=\Pr\{{\text{person }}i{\text{ and person }}j{\text{ have the same birthday}}\}={\frac {1}{n}}.\end{alignedat}}}

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

X=∑i=1k∑j=i+1kXij{\displaystyle X=\sum _{i=1}^{k}\sum _{j=i+1}^{k}X_{ij}}

E[X]=∑i=1k∑j=i+1kE[Xij]=(k2)1n=k(k−1)2n{\displaystyle {\begin{alignedat}{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{alignedat}}}

Forn = 365, ifk = 28, the expected number of pairs of individuals with the same birthday is⁠28 × 27/2 × 365⁠ ≈ 1.0356. Therefore, we can expect at least one matching pair with at least 28 people.

In the2014 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.[26]

Voracek, Tran andFormann 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.[27] 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

[edit]

The reverse problem is to find, for a fixed probabilityp,the greatestn for which the probabilityp(n) is smaller than the givenp, or the smallestn for which the probabilityp(n) is greater than the givenp.[citation needed]

Taking the above formula ford = 365, one has

n(p;365)≈730ln⁡(11−p).{\displaystyle n(p;365)\approx {\sqrt {730\ln \left({\frac {1}{1-p}}\right)}}.}

The following table gives some sample calculations.

pnn↓p(n↓)n↑p(n↑)
0.010.14178√365 =2.7086420.0027430.00820
0.050.32029√365 = 6.1191660.0404670.05624
0.10.45904√365 = 8.7700280.0743490.09462
0.20.66805√365 =12.76302120.16702130.19441
0.30.84460√365 = 16.13607160.28360170.31501
0.51.17741√365 = 22.49439220.47570230.50730
0.71.55176√365 = 29.64625290.68097300.70632
0.81.79412√365 = 34.27666340.79532350.81438
0.92.14597√365 = 40.99862400.89123410.90315
0.952.44775√365 = 46.76414460.94825470.95477
0.993.03485√365 =57.98081570.99012580.99166

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

Partition problem

[edit]

A related problem is thepartition problem, a variant of theknapsack problem fromoperations research. Some weights are put on abalance scale; each weight is an integer number of grams randomly chosen between one gram and one million grams (onetonne). 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 above100000. 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 are2N − 1 different partitions forN 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 approximatelyGaussian, with a peak at500000N and width1000000√N, so that when2N − 1 is approximately equal to1000000√N the transition occurs. 223 − 1 is about 4 million, while the width of the distribution is only 5 million.[28]

In fiction

[edit]

Arthur C. Clarke's 1961 novelA 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

[edit]
  1. ^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. Whatcalculators do not yield is understanding, or mathematical facility, or a solid basis for more advanced, generalized theories.

References

[edit]
  1. ^David Singmaster,Sources in Recreational Mathematics: An Annotated Bibliography, Eighth Preliminary Edition, 2004,section 8.B
  2. ^H.S.M. Coxeter, "Mathematical Recreations and Essays, 11th edition", 1940, p 45, as reported inI. J. Good,Probability and the weighing of evidence, 1950,p. 38
  3. ^Richard Von Mises, "Über Aufteilungs- und Besetzungswahrscheinlichkeiten",Revue de la faculté des sciences de l'Université d'Istanbul4:145-163, 1939, reprinted inFrank, P.; Goldstein, S.; Kac, M.; Prager, W.; Szegö, G.; Birkhoff, G., eds. (1964).Selected Papers of Richard von Mises. Vol. 2. Providence, Rhode Island: Amer. Math. Soc. pp. 313–334.
  4. ^seeBirthday#Distribution through the year
  5. ^(Bloom 1973)
  6. ^Steele, J. Michael (2004).The Cauchy‑Schwarz Master Class. Cambridge: Cambridge University Press. pp. 206, 277.ISBN 9780521546775.
  7. ^Mario Cortina Borja; John Haigh (September 2007)."The Birthday Problem".Significance.4 (3). Royal Statistical Society:124–127.doi:10.1111/j.1740-9713.2007.00246.x.
  8. ^Mathis, Frank H. (June 1991)."A Generalized Birthday Problem".SIAM Review.33 (2):265–270.doi:10.1137/1033051.ISSN 0036-1445.JSTOR 2031144.OCLC 37699182.
  9. ^Jim Gray, Catharine van Ingen.Empirical Measurements of Disk Failure Rates and Error Rates
  10. ^D. Brink, A (probably) exact solution to the Birthday Problem, Ramanujan Journal, 2012,[1].
  11. ^Brink 2012, Theorem 2
  12. ^abBrink 2012, Theorem 3
  13. ^abBrink 2012, Table 3, Conjecture 1
  14. ^"Minimal number of people to give a 50% probability of having at least n coincident birthdays in one year".The On-line Encyclopedia of Integer Sequences. OEIS. Retrieved17 February 2020.
  15. ^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.
  16. ^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
  17. ^Suzuki, K.; Tonien, D.; et al. (2006). "Birthday Paradox for Multi-collisions". In Rhee M.S., Lee B. (ed.).Lecture Notes in Computer Science, vol 4296. Berlin: Springer.doi:10.1007/11927587_5. Information Security and Cryptology – ICISC 2006.
  18. ^Z. E. Schnabel (1938)The Estimation of the Total Fish Population of a Lake,American Mathematical Monthly45, 348–352.
  19. ^abM. Pollanen (2024)A Double Birthday Paradox in the Study of Coincidences,Mathematics23(24), 3882.https://doi.org/10.3390/math12243882
  20. ^M. C. Wendl (2003)Collision Probability Between Sets of Random Variables, Statistics and Probability Letters64(3), 249–254.
  21. ^abM. Abramson and W. O. J. Moser (1970)More Birthday Surprises,American Mathematical Monthly77, 856–858
  22. ^Might, Matt."Collision hash collisions with the birthday paradox".Matt Might's blog. Retrieved17 July 2015.
  23. ^Knuth, D. E. (1973).The Art of Computer Programming. Vol. 3, Sorting and Searching. Reading, Massachusetts: Addison-Wesley.ISBN 978-0-201-03803-3.
  24. ^Flajolet, P.; Grabner, P. J.; Kirschenhofer, P.; Prodinger, H. (1995)."On Ramanujan's Q-Function".Journal of Computational and Applied Mathematics.58:103–116.doi:10.1016/0377-0427(93)E0258-N.
  25. ^Cormen; et al.Introduction to Algorithms.
  26. ^Fletcher, James (16 June 2014)."The birthday paradox at the World Cup".bbc.com. BBC. Retrieved27 August 2015.
  27. ^Voracek, M.; Tran, U. S.; Formann, A. K. (2008). "Birthday and birthmate problems: Misconceptions of probability among psychology undergraduates and casino visitors and personnel".Perceptual and Motor Skills.106 (1):91–103.doi:10.2466/pms.106.1.91-103.PMID 18459359.S2CID 22046399.
  28. ^Borgs, C.; Chayes, J.; Pittel, B. (2001). "Phase Transition and Finite Size Scaling in the Integer Partition Problem".Random Structures and Algorithms.19 (3–4):247–288.doi:10.1002/rsa.10004.S2CID 6819493.

Bibliography

[edit]

External links

[edit]
Portal:
Retrieved from "https://en.wikipedia.org/w/index.php?title=Birthday_problem&oldid=1279006540"
Categories:
Hidden categories:
[8]ページ先頭
©2009-2025 Movatter.jp