Doing some probability problems for fun. Can't seem to figure out where I'm going wrong here:

The army needs to test n soldiers for a disease. There is a blood test that accurately determines when a blood sample contains blood from a diseased soldier. The army presumes, based on experience, that the fraction of soldiers with the disease is approximately equal to some small number $p$.

Approach (1) is to test blood from each soldier individually; this requires $n$ tests. Approach (2) is to randomly group the soldiers into $g$ groups of $k$ soldiers, where $n = gk$. For each group, blend the $k$ blood samples of the people in the group, and test the blended sample. If the group-blend is free of the disease, we are done with that group after one test. If the group-blend tests positive for the disease, then someone in the group has the disease, and we to test all the people in the group for a total of $k+1$ tests on that group. Since the groups are chosen randomly, each soldier in the group has the disease with probability $p$, and it is safe to assume that whether one soldier has the disease is independent of whether the others do.

What is the expected number of tests in Approach (2) as a function of the number of soldiers $n$, the disease fraction $p$, and the group size $k$?

My thought about the approach is as follows:

First, calculate the probability that one or more samples are positive in a group of k samples: $$p' = 1 - \binom{k}{0}(1-p)^k = 1-(1-p)^k$$

Now, the number of positive pooled samples is binomial distributed with: $$E[number\ positive\ groups] = gp'$$

since when a group is positive, there will be $k+1$ tests, I would think the expected number of tests would be: $$E[number\ tests] = gp'(k+1) = g(k+1)(1-(1-p)^k) = gk - gk(1-p)^k + g - g(1-p)^k$$ $$= n-n(1-p)^k + \frac{n}{k} - \frac{n}{k}(1-p)^k$$

The next part of this question asks:

Show how to choose $k$ so that the expected number of tests using Approach (2) is approximately $n\sqrt{p}$. Hint: Since $p$ is small, you may assume that $(1 - p)^k \approx 1$ and $ln(1-p) \approx -p$.

However, assuming that $(1-p)^k \approx 1$ makes my expected number of positive pooled samples equal to zero. So I'm definitely doing something seriously wrong.


If $gp'$ groups are expected to test positive, then $g(1-p')$ groups are expected to test negative. The total expected number of tests is therefore $$gp'(k+1) + g(1-p'),$$ because negative groups require one test, and positive groups require $k+1$ tests. Thus the correct expectation is $$\operatorname{E}[\text{Tests}] = \frac{n}{k}(1+k-k(1-p)^k).$$

  • $\begingroup$ Wow, what a dumb oversight on my part. Thanks $\endgroup$ – lstbl Oct 15 '16 at 20:22
  • 1
    $\begingroup$ @lstbl No, it most certainly is not a dumb oversight. I carefully read through your solution at least three times before I realized what was missing. $\endgroup$ – heropup Oct 15 '16 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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