Suppose that we want to determine which members of a population have a certain disease, and that whether or not any of the members of a group has the disease can be ascertained by a single pooled test. Assuming that each member of the population independently has the disease with known probability p, the objective is to find a pooling scheme that minimizes the expected number of tests to classify all members of the population as being disease positive or negative.
The halving scheme for pooled testing was introduced in [1 ]. Say that a group is positive if it is known that at least one of its pooled members has the disease. In the halving scheme one breaks up the population into sets of size n and does a pooled test on a set. If it comes up positive, then the set is randomly split into two new groups of equal size (or as near as possible) and each of these groups is given a pooled test. This continues until the disease state of all members of the population has been determined. (Actually, if a positive group is broken in two subgroups, and the first one of its subgroups tests negative, then the other subgroup must be positive and so need not be tested as a whole but should just be randomly split.) Let X n denote the number of tests needed to classify a group of size n when you start by testing all n as a pooled group and then use the halving procedure afterwards. Recursions for the probability mass function of X n when n = 15 were given in [1 ] by an approach that does not appear to scale up for larger values of n. In the recent paper [2 ], the halving scheme was proposed as a possibility for use in the Covid-19 pandemic in places where test kits are limited. It is suggested in [2 ] that to minimize E[X n ]/n, the average number of tests per individual, n be chosen as close as possible to n 0 ≡ -log(2)/ log(1 -p), which would make (1 -p) n 0 , the probability of a positive result, approximately equal .5. The mean number of tests required per person was determined by a simulation in [2 ], and an analytic approximation was provided. Whereas [1 ] and [2 ] assume that p is know, the paper [3 ] deals with the problem of estimating p when a pooled scheme is used.
In this paper, we show how to derive E[X n ] and Var(X n ) by easily computed recursions. In doing so, we also indicate that the initial choice of pooling n 0 , while not optimal is quite close. Indeed, letting n(opt) be the value of n that minimizes E[X(n)] n ; if p = .05 then n 0 = 13.5 whereas n(opt) = 13; if p = .01 then n 0 = 68.9 whereas n(opt) = 75; if p = .001 then n 0 = 692.8 whereas n(opt) = 683; and if p = .0001 then n 0 = 6931.13 whereas n(opt) = 6827.
In our analysis we will suppose that if the pooled test of an odd number of people comes up positive, then the first of its two subgroups to be tested is the smaller one. In Section 2 we derive a recursion for E[X n ]. In Section 3 we give the R code for obtaining argmin n E[X(n)]/n and min E[X n ]/n, and comment on what can be done when p is initially unknown. Along the way, we obtain counterexamples showing that (a) the halving scheme of splitting a positive group into two equal subgroups need not be optimal, and (b) -E[X n ]/n is not necessarily a unimodal function of n (e.g., it is not necessarily true that E[X n ]/n first decreases and then increases). Finally, in Section 4 we derive a recursion for computing Var(X n ).
Let q = 1 -p. Let I be the indicator of the event that the group of size n tests positive. That is, I = 1 if the group tests positive, and 0 otherwise.
Then, with Y n denoting the number of tests needed to identify all members of a group of size n known to be positive,
Using that P (I = 1) = 1 -q n , we see that
To determine a recursion for E[Y n ], let J be the indicator function of the event that the first one of the 2 splittings of the positive group of size n (e.g., the one of size n-1 2 when n is odd) tests positive. Then
if n is even
Because the second subgroup will be known to be positive if the first tests negative, we see that when n is an even positive integer
Thus, when n is even
(4)
Now Y (1) = 0, and when n 3 is odd
(5)
Thus, when n 3 is odd
Starting with E[Y 1 ] = 0, Equations ( 1), (4), and (6) give the recursion for
Although dividing a positive group into two subgroups of equal size (or as close to equal as possible when the group size is odd) seems reasonable, it may be surprising to know that it need not be optimal. For a counterexample, suppose that p is very small, so that except for n extremely large, a positive group of sized n will, with probability extremely close to 1, have exactly one positive member. Then, using
we obtain that
Thus, using our halving scheme
On the other hand, if the positive group of size 8 were broken into subgroups of sizes 3 and 5, with the one of size 3 tested first, and the halving scheme followed from then on, then
Thus, for small p, the split (3, 5) is better than the split (4, 4).
The following R code yields, when N is an even number and q ∈ [0, 1], the value of a function m(q, N ) defined to the vector
where N is an even number and q = 1 -p. In the code
For given values of q, N, one inputs m(q, N ) and its value is given. For When p = .0001, the preceding indicates that the optimal number to test when the upper limit is 5, 000 is 4949, and the optimal number is 6827 when the upper limit is 10, 000. This is quite interesting because, with
n , it shows that F (6827) < F (4949) < F (5000), thus contradicting a seemingly reasonable hypothesis that F (n) first decreases and then increases in n.
When p is unknown, we suggest that it be continually estimated by x+1 x+y+2 where x is the number of people known to be positive and y is the number known to be negative, and when a new group is to be tested its size be determined as if p were equal to its estimated value. This would mean that initially a single individual should be tested; if negative then the next group should be of size 2 and if positive of size 1, and so on.