Adaptive Surveillance Testing for Efficient Infection Rate Estimation

In this paper, we study a surveillance testing problem where the learner aims to monitor the infection rate in a community with large population. At each time $t$, the learner is able to collect samples from a randomly selected group of individuals in the community and perform group testing. The test result is equal to one if at least one individual in the selected group is infected and zero otherwise. Assume each individual is infected according to an independent and identically distributed Bernoulli random variable with parameter $p$. Our objective is to design an efficient testing procedure to decide the number of samples included in each step for group testing and obtain an accurate estimate of the infection rate $p$ with high probability. We present a two-phase adaptive testing algorithm and show that it reduces the number of tests required to achieve the desired accuracy level compared with the single-sample testing approach. When $p$ is sufficiently small, which is the regime of interest in practice, it leads to an order-of-magnitude improvement. Simulation corroborates theoretical results.

I. Introduction

Group testing is the procedure of identifying a small number of defective items within a given set. Instead of testing each item individually, a group test mixes samples of a subset of items and tests them together. The test result will be positive if at least one of the items in the subset is defective. By deciding which subset of items to be included in each test, the objective of group testing is usually to identify all defective items with minimum number of tests. Since it was first introduced in [1], group testing has been widely applied in a variety of practical problems including quality control in product testing [2], sequential screening of experimental variables [3], file searching in storage systems [4], data compression [5], etc. Various settings with different assumptions on the underlying structure of the distribution of the defectives, on the constraints on the allowed queries and on the observation models have been studied [6]–[14]. More extensive surveys on this line of research can be found in [15]–[17] for non-adaptive testing and in [18] for adaptive testing.