calculate the probability of having no collision when two elements are hashed h(x)=(x^2+1)mod3

Question

How can I calculate the probability of having no collision after inserting 2 elements. answer is 4/9, but I do not see it how it is 4/9

Answer 1

I'm not so sure that this is an appropriate SO question, but here is my shot at the answer. It is by no means a legit mathematical proof, but it works.

For your function h(x) = (x^2+1)mod3, let's put it some sample values.

h(1) = (1+1)mod3 = 2mod3 = 2
h(2) = (4+1)mod3 = 5mod3 = 2
h(3) = (9+1)mod3 = 10mod3 = 1

h(4) = 17mod3 = 2
h(5) = 26mod3 = 2
h(6) = 37mod3 = 1

This pattern will continue due to the nature of the function (squaring and adding 1).

So, we have a (2/3) chance of an input to our function evaluating to 2, and a (1/3) chance that it will evaluate to a 1.

If we insert two elements, the probability that we HAVE a collision is the probability of both inputs evaluating to 2 plus the probability of both evaluating to 1. This is:

(2/3)(2/3) + (1/3)(1/3) = 4/9 + 1/9 = 5/9

Thus, the probability that any two inputs WILL NOT have a collision is 1 - (5/9)

or 4/9.