0
$\begingroup$

Question

Consider a hash table with $n$ buckets, where external (overflow) Chaining is used to resolve collisions. The hash function is such that the probability that a key value is hashed to a particular bucket is $\frac{1}{n}$. The hash table is initially empty and $K$ distinct values are inserted in the table. What is the probability that the first collision occurs at the $K^{th}$ insertions?

Approach

For the first collision occurs at the $K^{th}$ insertions, Insertion from $1$ to $k-1$ should not collide and then at $k^{th}$ itteration it should collide.

Insertion from $1$ to $k-1$ should not collide $$=\frac{n}{n} \times \frac{n-1}{n} \times \dots \times \frac{n-(k-2)}{n}$$

But i am not getting how to derive probaility for $k^{th}$ itteration collisions please help me out!

$\endgroup$
2
$\begingroup$

You're almost there. The probability for the $k$-th insertion to produce a collision, given that the first $k-1$ insertions haven't, is $\frac{k-1}n$, as $k-1$ buckets are occupied. Thus the overall probability for the first collision to occur at the $k$-th insertion is

$$ \frac{n!(k-1)}{(n-(k-1))!n^k}\;. $$

$\endgroup$
  • $\begingroup$ i got your point that final answer will be $\frac{n}{n} \times \frac{n-1}{n} \times \frac{n-2}{n} \times ..\frac{n-(k-2)}{n} \times \frac{k-1}{n}$ $=\frac{n!}{(n-(k-1))!} \times \frac{k-1}{n^k}$ but i am not getting "The probability for the k-th insertion to produce a collision, given that the first $k−1$insertions haven't, is $\frac{k−1}{n}$ as $k-1$ buckets are occupied" because $k-1$ insertion have not faced collisions so at kth insertion we have probability as $\frac{k}{n}$ $\endgroup$ – laura Aug 9 '18 at 11:09
  • 1
    $\begingroup$ @laura: I don't understand how you arrived at $\frac kn$. If $k-1$ items have been inserted without causing a collision, then $k-1$ out of $n$ buckets are now occupied. If we uniformly randomly select one of these $n$ buckets for the $k$-th item, the probability that we'll hit one of the $k-1$ occupied buckets is $\frac{k-1}n$. $\endgroup$ – joriki Aug 9 '18 at 14:41

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.