Problem on Probability -- Hash Table & Collisions

[22990atinesh]

Homework Statement

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

(a) What is the probability that bucket number 1 is empty after the the $K^{th}$ insertion ?
(b) What is the probability that no collision has occurred in any of the $K$ insertions ?
(c) What is the probability that the first collision occurs at the $K^{th}$ insertions ?

Homework Equations

The Attempt at a Solution

Probability that a key value is hashed to the first bucket = $\frac{1}{n}$
Probability that a key value is doesn't hashed to the first bucket = $1 - \frac{1}{n}$ = $\frac{n-1}{n}$

(a) Probability that bucket number 1 is empty after the the $K^{th}$ insertion = $(\frac{n-1}{n})^k$
(b) Probability that no collision has occurred in any of the $K$ insertions = $1 \times \frac{1}{n-1} \times \frac{1}{n-2} \times ... \times \frac{1}{n-(k-1)}$
(c) Probability that the first collision occurs at the $K^{th}$ insertions = $1 \times \frac{1}{n-1} \times \frac{1}{n-2} \times ... \times \frac{1}{n-(k-2)} \times \frac{1}{k-1}$

are my above ans correct or I've done some mistake. Please share

 

[mfb]

Where does the last factor at (c) come from?
Everything else looks right.

 

[22990atinesh]

Where does the last factor at (c) come from?
Everything else looks right.

Probability that no collision has occurred in any of the $K-1$ insertions P(K-1)= $1 \times \frac{1}{n-1} \times \frac{1}{n-2} \times ... \times \frac{1}{n-(k-2)}$
Probability that the first collision occurs at the $K^{th}$ insertions = $P(K-1) \times$ Probability of collision of $K^{th}$ element
As K-1 slots are filled, first collision will occur if $K^{th}$ element will get into these slot, It'll do it with probability = $\frac{1}{k-1}$
Hence
Probability that the first collision occurs at the $K^{th}$ insertions = $1 \times \frac{1}{n-1} \times \frac{1}{n-2} \times ... \times \frac{1}{n-(k-2)} \times \frac{1}{k-1}$

 

[mfb]

As K-1 slots are filled, first collision will occur if $K^{th}$ element will get into these slot, It'll do it with probability = $\frac{1}{k-1}$

No it does not.
If 2 out of 100 slots are filled, then the next element won't go to a filled slot with a probability of 1/(3-1)=1/2.

 

[22990atinesh]

No it does not.
If 2 out of 100 slots are filled, then the next element won't go to a filled slot with a probability of 1/(3-1)=1/2.

Would it be $\frac{k}{n}$ in place of $\frac{1}{k-1}$ in (c)

 

[mfb]

Nearly. The numerator should be k-1.

 

[22990atinesh]

Nearly. The numerator should be k-1.

Oops little mistake, you are right. $\frac{k-1}{n}$ is right.