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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Max Alekseyev Jul 4 '16 at 13:17
  • $\begingroup$ @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. $\endgroup$ – Christopher Jul 4 '16 at 19:53

Let $n:=C$. For any integer $i$ and real $x$, let \begin{equation} p_{i,x}:=P(h(x)=i)=P(i-x\le S<i+1-x)=F(i+1-x)-F(i-x), \end{equation} 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 \begin{equation} \sum_i p_{i,x}p_{i,y}, \end{equation} 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.