How to calculate the expected number of distinct items when drawing pairs?

Question

Suppose I have a set $\mathcal{S}$ of $N$ distinct items. Now consider the set $\mathcal{P}$ of all possible pairs that I can draw from $S$. Naturally, $|\mathcal{P}| = \binom{N}{2}$. Now when I draw $k$ items (pairs) from $\mathcal{P}$ with a uniform distribution, what is the expected number of distinct items from $S$ in those $k$ pairs?

Answer 1

To avoid the ambiguity of a terminology that refers to everything as an "item," let's suppose the set $S$ consists of $n$ distinct "letters." And, because this is a pretty generalization of the Birthday Paradox, let's generalize it a little further and set $P$ to be the set of all $r$-letter words having all distinct letters. The question as stated corresponds to $r=2$. We ask more generally

What is the expected number of distinct letters found in the $r k$-letter word obtained by concatenating $k$ random $r$-letter words of distinct letters?

We can compute this in three stages:

1. For any $m$, $r \le m \le n$, find the proportion of the $k$-fold $r$-letter words having $m$ or fewer distinct letters.

2. From this obtain the probability $p_{n,k,r}(m)$ of exactly $m$ distinct letters.

3. Compute the expected number of letters by summing $m p_{n,k,r}(m)$ over $m$ (from $r$ to $n$).

We find the proportions in #1 with a polynomial expansion. Let $f_r(x_1, x_2, \ldots, x_n)$ be the average of all words of length $r$ in which the letters are distinct. For example,

$$f_2(x_1, x_2, x_3) = \left( x_1 x_2 + x_2 x_1 + x_2 x_3 + x_3 x_2 + x_1 x_3 + x_3 x_1 \right)/6 \text{.}$$

The $k^\text{th}$ power of this (computed as a polynomial) displays the probabilities with which which words can be formed by a $k$-fold concatenation. For example, inspection of the coefficients of

$$f_2(x_1, x_2, x_3)^2 = \left( x_1^2 x_2^2 + x_2^2 x_3^2 + x_1^2 x_3^2 + 2 x_1^2 x_2 x_3 + 2 x_1 x_2^2 x_3 + 2 x_1 x_2 x_3^2 \right) / 9 $$

shows that the chance of forming a word with two $x_1$'s and two $x_2$'s (which can occur in four ways out of the 36 possible ways: $x_1x_2x_1x_2$, $x_1x_2x_2x_1$, $x_2x_1x_1x_2$, and $x_2x_1x_2x_1$) is 1/9.

When we set some of the $x_i$ equal to zero, they drop out of $f_r^k$ altogether, and when we set the remaining $x_i$ equal to one, what remains is the sum of their coefficients. Thus we could hope to find the probability of having $m$ distinct letters by setting exactly $m$ of the $x_i$ to one (and the remainder to zero) and summing the value of $f_r^k$ over all such possibilities. (This is easily done because the symmetry of $f_r$ implies all these values are equal, so we need only compute $f_r^k(1,\ldots,1,0,\ldots,0)$ and multiply that by ${n}\choose{m}$.) Unfortunately, this also over-counts words having fewer than $m$ distinct letters, so we have to apply the Principle of Inclusion-Exclusion to extract the desired value. The punchline is that $f_r$ is easy to evaluate; when we set $n-m$ of its arguments to $0$, there remain ${n}\choose{m}$ terms, all of which will evaluate to $1$, whence

$$f_r^k(1,\ldots,1,0,\ldots,0) = {{m}\choose{k}} / {{n}\choose{k}}.$$

Putting this together gives

$$p_{n,k,r}(m) = {{n}\choose{m}} \sum_{j=0}^{m-r}{(-1)^j {{m}\choose{m-j}} {{m-j}\choose{r}}^k } / {{n}\choose{r}}^k \text{.}$$

The expectation equals

$$\mathbb{E}[\text{# distinct letters}] = \sum_{m=r}^n{p_{n,k,r}(m) m}.$$

This looks like an expression that is unlikely to simplify. Its calculation requires $O(n^2)$ effort. When $k$ is small, this can be reduced to $O(n r k)$ by dynamic programming using a recursive relationship between the probability distribution for $k$ and the probability distribution for $k+1$. The recursion is obtained by considering how $m+r$ distinct letters can arise in a $k+1$-fold concatenation: either $r$ distinct letters are adjoined to a word of $m$ distinct letters, or $r-1$ distinct letters are adjoined to a word of $m+1$ distinct letters, ..., or no distinct letters are introduced to a word of $m+r$ distinct letters. Rather than write down this recursion generally, I'll display the case $r=2$:

$$\eqalign{ p_{n,k+1,2}(m+2) &= \Bigl[ {{n-m}\choose{2}} p_{n,k,2}(m) \cr &+ (m+1)(n-m+1)p_{n,k,2}(m+1) \cr &+ {{m+2}\choose{2}} p_{n,k,2}(m+2) \Bigr] / {{n}\choose{2}} }\text{.}$$

The dynamic program computes the entire distribution for the case $k=1$ and then uses this recursion to compute it for $k=2, \ldots$ up to the desired value.