Homework 6 Optional Problems

Recall that a set 𝐻 of hash functions (mapping the elements of a universe 𝑈 to the buckets {0,1,2,...,𝑛 −1}) is universal if for every distinct 𝑥,𝑦 ∈𝑈, the probability 𝑃⁢𝑟⁢𝑜⁢𝑏⁡[ℎ⁡(𝑥) =ℎ⁡(𝑦)] that 𝑥 and 𝑦 collide, assuming that the hash function ℎ is chosen uniformly at random from 𝐻, is at most 1𝑛. In this problem you will prove that a collision probability of 1𝑛 is essentially the best possible. Precisely, suppose that 𝐻 is a family of hash functions mapping 𝑈 to {0,1,2,...,𝑛 −1}, as above. Show that there must be a pair 𝑥,𝑦 ∈𝑈 of distinct elements such that, if ℎ is chosen uniformly at random from 𝐻, then 𝑃⁢𝑟⁢𝑜⁢𝑏⁡[ℎ⁡(𝑥) =ℎ⁡(𝑦)] ≥1𝑛 −1|𝑈|

ANSWER: Let 𝑛𝑖 be the size of the set {𝑥 :𝑥 ∈𝑈,ℎ⁡(𝑥) =𝑖}, for 𝑖 ∈{0,1,2,...,𝑛 −1}. That is, ℎ1 maps inputs to bucket 1, ℎ2 maps inputs to bucket 2, and so on.

• Let us fix a hash function ℎ ∈𝐻.
• Let 𝑁 =|𝑈|.
• Given 𝑛 = number of buckets.

Then, the number of distinct 𝑥1,𝑥2 ∈𝑈 that collide in bucket 1 is (𝑛𝑖2). The number of distinct 𝑥1,𝑥2 ∈𝑈 that collide in all buckets is, therefore, ∑𝑛𝑖=1(𝑛𝑖2) (call this expression 𝐿ℎ). Note that 𝑛𝑖 ≥0 and ∑𝑛𝑖=1𝑛𝑖 =𝑁. We are interested in lower-bounding the expression 𝐿ℎ.

It can be shown that the summation is minimized when all 𝑛𝑖 are equal, that is, when 𝑛𝑖 =𝑁𝑛 ^{1 2}. Therefore, we get:

Suppose 𝐻 ={ℎ1,ℎ2,...,ℎ𝑘} and |𝐻| =𝐾. Let us define 𝑃 be the set of all distinct 𝑥1,𝑥2 ∈𝑈. Note that |𝑃| =𝑁⁢(𝑁−1)2. Let 𝑋𝑖 be an indicator random variable, such that, given a hash function ℎ𝑖 ∈𝐻 and distinct 𝑥1,𝑥2 ∈𝑈:

Taking expectation of 𝑋𝑖:

By the Pigeon hole Principle, we get: There exists 𝑥,𝑦 ∈𝑈 such that the above inequality holds.

ReferencesPermalink