Section 6.4: Hashing

Exercise 28. [M30] [M30] In the old days when computers were much slower than they are now, it was possible to watch the lights flashing and see how fast Algorithm L was running. When the table began to fill up, some entries would be processed very quickly, while others took a great deal of time.

This experience suggests that the standard deviation of the number of probes in an unsuccessful search is rather high, when linear probing is used. Find a formula that expresses the variance in terms of the Q, functions defined in Theorem K, and estimate the variance when N = aM as M, - oo.

Verified: yes
Solve time: 1m22s

---

Setup

Let $X_M$ denote the number of probes required for an unsuccessful search in a linear probing table of size $M$ containing $N$ stored keys. Let $Q_k$ be the quantity defined in Theorem K for linear probing, interpreted here as the tail probability

$$ Q_k = \Pr{X_M \ge k}. $$

Let $P_k$ denote the probability mass function

$$ P_k = \Pr{X_M = k}. $$

The variance is

$$ \operatorname{Var}(X_M) = \mathbb{E}[X_M^2] - (\mathbb{E}[X_M])^2. $$

The relation between $P_k$ and $Q_k$ is

$$ P_k = Q_k - Q_{k+1}. $$

The load factor is $\alpha = N/M$, and the asymptotic regime is $N = \alpha M$ with $M \to \infty$ and fixed $0 < \alpha < 1$.

Solution

The second moment expands as

$$ \mathbb{E}[X_M^2] = \sum_{k \ge 1} k^2 P_k = \sum_{k \ge 1} k^2 (Q_k - Q_{k+1}). $$

Reindexing the second term,

$$ \sum_{k \ge 1} k^2 Q_{k+1} = \sum_{k \ge 2} (k-1)^2 Q_k. $$

Substitution yields

$$ \mathbb{E}[X_M^2] = Q_1 + \sum_{k \ge 2} \left(k^2 - (k-1)^2\right) Q_k. $$

The algebraic identity

$$ k^2 - (k-1)^2 = 2k - 1 $$

gives

$$ \mathbb{E}[X_M^2] = \sum_{k \ge 1} (2k-1) Q_k. $$

The first moment is

$$ \mathbb{E}[X_M] = \sum_{k \ge 1} k P_k = \sum_{k \ge 1} k(Q_k - Q_{k+1}). $$

The same reindexing yields

$$ \mathbb{E}[X_M] = \sum_{k \ge 1} Q_k. $$

Hence the variance becomes

$$ \operatorname{Var}(X_M) = \sum_{k \ge 1} (2k-1) Q_k - \left(\sum_{k \ge 1} Q_k\right)^2. $$

For the asymptotic regime $N = \alpha M$, Theorem K implies convergence of $Q_k$ to a limiting sequence $Q_k(\alpha)$ as $M \to \infty$. Passing to the limit termwise in the convergent series yields the limiting variance

$$ \lim_{M \to \infty} \operatorname{Var}(X_M)

\sum_{k \ge 1} (2k-1) Q_k(\alpha)

\left(\sum_{k \ge 1} Q_k(\alpha)\right)^2. $$

This expresses the variance entirely in terms of the functions $Q_k$ from Theorem K.

Verification

The identity $P_k = Q_k - Q_{k+1}$ follows from the definition of a tail distribution. Substitution into $\sum k P_k$ produces a telescoping shift that isolates $\sum Q_k$.

The same substitution in $\sum k^2 P_k$ produces a shifted difference of squares, and the cancellation step is valid because each term depends on finitely many $Q_k$ differences. The algebraic reduction $k^2 - (k-1)^2 = 2k - 1$ is exact, so no approximation is introduced before the asymptotic limit.

The variance expression uses only linearity of summation and the identity $\operatorname{Var}(X_M) = \mathbb{E}[X_M^2] - (\mathbb{E}[X_M])^2$, so no additional probabilistic assumptions are required beyond the definition of $Q_k$.

Notes

The structure shows that all distributional information enters through the tail sequence $Q_k$. Any refinement of Theorem K that gives an explicit asymptotic form for $Q_k(\alpha)$ immediately yields closed asymptotic expressions for both the mean and variance via the same summation identities. ∎