1

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.

DRF
  • 5,167
sena şaşmaz
  • 11
  • Welcome to Math.SE. I've fixed up your question a bit typographically to make it easier to read. You might want to take a look at http://meta.math.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference to find out how to correctly format your questions using mathjax. – DRF May 07 '15 at 14:14
  • On a content related note are the $S$'s in the sums supposed to be small $s$'s? – DRF May 07 '15 at 14:17

0 Answers0