# What is expected times of sampling that a full population is covered?

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?

• A variant on the coupon collector problem, (which may prove useful in jumping to a solution...). Feb 22, 2019 at 6:58
• The full distribution is given at stats.stackexchange.com/questions/320152/…. From there it's a short (easier) calculation to obtain the expectation. (cc @Glen_b)
– whuber
Feb 22, 2019 at 14:29

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