9
$\begingroup$

Say we have a hash function that produces $n$ bit outputs. From the birthday problem that after around $\sqrt{2^n}$ different inputs to the has function, we can expect a collision.

Say instead that we have $m$ outputs. How many collisions can we expect in those $m$ outputs?

If there are $k$ inputs that all have the same output, we say there are $\binom{k}{2}$ collisions.

$\endgroup$
0

1 Answer 1

11
$\begingroup$

The expected number of collisions (assuming that the hash function can be modeled as a random function) is precisely $2^{-n}\binom{m}{2}$; that is, the expected number of pairs of values $x \ne y$ with $H(x) = H(y)$ (and so, to answer Ricky's question, $H(x) = H(y) = H(z)$ would count as three collisions).

The reasoning is the obvious one; there are $\binom{m}{2}$ separate pairs, and each pair has a probability $2^{-n}$ of colliding (and hence has an expected number of collisions of $2^{-n}$), and the expected sum of a set of probabilistic values is the sum of each individual value's expectation. The probabilities are not independent (for example, if $H(x)=H(y)$ and $H(y)\ne H(z)$, we know that $H(x) \ne H(z)$); it turns out that the expected sum doesn't depend on independence.

$\endgroup$
4
  • 1
    $\begingroup$ @mikeazo Does that mean that these tables are inaccurate in their estimates of the p=50% scenario or am I misunderstanding what these tables represent. It seems to me if the p=0.5 should occur when number of "perfectly random and normally distributed hashes" is 2^(n/2) then the 50% column should read: 256 for 16 bit hashes, 65536 for 32 bit hashes and so on? (Meta question: should I be raising this as a new question? I know my question is different but It just seemed really relevant to what's discussed here). $\endgroup$
    – Iam Nick
    Commented Jan 11, 2016 at 16:04
  • $\begingroup$ @IamNick did you find an answer to that question by any chance? $\endgroup$
    – rinat.io
    Commented Aug 4, 2020 at 17:06
  • 1
    $\begingroup$ @rinat.io: I didn't see IamNick's question, however the answer is "those tables are addressing a different question than I did". I looked at the expected (average) number of collisions; the table looked at "at what point do you get at least one collision with the specified probability". The reason that an average of one collision doesn't occur precisely at $p=0.5$ is that you have a probability of having two collisions in the same collection; that bumps of the average, but doesn't change the probability of getting at least one collision $\endgroup$
    – poncho
    Commented Aug 4, 2020 at 18:12
  • 1
    $\begingroup$ There seems to be some perplexing quirks to this formula, as I can verify it with real-world collisions for $n=32$ but not $n=16$. However, an alternate formula seems to be correct in this case: n - m * (1 - ((m-1)/m) ^ n), where $m=2^{16}$ and $n=32421$ give $6845.466801931194 $. For reasons I don't understand, your binomial formula gives $8019.171295166015625$. $\endgroup$
    – bryc
    Commented Mar 2 at 4:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.