key: cord-1041018-ywibb6sj
authors: Papanicolaou, Vassilis G.
title: A binary search scheme for determining all contaminated specimens
date: 2021-09-20
journal: J Math Biol
DOI: 10.1007/s00285-021-01663-6
sha: a4da0a53809088fb73d6b205f3187cb13c29c01c
doc_id: 1041018
cord_uid: ywibb6sj

Specimens are collected from N different sources. Each specimen has probability p of being contaminated (in the case of a disease, e.g., p is the prevalence rate), independently of the other specimens. Suppose we can apply group testing, namely take small portions from several specimens, mix them together, and test the mixture for contamination, so that if the test turns positive, then at least one of the samples in the mixture is contaminated. In this paper we give a detailed probabilistic analysis of a binary search scheme, we propose, for determining all contaminated specimens. More precisely, we study the number T(N) of tests required in order to find all the contaminated specimens, if this search scheme is applied. We derive recursive and, in some cases, explicit formulas for the expectation, the variance, and the characteristic function of T(N). Also, we determine the asymptotic behavior of the moments of T(N) as [Formula: see text] and from that we obtain the limiting distribution of T(N) (appropriately normalized), which turns out to be normal.

each sample we assume that the probability of being contaminated (by, say, a virus, a toxic substance, etc.) is p and the probability that it is not contaminated is q := 1 − p, independently of the other samples. All N samples must undergo a screening procedure (say a molecular or antibody test in the case of a viral contamination, a radiation measurement in the case of a radioactive contamination, etc.) in order to determine exactly which are the contaminated ones.

One obvious way to identify all contaminated specimens is the individual testing, namely to test the specimens one by one individually (of course, this approach requires N tests). In this work we analyze a group testing (or pool testing) approach, which can be called "binary search scheme" and requires a random number of tests. In particular, we will see that if p is not too big, typically if p < 0.224, then by following this scheme, the expected number of tests required in order to determine all contaminated samples can be made strictly less than N . There is one requirement, though, for implementing this scheme, namely that each sample can undergo many tests (or that the sample quantity contained in each container suffices for many tests).

