TAOCP 6.4 Exercise 63
Let the hash table have $M$ locations.
Exercise 63. [M25] [M25] If repeated random insertions and deletions are made in a hash table, how many independent insertions are needed on the average before all M locations have become occupied at one time or another? (This is the mean time to failure of the deletion method that simply marks cells “deleted.”)
Verified: yes
Solve time: 1m12s
Solution
Let the hash table have $M$ locations. Each independent insertion selects a location uniformly from ${1,2,\dots,M}$, independently of previous insertions. Deletions are irrelevant for the event described, since a location that has once been occupied remains “used” in the sense of contributing to the failure condition.
The process fails when every location has been occupied at least once. This is the classical coupon collector condition with $M$ coupons.
Let $T$ be the number of insertions required until all $M$ locations have been occupied at least once.
For $k$ with $1 \le k \le M$, suppose exactly $k-1$ distinct locations have already been hit. The probability that the next insertion hits a new location is
$$ \frac{M-(k-1)}{M}. $$
Hence the waiting time $X_k$ until the $k$-th new location appears is a geometric random variable with mean
$$ \mathbb{E}[X_k] = \frac{1}{(M-k+1)/M} = \frac{M}{M-k+1}. $$
The total time satisfies
$$ T = X_1 + X_2 + \cdots + X_M. $$
Taking expectations and using linearity,
$$ \mathbb{E}[T] = \sum_{k=1}^M \frac{M}{M-k+1}. $$
Reindexing with $j = M-k+1$ gives
$$ \mathbb{E}[T] = \sum_{j=1}^M \frac{M}{j} = M \sum_{j=1}^M \frac{1}{j}. $$
Thus
$$ \mathbb{E}[T] = M H_M, $$
where $H_M = \sum_{j=1}^M \frac{1}{j}$ is the $M$-th harmonic number.
Using the standard asymptotic expansion of harmonic numbers,
$$ H_M = \ln M + \gamma + \frac{1}{2M} + O!\left(\frac{1}{M^2}\right), $$
so
$$ \mathbb{E}[T] = M \ln M + \gamma M + \frac{1}{2} + O!\left(\frac{1}{M}\right). $$
Therefore the mean number of independent insertions required before all $M$ locations have been occupied at least once is
$$ \boxed{M H_M}. $$
This completes the proof. ∎