Group testing is the following problem. Suppose there are n individuals, some of whom are infected with a disease. If a test exists that reliably detects the disease, then each individual can be separately tested for the disease to find if they have it or not, requiring n tests. However, in theory, a pooled strategy can be better: we can take samples from a number of individuals, pool the samples together, and test this pooled sample. If none of the individuals are infected, the test should be negative, while if one or more are the individuals are positive then, in theory, the test should be positive. It might be possible to ascertain which individuals have the disease in fewer than n such pooled tests, thus saving resources when tests are expensive or limited.
Recent experiments suggest that the group testing paradigm holds for SARS-CoV-2, the virus that causes the disease covid-19; that is, pools of samples with just one positive sample and many negative samples do indeed produce positive results, at least for pools of around 32 samples or fewer [1, 8, 29, 31] . This work has led to a great interest in group testing as a possible way to make use of limited tests for covid-19; such work includes [9, 18, 19, 20, 22, 27, 28] and other papers we cite later.
Many of these papers use a similar model that we also use here: the number of individuals n is large; the prevalence p is constant; each individual is infected independently with probability p (the 'i.i.d. prior'); we wish to reduce the average-case number of tests ET ; and we want to be certain that each individual is correctly classified (the 'zero-error' paradigm). We emphasise the fact that p is constant as n → ∞ puts us in the so-called 'linear regime', rather than the often-studied 'sparse regime' where p → 0 as n gets large; the linear regime seems more relevant with applications to covid-19 and other widely spread diseases.
Later, it will sometimes be convenient to instead consider the 'fixed-k' prior, where there is a fixed number k = pn of infected individuals. We discuss this mathematical convenience further in Subsection 3.3.
For more background on group testing, we point readers to the recent survey [5] .
An important distinction is between nonadaptive testing, where all tests are designed in advance and can be carried out in parallel, and adaptive testing, where each test result is examined before the next test pool is chosen.
Recall we are the linear regime, where p is constant. For nonadaptive testing, a result of Aldridge [2] shows that any nonadaptive scheme using T < n tests has error probability bounded away from 0. So simple individual testing will be the optimal nonadaptive strategy, unless errors are tolerated -and errors that don't even vanish in the large n limit at that. For adaptive testing, the best known scheme is a generalized binary splitting scheme studied by Zaman and Pippenger [32] and Aldridge [3] , based on ideas of Hwang [23] . This scheme is the optimal 'nested' strategy [32] , and is within 5% of optimal for all p ≤ 1/2 [3] . This algorithm (or special cases, or simplifications) was discussed in the context of covid-19 by [18, 19, 25] . However, adaptive schemes are unlikely to be suitable for testing for covid-19, as many tests must be performed one after the other, meaning results will take a very long time to come back.
We propose, rather, using an adaptive strategy with only two stages. Within stages, tests are performed nonadaptively in parallel, so results can be returned in only the time it takes to perform two tests. This provides a good compromise between the speed but inevitable errors (or full n individual tests) of nonadaptive schemes and the fewer tests but unavoidable slowness of fully adaptive schemes. Two-stage testing goes back to the foundational work of Dorfman [13] , and has been discussed more recently in the context of covid-19 by [6, 8, 10, 15, 18, 21, 30] .
From now on, we adopt standard group testing terminology as in, for example, [14, 4, 5] . In particular, individuals are 'items' and infected individuals are (slightly unfortunately) 'defective items'.
A two-stage algorithm that is certain to correctly classify every item works as follows:
1. In the first stage, we perform some number T 1 of nonadaptive tests. This will find some nondefective items: any item that appears in a negative tests is a definite nondefective (DND). This will also find some defective items: any item that appears in a positive tests in which every other item is DND is a definite defective (DD).
2. In the second stage, we must individually test every item whose status we so not yet know -that is, all items except the DNDs and DDs. This requires T 2 = n − (# DNDs + # DDs) tests.
Ruling out DNDs when they appear in a negative test is a simple procedure in practice: following a negative test, a laboratory must simply report the samples in that pool. Further, if the test procedure can be unreliable, the procedure can easily be changed to ruling out items after they appear in some number d > 1 of negative tests. However, 'ruling in' DDs is trickier: first information about all the DNDs must be circulated (potentially among many different laboratories, with the privacy problems that entails), then each positive test must be carefully checked to see if all but one of the samples has been ruled out as a DND. Confirming that an item is defective thus involves checking a long chain of test results and pool details, which is complicated, very susceptible to occasional testing errors, and can be difficult to prove to a clinician's or patient's satisfaction.
With these problems in mind, we introduce a variant we call conservative two-stage group testing. This adds the rule that every defective item must be definitively 'certified' by appearing in a (necessarily positive) test in the second stage in which it is the sole item. This gives a very simple proof that an item is defective, with the 'gold standard' individual test that will not be susceptible to dilution from other samples.
So in the first stage of conservative two-stage testing, a nonadaptive scheme is used only to rule out DNDs -that is, items that appear a negative tests and are thus definite nondefectives. In the second round, each remaining item is individually tested, requiring T 2 = n − # DNDs tests.
Since in the first stage of two-stage testing, we want to discover DNDs and DDs, while in the first stage of conservative two-stage testing we can concentrate on simply discover DNDs, we can say that two-stage testing has a lot in common with the 'DD algorithm' of [4, 24, 5] , while conservative two-stage testing is more like the 'COMP algorithm' of [11, 4, 24, 5] .
Two-stage testing has previously received attention in the sparse p = o(1) setting; we direct interested readers to [26] for more details, or [5, Section 5.2] for a high-level overview. In the sparse regime, recovery always requires order k log n tests, so the difference between testing up to k DDs or not -that is, the distinction between usual two-stage testing and conservative two-stage testing -makes up a negligible proportion of tests, and can be considered irrelevant. It is only in the linear regime we consider here that we have to worry about the costs of definitively confirming items we think are defective.
In this paper we consider five algorithms for nonconservative two-stage testing. Recall that the second stage is always 'test every item not ruled out as a DND', so we need only define the first stage.
Individual testing tests nothing in the first stage and tests every item individually in the second stage. Although very simple, this is provably the best scheme for p ≥ (3 − √ 5)/2 = 0.382, and is the best conservative two-stage scheme we consider here for
Dorfman's algorithm splits the items into sets of size s and tests each set in the first stage, then individually tests each item in the positive sets in the second stage. Dorfman's algorithm is the best scheme we consider here for p > 0.121, although for p > 0.307 the optimal value is s = 1, where it is equivalent to individual testing.
Bernoulli first stage where, in the first stage, each item is placed in each test independently with the same probability. This scheme is suboptimal, but within 0.2 bits of optimal for all p. For p > 1/(e + 1) = 0.269, the optimal number of first-stage tests is 0, and we recover individual testing.
Constant tests-per-item first stage where in the first stage, each item is placed in the same number r of tests, chosen at random. This scheme is suboptimal, but very close to optimal when p is small. For For p > 0.269, the optimal number of first-stage tests is 0, and we recover individual testing.
Doubly constant first stage where where in the first stage, each item is placed in the same number r of tests and each test contains the same number r of items, chosen at random. This is the best scheme we consider for all p, and is extremely close to our lower bound. For p > 0.268, the optimal the optimal number of first-stage tests is 0 and we recover individual testing; while for p > 0.121, the optimal number of tests per item is r = 1, and we recover Dorfman's algorithm.
We also give a lower bound for the number of tests required for conservative two-stage testing (Theorem 5). Along the way, we also find a new lower bound for usual non-conservative two-stage testing (Theorem 4), which may be of independent interest. Our main results on the average numbers of tests necessary are illustrated in Figure 1 . The top subfigure shows the 'aspect ratio' [3] : the expected number of tests normalised by the number of items ET /n (smaller is better) in the large n limit. We can compare the aspect ratio to individual testing with T /n = 1 and the counting bound (see, for example, [7, 5] ) which says that ET /n ≥ H(p), where H(p) is the binary entropy.
The middle subfigure shows the rate nH(p)/ET (higher is better) in the large n limit, which corresponds the average number of bits of information learned per test [7, 5] . The rate can be compared to individual testing, with nH(p)/T = H(p) and the counting bound nH(p)/ET ≤ 1.
The doubly constant design is so close to the lower bound for the number of tests (which becomes an upper bound on the rate), that it can be difficult to see both. The bottom subfigure shows a zoomed in section of the rate graph.
While the expressions in our main theorems are smooth for fixed values of the parameters, sometimes the parameters must be integers, with sudden jumps in the optimal value from one integer to the next. This leads to 'crooked' lines in graphs of the aspect ratio, and 'bumpy' lines in graphs of the rate. The 'kink' in the lower bound at p = 0.171 is where the dominant lower bound of Theorem 4 switches from Bound 2 to Bound 3 of that theorem.
Alongside our theoretical results for large n, we present evidence from simulations with n = 1000 items (or just above 1000, if convenient for rounding reasons) and prevalence p = 0.027. We picked this value of p as it is an estimate by the Imperial College covid-19 Response Team for the prevalence of covid-19 in the UK as of 28 March 2020 [17] .
Specifically, we used the following algorithms, with parameters suggested by the optimal value in the large-n limit:
Individual testing with n = 1000 items, so T = 1000 tests.
Dorfman's algorithm with n = 1001 items, and s = 7 items per test, so T 1 = n/s = 143 tests in the first stage.
Bernoulli first stage with n = 1000 items, Bernoulli parameter π = 1/pn = 0.037, and T 1 = 190 tests in the first stage, so σ = 1/p = 37.0 items per test on average.
Constant tests-per-item first stage with n = 1000 items, r = 4 tests per item, and T 1 = 160 tests in the first stage, so σ = nr/T 1 = 25 items per test on average.
Doubly constant first stage with n = 1000 items, r = 4 tests per item, and s = 25 items per test, so T 1 = nr/s = 160 tests in the first stage.
We simulated each algorithm 1000 times. Table 1 shows the results of the simulations, displaying the mean number of tests used, alongside the first and ninth deciles. These simulated results are compared with a 'theory' result, which takes the theoretical behaviour of ET as n → ∞ (from Section 3) and plugs in n = 1000. We see that, compared to individual testing, the other four algorithms give at least a three-fold reduction in the number of tests required on average, with constant tests-per-item and doubly constant designs giving a four-fold reduction. The Bernoulli first stage was a significant improvement on Dorfman's algorithm, while the constant tests-per-item and doubly constant designs were a large improvement further. The difference between a constant tests-per-item and doubly constant first stage was small; this is not surprising, as our theoretical results show that constant tests-per-item is very close to optimal for p this small (see Figure 1) .
We see that Dorfman's algorithm performs on average very close to theoretical predictions. The Bernoulli, constant tests-per-item and doubly constant designs require about 6 more tests on average than the n → ∞ asymptotics imply; this is presumably because pn = 27 is sufficiently small that rare large defective populations drive up the average number of tests in a way that becomes increasingly unlikely as pn → ∞.
3 Algorithms for conservative two-stage testing 3 
Individual testing has no first round T 1 = 0 then tests every item in the second round T 2 = n. This is a conservative algorithm with T = 0 + n = n.
It is proved in [2] that individual testing is the optimal one-stage algorithm for all p ∈ (0, 1). It is proved in [16] that individual testing is the optimal adaptive algorithm for all p > (3 − √ 5)/2 = 0.369.
Dorfman's algorithm [13] was the first group testing algorithm. We split the items into n/s groups of size s. (Here s has to be an integer, but since we are assuming n is large we don't have to worry about n/s being an integer.) If a group is positive, we test all its items individually in stage two.
Work that discusses Dorfman's algorithm in the context of testing for covid-19 include [6, 8, 10, 21] This has T 1 = n/s tests in stage 1. In stage 2, a group is positive with probability 1 − q s , so the expected number of tests is ET 2 = s(1 − q s )n/s = (1 − q s )n. This is a total of ET = n s + (1 − q s )n = n 1 s + 1 − q s tests on average. Dorfman's algorithm outperforms individual testing for all p < 1 − 1/ 3 √ 3 = 0.307. Interestingly, Dorfman's algorithm with s = 2 is never optimal.
There's no closed form for the optimal value of s, although it's approximately 1/ √ p when p is small.
The Bernoulli design is the most commonly used nonadaptive design and the mathematically simplest. In a Bernoulli design, each item is placed in each test independently with probability π. Here we suggest a Bernoulli design for the first stage of a two-stage algorithm. Bernoulli designs have been studied for nonadaptive group testing in the p = o(1) regime by [11, 4, 5] and others. It will be convenient to write σ = πn for the average number of items per test.
Although the Bernoulli first stage is not optimal (see Figure 1 ), it is close to optimal, and the mathematical simplicity allows us to explicitly find the optimal design parameter π = 1/np and the optimal number T 1 of first-stage tests. For models with slightly better performance, these can only be found numerically.
It will be convenient here to work here and for the following algorithms with the so-called 'fixed k' prior, where we assume there are exactly k = pn defective items, chosen uniformly at random from the n items. Since we are assuming the number of items n is large, standard concentration inequalities imply the true number of defectives under the i.i.d. prior will in fact be very close to k = pn. We also note that none of the algorithms we consider here will actual take advantage of exact knowledge of k; it is merely a mathematical convenience to make proving theorems easier. The results we prove under this 'fixed k' prior do indeed hold for the i.i.d. prior also in the large n limit; see [5, Appendix to Chapter 1] for formal details of how to transfer results between the different prior models.
Throughout we write ∼ for asymptotic equivalence: a(n) ∼ b(n) means that a(n) = (1 + o(1))b(n) as n → ∞. Theorem 1. Using a Bernoulli(π) first stage with an average of σ = πn items per test, conservative two-stage testing can be completed in
tests on average. When the prevalence p is known, the optimum value of π is 1/pn, and we can succeed with ET ∼ np e ln
tests on average when p ≤ 1/(e + 1) = 0.269, or ET = n tests otherwise.
Proof. We need to work out how many nondefective items are discovered by the Bernoulli design. A given nondefective item is discovered by a test if that item is in the test but the test is negative. This happens with with probability
When the p is known, simple calculus shows that this is maximised at σ = 1/p, where it takes the value e −1 /pn. Thus the probability a nondefective item is not discovered is
Therefore, the total number of tests used by this algorithm on average is
At the optimal σ = 1/p, this is
We differentiate to find the optimum value of T 1 , giving
from which we get the optimal value Otherwise, T 1 = 0 is optimal, and we have individual testing.
In a constant tests-per-item nonadaptive design, we have a constant number r tests per item. For convenience, we arrange these in r rounds of T 1 /r tests, one test per item in each round. Rounds can be conducted in parallel, so this is not adding extra stages to our two-stage algorithm. The test for an item in a given round is chosen uniformly at random from the T 1 /r tests, independently from other items. It will be convenient to write σ = nr/T 1 for the average number of items per test. Constant tests-per-item designs are optimal nonadaptive designs in the sparse p = o(n) regime [12, 24] , so are a good candidate for the nonadaptive stage of a two-stage scheme. It is therefore not surprising that its performance is very close to optimal when p is small (see 1).
Theorem 2. Using a first stage with a constant number r of tests per item and an average number of σ items per test, conservative two-stage testing can be completed in
tests on average. When the prevalence p is known, r and σ can be numerically optimised.
Proof. A nondefective item appearing in a given test sees a positive result with probability
as we get a positive result unless in that round all k defective items avoid the test that the given item is in. Thus all r tests are positive with probability (1 − e −pσ ) r , since splitting the tests into rounds and using the fixed-k prior ensures these events are independent. Therefore the number of tests required is
We now consider a first stage with both constant tests-per-item and constant items-per-test. We take r tests per item and s items per test. Note that doublecounting tells us we must have T 1 s = nr. Note also that r and s must be integers. Taking r = 1 and s = 1 gives individual testing. Taking r = 1 and s > 1 gives Dorfman's algorithm. Taking r = 2 gives the 'double pooling' algorithm of Broder and Kumar [10] . Taking r > 2 gives Broder and Kumar's more general 'r-pooling' algorithm [10] . Work to discuss doubly constant designs in the context of testing for covid-19 includes [8, 10, 30] .
Theorem 3. Using a first stage with a constant number r of tests per item and a constant number s of items per test, conservative two-stage testing can be completed in
tests on average, where q = 1 − p. When the prevalence p is known, r and s can be numerically optimised.
We note that the expression here is the same as that heuristically demonstrated by Broder and Kumar [10] , who use the i.i.d prior but assume independence within rounds. (They say that they will discuss the accuracy of this approximation in the final version of [10] ). By using the fixed-k prior here, we actually do have independence within rounds, so can formally prove the result. In the large n limit, this then transfers to the i.i.d. prior, as discussed earlier and in [5, Appendix to Chapter 1].
Proof. The probability that a given test containing a given nondefective item is negative is
Since with the fixed-k prior we have independence between rounds, we have that the probability all the tests containing the nondefective item are positive, meaning the item requires retesting in the second stage, is (1 − q s−1 ) r .
Over all, the expected number of tests required is
Note that putting r = 1 does indeed give
as for Dorfman's algorithm.
In order to see how good out conservative two-stage algorithms are, we will compare the number of tests they require to a theretical lower bound (Theorem 4). It will be convenient to start with a lower bound for usual non-conservative two-stage testing (Theorem 5), which may be of independent interest. We will then show how to adapt the argument to conservative two-stage testing.
Let us start by thinking about a lower bound on the number of tests necessary for usual two-stage testing.
Theorem 4. The expected number of tests required for two-stage testing is at least
Proof. Our goal is to bound the expected number T 2 of items that are not classified as DND or DD. A nondefective item fails to be classified DND if and only if it only appears in positive tests -that is, if for each test it is in, one of the other items is defective. A defective item fails to be classified DD if -but not only if -for each test it is in, one of the other items is defective. (It's not 'only if' because we also require one of these tests to contain solely definite nondefectives.) Let us call an item hidden if every test it is in contains at least one other defective item. Then
where H i is the event that item i is a hidden nondefective.
We seek a bound at least as good as individual testing T = n. Then without loss of generality we may assume there are no tests of weight w t = 1 in the first stage. If there is one, remove it and the item it tests; this leaves p the same, does not increase the error probability, and reduces the number of available tests per item.
It will be convenient to write x ti = 1 if item i is in test t, and x ti = 0 if it is not. With this notation, the probability that item i is hidden is bounded by
where q = 1 − p, due to a result of [2] . Note that 1 − q wt−1 is the probability of the event that i gets hidden in test t, and the bound (1) follows by applying the FKG inequality to these increasing events; see [2] for details. It will be useful later to write L(i) for the logarithm of the bound (1), so P(H i ) ≥ e L(i) , where
x ti ln(1 − q wt−1 ).
We now use the arithmetic mean-geometric mean inequality in the form
to get the bound
We now need to bound term inside the exponential. By manipulations similar to those in [2] we have
as in the statement of the theorem. (We introduce the minus sign so that f (p) is positive.) Putting this back into (2), we get
Thus the total expected number of tests required is at least
To find the optimal value of T 1 , we differentiate this, to get
with optimum
and we are done.
We can now use the machinery of the previous result to prove a lower bound for conservative two-stage testing.
Theorem 5. For conservative two-stage group testing we have the following bounds:
(ln g(p) + 1);
3. ET ≥ n p + 1 f It may be useful to know that Bound 2 dominates for p < 0.171, and Bound 3 dominates for 0.171 < p < 0.382.
Here, f is as in Theorem 4.
Proof. Bound 1 is a universal bound of Fischer, Klasner and Wegenera [16] that applies to any group testing algorithm. It's left to prove 2 and 3. The proof bound for conservative two-stage testing proceeds in a similar way to that of Theorem 4. There are two different ways we can count the number of items that require testing in the second stage. For Bound 2, we count every item that appears solely in positive tests -such an item is either defective or a hidden nondefective. For Bound 3, we count all the defective items, of which there are pn on average, plus all nondefective items that appear solely in positive tests.
For Bound 2, the probability a test of weight w is positive is 1 − q w , where q = 1 − p. We use the same argument as before -this time in less detail. (For conservative two-sage testing we don't have to be so careful about ruling out individual tests in the first round: they can simply be moved into the second round.) The probability an item i appears in only positive tests is P(E i ) ≥ t:xti=1 (1 − q wt ), by the FKG inequality. Going through exactly the same argument, the expected number of items in only positive tests is
where g(p) = max w=2,3,...
giving an average number of tests ET ≥ T 1 + n exp −g(p) T 1 n .
Optimising T 1 the same way gives the final bound ET ≥= n 1 g(p)
(ln g(p) + 1) .
For Bound 3, we must test the average of pn defective items, plus the average of (1 − p)nP(H i ) hidden nondefectives; here (1 − p)n is the average number of nondefectives, and P(H i ) is the probability a given nondefective is hidden. We can use from before the bound
ET ≥ T 1 + pn + (1 − p)n exp −f (p) T 1 n .
Optimising in the same way gives
and hence
Comparing these bound with the results of our algorithms (see Figure 1 ), we see that testing with a doubly constant first stage is extremely close to optimal for all p.