Group testing procedures have broad applications in areas ranging from medicine and engineering to airport security control, and they have attracted the attention of researchers for over seventy-five years (see, e.g., Dorfman's seminal paper (Dorfman 1943) , as well as Hwang 1972; Sobel and Groll 1959; Ungar 1960, etc.) . In fact, recently, group testing has received some special attention, partly due to the COVID-19 crisis (see, e.g., Aldridge 2019 Aldridge , 2020 Armendáriz et al. 2020 ; Golliery and Gossnerz 2020; Malinovsky 2019; Mallapaty 2020, and the references therein).

The contribution of the present work is a detailed quantitative analysis of a precise group testing procedure which is quite natural and easy to implement. The scheme goes as follows: First we take samples from each of the N containers, mix them together and test the mixture. If the mixture is not contaminated, we know that none of the samples is contaminated. If the mixture is contaminated, we split the containers in two groups, where the first group consists of the first N /2 containers and the second group consists of the remaining N /2 containers. Then we take samples from the containers of the first group, mix them together and test the mixture. If the mixture is not contaminated, then we know that none of the samples of the first group is contaminated. If the mixture is contaminated, we split the containers of the first group into two subgroups (in the same way we did with the N containers) and continue the procedure. We also apply the same procedure to the second group (consisting of N /2 containers).

The main quantity of interest in the present paper is the number T (N ) of tests required in order to determine all contaminated samples, if the above binary search scheme is applied.

Following the terminology of Aldridge (2019) we can characterize the aforementioned procedure as an adaptive probabilistic group testing in the linear regime ("linear" since the average number of contaminated specimens is pN , hence grows linearly with N ). "Adaptive" refers to the fact that the way we perform a stage of the testing procedure depends on the outcome of the previous stages. "Probabilistic" refers to the fact that each specimen has probability p of being contaminated, independently of the other specimens and, furthermore, that the required number of tests, T (N ), is a random variable. Let us be a bit more specific about the latter. Suppose ξ 1 , ξ 2 , . . . is a sequence of independent Bernoulli random variables of a probability space ( , F, P), with P{ξ k = 1} = p and P{ξ k = 0} = q, k = 1, 2, . . ., so that {ξ k = 1} is the event that the k-th specimen is contaminated. Then, for each N , the quantity T (N ) of our binary search scheme is a specific function of ξ 1 , ξ 2 , . . . , ξ N , say, T (N ) = T N (ξ 1 , ξ 2 , . . . , ξ N ).

(1.1)

In particular, is not hard to see that i.e. if none of the contents of the N containers is contaminated, then T (N ) = 1, whereas if all N containers contain contaminated samples, then by easy induction on N we can see that

. Thus, T (N ) can become bigger than N , while the deterministic way of checking of the samples one by one requires N tests (i.e. in the case of individual testing we would have T N ≡ N ). Let us mention that, for a given p, the optimal testing procedure, namely the procedure which minimizes the expectation of the number of tests required in order to determine (with zero-error) all contaminated specimens in an adaptive probabilistic group testing, remains unknown (Malinovsky 2019). However, Ungar (1960) has shown that if

then the optimal procedure is individual testing. In practice, though, p is usually quite small, much smaller than p * . We do not claim that our proposed procedure is optimal. However, for small values of p the numerical evidence we have suggests (see Tables 1 and 2 in Sects. 2.1 and 3.1 respectively) that, in comparison with the optimal results obtained by Aldridge (2019), Aldridge (2020) via simulation, our binary scheme is near-optimal.

Let us also mention that our "binary search scheme" is different from the "binary splitting" procedures of Sobel and Groll (1959) (see, also, Aldridge (2019) and Hwang (1972) ) where at each stage a group is splitted in two subgroups whose sizes may not be equal or even nearly equal. This feature makes these binary splitting procedures very hard to analyze theoretically, while the advantage of our proposed procedure is that, due to its simplicity it allows us to calculate certain relevant quantities (e.g., the expectation E[T (N )] and the variance V[T (N )]) explicitly. We even managed to determine the limiting distribution of T (N ) (appropriately normalized), which turns out to be normal.

Finally, let us mention that in Armendáriz et al. (2020) the authors consider optimality in the case where the pool sizes are powers of 3 (except possibly for an extra factor of 4 for the first pool). In the case where N = 100 and p = 0.02 their average number of tests in order to determine the contaminated specimens is 20, thus their average-case aspect ratio is 0.2. Tables 1 and 2 below, indicate that our proposed strategy gives comparable, if not better, results.

In Sect. 2 we study the special case where N = 2 n . Here, the random variable T (2 n ) is denoted by W n . We present explicit formulas for the expectation (Theorem 1) and the variance (Corollary 1) of W n . In addition, in formulas (2.12) and (2.42) we give the asymptotic behavior of E[W n ] and V[W n ] respectively, as n → ∞. Then, we determine the leading asymptotics of all the moments of W n (Theorem 3) and from that we conclude (Corollary 2) that, under an appropriate normalization W n converges in distribution to a normal random variable. Finally, at the end of the section, in Corollary 3 and in formula (2.75) we give a couple of Law-of-Large-Numbers-type results for W n .

Section 3 studies the case of an arbitrary N . In Theorem 4, Theorem 5, and Corollary 5 respectively we derive recursive formulas for μ(N ) Here, let us point out that the determination of the limiting behavior of a random quantity is a fundamental issue in many probabilistic models. Thus, our result that [T (N ) − μ(N )]/σ (N ) converges in distribution to the standard normal variable Z , and that the convergence is good to the point that we also have convergence of all moments to the corresponding moments of Z , gives much more information about the testing procedure than the information we obtain from the behavior of E[T (N )]. And since the number N can be in the order of 10 2 or, even 10 3 , and the explicit results can get very messy for such big values of N , the asymptotic behavior of T (N ) enables us to obtain valuable information without much effort.

At the end of the paper we have included a brief appendix (Sect. 4) containing a lemma and two corollaries, which are used in the proofs of some of the results of Sects. 2 and 3.

We first consider the case where the number of containers is a power of 2, namely

where n = 0, 1, . . . . (2.1)

As we have said in the introduction, the first step is to test a pool containing samples from all N = 2 n containers. If this pool is not contaminated, then none of the contents of the N containers is contaminated and we are done. If the pool is contaminated, we make two subpools, one containing samples of the first 2 n−1 containers and the other containing samples of the remaining 2 n−1 containers. We continue by testing the first of those subpools. If it is contaminated we split it again into two subpools of 2 n−2 samples each and keep going. We also repeat the same procedure for the second subpool of the 2 n−1 samples. One important detail here is that if the first subpool of the 2 n−1 samples turns out not contaminated, then we are sure that the second subpool of the remaining 2 n−1 samples must be contaminated, hence we can save one test and immediately proceed with the splitting of the second subpool into two subpools of 2 n−2 samples each. Likewise, suppose that at some step of the procedure a subpool of 2 n−k samples is found contaminated. Then this subpool is splitted further into two other subpools, each containing 2 n−k−1 samples. If the first of these subpools is found not contaminated, then we automatically know that the other is contaminated and, consequently, we can save one test.

Let W n be the number of tests required to find all contaminated samples by following the above procedure. Thus by (1.2) we have

(in the trivial case n = 0, i.e N = 1, we, of course, have W 0 = 1).

Example 1 Suppose that N = 4 (hence n = 2). In this case W 2 can take any value between 1 and 7, except for 2. For instance in the case where the samples of the first three containers are not contaminated, while the content of the fourth container is contaminated, we have W 2 = T 4 (0, 0, 0, 1) = 3. On the other hand, in the case where the samples of the first and the third container are contaminated, while the samples of the second and fourth container are not contaminated, we have W 2 = T 4 (1, 0, 1, 0) = 7.

Theorem 1 Let N = 2 n and W n as above. Then

(in the trivial case n = 0 the sum is empty, i.e. 0), where, as it is mentioned in the introduction, q is the probability that a sample is not contaminated.

Proof Assume n ≥ 1 and let D n be the event that none of the 2 n samples is contaminated. Then

and hence

where for typographical convenience we have set

(2.5)

In order to find a recursive formula for u n let us first consider the event A n that in the group of the 2 n containers none of the first 2 n−1 contain contaminated samples. Clearly, D n ⊂ A n and

Likewise, if B n is the event that in the group of the 2 n containers none of the last 2 n−1 contains contaminated samples, then

Let us also notice that A n B n = D n , hence P(A n B n |D c n ) = 0. Now, (i) given A n and D c n we have that W n d = 1 + W n−1 , where the notation X d = Y signifies that the random variables X and Y have the same distribution. To better justify this distributional equality we observe that, in the case N = 2 n , formula (1.1) takes the form

Hence, the given event A n D c n means that only some of the variables ξ (N /2)+1 , . . . , ξ N may differ from 0. Consequently, given A n D c n we have that W n d = 1 + W n−1 .

(ii) Similarly, given B n and D c n we have that W n d = 2 + W n−1 . Finally, (iii) given (A n ∪ B n ) c and D c n we have that W n = 1 + W n−1 +W n−1 , where,W n−1 is an independent copy of W n−1 . Thus (given D c n ) by conditioning on the events A n , B n and (A n ∪ B n ) c we get, in view of (2.5), (2.6), and (2.7),

Therefore, by using (2.8) in (2.4) and (2.9) we can eliminate u n , u n−1 and obtain

Finally, (2.3) follows easily from (2.10) and the fact that E[W 0 ] = 1.

For instance, in the cases n = 1, n = 2, and n = 10 formula (2.3) becomes

respectively. In the extreme case q = 0 we know that E[W n ] = 2 n+1 − 1, while in the other extreme case q = 1 we know that E[W n ] = 1, and these values agree with the ones given by (2.3).

Let us also notice that formula (2.3) implies that for any given q ∈ [0, 1) we have

It is clear that α 1 (q) is a power series about q = 0 with radius of convergence equal to 1 (actually, it is well known that the unit circle is the natural boundary of this power series), which is strictly decreasing on [0, 1] with α 1 (0) = 2 and α 1 (1) = 0. Furthermore, it is not hard to see that it satisfies the functional equation

(2.14)

Also, by using the inequality

and by estimating the integral as q → 1 − one can show that

Remark 1 By dividing both sides of (2.3) by 2 n and comparing with (2.13) we can see that as n → ∞

Actually, the convergence is much stronger, since for every m = 1, 2, . . . the m-th derivative of E[W n ]/2 n with respect to q converges to the m-th derivative of α 1 (q) uniformly on compact subets of [0, 1).

The expectation E[W n ] and, consequently, the average-case aspect ratio E[W n ]/2 n are getting smaller as q approaches 1 (equivalently, as p approaches 0). As an illustration, by employing (2.3) we have created the following table:

(by comparing the above values with the graphs, given in Aldridge (2019) and Aldridge (2020) , of the optimal average-case aspect ratio as a function of p, we can see that, if p ≤ 0.15, our procedure is near-optimal).

If q is such that

then, by applying the aforementioned testing strategy, the number of tests required to determine all containers with contaminated content is, on the average, less than N , namely less than the number of tests required to check the containers one by one. Let us set

and (2.17) holds if q ∈ (q n , 1] or, equivalently, if p ∈ [0, 1 − q n ). Therefore, it only makes sense to consider the procedure if q > q n . Alternatively, if q is given, one may try to find the optimal value, say m, of n which minimizes μ n (q)/2 n and, then, split N into subgroups having size m.

As an example, let us give the (approximate) values of q n for n = 0, 1, . . . , 10:

Thus, q 1 is the threshold found by Ungar (1960) 

which by letting n → ∞ yields 

which implies that the sequence q n is strictly increasing. Therefore, if q > .776, equivalently if p < .224, then E[W n ] < 2 n = N for any n ≥ 1.

We start with a recursive formula for the generating function of W n .

Proof With D n as in the proof of Theorem 1 we have

Let A n and B n be the events introduced in the proof of Theorem 1. Then, given A n and D c n we have that z W n d = zz W n−1 ; given B n and D c n we have that z W n d = z 2 z W n−1 ; finally given (A n ∪ B n ) c and D c n we have that z W n d = zz W n−1 zW n−1 , whereW n−1 is an independent copy of W n−1 . Thus (given D c n ) by conditioning on the events A n , B n and (A n ∪ B n ) c we get, in view of (2.25), (2.6), and (2.7),

By replacing n by n − 1 in (2.24) we get

and (2.23) follows by eliminating h n (z) and h n−1 (z) from (2.24), (2.26), and (2.27).

By setting z = e it in (2.23) it follows that the characteristic function

For instance, for n = 1 formula (2.29) yields

(2.30)

(in the trivial case n = 0 all the above sums are empty, i.e. 0).

Proof Differentiating (2.23) twice with respect to z and then setting z = 1 yields

where, in view of (2.22),

(2.34) Thus, σ 2 n = g n (1) + g n (1) − g n (1) 2 (2.35) and by using (2.10) and (2.35) in (2.33) we obtain

Finally, formula (2.36) together with the fact that

from which (2.32) follows by invoking (2.3).

As we have mentioned, in the extreme cases where q = 0 or q = 1 the variable W n becomes deterministic and, consequently, σ 2 n (0) = σ 2 n (1) = 0, which is in agreement with (2.32). E.g., setting n = 1 and n = 2 in formula (2.32) yields

and σ 2 2 (q) = V[W 2 ] = q(1 − q)(q 6 + q 5 + 7q 4 + 11q 3 + 5q 2 + 11q + 2). (2.39)

Notice that the maximum of σ 2 1 (q) on [0, 1] is attained at q ≈ .6462. Actually, both dσ 2 1 (q)/dq and d 2 σ 2 1 (q)/dq 2 have one (simple) zero in [0, 1]. The maximum of σ 2 2 (q) on [0, 1] is attained at q ≈ .744, while both dσ 2 2 (q)/dq and d 2 σ 2 2 (q)/dq 2 have one simple zero in [0, 1].

Let us also notice that, since

formula (2.32) can be also written as

From formula (2.41) it follows that for any given q ∈ [0, 1) we have

An equivalent way to write β(q) is

is a power series about q = 0 with radius of convergence equal to 1). We would like to understand the limiting behavior of W n , as n → ∞, for any fixed q ∈ (0, 1). Formulas (2.12) and (2.42) suggest that we should work with the normalized variables In view of (2.28) we have ψ n (t) = φ n 2 −n/2 t e −i2 n/2 α 1 (q)t (2.47) and using (2.47) in (2.29) yields ψ n (t) = e 2 −n/2 it ψ n−1 t/ √ 2 2 + e 2 −n/2 it − e 2·2 −n/2 it e −2 n/2 α 1 (q)it/2 q 2 n−1 ψ n−1 t/ √ 2 + e 2 −n/2 it − e 2·2 −n/2 it e −2 n/2 α 1 (q)it q 2 n , n = 1, 2, . . . ,

