TAOCP 6.4 Exercise 74
Let $H$ be a matrix whose rows are hash functions $h : \mathcal{K} \to {0,1,\dots,M-1}$, and whose columns correspond to keys.
Exercise 74. [M29] [M29] Let H define a universal family of hash functions. Prove or disprove: Given any N distinct columns, and any row chosen at random, the expected number of zeros in those columns is O(1) + O(N/M). [Thus, every list in the method of separate chaining will have this expected size.]
Verified: yes
Solve time: 1m16s
Setup
Let $H$ be a matrix whose rows are hash functions $h : \mathcal{K} \to {0,1,\dots,M-1}$, and whose columns correspond to keys. The family is universal in the sense that for any two distinct keys $K \neq K'$, the number of rows $r$ for which
$$ h_r(K) = h_r(K') $$
is at most $R/M$. A hash function $h$ is chosen by selecting a row uniformly at random from the $R$ rows.
Fix a set of $N$ distinct keys $K_1, K_2, \dots, K_N$. For a fixed key $K_i$, consider the list of all keys that collide with $K_i$ under the chosen hash function. The goal is to bound the expected size of this list by $O(1) + O(N/M)$, equivalently to prove a bound of the form
$$ \mathbb{E}[X_i] \le 1 + \frac{N-1}{M}, $$
where $X_i$ is the number of keys mapped to the same hash value as $K_i$.
Solution
Fix an index $i$ with $1 \le i \le N$. Define indicator random variables
$$ I_{ij} = \begin{cases} 1 & \text{if } h(K_i) = h(K_j), \ 0 & \text{otherwise}, \end{cases} $$
for $j = 1,2,\dots,N$.
The size of the list containing $K_i$ equals
$$ X_i = \sum_{j=1}^N I_{ij}. $$
Taking expectation and using linearity,
$$ \mathbb{E}[X_i] = \sum_{j=1}^N \mathbb{E}[I_{ij}] = \sum_{j=1}^N \Pr[h(K_i)=h(K_j)]. $$
For $j=i$, the event $h(K_i)=h(K_i)$ holds for every row, hence $\Pr[h(K_i)=h(K_i)] = 1$.
For $j \neq i$, universality implies that the number of rows in which $K_i$ and $K_j$ agree is at most $R/M$. Since the hash function is chosen uniformly among the $R$ rows,
$$ \Pr[h(K_i)=h(K_j)] \le \frac{R/M}{R} = \frac{1}{M}. $$
Substituting into the expectation,
$$ \mathbb{E}[X_i] \le 1 + \sum_{\substack{j=1 \ j \neq i}}^N \frac{1}{M} = 1 + \frac{N-1}{M}. $$
Thus,
$$ \mathbb{E}[X_i] = O(1) + O!\left(\frac{N}{M}\right). $$
This completes the proof. ∎
Verification
Each step uses only the definition of indicator variables and linearity of expectation. The bound $\Pr[h(K_i)=h(K_j)] \le 1/M$ follows directly from the universality condition that at most $R/M$ of the $R$ rows cause a collision between any fixed pair of distinct keys. No additional assumptions about uniformity of individual hash values are required.
Notes
The same argument applies to any fixed hash value $y \in {0,1,\dots,M-1}$ by replacing the condition $h(K_i)=h(K_j)$ with membership in a fixed bucket. The resulting estimate gives the standard expected chain length bound for separate chaining under universal hashing.