Sampling without replacement until all elements of specific type are found

Question

Suppose I have a population of size $n$ in which each element has a probability $p$ of being sick. By sampling this population without replacement, how many elements would I have to sample in average (expected value) to find all the sick ones?

Simulating this in Python, when $n=100$ and $p=0.5$, the expected value is $\approx$99.

Answer 1

Cumulative distribution function (CDF)

Based on @whuber's comments, their formula represents the probability that the final $n-k$ observations will be non-successes, which is the same as the first $k$ observations containing all existing successes (i.e., the CDF).

$$ P(k)=(1-p)^{n−k} $$

Probability mass function (PMF)

The PMF represents the probability that after $k$ observations, all existing successes have been found. We can derive it from the CDF:

$$ \begin{align*} p(k)&=P(k)-P(k-1)\\ &=(1-p)^{n−k}-(1-p)^{n−(k-1)}\\ &=p(1-p)^{n-k} \end{align*} $$

i.e.

$$ p(k)=p(1-p)^{n-k} $$

Expected value

To determine the expected value (mean) for our probability mass function, we use the expected value's general expression:

$$ E[X]=\sum_i x_i\,p(X=x_i) $$

where:

• $E[X]$ is the expected value of the random variable $X$
• $x_i$ represents the possible values of the random variable $X$
• $p(X=x_i)$ is the probability mass function of the random variable $X$, which gives the probability that $X$ takes on the value $x_i$

Replacing with the terms from our problem, we get:

$$ \begin{align*} E[k]&=\sum_{k=0}^{n}kp(1-p)^{n-k}\\ &=p(1-p)^n\sum_{k=0}^{n}k(1-p)^{-k} \end{align*} $$

We need to analytically simplify the summation $\sum_{k=0}^{n}k(1-p)^{-k}$. If we define $r=(1-p)^{-1}$, the summation becomes:

$$ \sum_{k=0}^{n} kr^k $$

To simplify our summation, we can now use the sum of the first $n$ terms of the arithmetico-geometric sequence, which has the form:

$$ \sum_{k=1}^{n}\left[a+(k-1)d\right]br^{k-1}=\frac{ab-(a+nd)br^n}{1-r}+\frac{dbr(1-r^n)}{(1-r)^2} $$

If we set $a=d=1$ and $b=r$, the expression becomes:

$$ \sum_{k=1}^{n}kr^k=\frac{r-(1+n)r^{n+1}}{1-r}+\frac{r^2(1-r^n)}{(1-r)^2} $$

Using it in our $E[k]$ expression while remembering that $r=(1-p)^{-1}$, we get:

$$ E[k]=p(1-p)^n\left[\frac{(1-p)^{-1}-(1+n)(1-p)^{-n-1}}{1-(1-p)^{-1}}+\frac{(1-p)^{-2}(1-(1-p)^{-n})}{(1-(1-p)^{-1})^2}\right] $$

Using SymPy to simplify the previous expression, we obtain:

$$ E[k]=\frac{p \left(n - \left(1 - p\right)^{n} + 1\right) + \left(1 - p\right)^{n} - 1}{p} $$

Which can be further rewritten to get to @Hunaphu's formula:

$$ \begin{align*} E[k]&=\frac{p \left(n - \left(1 - p\right)^{n} + 1\right) + \left(1 - p\right)^{n} - 1}{p}\\ &=n-(1-p)^n+1+\frac{(1-p)^n-1}{p}\\ &=n+\frac{p-p(1-p)^n+(1-p)^n-1}{p}\\ &=n+\frac{(1-p)^n(1-p)-(1-p)}{p}\\ &=n+\frac{(1-p)^{n+1}-(1-p)}{p} \end{align*} $$

Therefore, the answer to my question is:

$$ E[k]=n+\frac{(1-p)^{n+1}-(1-p)}{p} $$

Which is exactly @Hunaphu's formula, but doesn't seem at all related with the hypergeometric distribution, as they suggested.

In any case, thanks to @whuber for providing an idea on how to start solving the problem, and to @Hunaphu for having presented the final answer, although lacking any feasible explanation on how they got there.

If there's a shorter path to this answer, please provide more answers, as I would like to know about it.

Answer 2

Problem formulation

Index the subjects $1, 2, \ldots, n$ in the order to be observed and for each $k=1,2,\ldots, n$ let $X_k$ be the indicator of whether subject $i$ is sick. The index of the last sick subject, $K,$ is function of the $X_k$ and therefore also is a random variable. (When no subjects are sick, you don't have to sample any at all, in which case we will define $K=0.$) You want to know the expected value of $K.$

Solution

A simple, direct method begins with the distribution function of $K$ defined by

$$F_K(k) = \Pr(K\le k) = \Pr(X_{k+1}=\cdots=X_n= 0) = (1-p)^{n-k}$$

assuming the $\{X_k\}$ are independent. Now

$$E[K] = \int_0^\infty (1 - F_K(k))\,\mathrm dk = \sum_{k=0}^{n-1} (1 - (1-p)^{n-k}) = n - (1-p)\frac{1 - (1-p)^n}{p}.$$

(This is algebraically equivalent to the formulas given in the existing answers, but -- as requested -- is derived in a short, simple manner.)

---

Because it's easy to make off-by-one errors, let's do some quick checks of simple cases.

1. $n=0.$ By definition $K=0,$ so the formula had better give $0$ for its expectation. Indeed, $$0 - (1-p)\frac{1 - (1-p)^0}{p} = -(1-p)\frac{0}{p} = 0$$ provided $p\ne 0$ (an exception taken care of below).

2. $n=1.$ The unique subject is sick with probability $p,$ where $K=1;$ otherwise $K=0.$ Thus the expectation must be $p(1) + (1-p)(0) = p.$ The formula also gives $$1 - (1-p)\frac{1 - (1-p)^1}{p}=p,$$ again provided $p\ne 0.$

3. $p=1.$ All subjects are sick and so $K=n$ almost surely. The formula also gives $$n - (1-1)\frac{1 - (1-1)^n}{1} = n.$$

4. $p=0.$ No subjects are sick and so $K=0$ almost surely. The formula is undefined, but we may take the limit as $p\to 0$ from above via L'Hopital's Rule, $$\lim_{p\to 0^+}n - (1-p)\frac{1 - (1-p)^n}{p} = n - \lim_{p\to 0^+} \frac{-1 + (n+1)(1-p)^n}{1} = 0.$$

Answer 3

The number of sick patients on a specific sample follows a hypergeometric distribution. The expectation, once calculated, is $$ N+\frac{(1 - p)^{N + 1} - (1-p)}{p} $$