Number of draws required to draw a given number of special objects in SRSWOR

Question

Suppose we have a set of $N$ objects with $K$ special objects of interest. We draw from our set of objects using simple random sampling without replacement (SRSWOR), and we are interested in determining how many draws it will take to draw some fixed number of these special objects. Suppose we want to draw $1 \leqslant m \leqslant K$ of the special objects in the set. What is the probability distribution of the required number of draws?

Answer 1

To solve the problem, let $K_n$ denote the number of special objects that have been drawn by the $n$th draw. Since we are using simple random sampling without replacement, this random variable follows the hypergeometric distribution:

$$\mathbb{P}(K_n = k) = \text{Hyper}(k|N,K,n) = \frac{{K \choose k} {N-K \choose n-k}}{{N \choose n}} \quad \quad \quad \text{for all } k = 0,...,K.$$

Now, let $N_r \equiv \min \{ n =r,...,N | K_n = r \} $ denote the number of draws required until we draw the $r$th special object (with $0 \leqslant r \leqslant K)$. We can see that the event $N_r \leqslant n$ is equivalent to the event $K_n \geqslant r$, so we have the distribution function:

$$\begin{equation} \begin{aligned} F_{N_r}(n) &\equiv \mathbb{P}(N_r \leqslant n) \\[6pt] &= \mathbb{P}(K_n \geqslant r) \\[6pt] &= \sum_{k=r}^K \mathbb{P}(K_n = k) \\[6pt] &= \sum_{k=r}^K \frac{{K \choose k} {N-K \choose n-k}}{{N \choose n}}. \\[6pt] \end{aligned} \end{equation}$$

This gives us the corresponding probability mass function:

$$\begin{equation} \begin{aligned} p_{N_r}(n) &\equiv \mathbb{P}(N_r = n) \\[6pt] &= \sum_{k=r}^K {K \choose k} \Bigg[ \frac{{N-K \choose n-k}}{{N \choose n}} - \frac{{N-K \choose n-k-1}}{{N \choose n-1}} \Bigg] \\[6pt] &= \sum_{k=r}^K {K \choose k} \frac{(N-K)! (n-1)! (N-n)!}{N! (n-k-1)! (N-K-n+k)!} \Bigg[ \frac{n}{n-k} - \frac{N-n+1}{N-K-n+k+1} \Bigg] \\[6pt] &= \sum_{k=r}^K {K \choose k} \frac{(N-K)! (n-1)! (N-n)!}{N! (n-k-1)! (N-K-n+k)!} \cdot \frac{(N-1)k-nK}{(n-k)(N-K-n+k+1)} \\[6pt] &= \sum_{k=r}^K {K \choose k} \frac{(N-K)! (n-1)! (N-n+1)!}{N! (n-k-1)! (N-K-n+k+1)!} \cdot \frac{(N-1)k-nK}{(n-k)(N-n+1)} \\[6pt] &= \sum_{k=r}^K \frac{{K \choose k} {N-K \choose n-k-1}}{{N \choose n-1}} \cdot \frac{(N-1)k-nK}{(n-k)(N-n+1)} \\[6pt] &= \frac{{N-n \choose N-K-n+r} {n-1 \choose n-r}}{{N \choose N-K}} \\[6pt] &= \text{NegHyper}(n-r|N,N-K,r). \\[6pt] \end{aligned} \end{equation}$$

This gives a simplified form for the mass function of the random variable, which is closely related to the negative hypergeometric distribution.

---

Implementation in R: We can program this mass function into R as the drawtime distribution. We will program the mass function using the standard syntax for distributions.

#Create mass function for drawtime distribution
ddrawtime <- function(x, N, K, r, log = FALSE) {

  #Check inputs
  if (!is.numeric(N))     { stop('Error: N must be an integer'); }
  if (N != as.integer(N)) { stop('Error: N must be an integer'); }
  if (N <= 0)             { stop('Error: N must be positive'); }
  if (!is.numeric(K))     { stop('Error: K must be an integer'); }
  if (K != as.integer(K)) { stop('Error: K must be an integer'); }
  if (K <= 0)             { stop('Error: K must be positive'); }
  if (K > N)              { stop('Error: K cannot be bigger than N'); }
  if (!is.numeric(r))     { stop('Error: r must be an integer'); }
  if (r != as.integer(r)) { stop('Error: r must be an integer'); }
  if (r <= 0)             { stop('Error: r must be positive'); }
  if (r > K)              { stop('Error: r cannot be bigger than K'); }

  #Set output vector
  LLL <- rep(-Inf, N+1);
  OUT <- rep(-Inf, length(x));

  #Compute log-probabilities
  for (n in r:(N-K+r)) {
    LLL[n] <- lchoose(n-1, n-r) + lchoose(N-n, N-K-n+r) - lchoose(N, N-K); }

  #Extract values at arguments
  for (i in 1:length(x)) { if (x[i] %in% r:(N-K+r)) { OUT[i] <- LLL[x[i]+1]; } }

  if (log) { OUT; } else { exp(OUT); } }

We will test this function for a set of $N=60$ objects with $K=4$ special objects, and we will generate the mass function for the number of draws required to obtain $k = 3$ of the special objects.

#Set parameters
N <- 60;
K <- 4;
r <- 3;

#Generate mass function
PROBS <- ddrawtime(1:N, N, K, r);
DATA  <- data.frame(Draws = 1:N, Probability = PROBS);

#Generate barplot
library(ggplot2);
THEME <- theme(plot.title    = element_text(hjust = 0.5, size = 14, face = 'bold'),
               plot.subtitle = element_text(hjust = 0.5, face = 'bold'));
ggplot(aes(x = Draws, y = Probability), data = DATA) +
    geom_bar(stat = 'identity', fill= 'blue') +
    THEME + 
    ggtitle('Mass function for draw-time distribution') +
    labs(subtitle = paste0('(N = ', N, ', K = ', K, ', r = ', r, ')')) +
    xlab('Number of Draws');

Answer 2

This problem can be seen as having a group of $n$ men and $m$ women how can you pick a committee of size $N$ ($N < n + m$) such as you have exactly $k$ number of women on the committee.

$$ P(X=k)=\frac{\binom{m}{k}\binom{n}{N-k}}{\binom{n+m}{N}}$$

It helps thinking about the groups of tagged and untagged elements as separate.