From formula (2.48) one can guess the limiting distribution of X n : Assuming that for each t ∈ R the sequence ψ n (t) has a limit, say ψ(t), we can let n → ∞ in (2.48) and conclude that ψ(t) = ψ t/ √ 2 2 . Actually, if the limit ψ(t) exists, then formulas (2.49) and (2.50) below imply that ψ (0) = 0 and ψ (0) exists (in C).

From the existence of these derivatives and the functional equation of ψ(t) we get that the function h(t) := t −1 √ − ln ψ(t) is continuous at 0 and satisfies the equation

for all t ∈ R and, hence ψ(t) = e −at 2 for some a ≥ 0. Consequently, X n converges in distribution to a normal random variable, say X , with zero mean. As for the variance of X , formulas (2.42) and (2.45) suggest that V[X ] = β(q), where β(q) is given by (2.43)-(2.44).

The above argument is not rigorous since it assumes the existence of the (pointwise) limit lim n ψ n (t) for every t ∈ R. It is worth, however, since it points out what we should look for.

From (2.12), (2.42), and (2.45) we get that for any fixed q ∈ [0, 1)

(2.50)

One important consequence of (2.50) is Durrett (2005) that the sequence F n , n = 0, 1, . . ., where F n is the distribution function of X n , is tight.

