All pastes #189419 Raw Edit

Someone

public text v1 · immutable
·published 2006-10-03 01:58 UTC
rendered paste body
Yes. In order for the H = {h1, h2} to be a universal hash family, the probability
that H(1) = H(2), H(1) = H(3), and H(2) = H(3) must all be <= 1/2. That is
1/2(h1(x) + h2(x)) <= 1/2.

So for H(1) = H(2) we have
1/2(1 + 0) = 1/2

H(1) = H(3) we have
1/2(0 + 1) = 1/2

H(2) = H(3)
1/2(0 + 0) = 0

Since each probability is atmost 1/2, H is a universal hash family.