Identifying a subset with as few tests as possible

Question

Informal description: You are given a set of $n$ blood samples, each having probability $p$ of being infected with a disease. Your goal is to determine the set $P$ of infected samples with as few tests as possible (on average). Each test is applied to a subset $S$ (of your choice) of the samples and returns positive if at least one of the samples is infected ($P \cap S \neq \varnothing$). What's the optimal way to choose the subsets to test to determine $P$ as efficiently as possible?

Formal description:

Let $n\in\mathbb{N}$. A test protocol $\mathscr{T}$ for subsets of $\{1,\ldots,n\}$ is a finite binary tree in which each non-leaf node $x$ is labeled by a subset $S_x$ of $\{1,\ldots,n\}$ and the two edges descending from the node $x$ are labeled “positive” and “negative”. For a test protocol $\mathscr{T}$ and a subset $P \subseteq \{1,\ldots,n\}$, we define a branch $\mathscr{B}_P = (x_0,\ldots,x_r)$ in the tree (= path from the root $x_0$ to a leaf $x_r$) as follows: $x_0$ is the root and, so long as $x_i$ is not a leaf, we let $x_{i+1}$ be the node attained by following the edge $(x_i, x_{i+1})$ labeled “positive” resp. “negative” according as $P \cap S_{x_i} \neq \varnothing$ resp. $P \cap S_{x_i} = \varnothing$. (In other words, the test tells us to test $S_{x_0}$ where $x_0$ is the root of $\mathscr{T}$, then test $S_{x_1}$ where $x_1$ is the node reached from $x_0$ by following the positive or negative branch according as $P \cap S_{x_0}$ is inhabited or empty, and so on until we reach a leaf $x_r$.) Calling $x_P$ the leaf (previously denoted $x_r$) where the branch $\mathscr{B}_P$ associated to $P$ terminates, we say that the test protocol $\mathscr{T}$ is decisive when $P \mapsto x_P$ is a bijection between subsets of $\{1,\ldots,n\}$ and leaves of $\mathscr{T}$, i.e., $P \mapsto \mathscr{B}_P$ is a bijection between subsets of $\{1,\ldots,n\}$ and branches of $\mathscr{T}$. The length $r$ of the branch $\mathscr{B}_P$ is then called the testing length $\ell(P)$ of the subset $P$ for the decisive protocol $\mathscr{T}$.