Theorem 3 For m = 1, 2, . . . and q ∈ [0, 1) we have

where β(q) is given by (2.43)-(2.44) and Z is a standard normal random variable. In other words

Proof By differentiating both sides of (2.48) with respect to t we get ψ n (t) = √ 2 e 2 −n/2 it ψ n−1 t √ 2 ψ n−1 t √ 2 + 2 −n/2 ie 2 −n/2 it ψ n−1 t √ 2 2 + q 2 n−1 d dt e 2 −n/2 it − e 2·2 −n/2 it e −2 n/2 α 1 (q)it/2 ψ n−1 t √ 2 + q 2 n d dt e 2 −n/2 it − e 2·2 −n/2 it e −2 n/2 α 1 (q)it .

(2.53)

We continue by differentiating k − 1 times with respect to t both sides of (2.53), where k ≥ 2. This yields

and Q 4n (t) := q 2 n d k dt k e 2 −n/2 it − e 2·2 −n/2 it e −2 n/2 α 1 (q)it .

(2.58)

We will prove the theorem by induction. For m = 1 and m = 2 the truth of (2.51) follows immediately from (2.49) and (2.50). The inductive hypothesis is that the limit lim n E X k n = i −k lim n ψ 

where ψ (m)

Then, the inductive hypothesis together with (2.64) imply that the limit lim n b n exists in C. We can, therefore, apply Corollary A2 of the Appendix to (2.63) with z n = ψ (m) n (0), ρ = √ 2) −(m−2) and b n as in (2.65) to conclude that the limit lim n ψ (m) n (0) exists in C. This allows us to take limits in (2.63) and obtain

