3
$\begingroup$

Suppose we use a hash function $H$ to hash $N$ distinct balls into $M$ distinct bins. Assuming simple uniform hashing, what is the expected number of collisions?

Note that a collision is defined by adding a ball to an already occupied bin. If the already occupied bin has $k$ balls in it, then the number of collisions upon adding a new ball is $k.$


By using expectation, I tried as :

=> 1 × Probability of collision in first insertion +

2 × Probability of collision in second insertion + .......... +

n × Probability of collision in nth insertion

=> $(1 ∗ 0) + (2 ∗ 1/m) + (3 ∗ 2/m) + (4 ∗ 3/m) + … + (n ∗ n−1/m)$


Actually, The answer is $(n^2 - n)/2m$


But, I am not getting the answer. Where am I wrong here ?

$\endgroup$
  • $\begingroup$ note that it should be $n\times P(\textrm{n collisions}),$ not collision on the $n$th insertion $\endgroup$ – cats Dec 9 '16 at 15:09
  • $\begingroup$ @cats Sorry, didn't get it. Could you please explain it as answer ? $\endgroup$ – Jon Garrick Dec 9 '16 at 15:10
  • $\begingroup$ I'm just saying that your definition of expectation is incorrect. You need $1\times P(\textrm{1 collision}) + 2\times P(\textrm{2 collisions}) + \ldots ,$ which is not the same as what you've written $\endgroup$ – cats Dec 9 '16 at 15:12
  • $\begingroup$ @cats okk !! When I write "2 × Probability of collision in second insertion" then it means that for 2 collisions to happen, what is the probability ? Similarly, for 3 collisions to happen what is the probability? But instead, If I write "1 × Probability of collision in second insertion" then it means probability of having one collision in second attempt. Similarly, what is the probability of having one collision in 3rd attempt ? Am I right now ? $\endgroup$ – Jon Garrick Dec 9 '16 at 15:26
  • 1
    $\begingroup$ Collisions probably means the number of times you put a ball into an already occupied bin $\endgroup$ – cats Dec 9 '16 at 15:30
5
$\begingroup$

The expected number of new collisions caused at the time of inserting the $k$-th ball is $\frac{k-1}{M}$ since it has a $\frac1M$ collision probability with each ball already placed.

Thus the expected number of collisions is

$\frac0M+\frac1M+\frac2M+\cdots+\frac{N-1}{M}=\frac{N(N-1)}{2}\cdot\frac1M$

$\endgroup$
  • 2
    $\begingroup$ This is wrong. If there was already collisions then there are less spots of having collisions with. You need a recurrent definition and maybe have to do this with recursion $\endgroup$ – Charlie Tian Jan 30 '18 at 8:45
  • $\begingroup$ The recursive relationship I derived was that E(k, M) = (M-1/M)E(k-1) + (k-1)/M $\endgroup$ – Charlie Tian Jan 30 '18 at 8:59
  • $\begingroup$ My bad, I had read the question wrong. My way is the recursive DP way to do it when collision is just 1. This is for general k $\endgroup$ – Charlie Tian Jan 30 '18 at 9:07
2
$\begingroup$

Note that if you end with $k$ occupied bins, then there were $N-k$ collisions. In other words, we want $N$ minus the expected number of occupied bins. This is easy - the probability a bin is unoccupied at the end is $\left(\frac{M-1}{M}\right)^N,$ so the expected number of unoccupied bins is this times $M$ and the expected number of occupied bins is $M\left(1-\left(\frac{M-1}{M}\right)^N\right),$ so our answer is $N$ minus this.

edit: this answers a different version of the problem. see paw's answer for the updated :)

$\endgroup$
  • $\begingroup$ I enjoy this succinct explanation for the more common problem. Ironically, I could not find as good an explanation for the more common problem. I think it is good to have answers to both questions on the same one $\endgroup$ – Charlie Tian Jan 30 '18 at 9:08
0
$\begingroup$

you are claiming that $P(A \cap B)=P(A)+P(B)$, which is true iff the events are independent and they are not. Consider that when you insert 3rd element "Probability of collision in this insertion" = $1 \over m$ if there was a collision on 2nd insertion (2nd end up in the same bin as 1st) but it's $2 \over m$ is there was not, so $P_n$ depends on $P_1, \ldots ,P_{n-1}$

$\endgroup$
0
$\begingroup$

assuming @cats statment that "Collisions probably means the number of times you put a ball into an already occupied bin"

you can approach this by describing steps of the process and thinking about graph of states.

like: if while counting $c$ collisions so far and having $i$ balls left there are $k$ empty bins left then with probability $p={1 \over k}$ you move to the state "$i-1$ balls ; $k-1$ empty bins; $c$ collisions" and with probability $1-p$ you move to state "$i-1$ balls; $k$ empty bins; $c+1$ collisions".

In short:

Let $S(c,i,k)$ be state described above, the state graph looks like this:

$S(0,N,M)$ - start state

$S(c,0,k)$ - end stats (dla dowolnych $c,k$)

and the edges are:

$S(c,i,k)\begin{matrix}\overset{1 \over k}{\rightarrow} S(c,i-1,k-1)\\ \overset{k-1 \over k}{\rightarrow}S(c+1,i-1,k)\end{matrix} for\, i>0$

now Lets define $p_{cik}$ as probability of reaching state $S(c,i,k)$ and variable $\Bbb X$ which will be a number of collisions.

If we ask "from what state can i move into state $S(c,i-i,k-1)$", the answer will be "We where in $S(c,i,k)$ and we hit an empty bin or we where in $S(c-1,i,k-1)$ and we made a collision"

That gives us a recursive function: $$p_{c\,i-1\,k-1}={1 \over k}p_{c-1\,i\,k}+{k-1 \over k}p_{c-1\,i\,k-1}$$ And additionally we can say: $$p_{cik}=0\,for\,\begin{matrix}i \notin \{0,\dots,N\}\\ k \notin \{0,\dots,M\}\end{matrix}$$ since those are not possible and that $$p_{0NM}=1$$

that is enough to calculate $p_{cik}$ for $(i,k) \in \{0,\dots,N\} \times \{0,\dots,M\}$

Now we can say $$P(\Bbb X=x)=\sum_{c_n,i,k} p_{c_nik}$$ where $0\le i \le N$ , $0\le k \le M$ , $\sum_nc_n=x$

Such model could be implemented in any programing language.

$\endgroup$
  • $\begingroup$ see my answer for a quick way to solve this version of the problem $\endgroup$ – cats Dec 9 '16 at 20:05

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.