OPTIMUM SEQUENTIAL SEARCH WITH DISCRETE LOCATIONS AND RANDOM ACCEPTANCE ERRORS.
Abstract
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 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. The policy is optimum in that, for any number of steps, it minimizes the probability of no acceptances and, simultaneously, maximizes the probability that an acceptance occurs and the object is accurately located. 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. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 28, 1969
- Accession Number
- AD0694441
Entities
People
- John E. Walsh
- Mark W. Smith
Organizations
- Southern Methodist University