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$
0

1 Answer 1

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$
2
  • $\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
    Commented Aug 9, 2018 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
    Commented Aug 9, 2018 at 14:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .