TAOCP 6.4 Exercise 37

We consider a hash table with \(M\) buckets using separate chaining.

taocpmathematicsalgorithmsvolume-3math-hard

Section 6.4: Hashing

Exercise 37. ▶ [M29] Equation (19) gives the average number of probes in separate chaining when the search is successful; what is the variance of that number of probes?

Verified: no
Solve time: 2m31s

Setup

We consider a hash table with (M) buckets using separate chaining. (N) keys are inserted, and the hash function distributes keys uniformly so that each of the (M^N) hash sequences is equally likely. For a successful search, we choose one of the (N) keys uniformly at random and count the number of probes (list elements examined) until it is found. The lists are unordered, so given the bucket sizes the position of a key in its list is uniformly distributed over the length of that list.

Let (X_i) be the number of keys in bucket (i) ((1 \le i \le M)); then (\sum_{i=1}^M X_i = N). The random vector ((X_1,\dots,X_M)) follows a multinomial distribution with parameters (N) and (p_i = 1/M).

Equation (19) of the text gives the average number of probes for a successful search: [ E[P] = 1 + \frac{N-1}{2M}. ]

Solution

We compute the variance (\operatorname{Var}(P) = E[P^2] - (E[P])^2). First we find (E[P^2]) by conditioning on the bucket sizes.

Given (X_1,\dots,X_M), a random key falls into bucket (i) with probability (X_i/N), and its position is uniformly distributed on ({1,\dots,X_i}). Hence [ E[P^2 \mid X] = \frac{1}{N}\sum_{i=1}^M \sum_{j=1}^{X_i} j^2 = \frac{1}{N}\sum_{i=1}^M \frac{X_i(X_i+1)(2X_i+1)}{6}. ]

Taking the expectation over the multinomial distribution, [ E[P^2] = \frac{1}{6N},E!\left[ \sum_{i=1}^M \bigl(2X_i^3 + 3X_i^2 + X_i\bigr) \right]. ]

We need the first three moments of the sum of powers of (X_i). For a single multinomial category, (X_i \sim \operatorname{Binomial}(N, 1/M)), so [ \begin{aligned} E[X_i] &= \frac{N}{M},\[2pt] E[X_i^2] &= \frac{N}{M} + \frac{N(N-1)}{M^2},\[2pt] E[X_i^3] &= \frac{N}{M} + \frac{3N(N-1)}{M^2} + \frac{N(N-1)(N-2)}{M^3}. \end{aligned} ]

Summing over (i = 1,\dots,M) gives [ \begin{aligned} E!\left[\sum_{i=1}^M X_i\right] &= N,\[2pt] E!\left[\sum_{i=1}^M X_i^2\right] &= N + \frac{N(N-1)}{M},\[2pt] E!\left[\sum_{i=1}^M X_i^3\right] &= N + \frac{3N(N-1)}{M} + \frac{N(N-1)(N-2)}{M^2}. \end{aligned} ]

Substituting these into the expression for (E[P^2]): [ \begin{aligned} E[P^2] &= \frac{1}{6N}\left[ 2!\left(N + \frac{3N(N-1)}{M} + \frac{N(N-1)(N-2)}{M^2}\right) \right. \ &\qquad \left. + 3!\left(N + \frac{N(N-1)}{M}\right) + N \right] \[4pt] &= \frac{1}{6N}\left[ 2N + \frac{6N(N-1)}{M} + \frac{2N(N-1)(N-2)}{M^2} + 3N + \frac{3N(N-1)}{M} + N \right] \[4pt] &= \frac{1}{6N}\left[ 6N + \frac{9N(N-1)}{M} + \frac{2N(N-1)(N-2)}{M^2} \right] \[4pt] &= 1 + \frac{3}{2},\frac{N-1}{M} + \frac{1}{3},\frac{(N-1)(N-2)}{M^2}. \end{aligned} ]

Now (E[P] = 1 + \frac{N-1}{2M}), so [ (E[P])^2 = 1 + \frac{N-1}{M} + \frac{(N-1)^2}{4M^2}. ]

Therefore the variance is [ \begin{aligned} \operatorname{Var}(P) &= \left(1 + \frac{3}{2}\frac{N-1}{M} + \frac{1}{3}\frac{(N-1)(N-2)}{M^2}\right)

  • \left(1 + \frac{N-1}{M} + \frac{(N-1)^2}{4M^2}\right) \[4pt] &= \frac{1}{2}\frac{N-1}{M}
  • \left(\frac{1}{3}(N-1)(N-2) - \frac{1}{4}(N-1)^2\right)\frac{1}{M^2} \[4pt] &= \frac{N-1}{2M} + (N-1)\frac{4(N-2) - 3(N-1)}{12M^2} \[4pt] &= \frac{N-1}{2M} + \frac{(N-1)(N-5)}{12M^2}. \end{aligned} ]

[ \boxed{\operatorname{Var}(P) = \frac{N-1}{2M} + \frac{(N-1)(N-5)}{12M^2}} ]

Verification

  1. Boundary (N=1): Both terms vanish, giving variance (0), which is correct because a single key always requires exactly one probe.

  2. Boundary (M=1): All keys are in one bucket; the number of probes is uniformly distributed on ({1,\dots,N}). The variance of this uniform distribution is ((N^2-1)/12). Our formula gives [ \frac{N-1}{2} + \frac{(N-1)(N-5)}{12} = \frac{6(N-1) + (N-1)(N-5)}{12} = \frac{(N-1)(N+1)}{12} = \frac{N^2-1}{12}, ] which matches.

  3. Small case (N=2, M=2): Enumerating the (4) equally likely hash sequences yields [ P(P=1) = \frac{3}{4},\quad P(P=2) = \frac{1}{4},\quad E[P] = \frac{5}{4},\quad E[P^2] = \frac{7}{4},\quad \operatorname{Var}(P) = \frac{3}{16}. ] The formula gives (\frac{1}{4} + \frac{1\cdot(-3)}{48} = \frac{12}{48} - \frac{3}{48} = \frac{9}{48} = \frac{3}{16}), confirming the result.

All checks are consistent, so the derivation is correct.

This completes the proof. ∎