# Probability of collision of some family of hash functions

Given $x$ and $y$ in $\mathbb{R}$, and let $\mathcal{H} = \{ h \mid \mathbb{R} \to \mathbb{N} \}$ be a family of hash functions where $h(x) = \left\lfloor x + \sum^C_{i=1} U_i \right\rfloor$ for some constant $C$. Morever, $U_i$ is independently and uniformly choosen at random from [0,1].

What is the probability that $h_1(x) = h_2(y)$ occurs, where $h_1$ and $h_2$ are choosen independently at random from $\mathcal{H}$? I know that it looks similar to a hat kernel for $C=5$, see Plot (scaled to $[0,1]$). Moreover the distribution of the sum is an Irwin-Hall distribution. Any suggestions how to proceed?

I posted the question on math.stackexchange a week ago, but did not get an answer.

• What are $x$ and $y$? Are they given / chosen randomly? If $|x-y|>C+1$, then $h_1(x)\ne h_2(y)$ for sure. Jul 4 '16 at 13:17
• @MaxAlekseyev $x,y$ are in $\mathbb{R}$, and the probability in question should be expressed in terms of $x$ and $y$, e.g., the distance between them. Jul 4 '16 at 19:53

Let $n:=C$. For any integer $i$ and real $x$, let $$p_{i,x}:=P(h(x)=i)=P(i-x\le S<i+1-x)=F(i+1-x)-F(i-x),$$ where $S:=\sum^n_{i=1} U_i$, $F(s):=\frac1{n!}\,\sum_{j=0}^n(-1)^j\binom nj (s-j)_+^n$, $u_+:=0\vee u$. Of course, $F$ is the cdf of the Irwin--Hall distribution. Then the probability in question is $$\sum_i p_{i,x}p_{i,y},$$ where $\sum_i$ denotes the summation over all integers $i$ or, equivalently in this case, the summation over all integers $i$ such that $x\vee y-1\le i\le x\wedge y+n$. In particular, it follows (as pointed out by Max Alekseyev) that this probability will be $0$ in the case when $|x-y|>n+1$.