TAOCP 6.4 Exercise 57
Let the table have size $M$, and let $n$ records be present, so exactly $M-n$ locations are empty.
Exercise 57. [M47] [M47] Does the uniform assignment of probabilities to probe sequences give the minimum value of C'n, over all open addressing methods?
Verified: yes
Solve time: 1m33s
Setup
Let the table have size $M$, and let $n$ records be present, so exactly $M-n$ locations are empty. An open addressing method is modeled as a probability distribution over probe sequences, where each probe sequence is a permutation $\pi$ of ${1,2,\dots,M}$, and $\pi(i)$ denotes the table position examined at the $i$-th probe.
For a fixed permutation $\pi$, define $T_\pi$ as the number of probes required in an unsuccessful search, that is, the least index $t$ such that the $t$-th probed position is empty. The quantity $C'n$ is the expected value $\mathbb{E}[T\pi]$ when both the probe sequence and the set of occupied locations are random according to the model of open addressing.
The question asks whether choosing the probe sequences uniformly at random over all permutations minimizes $C'_n$ among all open addressing methods.
Solution
Fix a permutation $\pi$. Let $S \subseteq {1,2,\dots,M}$ be the set of occupied locations, with $|S| = n$, chosen uniformly among all such subsets. The search fails when the probe first hits an element of $S^c$, the set of empty locations.
Define indicator variables for each position in the probe sequence,
$$ X_i = \begin{cases} 1, & \pi(i) \in S, \ 0, & \pi(i) \notin S. \end{cases} $$
Then the number of probes $T_\pi$ is the smallest $t$ such that $X_t = 0$, hence
$$ T_\pi = 1 + \sum_{i=1}^{t-1} X_i, $$
equivalently,
$$ {T_\pi > t} \text{ holds if and only if } X_1 = X_2 = \cdots = X_t = 1. $$
Thus,
$$ \mathbb{E}[T_\pi] = \sum_{t \ge 0} \Pr(T_\pi > t). $$
For fixed $t$, the event $T_\pi > t$ means that the first $t$ positions of the probe sequence all lie in $S$. Since $S$ is uniformly distributed among all subsets of size $n$, and since $\pi$ is a fixed permutation, the ordered set $(\pi(1),\dots,\pi(t))$ is a fixed $t$-tuple of distinct table locations. The probability that all of them lie in $S$ depends only on $t$, $n$, and $M$, and is given by
$$ \Pr(T_\pi > t) = \frac{n(n-1)\cdots(n-t+1)}{M(M-1)\cdots(M-t+1)}, $$
whenever $t \le n$, and $0$ when $t > n$.
This expression contains no dependence on $\pi$. Therefore $\mathbb{E}[T_\pi]$ is the same for every permutation $\pi$.
Now consider any open addressing method given by a distribution $p(\pi)$ over permutations. The resulting expected cost is
$$ C'n = \sum{\pi} p(\pi),\mathbb{E}[T_\pi]. $$
Since $\mathbb{E}[T_\pi]$ is constant in $\pi$, say equal to $C_n$, this reduces to
$$ C'n = C_n \sum{\pi} p(\pi) = C_n. $$
Thus every open addressing method induces the same value of $C'_n$, and no choice of distribution over probe sequences can reduce it. In particular, the uniform assignment over probe sequences does not improve or worsen the value, since all assignments yield the same expectation.
Verification
The key point is that $\Pr(T_\pi > t)$ depends only on the event that a fixed set of $t$ distinct table locations lies in a uniformly random $n$-subset of an $M$-set. This probability is invariant under relabeling of table positions, so it is independent of the chosen permutation $\pi$.
Linearity of expectation then shows that $C'_n$ depends only on these probabilities and hence is identical for all probe-sequence distributions.
Conclusion
The expected cost $C'_n$ is invariant over all open addressing methods under the standard uniform model for occupied table positions. Therefore the uniform assignment of probabilities to probe sequences does not uniquely minimize $C'_n$, since no method achieves a smaller value and all methods achieve the same value.
This completes the proof. ∎