Hashing

Question

Consider a hash table with $n$ buckets, where external(overflow) chaining is used to resolve collision. The hash function is such that the probability that a key value is hashed to a particular bucket is $\dfrac 1 n$. The hash table is initially empty and $k$  distinct values are inserted in the table.

Q) What is the probability that bucket number $1$ is empty after the $k^{th}$ insertion?

1. $n$
2. $(n - 1)^k$
3. $((n-1)/n)^k$
4. $((n-1)/k)^n$

Q).  What is the probability that no collision has occurred in any of the $k$ insertions?

1. $n(n - 1)(n - 2)(n - k + 1)/n^k$
2. $n(n - 1)(n - 2)(n - k - 1)/n^k$
3. both (a) and (b)
4. none

Answer 1

1.  If bucket no 1 is empty after $k$ insertions that means keys must have mapped to remaining $n-1$ locations. $k$ insertions means $k$ keys mapped. Probability of bucket 1 being empty $= \left({\frac{n-1}{n}}\right)^k$

Ans C

2. No collision in $k$ insertions
Insertion 1: $\frac{n}{n}$ (key can go to any one of $n$ positions)
Insertion 2: $\frac{n-1}{n}$ (key can go to any one of $n-1$ remaining positions).
insertion 3: $\frac{n-2}{n}$ and continuing in same way
Insertion $k$: $\frac{n-(k-1)}{n}$
so we get Probability of no collision = $\frac{n.(n-1).(n-2)\dots(n-k+1)}{n^k}$
Ans A

Comments

There is one more subquestion for this:Find probability that first collision occurs at Kth insertion.

Probability that collision occurs at the Kth insertion will be= 1-(probability that no collision till (k-1)th insertion)

So P(collision at Kth)= n^k-n(n-1)(n-2).....(n-k+2)/n^k

is it good?

Answer 2

Q.1] probability that the hash fun mapping a key to a bucket number 1= 1/n 
 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 after 2 iteration= First Time  Missed And Second Time Missed = (n-1/n) (n-1/n)
none of these k keys mapped to bucket no. 1 after k Iteration=(n-1/n) (n-1/n) (n-1/n)...k times =
(n-1/n)^k Option C

For K=1, it's 1. For K=2, the second item must miss the bucket of the first item. 
So it has n−1 places it can go safely. The probability of success is therefore n−1/n
So the probability for K=3is 1*n−1/n*n−2/n.
similarly for P(k) = 1*n−1/n*n−2/n*n-3/n............n+1-k/n

Comments

sir,in Q.2] how you calculate probability of success please clear my doubt..

---

P(k)= Probability of no collision

for the first item it can go anywhere without any collision so P(1)=1
for second item it has only n-1 places free to go without collision so P(2) = P(1)*n-1/n

and so on!