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.
