Expected cardinal of the intersection between a random subset and a fixed subset

Question

I have a set of size $n$, and a fixed subset $A$ of cardinal $k$. I take a random subset $X$ of cardinal $d$. I need to compute the expected cardinal of the intersection between $A$ and $X$.

I tried the following: the probability that the intersection is of cardinal $i$ (for $i$ in $[\max(0, n-k-d), \min(k,d)]$) is:

$$ \mathbf{P}(|X\cap A|=i)=\frac{\binom{k}{i}\binom{n-k}{d-i}}{\binom{n}{d}} $$

I just choose the intersection, $i$ elements in $A$, then the $d-i$ remaining elements in the complementary. But now the expected value is:

$$ \mathbf{E}(|X\cap A|)=\frac{1}{\binom{n}{d}}\sum\limits_{i=0}^{d}i\binom{k}{i}\binom{n-k}{d-i} $$

and I don't know what to do from here. I'd like to use Vandermonde identity, but I don't know how to deal with the $i$ in the sum. Am I missing something ?

Thanks !

Answer 1

Your approach yields $$ \frac{\sum_{i=0}^d i \binom{k}{i} \binom{n-k}{d-i}}{\binom{n}{d}} = \frac{\sum_{i=1}^d k \binom{k-1}{i-1} \binom{n-k}{d-i}}{\binom{n}{d}} = k \frac{\binom{n-1}{d-1}}{\binom{n}{d}} = k \frac{\binom{n-1}{d-1}}{\frac{n}{d}\binom{n-1}{d-1}} = \frac{k d}{n}. $$

---

An alternative approach is to let $X=\{x_1,\dots,x_d\} \subset \{1,\dots,n\}$ and introduce indicator random variables $X_j$ for $j\in\{1,\dots,d\}$: $$X_j = \begin{cases} 1 & \text{if $x_j\in A$} \\ 0 & \text{otherwise} \end{cases} $$ Then $$ E[|X\cap A|] = E\left[\sum_{j=1}^d X_j\right] = \sum_{j=1}^d E\left[X_j\right] = \sum_{j=1}^d P[x_j \in A] = \sum_{j=1}^d \frac{k}{n} = \frac{dk}{n}. $$