Section 6.4: Hashing

Exercise 24. [M20] [M20] Suppose that the set of all possible keys that can occur has MP elements, where exactly P keys hash to any given address. (In practical cases, P is very large; for example, if the keys are arbitrary 10-digit numbers and if M = 10°, we have P = 10”.) Assume that M > 7 and N = 7. If seven distinct keys are selected at random from the set of all possible keys, what is the exact probability that the hash sequence 1262161 will be obtained (namely that h(K,) = 1, h(K2) = 2,..., h(K7) = 1), as a function of M and P?

Verified: yes
Solve time: 1m05s

---

Solution

Let the sample space consist of all sequences $(K_1,\dots,K_7)$ of seven distinct keys chosen from the set of $MP$ possible keys, with each such sequence having equal probability under successive uniform selection without replacement.

For each address $a \in {1,\dots,M}$, exactly $P$ keys satisfy $h(K)=a$. For each step $i$, conditioning is taken on the previously chosen keys, and only the counts of remaining keys in each hash class are relevant.

The required event is

$$ h(K_1)=1,\quad h(K_2)=2,\quad h(K_3)=6,\quad h(K_4)=2,\quad h(K_5)=1,\quad h(K_6)=6,\quad h(K_7)=1. $$

Let $A_i$ denote the event specifying the $i$th condition.

For $A_1$, the number of admissible keys is $P$ among $MP$, hence

$$ \Pr(A_1)=\frac{P}{MP}. $$

After selecting $K_1$, exactly one key from class $1$ is removed, leaving $P-1$ keys hashing to $1$ and $MP-1$ total keys.

For $A_2$, class $2$ is unconstrained by previous selections, hence

$$ \Pr(A_2 \mid A_1)=\frac{P}{MP-1}. $$

After selecting $K_2$, one key from class $2$ is removed. The total remaining keys are $MP-2$, and class counts are unchanged except class $1$ has $P-1$.

For $A_3$, class $6$ is still untouched, hence

$$ \Pr(A_3 \mid A_1A_2)=\frac{P}{MP-2}. $$

After selecting $K_3$, one key from class $6$ is removed. The total remaining keys are $MP-3$, and class $2$ has $P-1$ remaining.

For $A_4$, class $2$ now has $P-1$ admissible keys among $MP-3$, hence

$$ \Pr(A_4 \mid A_1A_2A_3)=\frac{P-1}{MP-3}. $$

After selecting $K_4$, one additional key from class $2$ is removed, so class $2$ has $P-2$ remaining. The total is $MP-4$, and class $1$ has $P-1$ remaining.

For $A_5$, class $1$ is required, hence

$$ \Pr(A_5 \mid A_1\cdots A_4)=\frac{P-1}{MP-4}. $$

After selecting $K_5$, class $1$ has $P-2$ remaining, class $6$ has $P-1$ remaining, and the total is $MP-5$.

For $A_6$, class $6$ is required, hence

$$ \Pr(A_6 \mid A_1\cdots A_5)=\frac{P-1}{MP-5}. $$

After selecting $K_6$, class $6$ has $P-2$ remaining, class $1$ has $P-2$ remaining, and the total is $MP-6$.

For $A_7$, class $1$ is required, hence

$$ \Pr(A_7 \mid A_1\cdots A_6)=\frac{P-2}{MP-6}. $$

Multiplying the conditional probabilities yields

$$ \Pr(A_1\cdots A_7)

\frac{P}{MP} \cdot \frac{P}{MP-1} \cdot \frac{P}{MP-2} \cdot \frac{P-1}{MP-3} \cdot \frac{P-1}{MP-4} \cdot \frac{P-1}{MP-5} \cdot \frac{P-2}{MP-6}. $$

The numerator collects factors by hash class usage:

class $1$ contributes $P(P-1)(P-2)$, class $2$ contributes $P(P-1)$, class $6$ contributes $P(P-1)$, giving

$$ P^3 (P-1)^3 (P-2). $$

The denominator is the falling factorial

$$ (MP)(MP-1)(MP-2)(MP-3)(MP-4)(MP-5)(MP-6). $$

Therefore,

$$ \Pr = \frac{P^3 (P-1)^3 (P-2)} {(MP)(MP-1)(MP-2)(MP-3)(MP-4)(MP-5)(MP-6)}. $$

$$ \boxed{ \frac{P^3 (P-1)^3 (P-2)} {(MP)(MP-1)(MP-2)(MP-3)(MP-4)(MP-5)(MP-6)} } $$

This completes the proof. ∎