where for typographical convenience we have set

We have, thus, shown that formula (2.66) holds for all m ≥ 1. If m = 1, the sum in the right-hand side of (2.66) is empty, i.e. zero, and, hence we get what we already knew, namely that λ(1) = 0. If m = 2 then (2.66) becomes vacuous (0 = 0), but we know that λ(2) = −β(q). Thus, formula (2.66) gives recursively the values of λ(m) for every m ≥ 3, and by using the induction hypothesis again, namely that λ(k) = i k β(q) k/2 E Z k for k = 1, . . . , m −1, it is straightforward to show that λ(m), as given by (2.66), equals i m β(q) m/2 E Z m for every m.

A remarkable consequence of Theorem 3 is the following corollary whose proof uses standard arguments, but we decided to include it for the sake of completeness.

where Z is a standard normal random variable and the symbol d −→ denotes convergence in distribution.

Proof As we have seen, the sequence of the distribution functions F n (x) = P {X n ≤ x}, n = 0, 1, . . ., is tight.

Suppose that X n k d −→ X , where X n k , k = 1, 2, . . ., is a subsequence of X n . Then (Durrett 2005) there is a sequence of random variables Y k , k = 1, 2, . . . converging a.s. to a random variable Y , such that for each k ≥ 1 the variables Y k and X n k have the same distribution (hence the limits Y and X also have the same distribution, since a.s. convergence implies convergence in distribution). Thus, by Theorem 3 we have

In particular, for m = 2 we get from (2.69) that sup k E Y 2 k < ∞ for all = 1, 2, . . . and, consequently (Chung 2001 ( , F, P) we denote the space of all real-valued random variables of our probability space ( , F, P), mentioned in the introduction, with a finite · r -norm), and (2.69) yields

