Talk:Birthday paradox: Difference between revisions

From Citizendium
Jump to navigation Jump to search
imported>Anthony Argyriou
(checklist)
 
imported>Peter Schmitt
 
(14 intermediate revisions by 8 users not shown)
Line 1: Line 1:
{{checklist
{{subpages}}
|                 abc = Birthday coincidence
 
|               cat1 = Mathematics
== Table for data ==
|                cat2 =  
 
|               cat3 =
Is there an easy way to put data, like in this article, into a table?
|           cat_check = no
--[[User:David W Gillette|David W Gillette]] 14:55, 21 July 2007 (CDT)
|             status = 2
:I've just put your data into a table - have a look at how it's constructed. [[User:Anthony Argyriou|Anthony Argyriou]] 10:58, 22 July 2007 (CDT)
|         underlinked = yes
::Thanks, it looks great.--[[User:David W Gillette|David W Gillette]] 15:45, 22 July 2007 (CDT)
|            cleanup = yes
 
|                 by = [[User:Anthony Argyriou|Anthony Argyriou]] 16:36, 18 July 2007 (CDT)
== Is there a mathematician in the house? ==
}}
I've just added an article [[birthday attack]] on a cryptographic application of the birthday paradox, with a link from here.
 
Part of the text there is: "In general, for a cryptographic primitive of size n bits, the attack cost is 2<sup>n/2</sup>." That's a well-known rule among crypto folk; it's in the standard references and is used in government standards, see the last paragraph of [[birthday attack]]. However, I've never seen a proof and do not know if it is a theorem or just a handy approximation. Can anyone clarify this? [[User:Sandy Harris|Sandy Harris]] 13:32, 1 November 2008 (UTC)
 
:I don't know what a cryptographic primitive is, and the article does not explain it (hint!). But I guess it is something like a hash function. If you use ''n''-bit hash values (each of them equally likely) and  then there is a 50% chance of a hash collision if you compute the hash of about 1.18 &middot; 2<sup>''n''/2</sup> pieces of data.
 
:With ''n'' bits there are ''N'' = 2<sup>''n''</sup> possibilities, so if you take ''k'' pieces of data, the probability of a hash collision is (the same formula as in the article):
::<math> 1 - \frac {N!}{(N-k)! \cdot N^k}. </math>
:Using Stirling's approximation for the factorial and assuming that ''k'' is large and ''N'' even larger, we find the approximation
::<math> 1 - \frac {N!}{(N-k)! \cdot N^k} \approx 1 - \exp \left( -\frac{k^2}{2N} \right). </math>
:Let me know if you're interested in the details of the computation. So the probability is 50% if
::<math> \exp \left( -\frac{k^2}{2N} \right) = \tfrac12, </math>
:and solving this yields
::<math> k = \sqrt{2 \ln 2 \cdot N} \approx 1.18 \sqrt{N}. </math>
:For instance, if ''N'' = 365 (which is the case in the article) then you get ''k'' = 1.18 &middot; ''N''<sup>1/2</sup> = 22.5, which is a pretty good approximation for the size of the group you need to get two people with the same birthday. -- [[User:Jitse Niesen|Jitse Niesen]] 00:48, 2 November 2008 (UTC)
 
:: That's all I needed. Thanks. [[User:Sandy Harris|Sandy Harris]] 02:56, 2 November 2008 (UTC)
 
== Misleading formulation ==
 
Just for the record: While the calculation is correct, it is badly explained -- persons have no probability.
Needs rewrite. --[[User:Peter Schmitt|Peter Schmitt]] 23:57, 8 July 2010 (UTC)
 
:Please look now. [[User:Boris Tsirelson|Boris Tsirelson]] 06:35, 9 July 2010 (UTC)
 
:But why the advanced theory of Jitse Niesen, 2008, :-) is outside the article? [[User:Boris Tsirelson|Boris Tsirelson]] 06:40, 9 July 2010 (UTC)
 
== A different calculation ==
 
Another way to look at it is that with <math>n</math> people, there are n{n-1)/2 possible pairs. For example, with 23 people there are 23*22/2 = 253 pairs. If each pair has an independent 1/365 chance of a match, the overall chance is 253/365.
 
