Markov group testing

Consider N objects moving on a graph G = (V,E). Each item executes a random walk on the graph. Suppose at most k of the N objects are defective, and S sensors are placed at unique locations on G. At each time, each sensor provides a binary decision for the collection of objects in its graph neighborhood. A sensor returns 0 if no defective objects are present in its neighborhood and 1 if at least one defective object is present. Our goal is to determine the scaling of the time required to identify the defectives as a function of the number of sensors, the range of the sensors, the number of objects, the number of defectives, and the properties of the graph. Our problem is a generalization of the conventional nonadaptive group testing. In non-adaptive group testing, at each instant of time, a random collection of objects are tested. The tests form an identical, independent process. In contrast, we have multiple tests at each instant of time, and the tests are not independent. It is well established that in probabilistic, non-adaptive group testing, the number of tests required is O(k log N). In this paper, similar results are derived for two classes of graphs, which at each instant of time test a collection objects generated by a Markov process. First, we examine the case of a graph with 2 nodes and a single sensor, for which we show that the number of tests required for a constant error scales with the number of objects and defective objects on the order of O(k log N). Next, we examine the case of connected regular graphs with multiple sensors, showing that classification with a constant error scales on the order of O(kτ(1/L/S) log N) tests. The effect of parameters such as the size of the graph, the number of sensors placed on the graph, and the size of the testing neighborhood of each sensor are examined. A phase transition effect dependent on the size of the testing neighborhood of each sensor is demonstrated and explained by the bound produced. Numeric si- - mulations confirm the functional accuracy of the bounds, notably the effect of these parameters on the number of tests required for classification.