Exercise 11.5.1

$\star$ Suppose that we insert $n$ keys into a hash table of size $m$ using open addressing and uniform hashing. Let $p(n,m)$ be the probability that no collisions occur. Show that $p(n, m) \le e^{-n(n-1)/2m}$. (Hint: see equation (3.12).) Argue that when $n$ exceeds $\sqrt{m}$, the probability of avoiding collisions goes rapidly to zero.

Equation (3.12) states that:

$$ e^x \ge 1 + x $$

Let's observe that:

$$ p(n, m) = \frac{m}{m} \cdot \frac{m-1}{m} \cdots \frac{m-n+1}{m} = \frac{m!}{n!m^n} $$

And that

$$ p(k + 1, m) = p(k, m) \cdot \frac{m - k}{m} = p(k, m) \cdot \left(1 - \frac{k}{m} \right) $$

Let's prove $p(n, m) \le e^{-n(n-1)/2m}$ by induction, fixing $m$ and treating $k = n$ as a variable.

For $n = 1$:

$$ p(1, m) = 1 \le e^{0} = 1 $$

If we assume the inequality holds for $k$, then for $k - 1$ we have:

$$ \begin{aligned} p(k + 1, m) &= p(k, m) \cdot \left( 1 - \frac{k}{m} \right) \\ &\le e^{-k(k-1)/2m} \cdot \left( 1 - \frac{k}{m} \right) \\ &\le e^{-k(k-1)/2m} \cdot e^{-k/m} \\ &= e^{-k(k-1)/2m - k/m} \\ &= e^{-k(k-1)/2m - 2k/2m} \\ &= e^{-(k(k-1) + 2k)/2m} \\ &= e^{-k(k+1)/2m} \\ \end{aligned} $$

As for the "rapidly goes to zero" part, observe that if we rewrite the equation a bit, we get:

$$ pr(n, m) = \frac{1}{e^{n(n-1)/2m}} $$

And that if $n \ge \sqrt{m}$ the power in the denominator becomes greater than 1, at which point it starts rapidly (exponentially) growing, and the fraction starts rapidly (exponentially) approaching zero.