# Given randomly selected $K, R \subset N$, what is the expected value of $|K \cap R|$?

If I randomly select subsets $K$ and $R$ of set $N$, what is the expected value of $|K \cap R|$ i.e. the number of elements in both $K$ and $R$?

EDIT: Clarifications: $N$ is finite and of known size, and $K$ and $R$ are uniformly distributed over subsets of given sizes $k$ and $r$. In other words, I'm looking for a function $P(k, r, n)$ that returns $|K \cap R|$.

I initially tried modelling this as a computation. If I select an element from $R$ and try to add it to $K$, the probability that said element is already in $K$ is $\frac{k}{n}$ ($k = |K|$; $n = |N|$; $r = |R|$). So the expected number of elements in $K$ after I add an element from $R$ should be $\frac{k}{n} k + \frac{n - k}{n} \left ( k + 1 \right )$. Following this train of logic gives us the recurrence relation

$P(k, r, n) = \frac{k}{n} P(k, r - 1, n) + \frac{n - k}{n} P(k + 1, r - 1, n)$

with the obvious boundary conditions $\forall k, n: P(k, 0, n) = 1$ and $\forall n, r: P(n, r, n) = 0$. (Finding $P(k, r, n)$ will obviously give us $|K \cup R|$, not $|K \cap R|$, but then $|K \cap R| = |K| + |R| - |K \cup R|$.) But I have no idea how to turn this recurrence relation into a closed-form, and I'm not even fully confident that it's correct in the first place. I would just write a C program to calculate $P(k, r, n)$ for me, but I'm dealing with values of $k$ and $r$ that are large enough (up to $2^{16}$) that I would blow my stack space.

• Just to clarify: $N$ is a finite set, and you're picking $K$ and $R$ using the uniform meausre on $\mathcal{P}(N)$ (so all subsets of $N$ are equally likely)? Feb 13, 2017 at 22:11
• Also, I'm a massive idiot and just rubber-ducked myself into a viable Monte Carlo algorithm that'll work in O(r) time and O(1) space per iteration. Still curious to see if analytic solutions exist. Feb 13, 2017 at 22:18

We have $$|K \cap R| = \sum_{x \in N}1_{x \in K \cap R} = \sum_{x \in N}1_{x\in K}1_{x\in R}$$ and taking expected values and using independence, $$E|K \cap R| = \sum_{x \in N}P(x \in K) P(x \in R).$$ So symmetry demands that $P(x \in K), P(x \in R)$ don't depend on $x$, only $k$ and $r$. The question remains, how many total subsets of $N$ have size $k$, and of those how many contain some fixed $x$?. By definition, $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ is how many ways there are to choose a subset of size $k$ from a set of size $n=|N|$. Choosing a subset of size $k$ containing $x$ is the same as choosing a subset of size $k-1$ from $N\setminus\{x\}$, so there are $\binom{n-1}{k-1}$ ways of doing this. Thus $$E|K \cap R| = |N| \frac{\binom{n-1}{k-1}}{\binom{n}{k}}\frac{\binom{n-1}{r-1}}{\binom{n}{r}}$$ and I believe you are capable of simplifying from here.
When you need to calculate the expectation of the cardinality of some set, its usually convinient to express this value as the sum of indicator functions. Let $X_n, n \in N$ be a random variable that is an indicator of the event $n \in K \cap R$. Note that $|K \cap R| = \sum_{n \in N} X_n$. Now, using the linearity of expectation and uniform distribution of subsets $$\mathbb{E}|K \cap R| = \sum_{n \in N} \mathbb{E}X_n = \sum_{n \in N}\mathbb{P}(n \in K \cap R) = |N| \cdot \mathbb{P}(n \in K \cap R).$$ To calculate the last probability, note that to choose a pair of subsets of $N$ with $n \in K \cap R$ is the same as fixing $n$ and choosing a pair of subsets of $N \setminus \{n\}$. So $\mathbb{P}(n \in K \cap R) = \frac{2^{2(|N| - 1)}}{2^{2|N|}} = \frac{1}{4}.$ Finally, we get $\mathbb{E}|K \cap R| = \frac{|N|}{4}$.