There is a population with N instances.
A sampling means we draw randomly M instances from the population without replacement.
Two samplings are independent, i.e. after one sampling we push back M instances to the pool and restart.
Call m is the number of sampling time as each instance in the population has been sampled at least once.
What is the expected value of m?
Out of the $X_t=j$ unsampled units at time $t$, the number that are still unsampled at time $t+1$ follows a hypergeometric distribution with parameters $N$, $N-M$ and $i$. The transition probabilities of this Markov chain are thus given by $$ p_{ij}=P(X_{t+1}=j|X_t=i)=\frac{{i \choose j}{N-i \choose N-M-j}}{{N \choose N-M}}. $$ Let $k_i$ denote the expected remaining time until all units are sampled given that the current state $X_t=i$. We then have $k_0=0$ and, from the law of total expectation, $$ k_i = 1 + \sum_{j=0}^i p_{ij} k_j. $$ The following R code solves these equations and computes $k_1,k_2,\dots,k_{10}$ for for $M=2$ and $N=10$.
expectation <- function(M,N) {
k <- NULL # k_1, k_2, ...
for (i in 1:N) {
p <- dhyper(1:i, N-M, M, i) # transition probabilities
k[i] <- (1 + sum(p[-i]*k))/(1 - p[i]) # solution of k_i = 1 + sum p_ij k_j
}
k
}
> expectation(2,10)
[1] 5.000000 7.352941 8.933824 10.117647 11.065126 11.854557 12.531270
[8] 13.123362 13.649689 14.123362
