Question

Consider the following deterministic "two-level" testing scheme. We divide a population of n individuals to be tested into C arbitrary groups of the same size. We then test each of these groups in aggregate. For any group that comes back positive, we retest all members of the group individually. Show that there is a choice for C such that, if k individuals in the population have COVID-19, we can find all of those individuals with ≤2√(nk) tests. You can assume k is known in advance (often it can be estimated accurately from the positive rate of prior tests). This is already an improvement on the naive n tests when k < 25%n.

Answer 1

To find a choice for C such that we can find all individuals with ≤2√(nk) tests, we can consider the worst case scenario and choose C = 2√n.

Step-by-step explanation:

To find a choice for C such that we can find all individuals with ≤2√(nk) tests, we can consider the worst case scenario. Let's assume that all k individuals who have COVID-19 are in the same group. In this case, if we test all groups in aggregate, we will get a positive result for that group. Then, we will need to retest all the individuals in that group individually. This would require nk tests to find all k individuals. Now, we need to choose a value for C that satisfies ≤2√(nk). Let's choose C = 2√n. By substituting this value, we get ≤2√(2√n * k). Simplifying further, we get ≤2√(2 * √(n * k)). And finally, ≤2 * √(√2 * √(n * k)). Therefore, by choosing C = 2√n, we can find all k individuals with ≤2√(nk) test