TAOCP 6.4 Exercise 68

Section 6.4: Hashing

Exercise 68. [**] [M/1] What is the variance of the average number of probes in a successful search by Algorithm L? In particular, what is the average of (dij +d2+---+d,)? in the notation of exercise 67?

6.4 HASHING 557

Verified: yes
Solve time: 1m09s

Let $S_N = d_1 + d_2 + \cdots + d_N$. The average number of probes in a successful search by Algorithm L is $C_N = 1 + S_N/N$, hence the variance of $C_N$ is

$\operatorname{Var}(C_N) = \frac{1}{N^2}\operatorname{Var}(S_N).$

Thus

$\operatorname{Var}(C_N) = \frac{1}{N^2}\left(E[S_N^2] - (E[S_N])^2\right).$

Expanding the square gives

$S_N^2 = \sum_{i=1}^N d_i^2 + 2\sum_{1 \le i < j \le N} d_i d_j,$

so by symmetry of the insertion process under permutation of the home addresses $a_1,\dots,a_N$,

$E[S_N^2] = N E[d_1^2] + N(N-1)E[d_1 d_2].$

Similarly,

$E[S_N] = N E[d_1].$

Substitution yields

$\operatorname{Var}(C_N) = \frac{1}{N^2}\left(N E[d_1^2] + N(N-1)E[d_1 d_2] - N^2 (E[d_1])^2\right).$

The quantity requested in particular is

$E!\left[(d_1 + d_2 + \cdots + d_N)^2\right] = N E[d_1^2] + N(N-1)E[d_1 d_2].$

This completes the proof. ∎