Avalg HW3

Oh, an empty article! You can get started by double clicking this text block and begin editing. You can also click the Text button below to add new block elements. Or you can drag and drop an image right onto this text!

Question 1 (Level E)

Old version

Consider a set \(S\) of \(k\) elements. Let \(h:S\) →{ 1 ; 2 ; … ; 40k} be a 2-universal hash function. For every element \(i\)\(S\) , define a random variable \(X_{i}\) to be 1 if \(h(i)=h(j)\) for some \(j\in S/i\) and 0 otherwise. Prove that \(E[X_{i}]\leq p\) , for some constant \(p<1/2\).

We by definition of a 2-universal hash function that:
Definition (Carter Wegman 1979): Family \(H\) of hash functions is 2 -universal if for any \(x\neq y\in S\) :
\(Pr_{h}{}_{\in}{}_{H}[h(x)=h(y)]\leq\dfrac{1}{n}\)

Our sought for expected value \(E[X_{i}]\) can be rewritten as \(E[\) \(\sum_{x\neq y}h(x)=h(y)]\) = \(\sum_{x}{}_{\neq}{}_{y}E[h(x)=h(y)]\) As we can know that the probabillity of collision is equally distrebuted:
\(\sum_{x}{}_{\neq}{}_{y}E[h(x)=h(y)]\leq{m\choose 2}\dfrac{1}{n}\)
where \(m\) is the number of eklements and \(n\) the number of hash functions in \(H\).

In our case, we have that \(m=k\) and \(n=40k\); which gives us:
\({m\choose 2}\dfrac{1}{n}\rightarrow\dfrac{k!}{2(k-2)!}*\dfrac{1}{40k}=\dfrac{k!}{80k(k-2)!}=\dfrac{k^{2}-k}{80k}=\dfrac{k-1}{80}\)
If we analyse \((k-2)!\)