Suppose we have $N$ people. A random selection of $k$ of these people meet each day. What is the expected number of days until everyone has met? I thought of this problem today and I'm not quite sure how it's solved. My idea is simply to use the definition of expectation:
$$E[\text{# of days until everyone has met}] = \sum_{x=1} x \cdot p(x)$$
Where $p(x)$ is the probability that everyone has met in $x$ days. After that, I'm not quite sure how to compute $p(x)$.
Is this the correct approach? If so, any ideas for how to compute $p(x)$?
Also, does anyone have ideas for how to solve the case for the expected number of days until $X \%$ of people have met?
 A: Let us cover at least some cases.
Case $k=2$
For any $n$, if $k=2$ this is the Coupon collector's problem on the $M=n(n-1)/2$ pairs of people. On any day, a random pair meets; if already $m$ pairs have met, then each day the success rate for a new pair meeting is $(M-m)/M$, and the expected number of days until success is its inverse. So the expected total is
$$
\frac{M}{M} + \frac{M}{M-1} + \ldots + \frac{M}{1} = M \cdot H_M,
$$
where $H_M$ is the $M$th harmonic number.
For example, with $n=4$, $k=2$ we have $M=6$ and the expectation is $6H_6 = 14.7$. (Simulations agree.)
Case $k=n-1$
There are $n$ different meetings possible (leaving any person out). Any two different meetings are not enough: if they leave out persons $i$ and $j$, then $i,j$ did not meet in either meeting. Any three different meetings are enough, because if the first two meetings left out $i$ and $j$, and the third meeting leaves out a third person, then $i,j$ meet in the third meeting.
So it is like a truncated coupon collector's problem: we only need to gather three different meetings. The first happens in 1 days, the second in $n/(n-1)$ days on average, and the third in $n/(n-2)$ days on average.
For example, with $n=5$ and $k=4$, we have $5$ different meetings possible, and the expectation is $1 + 5/4 + 5/3 \approx 3.92$. (Simulations agree.)
Case $n=5$, $k=3$
This is the smallest nontrivial case not covered above. Now the analysis is no longer straightforward. On day 1, a meeting of three persons is held; let us call them ABC, and the other two persons DE. On day 2, there are three structurally different possibilities:

*

*With probability $1/10$ ABC meet again.

*With probability $6/10$ two of ABC meet one of DE. (Such meetings are ABD, ABE, ACD, ACE, BCD, BCE.)

*With probability $3/10$ one of ABC meets DE. (Such meetings are ADE, BDE, CDE.)

So far, so good. But as the story continues, there are in total $11$ structurally different situations, as depicted below. This is in fact the state diagram of a Markov chain. A state is an unlabeled graph indicating which persons have met (up to isomorphism), and the edges are the possible transitions when a meeting is held. The transition probabilities are shown on the edges. The initial state is "no pairs met" at the left end, and the final (absorbing) state is "all pairs met" at the right end. Every intermediate state has also a loop (not shown), for the case that a meeting covers no new pairs.

Now we know the initial state, and we have the transition matrix between these 11 states. Letting $Q$ be the part of the transition matrix excluding the final state, and $W=(I-Q)^{-1}$, the first row sum of $W$ gives us the mean time to absorption (i.e. expected days to reach the final state). It turns out to be $107/12 \approx 8.917$ (again, simulations agree). For more details of this calculation, see Absorbing Markov chains by Dan Ma.
In principle, larger cases could be solved exactly with the same method, but the state diagrams will be more complicated.
