Suppose $H = \{h_1, ..., h_T\}$ be a family of pairwise independent hash functions mapping $\{0, 1\}^n$ to $\{0, 1\}^{n/2}$. Let $M = \frac{2^{n/4}}{10}$ and let $x_1, ..., x_M$ be any M distinct points in $\{0, 1\}^n$. If we choose $h$ randomly form $H$ and let $E$ be the event that $h(x_1), ..., h(x_M)$ are all distinct. We need to show that $Pr[E] \ge \frac{3}{4}$.

$\textbf{Markove's inequality:}$ If $X$ is a random variable which only takes non-negative values then, for any $t \ge 0$, $Pr[X \ge t] \leq E[X]/t$.

The idea is to compute $Pr[h(x_i) = h(x_j)]$, compute the expectation of the random variable $Z = |\{(i,j) : h(x_i) = h(x_j)\}|$ and use the Markove's inequality to prove the question.

For two independent points $x_i$ and $x_j$, the probability that $h(x_i)$ and $h(x_j)$ are equal is $1 - \{\text{the probability two independent points has the different hash values}\}$, which is $1 - \frac{2^{n/2}}{2^{n/2}}\cdot \frac{2^{n/2} - 1}{2^{n/2}}$. That shows $Pr[h(x_i) = h(x_j)] = \frac{1}{2^{n/2}}$.

As for the random variable $Z$, maybe we can let $Z_{i,j} = 1 \text{ if }h(x_i) = h(x_j)$. Otherwise, $Z_{i,j} = 0$. Then we can get $Pr(Z_{(i,j)}) = \frac{1}{2^{n/2}}$. This is where I stuck. I know how to compute the expectation the single random variable, which is $\sum_{i=1}^{n} x_i P(X = x_i)$. But I have no idea how to expand this formula to the pair random variable $(i,j)$. Also I am a little confused how Markove's Inequality could be used in this proof.

Could someone give me some hints? Any help would be appreciated. Thanks in advance.

  • $\begingroup$ I don't see how Markov's inequality is useful here. You just need to use a union bound. $\endgroup$ – Yuval Filmus May 6 at 1:11

For every $i < j$, the probability that $h(x_i) = h(x_j)$ is at most $2^{-n/2}$. The number of pairs of indices $1 \leq i < j \leq M$ is $M(M-1)/2 < M^2/2 = 2^{n/2}/200$, hence a union bound implies that the probability that $h(x_i) = h(x_j)$ for some pair $i < j$ is at most $$ 2^{n/2}/200 \cdot 2^{-n/2} = 1/200. $$ It follows that the probability that $h(x_1),\ldots,h(x_M)$ are all distinct is at least $199/200$.

  • $\begingroup$ Thanks for your comment! It is very clear. $\endgroup$ – user4565515 May 6 at 1:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.