Optimum sequential search with discrete locations and random acceptance errors

Much work has been done in search theory; however, very little effort has occurred where an object's presence at a location can be accepted when no object is present there. The case analyzed is of this type. The number of locations is finite, a single object is stationary at one location, and only one location is observed each step of the search. The object's location has a known prior probability distribution. Also known are the conditional probability of acceptance given the object's absence (small) and the conditional probability of rejection given the object's presence (not too large); these Probabilities remain fixed for all searching and locations. The class of sequential search policies which terminate the search at the first acceptance is assumed. A single two‐part optimization criterion is considered. The search sequence is found which (i) minimizes the probability of obtaining n rejections in the first n steps for all n, and (ii) maximizes the probability that the first acceptance occurs within the first n steps and occurs at the object's location for all n. The optimum sequential search policy specifies that the next location observed is one with the largest posterior probability of the object's presence (evaluated after each step from Bayes Rule) and that the object is at the first location where acceptance occurs. Placement at the first acceptance seems appropriate when the conditional probability of acceptance given the object's absence is sufficiently small. Search always terminates (with probability one). Optimum truncated sequential policies are also considered. Methods are given for evaluating some pertinent properties and for investigating the possibility that no object occurs at any location.