(2.70)

It is well known (and not hard to check) that the moments of the normal distribution satisfy the Carleman's condition and, consequently, a normal distribution is uniquely determined from its moments (Chung 2001; Durrett 2005 ) (alternatively, since the characteristic function of a normal variable is entire, it is uniquely determine by the moments). Therefore, it follows from (2.70) that X and √ β(q) Z have the same distribution. Hence, every subsequence of X n which converges in distribution, converges to √ β(q) Z and (2.68) is established.

From formula (2.45) we have

hence Theorem 3 has the following immediate corollary:

Corollary 3 For any r > 0 and q ∈ [0, 1] we have W n 2 n → α 1 (q) in L r ( , F, P), n → ∞.

(2.72)

Finally, let us observe that for any given > 0 we have (in view of (2.71) and Chebyshev's inequality) 

Let us now discuss the case of a general N , namely the case where N is not necessarily a power of 2. As we have described in the introduction, the first step of the binary search scheme is to test a pool containing samples from all N containers. If this pool is not contaminated, then none of the contents of the N containers is contaminated and we are done. If the pool is contaminated, we form two subpools, one containing samples of the first N /2 containers and the other containing samples of the remaining N /2 containers (recall that N /2 + N /2 = N ). We continue by testing the first of those subpools. If it is contaminated we split it again into two subpools of N /2 /2 and N /2 /2 samples respectively and keep going. We also apply the same procedure to the second subpool of the N /2 samples.

Suppose T (N ) = T (N ; q) is the number of tests required to find all contaminated samples by following the above procedure (thus T (2 n ) = W n , where W n is the random variable studied in the previous section). Then, as in formula (1.2),

(3.1)

In the extreme cases q = 1 and q = 0 the quantity T (N ) becomes deterministic and we have respectively

Evidently, T (N ) ≤ st T (N + 1), where ≤ st denotes the usual stochastic ordering (recall that X ≤ st Y means that P{X > x} ≤ P{Y > x} for all x ∈ R). In other words, T (N ) is stochastically increasing in N . In particular

where log 2 is the logarithm to the base 2. Also, it follows easily from a coupling argument that if q 1 > q 2 , then T (N ; q 1 ) ≤ st T (N ; q 2 ) .

Theorem 4 Let us set

Then μ(N ) satisfies the recursion

Proof We adapt the proof of Theorem 1. Assume N ≥ 2 and let D N be the event that none of the N samples is contaminated. Then

and hence

where for typographical convenience we have set

(3.7)

In order to find a recursive formula for u(N ) let us first consider the event A N that in the group of the N containers none of the first N /2 contain contaminated samples. Clearly D N ⊂ A N and

Likewise, if B N is the event that in the group of the N containers none of the last N /2 contains contaminated samples, then 

from which, in view of (3.6), formula (3.5) follows immediately.

In the case where N = 2 n formula (3.5) reduces to (2.10).

Remark 2 By easy induction formula (3.5) implies that, for N ≥ 2 the quantity μ(N ; q) = E[T (N ; q)] is a polynomial in q of degree N whose coefficients are ≤ 0, except for the constant term which is equal to 2N − 1. The leading term of μ(N ; q) is −q N . In the special case where N = 2 n these properties of μ(N ; q) follow trivially from (2.3).

For instance,

while μ(2), μ(4), and μ(1024) are given by (2.11), since W 1 = T (2), W 2 = T (4), and W 10 = T (1024).

With the help of (3.5) one can obtain an extension of formula (2.3) valid for any N . We first need to introduce some convenient notation: 

(3.14)

(the last equality follows from the fact that (N + 1)/2 = N /2 ). Then

(if N = 1 or N = 2, then the double sum in the right-hand side is 0).

and by recalling that (N + 1)/2 = N /2 and (N + 1)/2 = N /2 + 1, formula (3.5) implies (in view of (3.12) and (3.14))

From (3.17) we obtain

or, in view of (3.13),

(in the case N = 1, formula (3.18) is trivially true, since the sum in the right-hand side is empty). Consequently, (3.18) becomes

(3.19) from which (3.15) follows immediately.

With the help of (3.15) we have created the following table for the average-case aspect ratio:

(as in Table 1 , if we compare the above values with the graphs, given in Aldridge (2019) and Aldridge (2020) , of the optimal average-case aspect ratio as a function of p, we can see that, if p ≤ 0.15, our procedure is near-optimal).

Remark 3 Let us look at the case N = 2 n M, where M is a fixed odd integer. We set 

for all n ≥ 0. It follows that, as n → ∞, (3.28)

Then g(z; N ) satisfies the recursion

for N ≥ 2 (of course, g(z; 1) = z).

Notice that in the case where N = 2 n , formula (3.29) reduces to (2.23). By setting z = e it in (3.29) it follows that the characteristic function (3.31) with, of course, φ(t; 1) = e it . For example, for N = 2 formula (3.31) confirms the value of φ(t; 2) given in (2.30). By differentiating (3.29) twice with respect to z and then setting z = 1 and using (3.5) we get the following corollary:

(3.32)

Then σ 2 (N ) satisfies the recursion

In the case N = 2 n formula (3.33) reduces to (2.36) (e.g., if N = 2, then (3.33) agrees with (2.38)).

As we have mentioned, in the extreme cases where q = 0 or q = 1 the variable T (N ) becomes deterministic and, consequently, σ 2 (N ; 0) = σ 2 (N ; 1) = 0, which is in agreement with (3.33).

Using (3.35) in (3.33) implies

Now, as we have already seen, σ 2 (1; q) ≡ 0, while by (2.38) we have σ 2 (2; q) = q(1 − q)(q 2 + 3q + 1). We can, thus, choose

Then, (3.37) implies that σ 2 (2) = 3c 1 > 2c 2 and from (3.36) we have σ 2 (3) > σ 2 (2) = 3c 1 , i.e. the first inequality in (3.34) is valid for N = 2 and N = 3. Finally, the inequality c 1 N ≤ σ 2 (N ) for every N ≥ 2 follows easily from (3.36) by induction.

To establish the second inequality of (3.34) we set σ (N ) := σ 2 (N + 1) − σ 2 (N ).

(3.38) Then, formula (3.33) implies (in view of (3.12))

Observe that by (3.40) and (3.1) we have that

Now, as in the case of (3.18) we have, in view of (3.39),

where σ (1) = σ 2 (2) − σ 2 (1) = q(1 − q)(q 2 + 3q + 1). From (3.42) and (3.41) we get that σ (N ) is bounded. Therefore, the second inequality of (3.34) follows immediately from (3.38).

Of course, in the case where N = 2 n we have formula (2.42), which is much more precise than (3.34).

Let us also notice that with the help of (3.38), (3.42), and (3.15) we can get a messy, yet explicit formula for σ 2 (N ), extending (2.32) to the case of a general N .

We start with a Lemma. (N ; q) ] as in the previous subsection. Then for any fixed q ∈ (0, 1) we have

