Section 6.5: Retrieval on Secondary Keys

Exercise 4. [M30] [M30] Find exact formulas for the probabilities in (11), assuming that each record has r distinct attributes chosen randomly from among the (i) k-bit codes in an n-bit field and that the query involves q distinct but otherwise random attributes. (Don’t be alarmed if the formulas do not simplify.)

Verified: yes
Solve time: 3m46s

---

We restart from a correct event decomposition and avoid any use of the flawed distribution of $Q$.

1. Basic reformulation

Let

$$ Q=\bigcup_{i=1}^q A_i,\qquad R=\bigcup_{j=1}^r B_j, $$

where each $A_i,B_j$ is an independent uniformly chosen $k$-subset of $[n]$.

We want

$$ \Pr(Q \subseteq R). $$

Equivalently, define for each element $x \in [n]$ the bad event

$$ E_x := {x \in Q \text{ and } x \notin R}. $$

Then

$$ Q \subseteq R \quad \Longleftrightarrow \quad \bigcap_{x \in [n]} \overline{E_x}. $$

Hence by inclusion–exclusion,

$$ \Pr(Q \subseteq R)

\sum_{m=0}^n (-1)^m \sum_{\substack{S \subseteq [n]\ |S|=m}} \Pr\Big(\bigcap_{x \in S} E_x\Big). $$

By symmetry, the inner probability depends only on $m=|S|$, so:

$$ \Pr(Q \subseteq R)

\sum_{m=0}^n (-1)^m \binom{n}{m} \Pr\Big(\bigcap_{x \in S} E_x\Big), $$

for any fixed $S\subseteq[n]$, $|S|=m$.

2. Structure of $\bigcap_{x\in S} E_x$

For fixed $S$,

$$ \bigcap_{x\in S} E_x \quad \Longleftrightarrow \quad \big(S \subseteq Q\big)\ \text{and}\ \big(S \cap R = \varnothing\big). $$

Crucially:

• $Q$ depends only on the $A_i$,
• $R$ depends only on the $B_j$,
• and the two families are independent.

So the events are independent:

$$ \Pr(S \subseteq Q,\ S \cap R = \varnothing)

\Pr(S \subseteq Q),\Pr(S \cap R = \varnothing). $$

We compute both factors.

3. Probability that $S \subseteq Q$

Fix $|S|=m$. A given $A_i$ avoids a subset $T\subseteq S$ of size $j$ with probability

$$ \frac{\binom{n-j}{k}}{\binom{n}{k}}. $$

By inclusion–exclusion over elements of $S$,

$$ \Pr(S \subseteq Q)

\sum_{j=0}^{m} (-1)^j \binom{m}{j} \left(\frac{\binom{n-j}{k}}{\binom{n}{k}}\right)^q. $$

4. Probability that $S \cap R = \varnothing$

This means none of the elements of $S$ appear in any of the $r$ record $k$-sets.

For a fixed $j$-subset, a single $B_i$ avoids it with probability

$$ \frac{\binom{n-m}{k}}{\binom{n}{k}}. $$

By independence over the $r$ sets,

$$ \Pr(S \cap R = \varnothing)

\left(\frac{\binom{n-m}{k}}{\binom{n}{k}}\right)^r. $$

5. Combine everything

Substituting into the outer inclusion–exclusion gives

$$ \Pr(Q \subseteq R)

\sum_{m=0}^n (-1)^m \binom{n}{m} \left[ \sum_{j=0}^{m} (-1)^j \binom{m}{j} \left(\frac{\binom{n-j}{k}}{\binom{n}{k}}\right)^q \right] \left(\frac{\binom{n-m}{k}}{\binom{n}{k}}\right)^r. $$

6. Final exact formula

$$ \boxed{ \Pr(Q \subseteq R)

\sum_{m=0}^n (-1)^m \binom{n}{m} \left( \sum_{j=0}^{m} (-1)^j \binom{m}{j} \left(\frac{\binom{n-j}{k}}{\binom{n}{k}}\right)^q \right) \left(\frac{\binom{n-m}{k}}{\binom{n}{k}}\right)^r } $$

7. What was fixed

• The incorrect use of $\Pr(Q=T)$ was eliminated entirely.
• The argument now works directly with element-wise failure events.
• Independence is used only where it is valid: between the $A_i$ and $B_j$, not within unions of dependent structures.

This yields a fully exact formula with no incorrect conditioning.