TAOCP 6.4 Exercise 75
Let ${h_i}_{i=1}^R$ be independent random functions, each mapping the set of keys into ${0,1,\dots,M-1}$, and each value $h_i(K)$ is uniformly distributed over ${0,1,\dots,M-1}$ for every fixed key $K...
Exercise 75. [M26] [M26] Prove or disprove the following statements about the hash function h of (9), when the h; are independent random functions: a) The probability that h(K) = m is 1/M, for al0 <<m< M. b) If K # K’, the probability that h(K) = m and h(K’) = m’ is 1/M”, for all 0<m,m' <M. c) If K, K’, and Kk” are distinct, the probability that h(K) = m, h(K') = m’, and h(K") =m" is 1/M®, for allO <m,m’,m" < M. d) If K, Kk’, K", and K” are distinct, the probability that h(K) =m, h(K') =m’, h(K") =m", and h(K') = m'” is 1/M"“, for all 0 < m,m',m",m'" < M.
Verified: yes
Solve time: 1m10s
Setup
Let ${h_i}_{i=1}^R$ be independent random functions, each mapping the set of keys into ${0,1,\dots,M-1}$, and each value $h_i(K)$ is uniformly distributed over ${0,1,\dots,M-1}$ for every fixed key $K$.
Let $I$ be a random index uniformly distributed over ${1,\dots,R}$, independent of all $h_i$. The hash function $h$ is defined by selecting a random row:
$$ h(K) = h_I(K). $$
All probabilities are taken over the joint distribution of $I$ and the family ${h_i}$.
The task is to determine the validity of statements (a)–(d) for distinct keys $K,K',K'',K'''$.
Solution
(a)
Fix a key $K$ and a value $m \in {0,1,\dots,M-1}$.
Condition on $I=i$. Then
$$ \Pr(h(K)=m \mid I=i) = \Pr(h_i(K)=m) = \frac{1}{M}, $$
since each $h_i(K)$ is uniform over ${0,\dots,M-1}$.
Using total probability over $I$,
$$ \Pr(h(K)=m) = \sum_{i=1}^R \Pr(I=i)\Pr(h_i(K)=m \mid I=i) = \sum_{i=1}^R \frac{1}{R}\cdot \frac{1}{M} = \frac{1}{M}. $$
This proves (a).
(b)
Let $K \neq K'$ and fix $m,m'$.
Condition on $I=i$. Then $h(K)=h_i(K)$ and $h(K')=h_i(K')$, and by independence of the random functions,
$$ \Pr(h_i(K)=m \ \text{and}\ h_i(K')=m') = \frac{1}{M^2}. $$
Applying total probability over $I$,
$$ \Pr(h(K)=m \ \text{and}\ h(K')=m') = \sum_{i=1}^R \frac{1}{R}\cdot \frac{1}{M^2} = \frac{1}{M^2}. $$
This proves (b).
(c)
Let $K,K',K''$ be distinct and fix $m,m',m''$.
Condition on $I=i$. Independence of $h_i$ across distinct keys gives
$$ \Pr(h_i(K)=m,\ h_i(K')=m',\ h_i(K'')=m'') = \frac{1}{M^3}. $$
Averaging over $I$,
$$ \Pr(h(K)=m,\ h(K')=m',\ h(K'')=m'') = \sum_{i=1}^R \frac{1}{R}\cdot \frac{1}{M^3} = \frac{1}{M^3}. $$
This proves (c).
(d)
Let $K,K',K'',K'''$ be distinct and fix $m,m',m'',m'''$.
Condition on $I=i$. Independence across four distinct inputs yields
$$ \Pr(h_i(K)=m,\ h_i(K')=m',\ h_i(K'')=m'',\ h_i(K''')=m''') = \frac{1}{M^4}. $$
Averaging over $I$,
$$ \Pr(h(K)=m,\ h(K')=m',\ h(K'')=m'',\ h(K''')=m''') = \sum_{i=1}^R \frac{1}{R}\cdot \frac{1}{M^4} = \frac{1}{M^4}. $$
Thus the stated property holds for four distinct keys.
Verification
Each part reduces to conditioning on the random row index $I$, after which the independence assumptions apply within a fixed function $h_i$. The uniform distribution of each $h_i(K)$ over $M$ values gives factor $1/M$ per key, and independence across distinct keys multiplies these factors. Summation over $I$ preserves the same probability because every row contributes equally with weight $1/R$.
Conclusion
All statements (a), (b), (c), and (d) are true under the assumption that the functions $h_i$ are independent and uniformly random over ${0,1,\dots,M-1}$ for each key and each row.
This completes the proof. ∎