It might help if you describe more about what you've done rather than just pasting the problem here. How did you prove what you've proven so far?
- I think that I have managed to show that H_n,m is a strongly 2-universal family of hash functions. However, I'm stuck on the second part of the question. I was only able to show that |T| <= 32 with probability at least 1/2.
If anyone can figure this out please help!
Note: B = {0,1}.
- Okay so I have proved that is strongly 2-universal, so it is also 2-universal, that means for chosen independently and uniformly at random, and for any , we have that .
Because of this, we can deduce the following:
Now using Markov's inequality:
So, with probability at least .
Of course this is not the answer they want, but I'm not able to get a tighter bound on .
Have you tried applying the other side of the inequality? I don't see m+3 anywhere in your work above.
I have to bow out here because although I know a great deal about hash functions (I teach them) and a little about cryptography (I've taken pretty much every database class they have at OSU), this is beyond my area of knowledge. My intuition is that you can average m+3 and m+4 to get (16 + 32) / 2 = 24, but I have nothing to back that up with.
- Okay I think I might have another idea. Here it is:
,
since and
So , and
.
Now do you know any probability bound I can use to get the result with probability at least ?
- Actually thanks for your suggestion Annatala, it finally lead me to the final solution. From my above post, we just continue on to find the variance of |T|, then apply Chebyshev's inequality to get the final result. If you are interested in the formal proof, I could send it to you.
Anyway, thanks again mate.
-Peter