MADE EASY TEST SERIES

Question

Suppose we used a hash function H(n) to hash ‘n’ distinct elements (keys) into an array T of length ‘m’.
What is the expected number of colliding pairs of elements, if we used simple uniform hashing?

Comments

Is the question about expected no of collisions or about colliding pairs..As colliding pair is C(n,2)..But if asked about no of collisions it will be C(n,2) / m..

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

Answer 1

$\begin{align*} & \text{Let } X_k \text{ is a random variable and it is defined as follows :} \\ & X_k = \begin{cases} & 1 \quad \text{ if collision occurs at kth insertion}\\ & 0 \quad \text{ if collision does not occur at kth insertion}\\ \end{cases} \\ \\ &\text{before the {k}th insertion (k - 1) elements will be there in the hash array} \\ &\Rightarrow P(X_k = 1) = \frac{k-1}{m} \\ &\Rightarrow E(X_k) = P(X_k = 1) \\ &\text{By linearity of expectation} \\ &E = \sum E(X_k) \\ &E = \sum P(X_k = 1) \\ &E = \sum_{x=0}^{n-1} \frac{x}{m} \\ &E = \frac{1}{m}.\frac{(n-1).n}{2} \\ \end{align*}$

Comments

ur explanations are very nice @debashish//especially the latex ones :)

---

Im not able to follow this approach . Lot of math !! :( And im very weak in it 
 Could some one explain in words plz ? 

P(X_k=1)  what does this mean ? 

Answer 2

 I hope this would help simple and easy procedure..