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.

Answer 2

For a little background on why that pattern holds consider all the equivalency classes mod 3, that is { 0, 1, 2 }.

If x mod 3 = 0 then x^2 mod 3 = (x mod 3)(x mod 3) mod 3 = (0 * 0) mod 3 = 0 by distributive equivalency, so x^2 + 1 mod 3 = 1

If x mod 3 = 1 then x^2 mod 3 = (x mod 3)(x mod 3) mod 3 = (1 * 1) mod 3 = 1 , so x^2 + 1 mod 3 = 2

If x mod 3 = 2 then x^2 mod 3 = (x mod 3)(x mod 3) mod 3 = (2 * 2) mod 3 = 1 , so x^2 + 1 mod 3 = 2

It's still not 100% formal, and it's a clunky example by exhaustion, but it gives you an idea why this pattern holds for natural numbers union { 0 }. I also wish I was more familiar with math formatting on stack. Suppose it's time to hit up meta? :)