Expected Size of Random Subset Intersection
Fix $0 \leq a, b \leq n$. Let $A$ and $B$ be subsets of $[n] = \{1, 2, \ldots, n\}$, chosen independently and uniformly at random from all subsets of sizes $a$ and $b$, respectively.
Find $E[|A \cap B|]$ for the specific values $a = 6$, $b = 8$, $n = 12$.
Then give the general formula for arbitrary $a$, $b$, $n$.
Hints
- Computing the PMF of $|A \cap B|$ directly is hard. Instead, write the intersection size as a sum of indicator random variables -- one for each element of $[n]$.
- By symmetry, every element $i \in [n]$ has the same probability of landing in $A \cap B$. So $E[|A \cap B|] = n \cdot P(1 \in A \cap B)$.
- Since $A$ and $B$ are chosen independently, $P(1 \in A \cap B) = P(1 \in A) \cdot P(1 \in B)$. For a uniformly random size-$a$ subset of $[n]$, the probability that any fixed element is included is $a/n$.
Worked Solution
How to Think About It: Computing the full distribution of $|A \cap B|$ directly is painful -- you would need to enumerate how many ways two random subsets of given sizes can overlap by exactly $k$ elements. Instead, use indicator random variables. For each element $i \in [n]$, define $I_i = 1$ if $i \in A \cap B$, and 0 otherwise. Then $|A \cap B| = I_1 + I_2 + \cdots + I_n$. Linearity of expectation reduces the problem to computing a single probability.
Quick Estimate: $A$ picks 6 out of 12 elements (half the universe), $B$ picks 8 out of 12 (two-thirds). If both were picking independently at random, the fraction of elements in both should be roughly $(1/2) \times (2/3) = 1/3$ of the 12 elements, giving about 4. The exact answer should be close to this.
Approach: Linearity of expectation on indicator variables.
Formal Solution:
Define $I_i = \mathbf{1}[i \in A \cap B]$ for each $i \in [n]$. Then: $E[|A \cap B|] = E\left[\sum_{i=1}^n I_i\right] = \sum_{i=1}^n E[I_i] = n \cdot P(1 \in A \cap B)$
where the last equality uses the fact that, by symmetry, all elements have the same probability of being in $A \cap B$.
Since $A$ and $B$ are chosen independently: $P(1 \in A \cap B) = P(1 \in A) \cdot P(1 \in B)$
Now, $A$ is a uniformly random size-$a$ subset of $[n]$. Each element is equally likely to be included, and exactly $a$ out of $n$ elements are chosen, so: $P(1 \in A) = \frac{a}{n}, \qquad P(1 \in B) = \frac{b}{n}$
Therefore: $E[|A \cap B|] = n \cdot \frac{a}{n} \cdot \frac{b}{n} = \frac{ab}{n}$
For $a = 6$, $b = 8$, $n = 12$: $E[|A \cap B|] = \frac{6 \times 8}{12} = \frac{48}{12} = \boxed{4}$
This matches our estimate exactly.
Answer: $E[|A \cap B|] = ab/n$. For the given values: $E[|A \cap B|] = 4$.
Intuition
Linearity of expectation is often the fastest route to expected counts. Whenever you are asked for the expected size of a set defined by some random process, try writing that size as a sum of 0-1 indicators and computing each indicator's expectation separately. The power of this approach is that you do not need the indicators to be independent -- linearity holds regardless. Here the indicators $I_i$ are certainly not independent (including element 1 in $A$ makes it slightly less likely that element 2 is also in $A$, since the subset has a fixed size), but that does not matter at all for the expectation.
The formula $E[|A \cap B|] = ab/n$ has an elegant interpretation: it is the expected intersection size if each element independently chose to include itself in $A$ with probability $a/n$ and in $B$ with probability $b/n$. Fixed-size subsets are more constrained than this, but the expected intersection is the same. This is a general phenomenon -- many counting expectations are unchanged by replacing fixed-size uniform random subsets with independent Bernoulli inclusion, and the Bernoulli version is usually far easier to analyze.