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?

  • 2
    $\begingroup$ A variant on the coupon collector problem, (which may prove useful in jumping to a solution...). $\endgroup$
    – Glen_b
    Commented Feb 22, 2019 at 6:58
  • 1
    $\begingroup$ 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) $\endgroup$
    – whuber
    Commented Feb 22, 2019 at 14:29

1 Answer 1


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
> 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.