(3.43)

Proof As we have seen in the proof of Corollary 6, σ (N ) = σ 2 (N + 1) − σ 2 (N ) is bounded, hence

Now, if we divide (3.33) by σ 2 (N ) and invoke (3.34) we get

(3.45) Therefore, by using (3.44) in (3.45) and invoking again (3.34) we obtain (3.46) which is equivalent to the first equality of (3.43). The second equality follows immediately.

In order to determine the limiting behavior of T (N ), as N → ∞, for any fixed q ∈ (0, 1), it is natural to work with the normalized variables In view of (3.47) and (3.30) we have

; N e −itμ(N )/σ (N )t (3.50) and by using (3.50) in (3.31) and then invoking (3.5) we obtain the recursion

with ψ(t; 2) and ψ(t; 3) taken from (3.49). Actually, if we define ψ(0; 1) := 1, then (3.51) is valid for N ≥ 2.

We are now ready to present a general result, which can be viewed as an extension of Theorem 3 to the case of an arbitrary N . Theorem 6 For m = 1, 2, . . . and q ∈ (0, 1) we have

where Y (N ) is given by (3.47) and Z is a standard normal random variable. In other words

Proof We will follow the approach of the proof of Theorem 3. We apply induction. By (3.48) we know that (3.53) is valid in the special cases m = 1 and m = 2. The inductive hypothesis is that the We have, thus, shown that formula (3.58) holds for all m ≥ 1. If m = 1, the sum in the right-hand side of (3.58) is empty, i.e. zero, and, hence we get what we already knew, namely that (1) = 0. If m = 2 then (3.58) becomes vacuous (0 = 0), but we know that (2) = −1. Thus, formula (3.58) gives recursively the values of (m) for every m ≥ 3, and by using the induction hypothesis again, namely that (k) = i k E Z k for k = 1, . . . , m − 1, it is straightforward to show that (m), as given by (3.58), equals i m E Z m for every m.

