2-universal hash functions, which have collision probability 1/n for any two items. A k-universal hash...

Transcribed Image Text:

2-universal hash functions, which have collision probability ≤ 1/n for any two items. A k-universal hash function h: U → [n] is any random hash function that satisfies, for any inputs x1, ..., xk € U, Pr[h(x1) = h(x2) = . . . = h(xk)] s 1 nk-1. 1. (2 points) Suppose you hash n balls into n hash buckets using a 2-universal hash function. Show that for t = 5n, the number of pairwise collisions exceeds t with probability at most 1/10. 2. (2 points) Use the above to argue that for t = 4√ n, that the maximum load on any bin exceeds t with probability at most 1/10. Hint: Don't use a union bound. 3. (2 points) Generalize this result to k-universal hash functions for k> 2. Show that if t = cn1/k for large enough constant c, that the probability of the maximum load exceeding t at most 1/10. Hint: Instead of pairwise collisions, consider the expected number of k-wise collisions. 2-universal hash functions, which have collision probability ≤ 1/n for any two items. A k-universal hash function h: U → [n] is any random hash function that satisfies, for any inputs x1, ..., xk € U, Pr[h(x1) = h(x2) = . . . = h(xk)] s 1 nk-1. 1. (2 points) Suppose you hash n balls into n hash buckets using a 2-universal hash function. Show that for t = 5n, the number of pairwise collisions exceeds t with probability at most 1/10. 2. (2 points) Use the above to argue that for t = 4√ n, that the maximum load on any bin exceeds t with probability at most 1/10. Hint: Don't use a union bound. 3. (2 points) Generalize this result to k-universal hash functions for k> 2. Show that if t = cn1/k for large enough constant c, that the probability of the maximum load exceeding t at most 1/10. Hint: Instead of pairwise collisions, consider the expected number of k-wise collisions.

Answer rating: 100% (QA)

The detailed answer for the above question is provided below 1 Let the probability of a pair ... View the full answer