Assuming uniform hashing, Pr { Xlk = 1} = Pr { h (k) = h (l)} = 1 / m, and so E[Xlk] = 1 / m.
Now define the random variable Y to be the total number of collisions, so that . The expected number of collisions
is
E[Y] = E[ ∑Xkl ], k≠l since Y = ∑Xkl
= ∑ E[Xkl] k≠l by linearity property of expectation
= ∑ (1/m) as E[Xlk] = 1/m
Now we have to do summation of the above.For that we have to no. of terms
So no of terms such that k ≠ l = no of unordered pairs(a,b) in an n element set [Order does not matter since collision of a,b is same as collision (b,a) , hence we consider them once only ]
No of unordered pairs means selection of 2 elements from n elements which can be done in nC2 ways
Hence (1/m) is repeated n(n-1)/2 times.
So E[Y] = n(n-1)/2 * ∑(1/m)
= n(n-1)/2m
So options should be corrected.
Reference : Solution of exercise 11.2-1 of http://test.scripts.psu.edu/users/d/j/djh300/cmpsc465/notes-4985903869437/solutions-to-some-homework-exercises-as-shared-with-students/3-solutions-clrs-11.pdf
