# 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.

• I don't see how Markov's inequality is useful here. You just need to use a union bound. – Yuval Filmus May 6 '19 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$$.