Group Testing and Error-Correcting Codes

7 Group Testing and Error-Correcting Codes 7.1 Group Testing During the Second World War the United States was interested in weeding out all syphilitic soldiers called up for the army. However, syphilis testing back then was expensive and testing every soldier individually would have been very costly and inefficient. A basic breakdown of a test is: 1) Draw sample from a given individual, 2) Perform required tests, and 3) Determine presence or absence of syphilis. If there are n soldiers, this method of testing leads to n tests. If a significant portion of the soldiers were infected then the method of individual testing would be reasonable. The goal however, is to achieve effective testing in the more likely scenario where it does not make sense to test n (say n = 100, 000) people to get k (say k = 10) positives. Let’s say that it was believed that there is only one soldier infected, then one could mix the samples of half of the soldiers and with a single test determined in which half the infected soldier is, proceeding with a binary search we could pinpoint the infected individual in log n tests. If instead of one, one believes that there are at most k infected people, then one could simply run k consecutive binary searches and detect all of the infected individuals in k log n tests. Which would still be potentially much less than n. For this method to work one would need to observe the outcome of the previous tests before designing the next test, meaning that the samples have to be prepared adaptively. This is often not practical, if each test takes time to run, then it is much more efficient to run them in parallel (at the same time). This means that one has to non-adaptively design T tests (meaning subsets of the n individuals) from which it is possible to detect the infected individuals, provided there are at most k of them. Constructing these sets is the main problem in (Combinatorial) Group testing, introduced by Robert Dorfman [Dor43] with essentially the motivation described above.31 Let Ai be a subset of [T ] = {1, . . . , T } that indicates the tests for which soldier i participates. Consider A the family of n such sets A = {A1 , . . . , An }. We say that A satisfies the k-disjunct property if no set in A is contained in the union of k other sets in A. A test set designed in such a way will succeed at identifying the (at most k) infected individuals – the set of infected tests is also a subset of [T ] and it will be the union of the Ai ’s that correspond to the infected soldiers. If the set of infected tests contains a certain Ai then this can only be explained by the soldier i being infected (provided that there are at most k infected people). Theorem 7.1 Given n and k, there exists a family A satisfying the k-disjunct property for a number of tests
T = O k 2 log n . Proof. We will use the probabilistic method. We will show that, for T = Ck 2 log n (where C is a universal constant), by drawing the family A from a (well-chosen) distribution gives a k−disjunct family with positive probability, meaning that such a family must exist (otherwise the probability would be zero). 31 in fact, our description for the motivation of Group Testing very much follows the description in [Dor43]. Let 0 ≤ p ≤ 1 and let A be a collection of n random (independently drawn) subsets of [T ]. The distribution for a random set A is such that each t ∈ [T ] belongs to A with probability p (and independently of the other elements). Consider k + 1 independent draws of this random variable, A0 , . . . , Ak . The probability that A0 is contained in the union of A1 through Ak is given by  T Pr [A0 ⊆ (A1 ∪ · · · ∪ Ak )] = 1 − p(1 − p)k . This is minimized for p = 1 k+1 . For this choice of p, we have  k 1 1 k 1− 1 − p(1 − p) = 1 − k+1 k+1
n Given that there are n such sets, there are (k + 1) k+1 different ways of picking a set and k others to test whether the first is contained in the union of the other k. Hence, using a union bound argument, the probability that A is k-disjunct can be bounded as    k !T 1 n 1 Pr[k − disjunct] ≥ 1 − (k + 1) 1− . 1− k+1 k+1 k+1 In order to show that one of the elements in A is k-disjunct we show that this probability is strictly positive. That is equivalent to   k !T 1 1 1
1− 1− ≤ n . k+1 k+1 (k + 1) k+1  Note that 1 − 1 k+1 k → e−1 1−1 1 = e−1 k+1 k , as k → ∞. Thus, we only need k+1  

 n n log (k + 1) k+1 log k k+1  = T ≥ = O(k 2 log(n/k)), −1 ) 1 −1 k+1 − log (1 − (ek) − log 1 − k+1 e k where the last inequality uses the fact that log the Taylor expansion − log(1 − x−1 )−1 = O(x)  n k+1
 = O k log n k

due to Stirling’s formula and 2 This argument simply shows the existence of a family satisfying the k-disjunt property. However, it is easy to see that by having T slightly larger one can ensure that the probability that the random family satisfies the desired property can be made very close to 1. Remarkably, the existence proof presented here is actually very close to the best known lower bound. Theorem 7.2 Given n and k, if there exists a family A of subsets of [T ] satisfying the k-disjunct property, then  2  k log n . T =Ω log k Proof. l Fix a u such that 0 < u < T2 ; later it will be fixed to u := (T − k)/ constructing a few auxiliary family of sets. Let k−1 2
m . We start by A0 = {A ∈ A : |A| < u}, and let A1 ⊆ A denote the family of sets in A that contain their own unique u-subset,  A1 := A ∈ A : ∃F ⊆ A : |F | = u and, for all other A0 ∈ A, F 6⊆ A0 . We will procede by giving an upper bound to A0 ∪ A1 . For that, we will need a couple of auxiliary family of sets. Let F denote the family of sets F in the definition of A1 . More precisely, F := {F ∈ [T ] : |F | = u and ∃!A ∈ A : F ⊆ A} . By construction |A1 | ≤ |F| Also, let B be the family of subsets of [T ] of size u that contain an element of A0 , B = {B ⊆ [T ] : |B| = u and ∃A ∈ A0 such that A ⊆ B} . We now prove that |A0 | ≤ |B|. Let B0 denote the family of subsets of [T ] of size u that are not in B,  B0 = B 0 ⊆ [T ] : |B 0 | = u and B 0 ∈ /B . By construction of A0 and B, no set in B0 contains a set in A0 nor does a set in A0 contain a set in B0 . Also, both A0 and B0 are antichains (or Sperner family), meaning that no pair of sets in each family contains each other. This implies that A0 ∪ B0 is an antichain containing only sets with u or less elements. The Lubell-Yamamoto-Meshalkin inequality [Yam54] directly implies that (as long as u < T2 ) the largest antichain whose sets contain at most u elements is the family of subsets of [T ] of size u. This means that   T 0 0 |A0 | + B = A0 ∪ B ≤ = B ∪ B0 = |B| + B0 . u This implies that |A0 | ≤ |B|. Because A satisfies the k-disjunct property, no two sets in A can contain eachother. This implies that the families B and F of sets of size u are disjoint which implies that   T |A0 ∪ A1 | = |A0 | + |A1 | ≤ |B| + |F| ≤ . u Let A2 := A \ (A0 ∪ A1 ). We want to show that if A ∈ A2 and A1 , . . . , Aj ∈ A we have A\ j [ Ai > u(k − j ). (64) i=1 This is readily shown by noting that if (64) did not hold then one could find Bj+1 , . . . , Bk subsets of S S A of size t such that A \ ji=1 Ai ⊆ ki=j+1 Bi . Since A as no unique subsets of size t there must exist S Aj+1 , . . . , Ak ∈ A such that Bi ⊆ Ai for i = j + 1, . . . , k. This would imply that A ⊆ ki=1 Ai which would contradict the k-disjunct property. If |A2 | > k then we can take A0 , A1 , . . . , Ak distinct elements of A2 . For this choice and any j = 0, . . . , k [ Aj \ Ai ≥ 1 + u(k − j). 0≤i 2). This implies that |A2 | ≤ k which means that     T T l m
. n = |A| = |A0 | + |A1 | + |A2 | ≤ k + =k+ u (T − k)/ k+1 2 This means that  log n ≤ log k + l T (T − k)/  !  T m
log k , =O k+1 k2 2 which concludes the proof of the theorem. 2 We essentially borrowed the proof of Theorem 7.2 from [Fur96]. We warn the reader however that the notation in [Fur96] is drasticly different than ours, T corresponds to the number of people and n to the number of tests. There is another upper bound, incomparable to the one in Theorem 7.1 that is known. Theorem 7.3 Given n and k, there exists a family A satisfying the k-disjunct property for a number of tests  2 ! 2 log n T =O k . log k The proof of this Theorem uses ideas of Coding Theory (in particular Reed-Solomon codes) so we will defer it for next section, after a crash course on coding theory. The following Corollary follows immediately. Corollary 7.4 Given n and k, there exists a family A satisfying the k-disjunct property for a number of tests  2   k log n log n T =O min log k, . log k log k While the upper bound in Corollary 7.4 and the lower bound in Theorem 7.2 are quite close, there is still a gap. This gap was recently closed and Theorem 7.2 was shown to be optimal [DVPS14] (original I was not aware of this reference and closing this gap was posed as an open problem). Remark 7.5 We note that the lower bounds established in Theorem 7.2 are not an artifact of the requirement of the sets being k-disjunct. For the measurements taken in Group Testing to uniquely determine a group of k infected individuals it must be that the there are no two subfamilies of at most k sets in A that have the same union. If A is not k − 1-disjunct then there exists a subfamily of k − 1 sets that contains another set A, which implies that the union of that subfamily is the same as the union of the same subfamily together with A. This means that a measurement system that is able to uniquely determine a group of k infected individuals must be k − 1-disjunct. 7.2 Some Coding Theory and the proof of Theorem 7.3 In this section we (very) briefly introduce error-correcting codes and use Reed-Solomon codes to prove Theorem 7.3. We direct the reader to [GRS15] for more on the subject. Lets say Alice wants to send a message to Bob but they can only communicate through a channel that erases or replaces some of the letters in Alice’s message. If Alice and Bob are communicating with an alphabet Σ and can send messages with lenght N they can pre-decide a set of allowed messages (or codewords) such that even if a certain number of elements of the codeword gets erased or replaced there is no risk for the codeword sent to be confused with another codeword. The set C of codewords (which is a subset of ΣN ) is called the codebook and N is the blocklenght. If every two codewords in the codebook differs in at least d coordinates, then there is no risk of confusion with either up to d − 1 erasures or up to b d−1 2 c replacements. We will be interested in codebooks that are a subset of a finite field, meanign that we will take Σ to be Fq for q a prime power and C to be a linear subspace of Fq . The dimension of the code is given by m = logq |C|, and the rate of the code by m . N Given two code words c1 , c2 the Hamming distance ∆(c1 , c2 ) is the number of entries where they differ. The distance of a code is defined as R= d= min ∆(c1 , c2 ). c1 = 6 c2 ∈C For linear codes, it is the same as the minimum weight ω(C) = min ∆(c). c∈C\{0} We say that a linear code C is a [N, m, d]q code (where N is the blocklenght, m the dimension, d the distance, and Fq the alphabet. One of the main goals of the theory of error-correcting codes is to understand the possible values of rates, distance, and q for which codes exist. We simply briefly mention a few of the bounds and refer the reader to [GRS15]. An important parameter is given by the entropy function: Hq (x) = x log(q − 1) log x log(1 − x) . −x − (1 − x) log q log q log q • Hamming bound follows essentially by noting that if a code has distance d then balls of radius b d−1 2 c centered at codewords cannot intersect. It says that   1 d R ≤ 1 − Hq + o(1) 2N • Another particularly simple bound is Singleton bound (it can be easily proven by noting that the first n + d + 2 of two codewords need to differ in at least 2 coordinates) R≤1− d + o(1). N There are probabilistic constructions of codes that, for any  > 0, satisfy   d R ≥ 1 − Hq − . N This means that R∗ the best rate achievable satisties R∗ ≥ 1 − Hq  d N  , (65) known as the GilbertVarshamov (GV) bound [Gil52, Var57]. Even for q = 2 (corresponding to binary codes) it is not known whether this bound is tight or not, nor are there deterministic constructions achieving this Rate. This motivates the following problem. Open Problem 7.1 GV bound (65). 1. Construct an explicit (deterministic) binary code (q = 2) satisfying the 2. Is the GV bound tight for binary codes (q = 2)? 7.2.1 Boolean Classification A related problem is that of Boolean Classification [AABS15]. Let us restrict our attention to In error-correcting codes one wants to build a linear codebook that does not contain a codeword with weight ≤ d − 1. In other words, one wants a linear codebook C that does intersect B(d − 1) = {x ∈ {0, 1}n : 0 < ∆(x) ≤ d − 1} the pinched Hamming ball of radius d (recall that ∆(d) is the Hamming weight of x, meaning the number of non-zero entries). In the Boolean Classification problem one is willing to confuse two codewords as long as they are sufficiently close (as this is likely to mean they are in the same group, and so they are the same from the point of view of classification). The objective then becomes understanding what is the largest possible rate of a codebook that avoids an Annulus A(a, b) = {x ∈ {0, 1}n : a ≤ ∆(x) ≤ b}. We refer the reader to [AABS15] for more details. Let us call that rate ∗ RA (a, b, n). ∗ (1, d−1, n) corresponds to the optimal rate for a binary error-correcting code, conjectured Note that RA
to be 1 − Hq Nd (The GV bound). Open Problem 7.2 It is conjectured in [AABS15] (Conjecture 3 in [AABS15]) that the optimal rate in this case is given by ∗ ∗ RA (αn, βn, n) = α + (1 − α) RA (1, βn, (1 − α)) + o(1), where o(1) goes to zero as n goes to infinity. This is established in [AABS15] for β ≥ 2α but open in general. 7.2.2 The proof of Theorem 7.3 Reed-Solomon codes[RS60] are [n, m, n − m + 1]q codes, for m ≤ n ≤ q. They meet the Singleton bound, the drawback is that they have very large q (q > n). We’ll use their existence to prove Theorem 7.3 Proof. [of Theorem 7.3] We will construct a family A of sets achieving the upper bound in Theorem 7.3. We will do this by using a Reed-Solomon code [q, m, q − m + 1]q . This code has q m codewords. To each codework c we will correspond a binary vector a of length q 2 where the i-th q-block of a is the indicator of the value of c(i). This means that a is a vector with exactly q ones (and a total of q 2 entries)32 . We construct   the family A for T = q 2 and n = q m (meaning q m subsets of q 2 ) by constructing, for each codeword c, the set of non-zero entries of the corresponding binary vector a. These sets have the following properties, min |Aj | = q, j∈[n] and max |Aj1 ∩ Aj2 | = q − min ∆(c1 , c2 ) ≤ q − (q − m + 1) = m − 1. c1 = 6 c2 ∈C j1 6=j2 ∈[n] This readily implies that A is k-disjunct for   q−1 k= , m−1 because the union of Now we pick q ≈ j k q−1 m−1 n 2k log log k sets can only contain (m − 1) j q−1 m−1 k < q elements of another set. (q has to be a prime but there is always a prime between this number and n its double by Bertrand’s postulate (see [?] for a particularly nice proof)). Then m = log log q (it can be taken to be the ceiling of this quantity and then n gets updated accordingly by adding dummy sets). 32 This is precisely the idea of code concatenation [GRS15] This would give us a family (for large enough parameters) that is k-disjunct for $ %   n 2k log q−1 log k − 1 ≥ log n m−1 log q + 1 − 1   log q log q − = 2k log k log n ≥ k. Noting that   log n 2 . T ≈ 2k log k concludes the proof. 7.3 2 In terms of linear Bernoulli algebra We can describe the process above in terms of something similar to a sparse linear system. let 1Ai be the t − dimensional indicator vector of Ai , 1i:n be the (unknown) n−dimensional vector of infected soldiers and 1t:T the T −dimensional vector of infected (positive) tests. Then   |      |  | | |    1A1 · · · 1An  ⊗  1i:n  =  1t:T  ,    |  | | | | where ⊗ is matrix-vector multiplication in the Bernoulli algebra, basically the only thing that is different from the standard matrix-vector multiplications is that the addition operation is replaced by binary “or”, meaning 1 ⊕ 1 = 1. This means that we are essentially solving a linear system (with this non-standard multiplication). Since the number of rows is T = O(k 2 log(n/k)) and the number or columns n  T the system is underdetermined. Note that the unknown vector, 1i:n has only k non-zero components, meaning it is k−sparse. Interestingly, despite the similarities with the setting of sparse recovery discussed in a ˜ 2 ) measurements are needed, instead of O(k) ˜ previous lecture, in this case, O(k as in the setting of Compressed Sensing. 7.3.1 Shannon Capacity The goal Shannon Capacity is to measure the amount of information that can be sent through a noisy channel where some pairs of messages may be confused with eachother. Given a graph G (called the confusion graph) whose vertices correspond to messages and edges correspond to messages that may be confused with each other. A good example is the following: say one has a alphabet of five symbols 1, 2, 3, 4, 5 and that each digit can be confused with the immediately before and after (and 1 and 5 can be confused with eachother). The confusion graph in this case is C5 , the cyclic graph on 5 nodes. It is easy to see that one can at most send two messages of one digit each without confusion, this corresponds to the independence number of C5 , α(C5 ) = 2. The interesting question arises when asking how many different words of two digits can be sent, it is clear that one can send at least α(C5 )2 = 4 but the remarkable fact is that one can send 5 (for example: “11”,“23”,“35”,“54”, or “42”). The confusion graph for the set of two digit words C5⊕2 can be described by a product of the original graph C5 where for a graph G on n nodes G⊕2 is a graph on n nodes where the vertices are indexed by pairs ij of vertices of G and
(ij, kl) ∈ E G⊕2 if both a) i = k or i, k ∈ E and b) j = l or j, l ∈ E hold.
The above observation can then be written as α C5⊕2 = 5. This motivates the definition of Shannon Capacity [Sha56]  1 k θS (G) sup G⊕k . k √ Lovasz, in a remarkable paper [Lov79], showed that θS (C5 ) = 5, but determining this quantity is an open problem for many graphs of interested [AL06], including C7 . Open Problem 7.3 What is the Shannon Capacity of the 7 cycle? 7.3.2 The deletion channel In many applications the erasures or errors suffered by the messages when sent through a channel are random, and not adversarial. There is a beautiful theory understanding the amount of information that can be sent by different types of noisy channels, we refer the reader to [CT] and references therein for more information. A particularly challenging channel to understand is the deletion channel. The following open problem will envolve a particular version of it. Say we have to send a binary string “10010” through a deletion channel and the first and second bits get deleted, then the message receive would be “010” and the receiver would not know which bits were deleted. This is in contrast with the erasure channel where bits are erased but the receiver knows which bits are missing (in the case above the message received would be “??010”). We refer the reader to this survey on many of the interesting questions (and results) regarding the Deletion channel [Mit09]. A particularly interesting instance of the problem is the Trace Reconstruction problem, where the same message is sent multiple times and the goal of the receiver is to find exactly the original message sent from the many observed corrupted version of it. We will be interested in the following quantity: Draw a random binary string with
n bits, suppose the channel has a deletion probability of 12 for each bit (independently), define D n; 12 has the number of times the receiver needs to receive the message (with independent corruptions)
so that she can decode the message exactly, with high probability. It is easy to see that D n; 12 ≤ 2n , since roughly once in every 2n times the whole message will go √
through the channel unharmed. It is possible to show (see [HMPW]) that D n; 12 ≤ 2 n but it is not known whether this bound is tight. Open Problem 7.4
1. What are the asymptotics of D n; 12 ? 2. An interesting aspect of the Deletion Channel is that different messages may have different difficulties of decoding. This motivates the following question: What are the two (distinct) binary sequences x(2) and x(2) that are more difficult to distinguish (let’s say that the receiver knows that either x(1) or x(2) was sent but not which)?