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 1/n. The hash table is initially empty and k distinct values are inserted in the table. What is the probability that bucket number 1 is empty after the K insertions?
What is the probability that no collision has occurred in any of the K insertions?
What is the probability that first collision occurs at the Kth insertion?

Answer 1

for first answer:
probability that the hash fun mapping a key to a bucket number 1= 1/n and probability that the hash fun not mapping a key to a bucket number 1= 1-(1/n)
probability that the bucket no. 1 is empty=none of these k keys mapped to bucket no. 1 =(n-1/n) (n-1/n) (n-1/n)...k times =(n-1/n)^k

Answer 2

let p(k) = p(no collisions after k inserts)
p(1) = 0
p(2) = (1 - 1/n) = (n-1)/n
p(3) = p(2) * (n-2)/n P(none after 2)*P(next one missing)
p(k) = p(k-1)*(n-(k-1))/n P(none after k-1)*P(missed next )
= p(2)*p(3)..*.p(k-1)*(.....)
= (n-1)!/n*(k-1)! barring absurd arithmetic errors...
and P(first at k) = P(none at k-1)*P(kth colliding)=p(k-1)*(k/n)
but better check it...

Answer 3

Thanks snark...its really helpful...