Theorem 6 together with the fact that the sequence Y (N ) is tight imply the following corollary which can be considered an extension of Corollary 2. Its proof is omitted since it is just a repetition of the proof of Corollary 2. for any r > 0 and any q ∈ [0, 1]. It follows that if N n , n = 1, 2, . . ., is a sequence of integers (with lim n N n = ∞) such that the limit lim n E[T (N n )]/N n exists (e.g., N n = 2 n or N n = 3 · 2 n ), then (3.61) in the L r ( , F, P)-sense, for every r > 0 (the case N n = 2 n is treated by Corollary 3). Also, by Chebyshev's inequality (applied to a sufficiently high power of T ( with |ρ 1 | + |ρ 2 | < 1. Then

(4.7)

Proof Pick > 0 so that |ρ 1 | + |ρ 2 | + 2 < 1 and then choose N 0 ≥ 2 so that |ρ 1 (N ) − ρ 1 | < and |ρ 2 (N ) − ρ 2 | < for all N ≥ N 0 . Then (4.5) implies |z(N )| ≤ (|ρ 1 | + ) z ( N /2 ) + (|ρ 2 | + ) z ( N /2 ) + b * , N ≥ N 0 ,(4.8)

where b * := sup N |b(N )| < ∞, and the argument at the end of the proof of Lemma A1 applies to (4.8) and implies that the sequence z(N ) is bounded. Next, we write (4.5) as

where δ(N ) := ρ 1 (N ) − ρ 1 z ( N /2 ) + ρ 2 (N ) − ρ 2 z ( N /2 )

(4.10)

Notice that our assumptions for ρ 1 (N ), ρ 2 (N ), and b(N ), together with the fact that z(N ) is bounded, imply that lim N δ(N ) = 0. Thus, if we take absolute values in (4.9) and set

we obtain ε(N ) ≤ |ρ 1 | ε ( N /2 ) + |ρ 2 | ε ( N /2 ) + |δ(N )|, N ≥ 2, (4.12)

hence (since |ρ 1 | + |ρ 2 | < 1) Lemma A1 implies that lim N ε(N ) = 0.

Finally, by using the above arguments we can also show the following simpler result:

Rates of adaptive group testing in the linear regime

Conservative two-stage group testing

Group testing with nested pools

The detection of defective members of large populations

Group Testing against Covid-19

A method for detecting all defective members in a population by group testing

Sterrett procedure for the generalized group testing problem

The mathematical strategy that could transform coronavirus testing

Group testing to eliminate efficiently all defectives in a binomial sample

The cut off point for group testing

Publisher's Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations

The author wishes to thank the two anonymous referrees, as well as Professor Tom Britton, associate editor of JOMB, for their constructive comments and suggestions.

Lemma A1 Let ε(N ), N = 1, 2, . . ., be a sequence of nonnegative real numbers such that there exists an integer N 0 ≥ 2 for whichwhere r 1 , r 2 are nonnegative constants satisfying r := r 1 +r 2 < 1 and lim N δ(N ) = 0. Then,Thus, by taking lim sup in both sides of (4.1) we getSince r < 1, to finish the proof it suffices to show that ε(N ) is bounded , and we can, e.g., see that as follows. Let δ * := max N |δ(N )| andThen (noticing that (4.4) implies that r M + δ * ≤ M), easy induction on N implies that ε(N ) ≤ M for all N ≥ 1.If r 1 + r 2 = 1, then (4.2) does not hold. For example, if ε(N ) = r 1 ε ( N /2 ) + (1 − r 1 ) ε ( N /2 ) for N ≥ 2, then ε(N ) = ε(1) for all N . Let z(N ), N = 1, 2, . . ., be a sequence of complex numbers satisfying the recursion

Corollary A2 Let z n , n = 0, 1, . . ., be a sequence of complex numbers satisfying the recursion z n = ρz n−1 + b n , n = 1, 2, . . . , (4.13)where |ρ| < 1 and lim n b n ∈ C. Then, lim n z n = lim n b n 1 − ρ .(4.14)