This appears to give somewhat different results than the calculation in the article. What is wrong? [[User:Sandy Harris|Sandy Harris]] 09:56, 19 October 2010 (UTC)
 
:What's wrong is that they're not independent. Any 2 pairs are independent, but start thinking about 3 pairs. [[User:Peter Jackson|Peter Jackson]] 10:07, 19 October 2010 (UTC)
 
:: It is true that the probability for the pairs are not independent, but each pair has 1/365 as its probability. However, the events do not mutually exclude each other. Therefore the overall probability is not the sum of the probabilities, but less than it. --[[User:Peter Schmitt|Peter Schmitt]] 10:18, 19 October 2010 (UTC)

Latest revision as of 05:18, 19 October 2010

This article is developing and not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
To learn how to update the categories for this article, see here. To update categories, edit the metadata template.
 Definition The counterintuitive result that for any (random) group of 23 or more people it is more likely than not that two of them celebrate their birthday on the same day of the year. [d] [e]
Checklist and Archives
 Workgroup category Mathematics [Categories OK]
 Talk Archive none  English language variant British English

Table for data

Is there an easy way to put data, like in this article, into a table? --David W Gillette 14:55, 21 July 2007 (CDT)

I've just put your data into a table - have a look at how it's constructed. Anthony Argyriou 10:58, 22 July 2007 (CDT)
Thanks, it looks great.--David W Gillette 15:45, 22 July 2007 (CDT)

Is there a mathematician in the house?

I've just added an article birthday attack on a cryptographic application of the birthday paradox, with a link from here.

Part of the text there is: "In general, for a cryptographic primitive of size n bits, the attack cost is 2n/2." That's a well-known rule among crypto folk; it's in the standard references and is used in government standards, see the last paragraph of birthday attack. However, I've never seen a proof and do not know if it is a theorem or just a handy approximation. Can anyone clarify this? Sandy Harris 13:32, 1 November 2008 (UTC)

I don't know what a cryptographic primitive is, and the article does not explain it (hint!). But I guess it is something like a hash function. If you use n-bit hash values (each of them equally likely) and then there is a 50% chance of a hash collision if you compute the hash of about 1.18 · 2n/2 pieces of data.
With n bits there are N = 2n possibilities, so if you take k pieces of data, the probability of a hash collision is (the same formula as in the article):
Using Stirling's approximation for the factorial and assuming that k is large and N even larger, we find the approximation
Let me know if you're interested in the details of the computation. So the probability is 50% if
and solving this yields
For instance, if N = 365 (which is the case in the article) then you get k = 1.18 · N1/2 = 22.5, which is a pretty good approximation for the size of the group you need to get two people with the same birthday. -- Jitse Niesen 00:48, 2 November 2008 (UTC)
That's all I needed. Thanks. Sandy Harris 02:56, 2 November 2008 (UTC)

Misleading formulation

Just for the record: While the calculation is correct, it is badly explained -- persons have no probability. Needs rewrite. --Peter Schmitt 23:57, 8 July 2010 (UTC)

Please look now. Boris Tsirelson 06:35, 9 July 2010 (UTC)
But why the advanced theory of Jitse Niesen, 2008, :-) is outside the article? Boris Tsirelson 06:40, 9 July 2010 (UTC)

A different calculation

Another way to look at it is that with people, there are n{n-1)/2 possible pairs. For example, with 23 people there are 23*22/2 = 253 pairs. If each pair has an independent 1/365 chance of a match, the overall chance is 253/365.

This appears to give somewhat different results than the calculation in the article. What is wrong? Sandy Harris 09:56, 19 October 2010 (UTC)

What's wrong is that they're not independent. Any 2 pairs are independent, but start thinking about 3 pairs. Peter Jackson 10:07, 19 October 2010 (UTC)
It is true that the probability for the pairs are not independent, but each pair has 1/365 as its probability. However, the events do not mutually exclude each other. Therefore the overall probability is not the sum of the probabilities, but less than it. --Peter Schmitt 10:18, 19 October 2010 (UTC)