probability that random draws from the same pool will collectively select 90% of the pool

Question

There are a total of 200 names on a list. 30 times names are selected from the full list. How many names should be selected each time to predict with 90% certainty that 90% of all the names will be selected at least once?

Answer 1

The answer is $n=17$.

I can't see an easy analytic solution to this question. Instead, we will develop an analytic solution to a closely related problem, and then find the answer to your exact question via simulation.

Clarification:

Since the question is slightly vague, let me re-state the problem. There are $200$ names on a list and $n$ names will be selected from this list without replacement. This process, using the full $200$ names each time, is repeated a total of $30$ times.

A related problem.

Let $X_i$ equal $1$ if the $i^{th}$ name is selected at least once and equal to $0$ otherwise. This implies that $$X = \sum_{i=1}^{200}X_i$$ represents the total number of names which are selected at least once. Since the $X_i$ are dependent, the exact distribution of $X$ is not-trivial, and the original question is hard to answer. Instead, we can easily determine the value of $n$ such that $90\%$ of the names are selected on average.

First, note that $$P(X_i = 0) = \left(\frac{200 - n}{200}\right)^{30}$$ which implies $$E(X_i) = P(X_i =1) = 1 - \left(1- \frac{n}{200}\right)^{30}.$$

Now by linearity of expectation we have $$E(X) = \sum_{i=1}^{200}E(X_i) = 200\left(1 - \left(1- \frac{n}{200}\right)^{30}\right).$$

For this expectation to equal $90\%$ of the names, we need to set $E(X) = 180$ and solve for $n$. This gives $$n = 200\left(1 - (1 - 0.9)^{1/30}\right) = 14.776.$$

Thus $n=15$ names should be drawn from the list each time for this to occur on average. This answer will be close to (but not the same as) the original question with $50\%$ certainty. To achieve $90\%$ certainty, we will need to increase $n$.

Simulations.

First, we write a function which is able to generate $X$ a large number (say $M$) times for a given value of $n$.

sample_X <- function(n, M){
  X <- rep(NA, M)
  for(i in 1:M){
    #Set all names to false
    names <- rep(FALSE, 200)
    #Repeat process 30 times
    for(k in 1:30){
      #Sample n names from list
      selection <- sample(200, n, replace=F)
      #Mark that these names have been selected
      names[selection] <- TRUE
    }
    #Let X be the number of selected names
    X[i] <- sum(name_been_selected)
  }
  return(X)
}

Now, for a given value of $n$ we can approximate "the probability that at least $90\%$ of the names are selected", i.e. $P(X \geq 180)$. In R, this probability can be approximated by typing:

X <- sample_X(n, M=10000)
prob <- mean(X >= 180)

Repeating this for $n = 14, 15, \cdots 20$ gives us the following plot.

From the plot, we can determine that $n=17$ names must be selected in each round for the probability of selecting at least $180$ names to exceed $0.9$.

The blue line in the figure shows the exact simulations detailed above. The orange line is an approximation which is obtained by ignoring the dependency of the $X_i$ (see previous section) and assuming that $$X \sim \text{Binom}\left(200, 1 - \left(1- \frac{n}{200}\right)^{30}\right).$$

Although the assumption of independence is obviously incorrect, the probabilities obtained by this simple assumption are reasonably close to the simulated probabilities.

Answer 2

Here is a general analytic solution --- does not require simulation

This is a variation on the classical occupancy problem, where you are sampling lots of thirty names at each sampling point, instead of sampling individual names. The simplest way to compute this result is by framing the problem as a Markov chain, and then computing the required probability using the appropriate power of the transition probability matrix. For the sake of broader interest to other users, I will generalise from your example by considering a list with $m$ names, with each sample selecting $1 \leqslant h \leqslant m$ names (using simple-random-sampling without replacement).

---

The general problem and its solution: Let $0 \leqslant K_{n,h} \leqslant m$ denote the number of names that have been sampled after we sample $n$ times with each lot sampling $h$ names. For a fixed value $h$ the stochastic process $\{ K_{n,h} | n = 0,1,2,... \}$ satisfies the Markov assumption, so it is a Markov chain. Since each sampling lot is done using simple-random-sampling without replacement, the transition probabilities for the chain are given by the hypergeometric probabilities:

$$P_{t,t+r} \equiv \mathbb{P}(K_{n,h} = t+r | K_{n-1,h} = t) = \frac{{m-t \choose r} {t \choose h-r}}{{m \choose h}}.$$

Let $\mathbf{P}_h$ denote the $(m+1) \times (m+1)$ transition probability matrix composed of these probabilities. If we start at the state $K_{0,h} = 0$ then we have:

$$\mathbb{P}(K_{n,h} = k) = [ \mathbf{P}_h^n ]_{0,k}.$$

This probability can be computed by matrix multiplication, or by using the spectral decomposition of the transition probability matrix. It is relatively simple to compute the mass function of values over $k=0,1,...,m$ for any given values of $n$ and $h$. This allows you to compute the marginal probabilities associated with the Markov chain, to solve the problem you have posed.

The problem you have posed is a case of the following general problem. For a specified minimum proportion $0 < \alpha \leqslant 1$ and a specified minimum probability $0 < p < 1$, we seek the value:

$$h_* \equiv h_* (\alpha, p) \equiv \min \{ h = 1,...,m | \mathbb{P}(K_{n,h} \geqslant \alpha m) \geqslant p \}.$$

In your problem you have $m=200$ names in your list and you are taking $n=30$ samples. You seek the value $h_*$ for the proportion $\alpha = 0.9$ and the probability cut-off $p = 0.9$. This value can be computed by computing the relevant marginal probabilities of interest in the Markov chain.

---

Implementation in R: We can implement the above Markov chain in R by creating the transition probability matrix and using this to compute the marginal probabilities of interest. We can compute the marginal probabilities of interest using standard analysis of Markov chains, and then use these to compute the required number of names $h_*$ in each sample. In the code below we compute the solution to your problem and show the relevant probabilities increasing over the number of samples (this code takes a while to run, owing to the computation of matrix-powers in log-space).

#Create function to compute marginal distribution of Markov chain
COMPUTE_DIST <- function(m, n, H) {
  
  #Generate empty matrix of occupancy probabilities
  DIST <- matrix(0, nrow = H, ncol = m+1);
  
  #Compute the occupancy probabilities
  for (h in 1:H) {
    
    #Generate the transition probability matrix
    STATES <- 0:m;
    LOGP <- matrix(-Inf, nrow = m+1, ncol = m+1);
    for (t in 0:m) {
    for (r in t:m) { 
      LOGP[t+1, r+1] <- lchoose(m-t, r-t) + lchoose(t, h-r+t) - lchoose(m, h); } }
    PP <- exp(LOGP);
    
    #Compute the occupancy probabilities
    library(expm);
    DIST[h, ] <- (PP %^% n)[1, ]; }
  
  #Give the output
  DIST;  }

#Compute the probabilities for the problem
m <- 200;
n <- 30;
H <- 20;
DIST <- COMPUTE_DIST(m, n, H);

From the marginal probabilities for the Markov chain, we can now compute the required value $h_*$ for your particular problem.

#Set parameters for problem
alpha  <- 0.9;
cutoff <- ceiling(alpha*m);
p      <- 0.9;

#Find the required value
PROBS <- rowSums(DIST[, (cutoff+1):(m+1)]);
hstar <- 1 + sum(PROBS < p);

#Show the solution and its probability
hstar;
[1] 17

PROBS[hstar];
[1] 0.976388

We can see here that we require $h_* = 17$ samples in order to obtain a minimum $p=0.9$ probability of sampling at least $\alpha \cdot m = 180$ of the names on the list. Below we show a plot of the probabilities for values $h=1,...,20$ with the required value highlighted in red.

#Plot the probabilities and the solution
library(ggplot2);
THEME <- theme(plot.title    = element_text(hjust = 0.5, size = 14, face = 'bold'),
               plot.subtitle = element_text(hjust = 0.5, face = 'bold'));
DATA <- data.frame(h = 1:H, Probability = PROBS);
ggplot(aes(x = h, y = Probability), data = DATA) + 
    geom_point(size = 3, colour = 'blue') +
    geom_point(size = 4, colour = 'red', data = DATA[hstar, ]) +
    geom_hline(yintercept = p, size = 1, linetype = 'dashed') + 
    geom_segment(aes(x = hstar, y = 0, xend = hstar, yend = DATA[hstar, 2]),
                 colour = 'red', size = 1) + 
    annotate("text", x = hstar + 1, y = 0.1,
             label = paste0('h = ', hstar), colour = 'red', fontface = 'bold') + 
    THEME +
    ggtitle('Probability of required occupancy') + 
    labs(subtitle = paste0('(Occupancy problem taking ', n, 
         ' samples of size h from ', m, 
         ' units) \n (We require ', sprintf(100*alpha, fmt = '%#.1f'),
         '% occupancy with ', sprintf(100*p, fmt = '%#.1f'), '% probability)'));

Answer 3

