TAOCP 6.4 Exercise 40
We analyze Algorithm C (chaining) with a hash table of \(M\) lists and \(N\) keys already inserted.
Exercise 40. [M33] Equation (15) gives the average number of probes used by Algorithm C in an unsuccessful search; what is the variance of that number of probes?
554 SEARCHING 6.4
Verified: no
Solve time: 3m51s
Setup
We analyze Algorithm C (chaining) with a hash table of (M) lists and (N) keys already inserted. The hash function assigns each key uniformly and independently to one of the (M) lists. For an unsuccessful search we consider a new key (K) not present in the table; its hash value (h(K)) is uniformly distributed over the (M) lists and independent of the hash values of the (N) inserted keys. The number of probes (X) is the number of keys in the list that (K) hashes to (if the initial list header access is counted as a probe, the total is (1+X); the variance is unchanged).
Solution
For (i = 1,\dots,N) let (I_i) be the indicator that the (i)-th inserted key has the same hash value as (K). Because the hash values are independent and uniform, [ \Pr(I_i = 1) = \frac{1}{M}, ] and the indicators (I_1,\dots,I_N) are independent. Hence [ X = \sum_{i=1}^N I_i ] follows a binomial distribution with parameters (N) and (p = 1/M). The mean is (\mathbb{E}[X] = N/M) (which agrees with Equation (15) up to the possible additive constant 1). The variance of a binomial random variable is [ \operatorname{Var}(X) = N p (1-p) = N \cdot \frac{1}{M} \cdot \left(1 - \frac{1}{M}\right) = \frac{N(M-1)}{M^2}. ] If Equation (15) defines the number of probes as (1+X), the variance remains (\frac{N(M-1)}{M^2}).
[ \boxed{\frac{N(M-1)}{M^2}} ]
Verification
We recompute the variance directly from the definition. Since (X = \sum I_i), [ \mathbb{E}[X^2] = \sum_i \mathbb{E}[I_i] + \sum_{i \ne j} \mathbb{E}[I_i I_j] = N \cdot \frac{1}{M} + N(N-1) \cdot \frac{1}{M^2}. ] Then [ \operatorname{Var}(X) = \mathbb{E}[X^2] - (\mathbb{E}[X])^2 = \frac{N}{M} + \frac{N(N-1)}{M^2} - \frac{N^2}{M^2} = \frac{N}{M} - \frac{N}{M^2} = \frac{N(M-1)}{M^2}. ] Boundary checks: (N=0) gives variance (0); (M=1) gives variance (0) (all keys fall in the single list, so (X=N) deterministically); (M \to \infty) gives variance (\to 0). All are consistent with the formula.
This completes the proof. ∎