Prove the probability of which a hash function is collision-free 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.
For every $i &lt; 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 &lt; j \leq M$ is $M(M-1)/2 &lt; 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 &lt; 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$.