Suppose $ℎ: \to $ is a hash function. For any $\in $ , let $ℎ^{−1}()=\{:ℎ()=\}$ and denote $=|ℎ^{−1}()|$. Define $=|\{\{_1,_2\}:ℎ(_1)=ℎ(_2)\}|$. Note that N counts the number of unordered pairs in X that collide under h.
a) Prove that $\sum_{y\in Y} S=||$, so the mean of $Sy^\prime$ s is $\bar{s}=│X|/││$.
b) Prove that $N=\sum (Sy2) = 1/2 \sum S^2−||/2$
I am a new user of this web site. so if I made mistake on writing the question, please warn me.