Exercise 45. [M43] [M43] Solve the analog of exercise 44 with tertiary clustering, when the probe sequence begins hi(K), ((hi(K) + h2(K)) mod M, and the succeeding probes are randomly chosen depending only on hi(K) and h2(K). (Thus the (M, 2)!“(“, possible choices of M(M, 1) probe sequences with this property are considered to be equally likely.) Is this procedure asymptotically equivalent to uniform probing?

Verified: yes
Solve time: 4m25s

We restart from the actual stochastic structure of tertiary clustering and keep track of the dependence that was incorrectly removed in the previous solution.

1. Exact probabilistic model

Let the table size be $M$ and let $n = \alpha M$ keys be inserted, with fixed $0 < \alpha < 1$.

For each key $K$, we choose an ordered pair

$$ (h_1(K), h_2(K)) \in {0,1,\dots,M-1}^2,\quad h_1 \neq h_2, $$

uniformly over the $M(M-1)$ possibilities.

The probe sequence for key $K$ is then:

$h_1(K)$,
$(h_1(K) + h_2(K)) \bmod M$,
a random permutation of the remaining $M-2$ positions.

Crucial point (correcting the previous proof):

the random ordering of the last $M-2$ positions depends only on the pair $(h_1(K), h_2(K))$, not independently for each key.

Hence we may formalize the model as:

For each ordered pair $p = (i,j)$, fix a random permutation

$$ \pi_p \text{ of } {0,\dots,M-1} $$

consistent with the constraint that it begins with $i, (i+j)\bmod M$.

Every key with $(h_1,h_2)=p$ uses the same $\pi_p$.

Thus keys are coupled through shared probe sequences whenever they share the same initial pair.

This is the sole source of dependence.

2. Structure of the dependence

Let $N_p$ be the number of keys hashing to pair $p$. Then:

$$ N_p \sim \text{Binomial}!\left(n, \frac{1}{M(M-1)}\right). $$

Since $n = \alpha M$,

$$ \mathbb{E}[N_p] = \frac{\alpha M}{M(M-1)} = \Theta!\left(\frac{1}{M}\right). $$

Hence:

Most pairs receive no keys,
A vanishing fraction receive one key,
Collisions $N_p \ge 2$ are extremely rare.

We quantify this.

3. Expected number of colliding pairs

Let

$$ X = \sum_p \mathbf{1}_{{N_p \ge 2}}. $$

Using standard occupancy estimates over $M(M-1) \sim M^2$ bins:

$$ \mathbb{E}[X] ;\le; \sum_p \mathbb{P}(N_p \ge 2) ;\le; M^2 \cdot O!\left(\frac{1}{M^2}\right) ;=; O(1). $$

More precisely, since $N_p$ has mean $\Theta(1/M)$,

$$ \mathbb{P}(N_p \ge 2) = O!\left(\frac{1}{M^2}\right). $$

Therefore:

$$ \mathbb{E}[X] = O(1). $$

So only $O(1)$ pairs, in expectation, exhibit any coupling between keys.

4. Effect of collisions within a pair

If $N_p = 0$ or $1$, that pair contributes exactly one independent probe sequence.

If $N_p \ge 2$, then multiple keys share the same permutation $\pi_p$, creating dependence.

However:

the total number of affected keys is at most $\sum_p N_p \mathbf{1}_{N_p \ge 2}$,
and since $\mathbb{E}[X] = O(1)$, the expected number of such keys is also $O(1)$.

Thus the number of keys whose probe sequences are not independent permutations is $O(1)$ in expectation.

Relative to $n = \Theta(M)$, this is negligible.

5. Reduction to uniform probing

Define a modified process:

If $N_p \le 1$, treat the (at most one) key in class $p$ as having an independent uniform random permutation.
Ignore classes with $N_p \ge 2$.

This modification changes at most $O(1)$ keys in expectation.

Hence any statistic $S_n$ that is:

sum of per-key probe costs, or
normalized average cost,

satisfies:

$$ \mathbb{E}[S_n^{\text{tertiary}}]

\mathbb{E}[S_n^{\text{uniform}}] + O(1). $$

Dividing by $n = \Theta(M)$ yields:

$$ \frac{1}{n}\left(\mathbb{E}[S_n^{\text{tertiary}}] - \mathbb{E}[S_n^{\text{uniform}}]\right) \to 0. $$

Thus all average-cost quantities agree asymptotically.

6. Clustering behavior

The only possible deviation from uniform probing comes from shared permutations within a pair.

But since:

the number of such shared-permutation groups is $O(1)$,
each affects at most $O(1)$ keys on average,

they cannot generate macroscopic clustering (which would require $\Theta(M)$-scale correlation).

Therefore tertiary clustering does not change the asymptotic load behavior derived in Exercise 44.

7. Conclusion

The correct comparison is not between independence structures per key, but between:

a fully independent-permutation model (uniform probing), and
a model in which dependencies are confined to $M^2$ groups with expected size $O(1/M)$.

Those dependencies are asymptotically negligible.

Hence all asymptotic insertion statistics coincide with uniform probing.

Final result

$$ \boxed{ \text{The tertiary clustering scheme is asymptotically equivalent to uniform probing.} } $$

More precisely, it differs from uniform probing only on a set of keys of expected size $O(1)$, so all normalized performance measures (expected probes per insertion, successful/unsuccessful search cost, load behavior) agree in the limit $M \to \infty$.

TAOCP 6.4 Exercise 45