Prove the probability of which a hash function is collision-free
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$.