# What is the probability that the first collision occurs at the Kth insertions?

## 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!

## 1 Answer

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}\;.$$

• 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}$ – laura Aug 9 '18 at 11:09
• @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$. – joriki Aug 9 '18 at 14:41