How to calculate the expected number of distinct items when drawing pairs? 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?
P.S.: I also asked this question over at stats, but got no answers so far, so I am trying here. Thanks for your time!
Edit I pick the pairs without replacement.
 A: For choosing without replacement, here is an exact answer.  Assuming $n \geq 2$, so that there is at least one pair, and $1 \leq k \leq \binom{n}{2}$, so that you're choosing at least one pair but not more than the total number of pairs, the expected value is  
$$n - \left(\frac{n^2 - 3n - 2k + 4}{n-1}\right) \frac{\binom{\binom{n}{2} - n + 1}{k-1}}{\binom{\binom{n}{2} - 1}{k-1}}.$$
We can assume that we are choosing pairs in order.  Let $X_k$ be the number of distinct items from $S$ through $k$ pairs.  Let $Y_i$ be the number of items in the $i$th pair that did not appear in any of the previous pairs.  So $X_k = \sum_{i=1}^k Y_i$.
Now, $Y_i$ is either 0, 1, or 2.  Since there are $\binom{n}{2} - n + 1$ pairs that do not contain a given item and $\binom{n}{2} - 2n + 3$ pairs that do not contain either of two given items, we have
$$P(Y_i = 1) = \frac{\binom{\binom{n}{2} - n + 1}{i-1} + \binom{\binom{n}{2} - n + 1}{i-1} - 2 \binom{\binom{n}{2} - 2n + 3}{i-1}}{\binom{\binom{n}{2} - 1}{i-1}}$$
and
$$P(Y_i = 2) = \frac{\binom{\binom{n}{2} - 2n + 3}{i-1}}{\binom{\binom{n}{2} - 1}{i-1}}.$$
Thus 
$$E[Y_i] = 2\frac{\binom{\binom{n}{2} - n + 1}{i-1}}{\binom{\binom{n}{2} - 1}{i-1}}.$$
It can be proved by induction that 
$$\sum_{i=0}^k \frac{\binom{M}{i}}{\binom{N}{i}} = \frac{(N+1)\binom{N}{k} - (M-k)\binom{M}{k}}{(N+1-M)\binom{N}{k}}.$$
Thus 
$$E[X_k] = \sum_{i=1}^k E[Y_i] = 2\sum_{i=1}^k \frac{\binom{\binom{n}{2} - n + 1}{i-1}}{\binom{\binom{n}{2} - 1}{i-1}} $$ 
$$= 2\frac{(\frac{n(n-1)}{2}-1+1)\binom{\binom{n}{2}}{k-1} - (\frac{n(n-1)}{2} - n + 1 - k + 1)\binom{\binom{n}{2} - n + 1}{k-1}}{(\binom{n}{2} - 1+1-\binom{n}{2} + n - 1)\binom{\binom{n}{2} - 1}{k-1}}$$
$$= \frac{n(n-1)\binom{\binom{n}{2}}{k-1} - (n^2 - 3n - 2k + 4)\binom{\binom{n}{2} - n + 1}{k-1}}{(n - 1)\binom{\binom{n}{2} - 1}{k-1}}$$
$$= n -\frac{(n^2 - 3n - 2k + 4)\binom{\binom{n}{2} - n + 1}{k-1}}{(n - 1)\binom{\binom{n}{2} - 1}{k-1}}.$$
A: You are picking edges from a complete graph and looking for the expected number of vertices that get picked.
Consider the expected number of vertices that don't get picked.
The probability that a vertex gets picked in 1 try is $\dfrac{2}{n}$.
Thus it does not get picked in all tries is $(1-\dfrac{2}{n})^k$.
Thus the expected number of vertices that don't get picked is $n(1-\dfrac{2}{n})^k$
and thus the expected number of vertices that get picked is
$n(1 - (1-\dfrac{2}{n})^k)$
As Ross points out, this assumes you pick the pairs with replacement.
A: You can calculate the exact probability of drawing $t$ unique vertices using inclusion-exclusion. We can estimate this probability as
$\binom{n}{t} \binom{\binom{t}{2}}{k}$
but you're overcounting instances when less than $ t $ vertices actually appear; you can fix that using inclusion exclusion.
Given that, you can try to calculate the expectation directly.

You can also try to work your way from Moron's formula. His formula gives the expectation when k edges are drawn with replacement. We know that distribution of the number of distinct edges drawn, so we can express the expectation when k edges are drawn with replacement using the expectations when $k_0$ unique edges are drawn for $k_0 \leq k$. We get linear equations and maybe we can solve them to find the probability when k unique edges are drawn.
