Talk:Birthday paradox

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 2^n/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 · 2^n/2 pieces of data.

With n bits there are N = 2ⁿ possibilities, so if you take k pieces of data, the probability of a hash collision is (the same formula as in the article):

$1-{\frac {N!}{(N-k)!\cdot N^{k}}}.$

Using Stirling's approximation for the factorial and assuming that k is large and N even larger, we find the approximation

$1-{\frac {N!}{(N-k)!\cdot N^{k}}}\approx 1-\exp \left(-{\frac {k^{2}}{2N}}\right).$

Let me know if you're interested in the details of the computation. So the probability is 50% if

$\exp \left(-{\frac {k^{2}}{2N}}\right)={\tfrac {1}{2}},$

and solving this yields

$k={\sqrt {2\ln 2\cdot N}}\approx 1.18{\sqrt {N}}.$

For instance, if N = 365 (which is the case in the article) then you get k = 1.18 · N^1/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 $n$ 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)