TAOCP 6.4 Exercise 61
The error in the previous solution is the assumption that column-wise uniformity of the permutations implies optimality of all coefficients $c_k$.
Exercise 61. [M46] [M46] Is the method analyzed in exercise 46 the worst possible single-hashing scheme, in the sense of exercise 60?
Verified: no
Solve time: 4m39s
The error in the previous solution is the assumption that column-wise uniformity of the permutations implies optimality of all coefficients $c_k$. This is insufficient because $c_k$ depends on joint behavior of the first $k$ probes, not on each probe separately. The correct argument must use the full combinatorial structure of the construction in Exercise 6.4.46.
Correct solution
Let $a = n/M$ and let $C_a$ denote the expected number of probes in a successful search under a single-hashing scheme.
Exercise 6.4.60 gives the expansion
$$ C_a = 1 + \sum_{k \ge 1} c_k a^k, $$
together with the sharp upper bounds
$$ c_k \le \frac{1}{k+1}, $$
where equality holds exactly when the probing process behaves, up to order $k$, like uniform probing in the sense that every ordered pattern of $k$ distinct probe locations occurs with equal probability.
The key point is that $c_k$ is determined by events of the form
$$ {\text{the first } k \text{ probes all hit occupied cells}}, $$
which depend on the joint distribution of
$$ (\pi_i(1), \dots, \pi_i(k)), $$
not on the marginal distribution of each $\pi_i(t)$.
Thus, to prove optimality, it is necessary and sufficient to show that the construction in Exercise 6.4.46 makes these $k$-tuples uniformly distributed over all ordered $k$-tuples of distinct table locations.
Structure of the scheme in Exercise 6.4.46
The method constructs a family of $M$ probe permutations ${\pi_i}_{i=0}^{M-1}$ of ${0,1,\dots,M-1}$ with the property that the associated $M \times M$ array
$$ A(i,t) = \pi_i(t) $$
is a Latin square with an additional cyclic symmetry: the family is generated so that shifting the initial address $i$ induces a consistent relabeling of all probe sequences.
From this structure one obtains a stronger property than column-wise uniformity:
Claim (k-wise uniformity)
For every fixed $k \le M$, the multiset
$$ {(\pi_i(1),\dots,\pi_i(k)) : 0 \le i \le M-1} $$
contains each ordered $k$-tuple of distinct elements of ${0,\dots,M-1}$ exactly $(M-k)!$ times.
Equivalently, if $i$ is chosen uniformly at random, then
$$ (\pi_i(1),\dots,\pi_i(k)) $$
is uniformly distributed over all ordered $k$-permutations of the table.
Consequence for probe probabilities
Fix a set $S$ of $k$ distinct table positions. In a successful search, the event that the first $k$ probes all fall into $S$ depends only on whether the probe sequence hits $S$ in some order.
By the $k$-wise uniformity property, for every ordered $k$-tuple $(x_1,\dots,x_k)$ of distinct elements,
$$ \Pr\bigl((\pi_i(1),\dots,\pi_i(k)) = (x_1,\dots,x_k)\bigr) = \frac{1}{M(M-1)\cdots(M-k+1)}. $$
Hence every $k$-tuple of probe locations is equally likely, exactly matching the distribution of complete uniform probing up to length $k$.
Therefore, the probability that the first $k$ probes all land in occupied cells depends only on $a^k$ and matches the extremal case analyzed in Exercise 6.4.60.
Determination of the coefficients
Because the joint distribution of the first $k$ probes is identical to that of complete uniform probing (up to order $k$), the inclusion–exclusion calculation in Exercise 6.4.60 applies with equality at every stage. Consequently,
$$ c_k = \frac{1}{k+1}, \quad k \ge 1. $$
Thus,
$$ C_a = 1 + \frac{1}{2}a + \frac{1}{3}a^2 + \frac{1}{4}a^3 + \cdots. $$
Conclusion
The construction in Exercise 6.4.46 is not justified by marginal uniformity alone. Its extremality follows from the stronger fact that it induces full $k$-wise uniformity of probe sequences for every $k$, which matches the equality case of the coefficient bounds in Exercise 6.4.60.
Therefore, the method analyzed in Exercise 6.4.46 is indeed the worst possible single-hashing scheme in the sense of Exercise 6.4.60. ∎