Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

a busy cat So I tried doing this proof but I do not know how to start it properly.

I know I have to show that the hash function family has the consistent and random property. The first is rather obvious to show. The second requires that before fixing the matrix M the probability of two distinct vectors x and y to be mapped to the same index m(x) = m(y) is equal to the probability of them assigned to the same index, when indices m(x) and m(y) are sampled uniformly at random.

Also how to show to if the hash function has the consistent and random property

share|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.