TAOCP 6.4 Exercise 64
Let $M$ be the table size and $\alpha=n/M$.
Exercise 64. [**] [M/1] Analyze the expected behavior of Algorithm R (deletion with linear probing). How many times will step R4 be performed, on the average?
Verified: yes
Solve time: 2m41s
Let $M$ be the table size and $\alpha=n/M$. Work in the standard linear probing model with uniform hashing, where the occupancy of the table can be approximated by a cyclic sequence of independent Bernoulli trials with
$$ \Pr{\text{occupied}}=\alpha,\qquad \Pr{\text{empty}}=1-\alpha. $$
1. What Algorithm R actually measures
In Algorithm R, step R4 scans forward from the deletion position through consecutive occupied cells until the first empty cell is encountered.
Let $L$ denote the length of the occupied block (cluster segment) encountered starting from the deletion position. Then the number of executions of R4 is exactly $L$, since R4 is performed once per occupied cell in the run before the first empty cell stops the scan.
The key point is that the deletion position is not a uniformly random table position. It is a uniformly random occupied position, hence it lies inside a run of occupied cells. This induces a size-biased distribution on run lengths.
Thus we must compute:
$$ \mathbb{E}[R4] = \mathbb{E}[L \mid \text{a uniformly chosen occupied cell}]. $$
2. Distribution of run lengths
In the Bernoulli model, the lengths of maximal runs of occupied cells between empty cells are geometrically distributed.
If $L$ is the length of an occupied run (starting immediately after an empty cell), then
$$ \Pr{L=k} = (1-\alpha)\alpha^{k-1}, \qquad k \ge 1. $$
Hence
$$ \mathbb{E}[L] = \frac{1}{1-\alpha}, \qquad \mathbb{E}[L^2] = \frac{1+\alpha}{(1-\alpha)^2}. $$
3. Size bias induced by choosing a random occupied cell
A uniformly random occupied cell lies in a run of length $k$ with probability proportional to $k$. Therefore the relevant distribution is the size-biased version:
$$ \Pr{L^\ast = k} = \frac{k \Pr{L=k}}{\mathbb{E}[L]}. $$
Its expectation is
$$ \mathbb{E}[L^\ast] = \frac{\mathbb{E}[L^2]}{\mathbb{E}[L]}. $$
Substituting the moments computed above gives
$$ \mathbb{E}[L^\ast] = \frac{\frac{1+\alpha}{(1-\alpha)^2}}{\frac{1}{1-\alpha}} = \frac{1+\alpha}{1-\alpha}. $$
4. Expected number of executions of R4
Since R4 is executed once per occupied cell in the run encountered from the deletion point, we have
$$ \mathbb{E}[R4] = \mathbb{E}[L^\ast]. $$
Therefore,
$$ \boxed{\mathbb{E}[R4] = \frac{1+\alpha}{1-\alpha}}. $$
5. Why the unsuccessful-search analogy fails
The previous solution incorrectly replaced this quantity by the cost of an unsuccessful search. That comparison fails because:
- unsuccessful search starts from a uniformly random table position,
- Algorithm R starts from a uniformly random occupied position,
so the second case is size-biased toward longer runs. This changes the first moment from $\mathbb{E}[L]$ to $\mathbb{E}[L^2]/\mathbb{E}[L]$, which is strictly larger and has a different dependence on $\alpha$.
The correct expectation must therefore be computed via size-biased run lengths, not probe sequences of unsuccessful search.