Made Easy Test Series : Consider an open addressing hashing scheme with m slots and n keys. Assuming uniform hashing, the expected number of empty slots in the hash table for m=7 and n=3 is equal to ____________(Round off to two decimal places)

Question

Below is my approach to solving this question, can anyone please explain if I am doing it the right way?

Let X = #free slots
since, m =7 and n = 3

So,  $4 \leqslant x\leqslant 6$

Now, P(x=4) => Probability that all three keys map to different locations = $(7*6*5)/7^3$

Similarly P(x=5) => Probability that 2 keys map to different slots and the third key collides with any of the previously filled slots = $(7*6*2)/7^3$
similarly for P(x=6) => Probability that all three maps to the same slot = $(7*1*1)/7^3$

Now for expectation, E(X) = $\sum_{}^{}$PiXi

So, E(X) = $4* (7*6*5)/7^3 + 5 * (7*6*2)/7^3 + 6 * (7*1*1)/7^3$ = 3.795 $\approx$ 3.8

But the answer given in the test series is 4.408, I am not getting why is my approach wrong, can anyone explain, please!

 

---

I am providing a screenshot of their solution below – 

Answer 1

Independently , each key has $1/m$ probability of hashing into the first slot   so probability for being empty of first slot is $1-1/m$ thus the Probability that  no  key hashes into the first slot is $(1-1/m)^{n}$.

Now Let $X_{i}$ be the event (or just break it into bernouli RV) that slot $i$ is Empty. Since  $X_{i}$ =1 When slot  ${i}$ is Empty and  is $0$ other wise,

$E[X_{i}]=Pr(X_{i} =1)$ is the Probability of slot $i$ being Empty.

Now Expected  Number of Empty Slots

 $E[\sum X_{i}]=\sum E[X_{i}]*P_{i}$

$E[X_{1}] =(1-1/m)^n$ which will same for all slots  

then it will be $m(1-1/m)^n$