# Problem on Probability -- Hash Table & Collisions

## 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 occured in any of the ##K## insertions ?
(c) What is the probability that the first collision occurs at the ##K^{th}## insertions ?

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

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

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

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

mfb
Mentor
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.

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
Mentor
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.