Probability of two pairs giving equal sum

Question

Given four different natural numbers $v1, v2, v3, v4\in [0, n]$ ($n$ is any finite number), what is the probability of $v1 + v2 = v3 + v4$.

I'm trying to know the probability of collision of a hash function of mine and I've reduced my problem to calculate that specific situation.

NOTE: I don't know if the numbers being bounded by an interval matters, but I've added it just in case. If that can change, refine or simplify the probability calculation, $n$ is actually $2^x$ where $x$ is probably 64.

NOTE: If applying some efficient bit-wise operation (like $XOR$, or $AND$), or multiplying, instead of summing, could reduce drastically the probability of collision, a comment will be appreciated.

Answer 1

The number of all the quadruples in $[0,n]$ is clearly $$ \left( {n + 1} \right)^{\,4} $$

The number of couples satisfyng $$ \left\{ \matrix{ 0 \le v_{\,1} ,v_{\,2} \le n \hfill \cr v_{\,1} + v_{\,2} = s \hfill \cr} \right. $$ is $$ \left\{ {\matrix{ {s + 1} & {\left| {\,0 \le s \le n} \right.} \cr {2n - s + 1} & {\left| {\,n < s \le 2n} \right.} \cr } } \right. $$ as can be verified geometrically, drawing the line $v_{\,1} + v_{\,2} = s$ inside the square $[0,n]^2$.

Same for $v_{\,3} + v_{\,4} = s$.

Therefore the number of ways to have $v_{\,1} + v_{\,2} = v_{\,3} + v_{\,4} = s$ will be the square of the above, and the total will be given by the sum over $s$, i.e. $$ \eqalign{ & 2\sum\limits_{s = 0}^{n - 1} {\left( {s + 1} \right)^{\,2} } + \left( {n + 1} \right)^{\,2} = {{n\left( {2n + 1} \right)\left( {n + 1} \right)} \over 3} + \left( {n + 1} \right)^{\,2} = \cr & = {{\left( {n + 1} \right)\left( {2n^{\,2} + 4n + 3} \right)} \over 3} \cr} $$

Thus the probability you are looking for is $$ p(n) = {{2n^{\,2} + 4n + 3} \over {3\left( {n + 1} \right)^{\,3} }} $$

Answer 2

If your numbers are uniformly distributed in $ i \in [-n,n]$, $P(v_1 + v_2 = n + i) = (n - \mid i \mid))/(n + 1)^2 $ where $\mid x \mid$ is the asolute value of $x$ ans you also have $$P(v_1 + v_2 = v_3 + v_4) = \sum_{i = -n}^n P(v_1 + v_2 = n + i) P(v_3 + v_4 = n + i)$$ Then you combine both expressions above, you have $$P(v_1 + v_2 = v_3 + v_4) = \frac{2 * \sum_{i = 1}^n i^2}{(n + 1)^4} + 1/(n+1)^4 = \frac{n (n + 1) (2 n + 1)}{3 (n + 1)^4} + 1/(n +1)^4 $$

Answer 3

I’ll use the convention that the hash values are in $S=[0,n),$ also known as $[0,n-1].$ I’ll also assume addition is modulo $n.$ This fits with a typical unsigned integer implementation in a computer.

Then if $v_1$ and $v_2$ are each independently uniformly distributed over $S,$ their sum $v_1+v_2\pmod n$ is also uniformly distributed over $S.$ Then regardless of how we got $v_3$ and $v_4,$ the probability that the sum $v_1+v_2\pmod n$ equals the sum $v_3+v_4\pmod n$ is $1/n.$

---

In fact it’s enough if only one of the four numbers, say $v_1,$ is uniformly distributed, as long as it is not dependent on any of the other numbers. Regardless of what $v_2$ is, every number in $S$ is the sum modulo $n$ of $v_2$ and a unique value of $v_1,$ so each number has an equal chance to be the sum.

---

The final probability is the same if you use XOR instead of addition, for much the same reasons, because for any integer $v_2$ in $S,$ every other integer in $S$ is the XOR of $v_2$ and some unique integer in $S$.