Problem on Probability -- Hash Table & Collisions

  • #1
142
1

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 ?

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

Answers and Replies

  • #2
35,268
11,534
Where does the last factor at (c) come from?
Everything else looks right.
 
  • #3
142
1
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}##
 
  • #4
35,268
11,534
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.
 
  • #5
142
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.
Would it be ##\frac{k}{n}## in place of ##\frac{1}{k-1}## in (c)
 
  • #6
35,268
11,534
Nearly. The numerator should be k-1.
 
  • Like
Likes 22990atinesh
  • #7
142
1
Nearly. The numerator should be k-1.
Oops little mistake, you are right. ##\frac{k-1}{n}## is right.
 

Related Threads on Problem on Probability -- Hash Table & Collisions

Replies
6
Views
3K
  • Last Post
Replies
3
Views
645
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
2
Views
605
  • Last Post
Replies
1
Views
875
  • Last Post
Replies
2
Views
697
  • Last Post
Replies
1
Views
742
Replies
2
Views
12K
Replies
2
Views
821
Top