# Problem on Probability -- Hash Table & Collisions

Tags:
1. Jan 6, 2015

### 22990atinesh

1. The problem statement, all variables and given/known data
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 occured in any of the $K$ insertions ?
(c) What is the probability that the first collision occurs at the $K^{th}$ insertions ?

2. Relevant equations

3. 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 occured 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

2. Jan 6, 2015

### Staff: Mentor

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

3. Jan 7, 2015

### 22990atinesh

Probability that no collision has occured 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}$

4. Jan 7, 2015

### Staff: Mentor

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.

5. Jan 10, 2015

### 22990atinesh

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

6. Jan 10, 2015

### Staff: Mentor

Nearly. The numerator should be k-1.

7. Jan 11, 2015

### 22990atinesh

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