Misplaced Pages

Birthday problem: Difference between revisions

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Browse history interactively← Previous editNext edit →Content deleted Content addedVisualWikitext
Revision as of 18:14, 23 March 2004 editArvindn (talk | contribs)Extended confirmed users4,332 edits remove long Halmos quote. Anti-calculator advocacy is not relevant to the article.← Previous edit Revision as of 18:17, 23 March 2004 edit undoArvindn (talk | contribs)Extended confirmed users4,332 editsNo edit summaryNext edit →
Line 16: Line 16:
:<math>p = { 365! \over 365^n (365-n)! }</math> :<math>p = { 365! \over 365^n (365-n)! }</math>


Now, 1 - ''p'' is the probability that at least two persons have the same birthday. For ''n'' = 23 you will obtain a probability of about 0.507... Now, 1 - ''p'' is the probability that at least two persons have the same birthday. For ''n'' = 23 one obtains a probability of about 0.507.


By contrast, the probability that someone in a room of ''n'' other people has the same birthday as you is given by By contrast, the probability that someone in a room of ''n'' other people has the same birthday as you is given by
Line 22: Line 22:
which for ''n'' = 22 gives only about 0.059, and would need ''n'' to be at least 253 to give a value over 0.5. which for ''n'' = 22 gives only about 0.059, and would need ''n'' to be at least 253 to give a value over 0.5.


The birthday paradox in its more generic sense applies to ]s where the number of ''N''-] hashes you can generate before probably getting a collision is not 2<sup>''N''</sup>, but rather only 2<sup>''N''/2</sup>. This is exploited by ]s on ]. The birthday paradox in its more generic sense applies to ]s: the number of ''N''-] hashes that can be generated before probably getting a collision is not 2<sup>''N''</sup>, but rather only 2<sup>''N''/2</sup>. This is exploited by ]s on ] (see ]).




Revision as of 18:17, 23 March 2004

The birthday paradox states that if there are 23 people in a room then there is roughly a 50/50 chance that at least two of them have the same birthday. For around 60 or more people the probability is greater than 99%. This is not a paradox in the sense of it leading to a logical contradiction; it is a paradox in the sense that it is a mathematical truth that contradicts common intuition.

Calculating this probability (and related ones) is the birthday problem. The theory behind it was described in the American Mathematical Monthly in 1938 in Zoe Emily Schnabel's The estimation of the total fish population of a lake, under the name of capture-recapture statistics.

The key to understanding the birthday paradox is to realize that there are many possible pairs of people whose birthdays could match. Specifically, among 23 people, there are 23*22/2 = 253 pairs, each of which being a potential candidate for a match. To emphasize the point, consider a different scenario: if you enter a room with 22 people, the chance that somebody there has the same birthday as you is not 50/50, but much lower. This is because now there are only 22 possible pairs that could yield a match.

To compute the approximate probability that in a room of n people, at least two have the same birthday, we disregard leap years and twins, and assume that the 365 possible birthdays are equally likely. The trick is to first calculate the probability that the n birthdays are different. This probability is given by

p = 364 365 ⋅ 363 365 ⋅ 362 365 ⋯ 365 − n + 1 365 {\displaystyle p={\frac {364}{365}}\cdot {\frac {363}{365}}\cdot {\frac {362}{365}}\cdots {\frac {365-n+1}{365}}}

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. Using factorial notation, this expression can also be written as

p = 365 ! 365 n ( 365 − n ) ! {\displaystyle p={365! \over 365^{n}(365-n)!}}

Now, 1 - p is the probability that at least two persons have the same birthday. For n = 23 one obtains a probability of about 0.507.

By contrast, the probability that someone in a room of n other people has the same birthday as you is given by

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

which for n = 22 gives only about 0.059, and would need n to be at least 253 to give a value over 0.5.

The birthday paradox in its more generic sense applies to hash functions: the number of N-bit hashes that can be generated before probably getting a collision is not 2, but rather only 2. This is exploited by birthday attacks on cryptographic systems (see cryptographic hash function).


External links