6
$\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$
8
$\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.

| improve this answer | |
$\endgroup$
  • 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 Jan 11 '16 at 16:04
  • $\begingroup$ @IamNick did you find an answer to that question by any chance? $\endgroup$ – rinat.io Aug 4 at 17:06
  • $\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 Aug 4 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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