Now let $0<p<1$ be given: what is $\ell_{\mathrm{min}}$ (in function of $n$ and $p$) the smallest possible expected value $\sum_{P\subseteq\{1,\ldots,n\}} p^{\#P}\,(1-p)^{(n-\#P)}\,\ell(P)$, for a decisive protocol $\mathscr{T}$, of the testing length $\ell(P)$ of a subset $P$ that is drawn by choosing whether $i \in P$ using a Bernoulli distribution with probability $p$ independently for each $i$?

Examples:

The simplest decisive test protocol consists of testing each sample on its own, i.e., create a balanced binary tree with depth $n$ and $S_{x_i} = \{i+1\}$ for $x_i$ a node at depth $i$. This has $\ell(P) = n$ for every subset $P$ and provides a trivial upper bound on $\ell_{\mathrm{min}}$.

If $p$ is very small, we can create a test protocol which starts by testing whether any sample is infected, i.e., $S_{x_0} = \{1,\ldots,n\}$, so the negative branch can conclude immediately that $P = \varnothing$, whereas in the positive branch we use, say, the trivial test described above (pruning the cases where $n-1$ samples have tested negative and we know there is a positive). This provides an upper bound of $(1-p)^n + (n+1)(1-(1-p)^n) = 1 + n(1-(1-p)^n)$ on $\ell_{\mathrm{min}}$.

A lower bound on $\ell_{\mathrm{min}}$ comes from information theory: the subset $P$ has $n(-p\,\log_2 p - (1-p)\,\log_2(1-p))$ bits of information, so $\ell_{\mathrm{min}}$ must be at least this value. (But clearly this lower bound is not optimal since when $p\to 0$ this tends to $0$ whereas we can't do less than $1$ test.)

However, when $p=\frac{1}{2}$, the lower bound just given coincides with the trivial upper bound of $n$, so $\ell_{\mathrm{min}} = n$.

Answer 1

A few quick thoughts.

0. This is called the group testing problem. If folks wanted to learn more, I suppose they could look it up, and here is a substantial survey on the question (it likely answers whatever you want to know). But that might ruin the fun.

1. I would really like to say that if you increase $p$, then the best algorithm only gets slower...

2. The following algorithm works in at most $1 + 2np \log(n)$ steps on average, so for $p \leq n^{-c}$, this matches the information theory lower bound within a multiplicative constant.

(i) Initially test the entire set. (ii) If you test a set, and it contains at least one infected element, then cut the set into two almost equal-sized pieces, and recursively test each piece.

[To analyze that algorithm, perhaps consider the problem where we know that exactly $k$ elements are infected. Then the above algorithm tests at most $1+2k \lceil \lg(n) \rceil$ sets, where $\lg$ is the log base $2$ and $\lceil x \rceil$ denotes the ceiling function (to prove this bound, draw the binary tree of what is tested in this algorithm. Note that each infected element has at most $\lceil \lg(n) \rceil$ sets above it, and each of those contributes at most $2$ tests to the total count). Then just take the expected value of both sides, and we're done since the expected value of $k$ is $np$.]

For larger values of $p$ (e.g., $p = 1 / \log(n)$), I'm not sure what should be the truth. For all $p \geq 1/2$, I would like the answer to be $n$ (see point (1) above).

---

Added afterwards: I looked at that survey, and I'm kicking myself for not getting the full answer to this. See their Theorem 1.3 which answers your question fully. I suppose I'll post this in a comment to this answer. If you don't want to know, don't look.

Answer 2

This isn't intended to be a complete answer, just a formalization of the most "obvious" idea.

A natural approach is to try to maximize the information gained with each test. If we are currently at the node $x$ of the test protocol $\mathscr{T}$, then for every subset $B \subseteq \{1, ..., n\}$ we can (in principle) compute the conditional probability $\mathbb{P}[B\mid x]$ that testing the subset $B$ will give a positive result, and then try to select the subset $B$ such that $\mathbb{P}[B\mid x]$ is as close to $\frac{1}{2}$ as possible, since this choice of $B$ will then maximize the conditional entropy $H(B \mid x)$. I will call this protocol the greedy strategy, and will use the symbol $\mathscr{G}$ to refer to this protocol.

It is unclear if the greedy strategy can be implemented in practice for large values of $n$. Even computing one of the conditional probabilities $\mathbb{P}[B \mid x]$ seems like it could be difficult, if we arrive at the node $x$ after making a sufficiently complex sequence of choices. However, for $p > 0.245...$, it is possible to work out what the greedy strategy will do.

The simplest case is the case $p > \frac{3-\sqrt{5}}{2} \approx 0.382$. In this case, the greedy strategy recommends that we always choose $B$ of size $1$, and the expected length of the greedy strategy in this case is $\ell(\mathscr{G}) = n$.

More generally, we can at least predict what the greedy strategy will do in its first step. The greedy strategy will pick a set $B$ of size $m$, where $m$ maximizes $H(1-(1-p)^m)$ among all choices $m \le n$. So the cutoff where we go from picking a set of size $m$ to picking a set of size $m+1$ occurs when $1-(1-p)^m = (1-p)^{m+1}$.

In particular, for $0.382... > p > 0.245...$, the first thing the greedy strategy will do is to examine a set $B_1$ of size $2$. If none of the samples in $B_1$ is infected, then we end up recursively applying the greedy strategy on a set of size $n-2$.

What if at least one of the samples in our first set $B_1$ of size $2$ is infected? Now there are several different choices that we could make in the next step: choose a set $B_2$ (of size $2$) which is disjoint from $B_1$, or choose a set $B_2$ (with the size of $B_2$ to be determined) such that $|B_2 \cap B_1| = 1$. The conditional probability that an element of $B_1$ is infected is $\frac{p}{1 - (1-p)^2} = \frac{1}{2-p} > \frac{1}{2}$, so if we choose $B_2$ to intersect $B_1$, then we may as well take $B_2$ to be a subset of $B_1$ of size $1$. Oddly enough, the greedy strategy always prefers to try taking $B_2$ to be another disjoint subset of size $2$.

So in the range $0.382... > p > 0.245...$, the greedy strategy will always begin by breaking up the set $\{1,...,n\}$ into groups of size $2$ (with one element left over if $n$ is odd), and testing each group. Then it will try testing the first element from one of the groups of two that contains an infected sample. If that first element is uninfected, then we know the second element of the group of two is infected and can ignore it. If that first element is infected, then we have no information about the second element of the group of two, so the greedy strategy will try to pair this element up with the leftover element if $n$ is odd, or will hold onto it for later if $n$ is even. This process then continues in an obvious way.

Thus in the range $0.382... > p > 0.245...$, the greedy strategy is equivalent to the following strategy: as long as there are at least $2$ unknown samples, we test the first two unknown samples together, throw them both away if the group tests negative, and otherwise immediately test the first of the two samples if the group tests positive, throwing both away if the first tests negative, and throwing just the first away if it tests positive. This gives us the recurrence $$\ell(\mathscr{G}_n) = 2-(1-p)^2 + p\ell(\mathscr{G}_{n-1}) + (1-p)\ell(\mathscr{G}_{n-2}),$$ which has the solution $$\ell(\mathscr{G}_n) = \frac{2-(1-p)^2}{2-p}n + \frac{(1-p)^2-p}{(2-p)^2}(1 - (p-1)^n).$$

Can anyone continue the analysis of the greedy strategy? Does it end up doing something simple in the end?

Answer 3

The following paper by Price and Scarlett appeared today on arXiv. It considers $k$ defective items, but given a fixed $p,$ one can choose $k=c p n,$ for example to have control over the probability of failure of this algorithm, via, say the Chernoff bound.

Picking $c=2,$ for example would give probability of failure $P_{err}$ upper bounded by $$P_{err}\leq (e/4)^t\approx \frac{1}{1.47^t}$$ by the multiplicative Chernoff bound.

A Fast Binary Splitting Approach to Non-Adaptive Group Testing

From the abstract:

In this paper, we consider the problem of noiseless non-adaptive group testing under the for-each recovery guarantee, also known as probabilistic group testing. In the case of $n$ items and $k$ defectives, we provide an algorithm attaining high-probability recovery with $O(k \log n)$ scaling in both the number of tests and runtime, improving on the best known $O(k^2 \log k · \log n)$ runtime previously available for any algorithm that only uses $O(k \log n)$ tests.

We recursively work with groups of items of geometrically vanishing sizes, while maintaining a list of “possibly defective” groups and circumventing the need for adaptivity. While the most basic form of our algorithm requires $\Omega(n)$ storage, we also provide a low-storage variant based on hashing, with similar recovery guarantees.