Probability of two pairs giving equal sum 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.
 A: 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} }}
$$
A: 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 $$
A: 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$.