The answer is $n = 17$, with $P(N_{30}\ge180)=0.976388$.

The approach I took to calculate the probability after 30 draws was to determine the probability of drawing seen vs. unseen names at each round.

When drawing $n$ names out of $p=200$ after having seen $s$ of them, let's call $U_s$ the number of names out of those $n$ which were previously unseen.

Then we have:

$$P(U_s = u) = \frac{\text{P}(200-s, u) \text{P}(s, n-u) \text{C}(n, u)}{\text{P}(200, n)}$$

The first term is the permutations of u previously unseen names, the second permutations of previously seen ones. The last term $\text{C(n, u)}$ accounts for the $u$ unseen names coming in different positions out of the $n$ drawn. The denominator accounts for all possible draws of $n$ names.

Having calculated that, we can look at successive draws of names. Let's call $N_d$ the total number of names after draw $d$.

Before the first draw, there will be no previously seen names, so in the first draw all $n$ names will be seen for the first time.

$$P(N_1=n)=1$$

We can then calculate the probability of drawing a certain number of names on draw $N_{d+1}$ by looking at the possibilities of drawing after $N_d$ and having a specific number of previously unseen names. Which we can calculate with:

$$P(N_{d+1} = x) = \sum_{i=0}^{n}{P(N_d = x-i) P(U_{x-i} = i)}$$

For example, if we're drawing $n=16$ every time, then drawing exactly 180 names in total in a specific drawing can be arrived at by drawing 164 names in the previous drawing an then drawing exactly 16 unseen names (totalling 180), or having previously seen 165 names and drawing 15 unseen and one previously seen name, and so on... Until the possibility of having seen 180 names in the previous iteration and drawing all 16 previously seen names.

At this point we can use iteration to calculate $P(N_{30} \ge 180)$ for different values of $n$.

Iteration in Python:

This code uses Python 3 and as written requires Python 3.8 for math.comb() and math.perm() from the standard library (if using an older version of Python, you can use a different implementation of those functions.)

Let's start with $P(U_s = u)$:

from functools import lru_cache
from math import comb, perm

@lru_cache
def prob_unseen(n, p, s, u):
    # Return  the probability of drawing
    # exactly $u$ unseen names when
    # drawing $n$ names out of a total of $p$,
    # having previously seen $s$ of them.
    return (perm(p-s, u) *
            perm(s, n-u) *
            comb(n, u) /
            perm(p, n))

Pretty straightforward. Now for $P(N_d = x)$ let's use a list of 201 elements (indices go from 0 to 200) to track the probabilities for each $x$:

def names_in_draw(prev_draw, n):
    # Calculate probabilities of finding
    # exactly $x$ names in this draw,
    # for every $x$, taking in consideration
    # the probabilities of having drawn specific
    # numbers of names in the previous draw.
    p = len(prev_draw) - 1
    this_draw = [0.0] * (p+1)
    for x in range(n, p+1):
        this_draw[x] = sum(
           prev_draw[x-u] * prob_unseen(n, p, x-u, u)
           for u in range(n+1))
    return this_draw

Finally, let's calculate the probability for the number of names after $d$ draws.

def total_names(n, p, d):
    # Calculate probabilities for finding
    # exactly $x$ names after $d$ draws.
    draw = [0.0] * (p+1)
    draw[n] = 1.0  # first draw
    for _ in range(d):
        draw = names_in_draw(draw, n)
    return draw

We start from the first draw, where we know for sure we'll draw $n$ unique names. Than we repeatedly calculate the probabilities $d-1$ times.

Finally, we can calculate the probability of drawing at least $x$ names, drawing $n$ out of $p$ at a time, performing $d$ drawings:

def prob_names(n, p, d, x):
    # Return the probability of seeing
    # at least $x$ names after $d$ drawings,
    # each of which draws $n$ out of $p$ names.
    return sum(total_names(n, p, d)[x:])

Finally, we can run this for a few values of $n$ to find the probabilities:

>>> for i in range(13, 20):
...     print(i, prob_names(i, 200, 30, 180))
13 0.058384795418431244
14 0.28649904267865317
15 0.6384959089930037
16 0.8849450106842117
17 0.976388046862824
18 0.9966940083338005
19 0.9996649977705089

So $n=17$ is the answer, with probability of 97.6388% of seeing at least 90% of the names. $n=16$ comes close, with 88.4945%.

(Since I had the code, I also looked at how many drawings of a single name are needed to see 90% of the names, with 90% probability. It turns out it's 503 drawings, or 454 drawings to see 90% of the names with 50% probability. Quite interesting result!)